Методы оптимизации. Азарнова Т.В - 44 стр.

                                    46
решения очередной вспомогательной задачи      можно       эффективно
использовать для решения следующей. К данным методам относятся: метод
штрафов, метод барьеров, метод множителей Лагранжа.

                    Методы возможных направлений
     Методы, входящие в эту группу методов, базируются на построении
возможных и подходящих направлений, по которым осуществляется
движении из одной допустимой x k точки к другой допустимой точке x k +1 с
"лучшим" значением целевой функции. Движение осуществляется по
правилу x k +1 =x k +α k y k .
Определение 1. Пусть x допустимая точка в задаче выпуклого
программирования
                                     f ( x) → min
                           g j ( x) =0, j =1, m, m 0 , что точки
 x +αy являются допустимыми в задаче для всех α ∈[0, δ ] . Вектор y
называется подходящим направлением в точке x , если выполняется
неравенство ∇ f ( x ) y T <0 .
З а м е ч а н и е . Если некоторое направление y является возможным и
подходящим в точке x , то существует такое δ >0 , что точки x +αy
являются допустимыми в задаче и f ( x +αy ) < f ( x) для всех α ∈[0, δ ]
(Доказать !).
Теорема 1. Для того, чтобы допустимая точка x была решением задачи
выпуклого программирования необходимо и достаточно, чтобы в этой точке
не существовало одновременно возможных и подходящих направлений.
        Рассмотрим вначале частный случай задачи (1) - задачу с линейными
ограничениями
                                        f ( x) → min
                                            Ax ≤b
                                           Cx =d
где A матрица размера (m ×n) , C - матрица размера ( p ×n) , b -вектор
размера m , d - вектор размера p .
        Заметим, что, в частности, может быть задача только с ограничениями
равенствами или только ограничениями неравенствами.
Утверждение 1. Пусть x допустимая точка в задаче с линейными
ограничениями и предположим, что A1 - это подматрица матрицы A ,
отвечающая активным ограничениям в точке x . Тогда ненулевой вектор y
является возможным направлением в точке x в том и только в том случае,
если A1 y ≤0, Cy =0 .