Метод проекции градиента

решается задача минимизации нелинейной функции с ограничениями.

Хотя метод применим и в задачах с нелинейными ограничениями, хорошая сходимость имеет место только в случае, когда ограничения – линейны.

Постановка задачи: найти x (n-мерный вектор) , доставляющий минимум выпуклой скалярной функции f(x) при условиях: A1x = B1, A2x ≤ B2

Примечание: Если должна быть учтена неотрицательность х, то, в отличие от ЛП, ограничения х≥0 должны быть включены в общую систему ограничений в форме -х ≤ 0.

Напомним основные позиции метода наискорейшего спуска (поиск минимума выпуклой функции f(x) без ограничений)

и перемещаемся в точку минимума по этому направлению

3. В точке минимума по направлению траектория перемещения касается одной из линий равного уровня

4. Определяется новое направление антиградиента (если критерий квадратичный – ортогональное предыдущему)

5. Последующие точки находятся аналогично – до тех пор, пока градиент не станет близок к 0

его на задачи с ограничениями

Старт – из допустимой точки

Если бы ограничений не было, точка переместилась бы по траектории наискорейшего спуска

Но «по дороге» траектория наискорейшего спуска наталкивается на ограничение, мешающее продолжить траекторию. Такое ограничение называется АКТИВНЫМ.

Поэтому точка перемещается в положение, ближайшее к той, которая получилась бы, если бы ограничения отсутствовали – т.е. на поверхность области ограничений.

числа возможных такое, перемещение в котором ведет к самому быстрому уменьшению критерия.

Это направление – проекция антиградиента на поверхность активных ограничений.

Перемещаем точку в направлении проекции до достижения минимума по этому направлению.

Далее снова находим антиградиент, его проекцию, перемещаемся до минимума в направлении проекции.

Окончание: проекция вырождается в точку, минимум найден