Рассмотрим задачу выпуклого программирования вида

,

где  и  - выпуклые дифференцируемые функции. В данном случае допустимое множество выпукло, поэтому в любой допустимой точке существует возможное направление . Для того, чтобы в данной задаче направление  было возможным и подходящим в точке , достаточно, чтобы оно удовлетворяло системе неравенств

                                               (1)

, ,

где  - множество активных в точке  ограничений.

Возможное и подходящее направление, удовлетворяющее данной системе неравенств, определяется из решения задачи линейного программирования

,

.

Заметим, что  удовлетворяет всем ограничениям задачи, следовательно, ожидаемый результат . Если , то система (1) имеет решение . В этом случае строится новая точка . При этом  выбирается таким образом, чтобы  была допустимой точкой, например,

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

Если , то система (1) несовместна, т.е. все возможные в точке  направления не являются подходящими. Это означает, что в точках  допустимого множества, достаточно близких к , выполняется неравенство , т.е. -точка локального минимума  на допустимом множестве. Но для выпуклой функции  на выпуклом множестве этот минимум является и глобальным. Таким образом, точка  есть решение задачи.

 

                                                 Алгоритм

Шаг 1. Задать начальную точку , характеристику точности алгоритма . Положить .

Шаг 2. Найти . Если , то вычисления прекратить и положить , иначе перейти к шагу 3.

Шаг 3. Подставить  в неравенства и определить множество индексов активных ограничений .

Шаг 4. Если , то положить , иначе определить  из решения задачи

,

.

    Шаг 5. Если  или , то положить . Иначе для найденного вектора  определить

,

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

Шаг 6. Найти очередное приближение .

Пример 2. Найти минимум в задаче

.

Решение.

1. Возьмем в качестве начальной точки . Легко проверить, что данная точка принадлежит допустимому множеству, причем . Положим , .

2. Найдем . Так как , то продолжим решение задачи. Для нахождения  вычислим   и составим задачу линейного программирования

, .

3. Решая полученную задачу симплексным методом, получим , , .

Метод линеаризации (Франка Вулфа)

 

Рассмотрим задачу минимизации выпуклой нелинейной функции на множестве, задаваемом линейными ограничениями:

Метод линеаризации основан на замене в окрестности точки x^k нелинейной функции  линейной функцией . Из формулы Тейлора следует, что . Положим .

Рассмотрим задачу линейного программирования

Обозначим решение к - той ЗЛП. Тогда направление    в исходной задаче будет подходящим. Формула пересчета имеет вид , где шаг  ищется по правилу наискорейшего спуска с учетом условия  (при таком выборе  точка  будет выпуклой линейной комбинацией точек  и , что обеспечивает ее допустимость).

 В качестве критериев останова алгоритма применяются стандартные критерии:

Алгоритм

Шаг 0. Зафиксировать начальное приближение.

      Положить к=0.

Шаг 1. Решить задачу линейного программирования

,

        найти .

Шаг 2. Зафиксировать вектор   в качестве направления

       поиска.

Шаг 3. Вычислить .

Шаг 4. Положить

Шаг 5. Проверить условия останова и, если они выполнены, вычисления

       прекратить и взять точку  в качестве искомого решения. Иначе

        положить k=k+1 и перейти на шаг1.

 

Пример 1. Решить методом линеаризации задачу нелинейного программирования

Решение. Данная задача была графически решена в §2: x*=(5/2,1/2).

Для решения задачи методом линеаризации выберем x⁰ ,

                                              например, x⁰ =(0,0). Вычислим

  

Итерация 1. . Рассмотрим задачу линейного программирования Решив ее графически, получаем

                                     

                                            

. x*

Ω

	x ^0.

  

        

                                                                           

,  где .

 Запишем задачу одномерной оптимизации

Решением этой задачи будет

Итерация 2

. Рассмотрим задачу

Решением этой ЗЛП является отрезок, соединяющий точки (2,1) и (0,2).

Выберем одну из них, например, (2,1). Тогда , . Запишем задачу одномерной оптимизации                  

Решением этой задачи будет

Итерация 3.

. Рассмотрим задачу

Решением этой ЗЛП является отрезок, соединяющий точки (2,1) и (3,0).

Выберем одну из них, например, (3,0). Тогда . 

.

 Запишем задачу одномерной оптимизации

                                         

Решением этой задачи будет . Останов. Получено оптимальное решение х*= .

 

Метод секущих плоскостей

 

 Данный метод применяется для решения задач выпуклого программирования с линейной целевой функцией:

                                          (1)

Замечание 1. Любая задача выпуклого программирования может быть записана в виде (1).

Действительно, если есть задача с нелинейной целевой функцией

то она может быть переписана следующим образом

Метод секущих плоскостей основан на приближении всех нелинейных функций  линейными с использованием разложения по формуле Тейлора.

Рассмотрим задачу

                                     (2)

Если множество  ограничено, то задача (2) всегда разрешима (в противном случае может оказаться, что , даже если задача (1) разрешима)

Так как функции  выпуклы вниз, справедливо неравенство

. Следовательно . Пусть - решение задачи (2).

1) Если точка  допустима в задаче (1), то она является оптимальным решением этой задачи (поскольку это экстремум той же целевой функции на более широком множестве).

2) Если , то в задаче (2) добавляются новые линейные ограничения: .Эти ограничения обладают следующими свойствами:

a) точка  не удовлетворяет этим ограничениям;

b) во всех точках множества  они выполняются.

Таким образом, получаем новое множество   , такое что . Далее итерационный процесс повторяется. Доказано, что генерируемая таким образом последовательность { } решений ЗЛП сходится к оптимальной точке исходной задачи. Алгоритм метода имеет следующий вид.