Лекция: МЕТОДЫ УСЛОВНОЙ МИНИМИЗАЦИИ. Случай линейных ограничений

Пусть дана задача:

(1)

Пусть требуется решить задачу:

(2)

где – множество простой структуры, которое задаётся с помощью ограничений на одну переменную вида .

В методах 1-го порядка на -ой итерации по известному решается задача

(3)

Как правило, окрестность в (3) формируется с помощью линейных ограничений. Поэтому задача (3) представляет из себя задачу линейного программирования, её решение принимается за .

Если в задаче (3) вначале искать направление итерации и положить, то в результате придём к задаче

(4)

Решение этой задачи принимается за. Задача (4), как правило, линейная задача. После определения направления итерации шаг выбирают одним из описанных 3-х способов.

Пример 1. Положим в (4), тогда получим задачу:

(5)

Решение этой задачи называется направлением условного градиента. Это направление даёт наибольшую проекцию на антиградиент и не выводит за пределы .

Пример 2. Положим, тогда получим задачу:

(6)

а). В этом случае совпадает по направлению с антиградиентом и имеет длину, (то есть в этом случае используется классический градиентный метод).

б), значит, антиградиент проектируется на и имеет длину .

Если в (3) вместо использовать, то для задачи (2) получаем метод Ньютона.