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

                                                 54
                         T
                      cx → max
                                                                                                  (1)
                   Ω : f i ( x) ≤bi , i =1, m
За ме ча н и е 1 . Любая задача выпуклого программирования может быть
записана в виде (1).
Действительно, если есть задача с нелинейной целевой функцией
                                    ϕ ( x) → max
                            f i ( x) ≤bi , i =1, m,
то она может быть переписана следующим образом
                            µ → max
                            µ −ϕ ( x) ≤0
                                      f i ( x) ≤bi , i =1, m
Метод секущих плоскостей основан на приближении всех нелинейных
функций f i (x) линейными с использованием разложения по формуле
Тейлора.
                          f i ( x) ≈ f i ( x 0 ) +∇ f i ( x 0 )( x −x 0 ) T
Рассмотрим задачу
                                 cx T → max
                                                                            (2)
         Ω1 : f i ( x 0 ) +∇ f i ( x 0 )( x −x 0 ) T ≤bi , i =1, m
     Если множество Ω1 ограничено, то задача (2) всегда разрешима (в
противном случае может оказаться, что                 sup   cx T =+∞, даже если задача (1)
                                                       Ω1
разрешима)
     Так как функции f i (x ) выпуклы вниз, справедливо неравенство
 f i ( x) ≤ f i ( x 0 ) +∇ f i ( x 0 )( x −x 0 ) T ≤bi . Следовательно Ω ⊆ Ω1 . Пусть x 1 -
решение задачи (2).
                              1
1) Если точка x допустима в задаче (1), то она является оптимальным
       решением этой задачи (поскольку это экстремум той же целевой функции
       на более широком множестве).
2) Если x1 ∉Ω , то в задаче (2) добавляются новые линейные ограничения:
        f i ( x 1 ) +∇ f i ( x 1 )( x −x 1 ) T ≤bi , i : { f i ( x 1 ) >bi } .Эти ограничения обладают
       следующими свойствами:
       a) точка x 1 не удовлетворяет этим ограничениям;
       b) во всех точках множества Ω они выполняются.
Таким образом, получаем новое множество Ω 2 , такое что Ω ⊆ Ω 2 ⊆ Ω1 .
Далее итерационный процесс повторяется. Доказано, что генерируемая таким
образом последовательность { x k } решений ЗЛП сходится к оптимальной
точке исходной задачи. Алгоритм метода имеет следующий вид.