Курс: Методы оптимизации

Пример: Решить методом проекции градиента:
(9)
. (10)
Решение. Задачу (9)-(10) решим методом проекции градиента, используя соотношение (6). Выберем начальное приближение . Пусть шаг в выражении (6) равен . Критерий останова выберем следующий: , где .
Итерация 1. В соответствии с выражением (6) определяем .
, .
Точка выходит за пределы области X. Так как множество X- координатный параллелепипед, то можно указать явный вид проекции точки на множество. Известно, что если – координатный параллелепипед, то : (см.[Сухарев, с.227], а также лекцию о проекциях.
В нашем случае , .
Так как , то проверяем критерий останова: . Критерий останова не выполняется, значит, переходим к следующей итерации.
Итерация 2. В соответствии с выражением (6) определяем
.
, .
Точка выходит за пределы области X.
Значит, , . .
Критерий останова выполняется, значит, процесс вычислений закончен.

Вспомним некоторые определения и теоремы из прошлых лекций по математическому программированию.

Система из m линейных неравенств (ЛН) Ax  b (1)
называется разрешимой, если  x≥0: Ax  b, xRⁿ, bR^m и неразрешимой - в противном случае.
ОзЛП max c, x Ax  b (2)
разрешима, когда разрешима система (1) и максимум в (2) достигается.
Определение 1. Линейное неравенство c, x  d (3)
является следствием разрешимой системы линейных неравенств (1), если для любого x, удовлетворяющего (1), выполнено (3).
Пусть - вектор-строка матрицы А, т.е. коэффициенты i-го неравенства из (1); .