Прямые методы условной оптимизации

Лекция №13
Методы условной оптимизации
План:

1. 
   Прямые и непрямые методы оптимизации
   
2. 
   Метод проекции градиента
   
3. 
   Методы возможных направлений
   

В общем случае численные методы решения задач нелинейного программирования можно разделить на прямые и непрямые. Прямые методы оперируют непосредственно с исходными задачами оптимизации и генерируют последовательности точек {x[k]}, таких, что f(х[k+1]) < f(x[k]). Здесь в [] – индекс. В силу этого такие методы часто называют методами спуска.

Математически переход на некотором k-м шаге (k. 0, 1, 2, ...) от точки х[k] к точке x[k+1] можно записать в следующем виде:
x[k+l] x[k] + a_kp[k],
где р[k] — вектор, определяющий направление спуска;
а_k — длина шага вдоль данного направления.
При этом в одних алгоритмах прямых методов точки х[k] выбираются так, чтобы для них выполнялись все ограничения задачи, в других эти ограничения могут нарушаться на некоторых или всех итерациях. Таким образом, в прямых методах при выборе направления спуска ограничения, определяющие допустимую область G, учитываются в явном виде.
Непрямые методы сводят исходную задачу нелинейного программирования к последовательности задач безусловной оптимизации некоторых вспомогательных функций. При этих методах ограничения исходной задачи учитываются в неявном виде. К ним относятся методы функции Лагранжа и штрафных функций, рассмотренные на прошлых лекциях. Рассмотрим теперь некоторые алгоритмы прямых методов.


Метод проекции градиента

Проведем сначала «правдоподобные рассуждения» и рассмотрим алгоритм данного метода применительно к задаче оптимизации с ограничениями-неравенствами. В качестве начальной выбирается некоторая точка допустимой области G. Если х[0] - внутренняя точка множества G

(Рис. 1), то рассматриваемый метод является обычным градиентным методом:
x[k+l] x[k] –a_kf’(x[k]), k 0, 1, 2, ...,
где градиент целевой функции f(х) в точке x[k].
После выхода на границу области G в некоторой граничной точке х[k] , k 0, 1, 2,..., движение в направлении антиградиента -f’(х[k]) может вывести за пределы допустимого множества (см. Рисунок 1). Поэтому антиградиент проецируется на линейное многообразие М, аппроксимирующее участок границы в окрестности точки х[k]. Двигаясь в направлении проекции вектора -f'(x[k]) на многообразие М, отыскивают новую точку х[k+1], в которой f(х[k+1]) f(x[k]), принимают х[k+1] за исходное приближение и продолжают процесс. Проведем более подробный анализ данной процедуры.

Рисунок 1. Геометрическая интерпретация метода проекции градиента

В точке х[k] часть ограничений-неравенств удовлетворяется как равенство:

h_j(x) 0, j 1, ..., l; l < m. Такие ограничения называют активными.
Обозначим через J набор индексов j (1 j l) этих ограничений. Их уравнения соответствуют гиперповерхностям, образующим границу области G в окрестности точки х[k] . В общем случае эта граница является нелинейной (см. рис.1). Ограничения h_j(x), j J, аппроксимируются гиперплоскостями, касательными к ним в точке х[k]:

Полученные гиперплоскости ограничивают некоторый многогранник М, аппроксимирующий допустимую область G в окрестности точки х[k] (см. Рис. 1).
Проекция р[k] антиградиента -f'(x[k]) на многогранник вычисляется по формуле p[k]  [-f’(x[k])].
Здесь  - оператор ортогонального проектирования, определяемый выражением  E – A^T(AA^T)^-1A, где Е - единичная матрица размерности пп;
А - матрица размеров l  n . Она образуется строками – транспонирован­ными вектор-столбцами градиентов активных ограничений из множества J: а_j=(h_j)^T, j 1, ..., l.
(см. Лекцию 4 о конусах и проекциях – файл Моп_Л4_2сПМ.doc. Здесь x[k]Г(G) является началом координат, из которого проводится радиус-вектор f. Значит b=0, и это – проекция на подпространство, а не на многообразие ).
Далее осуществляется спуск в выбранном направлении: x[k+1] x[k] + _kp[k]. Можно показать, что точка х[k+1] является решением задачи минимизации функции f(х) в области G тогда и только тогда, когда [-f’(x[k])] 0, т. е , и u (u₁, ..., u_l) (A^TA)^-1A^T(-f (х[k])) > 0.
Эти условия означают, что антиградиент (-f (х[k])) целевой функции является линейной комбинацией с неотрицательными коэффициентами градиентов активных ограничений h_j(x) 0. Напомним, что h есть нормаль касательной гиперплоскости.
В соответствии с изложенным, алгоритм метода проекции градиента состоит из следующих операций.
1. В точке х[k] определяется направление спуска р[k].
2. Находится величина шага _k.
3. Определяется новое приближение х[k+1].
Рассмотрим детально каждую из этих операций.
1. Определение направления спуска состоит в следующем. Пусть найдена некоторая точка х[k] G и известен набор активных ограничений h_i(х[k]) 0, j J. На основании данной информации вычисляют (-f (х[k])) и определяют проекцию  [-f (х[k])]. При этом возможны два случая:
а)  [-f’(х[k])] не равна 0. В качестве направления спуска р[k] принимают полученную проекцию;
б)  [-f (х[k])] 0, т. е.
Данное выражение представляет собой систему из п уравнений для определения коэффициентов и_j. Если все и_j 0, j J, то в соответствии с вышеизложенным точка х[k] является решением задачи. Если же некоторый компонент и_q 0, то соответствующий ему градиент выводится из матрицы А и порождается новая проецирующая матрица . Она определит новое направление спуска.
2. Для определения величины шага _k целевая функция минимизируется по направлению р[k] при условии соблюдения ограничений задачи с установленной точностью. Последняя задается введением некоторого положительного числа . Считают, что точка х удовлетворяет условиям задачи с заданной точностью, если h_i(х) , j 1, ..., m. Величина шага _k определяется решением задачи вида:
f(x[k] + р[k])  min;
h_j(x[k] + р[k]) , j 1, ..., m.
3. Определение нового приближения состоит в том, что очередная точка вычисляется по формуле
x[k+1] x[k] + _k р[k].
Признаком сходимости является стремление к нулю векторов р[k].

Рассмотренный метод является в некотором смысле аналогом градиентных методов для решения задач на безусловный экстремум, и ему свойствен их недостаток - медленная сходимость.

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