Comments 8
Если Вы когда‑то учились в вузе на технической специальности или учитесь сейчас (иначе, зачем бы Вам эта статья), у Вас наверняка есть предмет, который назывался примерно так — «Методы оптимизации» / «Введение в оптимизацию» или что‑то похожее.
Учился на технической специальности, ничего даже близко похожего не было
Спасибо, интересно было вспомнить (хотя у мы только симплекс-метод проходили, когда-то вручную его программировал, без всяких библиотек).
Курс лекций МФТИ «Введение в теорию выпуклой оптимизации»
это вот этот курс? оставлю ссылку, может, кто-то захочет посмотреть (а вдруг?!!)
Конкретно того курса, на который я ссылаюсь, нет в открытом доступе, поэтому без ссылок. Но есть не менее замечательный курс на ютубе, тоже от мфти - вот этот
Если позволите, вот мои 5 копеек.
Слева направо, сверху вниз
Случай отсутствия ограничений (теорема Ферма): если градиент не 0, то чуть-чуть идём в противоположном ему направлении -- линейна часть функции уменьшится, а значит при достаточно малом размере шага и сама функция уменьшается. Значит в точки минимума градиент обязан быть нулём.
Случай ограничений в виде равенств (метод множителей Лагранжа): ограничения задают некоторую поверхность/многообразие в пространстве. Попытаемся применить логику из предыдущего пункта, не должно существовать направления вдоль поверхности, движение по которому изменяло бы линейную часть функции. Геометрически это означает, что градиент функции обязан быть ортогонален поверхности.
Случай ограничений в виде неравенств, точка внутри (условия ККТ): если у нас есть ограничение, выполняющееся строго, то его можно просто выкинуть, на локальные свойства оно никак не повлияет, работает логика из первого пункта
Случай ограничений в виде неравенств, точка на границе (условия ККТ): наконец самый сложный случай, в целом схож с 2, но теперь у нас не только граница, но и внутренняя область. Качественная разница в том, что в одну сторону от границы мы можем перемещаться, а в другую нет. Из-за этого для гарантии минимума градиент должен быть не просто ортогонален границе, но и указывать вовне.
Условия неотрицательности -- соответствуют последнему пункту, условие дополняющей нежёсткости -- это неявный разбор случаев 3 и 4. Если убрать функцию g, отвечающую за неравенства, то останется пункт 2.
Добрый день!
Я только начинаю разбираться с ККТ и у меня возникли некоторые недопонимания на моменте решения системы уравнений.
Поэтому, действуя вслепую, в нашей задаче пришлось бы перебрать комбинации (h, g1) и т.д.
Из этой формулировки я понял, что из всех имеющихся ограничений типа неравенств только одно из них может быть активным. Но так ли это на самом деле? Ведь вдруг комбинация (h, g4, g5) тоже бы сработала. Может в конкретно это случае это не так, однако я не могу сказать наверняка, что это сработает для всех задач. Не могли бы вы пояснить этот момент, пожалуйста.
И вопрос насчёт этой цитаты
Ограничения-равенства активны всегда.
Почему это так?
Здравствуйте!
1. Равенство всегда активно, потому что Вы не можете от него отклониться: оно задает линию (или поверхность), которая совершенно точно будет содержать точку оптимума. Ведь если это не так, то система ограничений не выполняется. В этом и смысл понятия активного ограничения - оно говорит, что данное ограничение не просто выполняется, а где-то на линии ограничения лежит точка оптимума.
2. Да, могло и такое быть, что сработала бы комбинация (h,g4,g5). Да хоть все ограничения могли сработать и оказаться активными. И что бы это означало геометрически? Что они все пересекаются в одной точке. Но в 2-мерном пространстве для определения точки вполне хватит двух прямых.
Разбираем условия Каруша–Куна–Таккера. Решаем сложно простую задачу