МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ
Лекция №13
МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ
Рассмотрим задачу выпуклого программирования
(13.1)
где допустимая область задается так
(13.2)
Поскольку функции , ,.., предполагаются выпуклыми, то в силу рассмотренных ранее свойств выпуклых функций задача (13.1)-(13.2) есть задача минимизации выпуклой функции на выпуклом множестве.
Введя в рассмотрение индексные множества
, ,
имеем
. (13.3)
Для сокращения записей обозначим
,
Тогда ЗВП запишется в виде
.
Идея метода возможных направлений (МВН) заключается в том, что в каждой очередной точке находится направление спуска такое, что перемещение точки по этому направлению на некоторое расстояние не приводит к нарушению ограничений задачи. Таким образом, МВН можно рассматривать как естественное распространение метода градиентного спуска на задачи минимизации с ограничениями. В отличие от других численных методов решения таких задач, метод возможных направлений обладает тем преимуществом, что для отыскания направления спуска достаточно решить задачу линейного программирования с небольшим числом ограничений.
Для описания метода возможных направлений введем ряд определений.
Определение 13.1. Направление, определяемое вектором , называется возможным направлением в точке , если достаточно малое перемещение из в направлении не выводит точку за пределы допустимой области, т.е., если существует такое число , что для всех .
Очевидно, если является внутренней точкой множества , то любое направление в этой точке является возможным.
Определение 13.2. Возможное направление, определяемое вектором , называется подходящим направлением в точке , если перемещение из точки по этому направлению осуществляется с уменьшением значения функции, т.е., если .
Очевиден геометрический смысл этого утверждения: угол между вектором, задающим подходящее направление в точке , и антиградиентом минимизируемой функции в данной точке острый.
Следствием введенных определений является утверждение: если в точке подходящих направлений нет, то функция достигает в этой точке своего минимума на множестве , т.е.
.
В самом деле. Пусть в точке нет ни одного подходящего направления, т.е. для любого вектора в точке выполняется неравенство . Тогда при перемещении из точки по любому из этих направлений функция не убывает
.
Следовательно, - точка локального минимума .
Вычислительные алгоритмы метода возможных направлений
Метод возможных направлений осуществляется следующим образом.
1. Точка начального приближения находится в допустимой области .
2. Последовательность точек , принадлежащих , строится так, чтобы выполнялись неравенства . При этом, строя точку так, чтобы выполнялось неравенство
, обнаруживаем, что либо не ограничена, либо такой точки не существует, т.е. - оптимальная точка. В обоих случаях процесс решения задачи прекращается. Задача решена.
Процедура построения точки состоит из двух этапов:
а) в точкеопределяется подходящее направление ,
б) определяется длина шага такая, что принадлежит и . Так как направление подходящее, то при этом оказывается, что .
3. Выбор подходящих направлений в точках производится так, что обеспечивается сходимость значений к , либо обнаруживается, что последовательность не ограничена.
Методы возможных направлений можно рассматривать как градиентные методы с конечным шагом. Многие методы линейных и нелинейных задач математического программирования можно трактовать как методы возможных направлений. Они различаются лишь дополнительными требованиями к выбору начальной точки , направления и длины шага . В частности к таким методам относится и симплекс- метод решения ЗЛП.
Построение начального приближения
- Строим точку , где С – заданный вектор.
- Располагая точкой , вычисляем значения функций
, .
Если значение функции , то точка удовлетворяет -му линейному ограничению задачи, т.е. выполняется неравенство .
Если число , то в точке не выполняется условие и, следовательно, точка не удовлетворяет -му линейному ограничению задачи.
- Введем в рассмотрение неотрицательные числа , положив для тех индексов , для которых и положив для тех индексов, для которых .
- Вводим дополнительную переменную , увеличивая тем самым размерность вектора неизвестных на единицу, и в (n+1)-мерном пространстве формируем следующую задачу:
Таким образом, получим в (n+1)-мерном пространстве задачу минимизации линейной функции на множестве, задаваемом линейными ограничениями, т.е. задачу линейного программирования, которая решается за конечное число шагов симплекс-методом. При этом в качестве начального опорного плана можно выбрать точку
.
В качестве можно взять.
Решая вспомогательную задачу (13.4) симплекс-методом, за конечное число шагов получим оптимальный план, в котором . Тогда первые n компонент этого опорного плана определят точку , которая будет удовлетворять всем линейным ограничениям исходной задачи, т.е.
.
- Вычисляем . Задаем неотрицательные числа и полагаем для тех индексов , для которых и для тех индексов, для которых .
- Вводим дополнительную переменную и формулируем еще одну вспомогательную задачу, следующим образом:
(13.5)
Это есть задача выпуклого программирования, для которой известна начальная точка с координатами
Если выбрать в качестве , тогда начальная точка будет . Очевидно, если в ходе решения ЗВП (13.5) на каком-то шаге получим , то есть вектор , то соответствующий вектор определит искомую точку , которая будет являться начальной точкой исходной задачи.
Теорема 13.1. Если непусто и регулярно по Слейтеру, то, применяя для решения задачи (13.5) метод возможных направлений, получим за конечное число шагов.
Д о к а з а т е л ь с т в о. Допустим, что задача (13.5) решается методом возможных направлений без требования . В силу условия Слейтера существует точка такая, что для всех , тогда ограничения , допускают существование точки с компонентой . Так как минимизируется, то последовательность значений минимизируемой функции будет сходиться к значению . При этом, даже если оптимальное значение является пределом сходящейся последовательности, становится неположительным за конечное число шагов. Следовательно, при условии оптимальное значение достигается за конечное число шагов.
Замечание. Вместо того, чтобы последовательно удовлетворять сначала линейным, а затем нелинейным ограничениям, можно, избегая пунктов 5 и 6 и имея точку , сразу решить задачу
(13.6)
где для тех индексов , для которых .
Задача (13.6) является задачей выпуклого программирования, для которой за нулевое приближение можно взять точку
Однако, решение задачи (13.6) является более сложным, чем решение задач, которые рассматривались на шагах 5 и 6.
Определение подходящего направления
Для описания алгоритма выбора наилучшего направления поиска очередной точки минимизирующей последовательности введём ряд важных понятий.
Определение 13.3. Ограничение ( ) называется
активным в фиксированной точке , если
( ).
Введём в рассмотрение множества индексов активных ограничений
в фиксированной точке : - индексное множество активных нелинейных ограничений; - индексное множество активных линейных ограничений;
; .
Введем в рассмотрение множество n-мерных векторов в точке и построим множество
Множество представляет собой конус возможных направлений в точке . Если - внутренняя точка множества R, то множество пусто, т.е. в этой точке нет активных ограничений, и на выбор вектора S не накладывается никаких ограничений.
Введем искусственную переменную и определим множество (n+1)-мерных векторов следующим образом:
.
Задачу выбора подходящего направления сформулируем как задачу линейного программирования:
. (13.7)
Очевидно, что при множества и совпадают. Если , то из ограничения следует, что и направление будет подходящим. В этом случае , т.е. не направлено по касательной к нелинейным границам. При этом, чем больше , тем больше отличается от нуля , т.е. тем больший угол образуется между и внешней нормалью . Если, то точка оказывается точкой минимума функции .
Присутствие в задаче (13.7) ограничения объясняется следующим образом. Когда речь идёт о выборе направления, нас интересует именно направление, которое задаётся некоторым вектором произвольной длины. Но при решении ЗЛП (13.7) величина может оказаться неограниченной. Чтобы этого избежать следует наложить на длину S некоторые ограничения. Поэтому в постановке задачи (13.7) должно присутствовать так называемое условие нормализации. Таким условием может быть одно из следующих ограничений:
№1..
№2.
№3.если или если
№4.
Признак оптимальности в задаче выбора наилучшего подходящего направления устанавливается следующей теоремой.
Теорема 13.2. Точка является точкой минимума на , регулярном по Слейтеру тогда и только тогда, когда для всех , удовлетворяющих неравенству .
Д о к а з а т е л ь с т в о.Если в решении задачи выбора направления (13.7) окажется, что , то соответствующее направление будет подходящим, и точка не может быть точкой минимума функции .
Пусть теперь для всех , удовлетворяющих условиям
Будем считать для сокращения записей, что в (13.10) содержатся также и прямые ограничения на переменные задачи .
Введя в рассмотрение - мерные вектора , неравенство можно записать в виде
В силу теоремы Фаркаша, устанавливающей равносильность условий
,
найдется такой вектор , , что имеют место равенства
Если , т.е. , то из (13.11)
, (13.13)
Умножая скалярно равенство (13.13) на некоторый произвольный вектор , принадлежащий множеству получим
.
Но в множестве выполняются условия и для любого . Следовательно, для любого , а значит в точке нет подходящего направления и она является точкой минимума функции на .
Если , то из условия и равенства (13.12) следует существование по крайней мере одного , . Тогда умножая (13.11) на
(13.14)
Но из регулярности по Слейеру следует существование точки такой, что для всех . Тогда, полагая , в силу теоремы 12.5 имеем
т.к. , а . Таким образом, хотя бы одно из слагаемых в (13.14) строго меньше нуля а все остальные неположительны. Поэтому левая часть равенства (13.14) не может быть равна нулю, т.е. случай невозможен. Теорема доказана.
Контрольные вопросы
1. В чем заключается основная идея метода возможных направлений?
2. Какое направление называется возможным в допустимой точке?
3. Поясните понятие подходящего направления в допустимой точке.
4. Какие ограничения называются активными в фиксированной точке?
5. Какой метод решения задачи выпуклого программирования называется методом возможных направлений?
6. Приведите алгоритм построения начального приближения в методе возможных направлений.
7. Опишите процедуру построения очередной точки минимизирующей последовательности в методе возможных направлений.
8. Дайте определение конуса возможных направлений в точке.
9. Опишите постановку вспомогательной задачи для выбора наилучшего подходящего направления в допустимой точке.
10. Сформулируйте признак оптимальности в задаче выбора наилучшего подходящего направления в допустимой точке.
PAGE 142
МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ