4.6. Метод возможных направлений

Основная идея этой группы методов решения задач нелинейного программирования заключается в построении последовательных приближений к точке минимума целевой функции на допустимом множестве [7], [12]:

(51)

Эти методы напоминают безусловную минимизацию градиентными методами.

Вектор , определяющий направление перемещения (51) из точки в точку , должен удовлетворять следующим двум требованиям.

1. Для достаточно малых точка из (51) принадлежит множеству (то есть задает возможное направление).

2. Для достаточно малых выполняется неравенство (то есть определяет направление убывания).

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

Величина в (51) выбирается из условия наибольшего убывания целевой функции в направлении с учетом требования .

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

(52)

(53)

(54)

Опишем выбор вектора из (51), определяющего возможное направление убывания функции в точке . Рассмотрим возможные случаи.

1. Пусть в точке все неравенства (53) и (54) выполняются как строгие. Это означает, что - внутренняя точка допустимого множества . Тогда

(55)

то есть определение очередного приближения из (51) совпадает с итерацией градиентного метода.

2. Пусть хотя бы одно из неравенств (53), (54) в точке обращается в равенство, то есть является граничной точкой допустимого множества . Тогда выбор в соответствии с (55), вообще говоря, невозможен, так как может оказаться, что точка из (51) при любом не принадлежит множеству (направление из (55) не является возможным в точке направлением).

Опишем, как определить возможное направление убывания в этом случае.

Обозначим через и множества индексов, соответствующих ограничениям (53) и (54), которые в точке обращаются в равенства, то есть

(56)

Представим компоненты вектора для в виде

, (57)

где

Очевидно, , , и =0 для всех .

Вектор из (51) ищется как решение следующей задачи линейного программирования:

(58)

, (59)

(60)

(61)

, , , (62)

, =0, , (63)

где .

Поясним смысл соотношений (58)-(60).

1. Минимуму целевой функции из (58) соответствует минимально возможный с учетом ограничений (59)-(63) угол между искомым вектором и антиградиентом , определяющим направление скорейшего убывания в точке .

2. Ограничение (60) для каждого означает, что вектор составляет угол с вектором , нормальным к граничной гиперплоскости допустимого множества и направленным вне .

Так как точка принадлежит этой гиперплоскости, то условие (59) для любого гарантирует, что направление является возможным по отношению к -му ограничению (53) исходной задачи.

3. Условие (60) является ограничением на длину вектора и обеспечивает ограниченность снизу целевой функции из (32).

4. Неравенство (61) для каждого гарантирует, что направление искомого вектора является возможным по отношению к -му ограничению (54) исходной задачи.

5. Соотношения (62) и (63) следует из представления (57) компонент вектора .

Опишем теперь, как определить величину перемещения вдоль направления из (50). Для найденного вектора она находится из условия

т.е.

, (64)

где - максимальные перемещения, при которых для точки из (51) выполняются соответственно -е ограничение (53) и ограничение (54). т.е.

(65)

(66)

а находится из условия наискорейшего спуска вдоль направления вектора без учета ограничений (53), (54), т.е.

где

(67)

Приведем описание -го шага решения задачи (52) - (54) методом возможных направлений.

1. Подставить в неравенства (53) и (54) и определить множество индексов по формулам (56).

2. Если , найти вектор из (55), в противном случае определить из решения задачи линейного программирования (58) - (62) с помощью формулы (57).

3. Для найденного вектора определить из формул (63) - (66).

4. Найти очередное приближение по формуле (51).

При выполнении хотя бы одного из условий или , где - число, определяющее точность решения задачи, вычисления завершают, полагая .

Любое из равенств

означает, что точка минимума функции на множестве найдена точно :

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

методом возможных направлений, завершая вычисления при .

Решение. Функции являются выпуклыми и дифференцируемыми в поэтому можно использовать метод возможных направлений. Выберем начальное приближение . Очевидно .

Шаг 1.1. Так как , то является внутренней точкой множества и .

2. Вектор находим по формуле

3. Найдем максимально возможное перемещение из условия

откуда .

Определяя из (67), получим ,так как функция ==-2-1 неограниченно убывает при . Отсюда находим величину перемещения на первом шаге:

4. Найдем следующее приближение по формуле (51):

Шаг 2. 1. Поскольку , то - граничная точка множества и .

2. Вектор находим из решения задачи линейного программирования (47):

Решив ее симплекс-методом, получим

3. Величину перемещения находим, как и на предыдущем шаге: .

4. Очередное приближение находим из (51):

=(3;4)+.

Шаг 3. Так как , то точка является граничной. Находя и по общему правилу, получим:

Отсюда .

Переходя к следующему шагу, найдем , т.е. требуемая точность достигнута и

Пример 9. Решить следующую задачу нелинейного программирования с линейными ограничениями методом возможных направлений, завершая вычисления при или .

Решение. В качестве начального приближения выберем, например, точку (0,4; 1,4) (убедитесь, что ).

Шаг 1. 1. Ограничения (53) и (54) в точке выполняются как строгие неравенства, т.е. – внутренняя точка множества , т.е. .

2. В соответствии с (55) находим

. (68)

3. Из формул (65), (66) получаем

Определим в соответствии с (67), используя условие минимума =0:

==(0,4+72-4)²+(1,4+1,2-2)²,

=107,04-53,52=0,

откуда =1/2.

Из (64) окончательно находим

=min(1/7,1/12,1/2,)=1/12. (69)

4. Используя равенства (51), (67) и (68), получим

. (70)

Шаг 2. 1. В точке из (70) второе из ограничений задачи выполняется как равенство, поэтому - граничная точка множества , причем .

2. Задача (58) - (62) для определения принимает вид

Записав эту задачу в каноническом виде с помощью дополнительных переменных и выбрав эти переменные в качестве базисных, в результате двух шагов симплекс-метода получим , т.е.