5 Численные методы поиска условного экстремума (Лекции по теории оптимизации и численным методам)

Лекция 55. ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА УСЛОВНОГО ЭКСТРЕМУМАА. МЕТОД ШТРАФОВПостановка задачиДаны дважды непрерывно дифференцируемые целевая функция f ( x)  f  x1,, xn и функции ограничений g j ( x)  0 , j  1,  , m ; g j ( x)  0 , j  m  1,  , p , определяющие множество допустимых решений Х.Требуется найти локальный минимум целевой функции на множестве Х, т.е.

такуюточку x   X , чтоf ( x  )  min f ( x) ,xXгде X   xg j ( x)  0,g j ( x)  0,m  n .j  m  1, , pj  1, , m;Стратегия поискаИдея метода заключается в сведении задачи на условный минимум к решению последовательности задач поиска безусловного минимума вспомогательной функции:F x, r k  f ( x)  P x, r k  min ,где P x , r kxR n– штрафная функция, r k – параметр штрафа, задаваемый на каждой k-йитерации. Это связано с возможностью применения эффективных и надежных методовпоиска безусловного экстремума.Штрафные функции конструируются, исходя из условий:при выполнении ограничений, 0,P x, r k    0,при невыполнении ограничений,причем при невыполнении ограничений и r k   , k   справедливо P ( x , r k )   .Чем больше r k , тем больше штраф за невыполнение ограничений.

Как правило,для ограничений типа равенств используется квадратичный штраф, а для ограниченийтипа неравенств – квадрат срезки:P x, rkrk2 m2  [ g j ( x) ]  j 1где g j ( x) – срезка функции:512gx[()], jj  m 1pg j ( x)  0, g j ( x),g j ( x)  max 0, g j ( x)  g j ( x)  0. 0,Начальная точка поиска задается обычно вне множества допустимых решений Х . На каждой k-й итерации ищется точка x  r k при заданном параметре rмизации.

Полученная точка x r F x, r kkkминимума вспомогательной функциис помощью одного из методов безусловной минииспользуется в качестве начальной на следующейитерации, выполняемой при возрастающем значении параметра штрафа. При неограниченном возрастании r k последовательность точек x  r k стремится к точке условного минимума x  .З а м е ч а н и я.1.

Так как сходимость метода обеспечивается при r k   , то возникает вопрос отом, нельзя ли получить решение исходной задачи в результате однократного поиска безусловного минимума вспомогательной функции с параметром r k , равным большомучислу, например 1020 . Однако такая замена последовательного решения вспомогательных задач не представляется возможной, так как с ростом r k функция F x , r k приобре-тает ярко выраженную «овражную» структуру.2. Точки x  ( r k ) в алгоритме – это точки локального минимума функции F x , r k .Однако функция F x , r k может быть неограниченной снизу и процедуры методов без-условной минимизации могут расходиться.

Эти обстоятельства необходимо учитыватьпри программной реализации.3. Обычно выбирается r 0  0,01; 0,1;1 , C   4,10 , а r k 1  Cr k . Иногда начинаютс r 0  0 , т.е. с задачи поиска безусловного минимума.4. При решении задач процедура расчетов завершается при некотором конечномзначении параметра штрафа r k . При этом приближенное решение, как правило, не лежитв множестве допустимых решений, т.е. ограничения задачи не выполняются. Это является одним из недостатков метода. С ростом параметра штрафа r k генерируемые алгоритмом точки приближаются к решению исходной задачи извне множества допустимых решений.

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

МЕТОД БАРЬЕРНЫХ ФУНКЦИЙПостановка задачиДаны дважды непрерывно дифференцируемые целевая функция f ( x)  f  x1,, xn и функции ограничений-неравенств g j ( x)  0 , j  1,  , m , определяющие множестводопустимых решений Х.Требуется найти локальный минимум целевой функции на множестве Х , т.е. такуюточку x   X , чтоf ( x  )  min f ( x) ,где X xxXg j ( x)  0, j  1, , m .Стратегия поискаИдея метода заключается в сведении задачи на условный минимум к решению последовательности задач поиска безусловного минимума вспомогательной функции F x, r k  f ( x)  P x, r k , где P x, r k – штрафная функция, r k  0 – параметр штрафа.Как правило, используются:mа) обратная штрафная функция P x, r k   r k j 11;g j ( x)mб) логарифмическая штрафная функция P x, r k   r k  ln   g j ( x) j 1Обе штрафные функции определены и непрерывны внутри множества Х, т.е.

намножествеxg j ( x)  0, j  1, , m , и стремятся к бесконечности при приближении кгранице множества изнутри. Поэтому они называются барьерными функциями. Приr k  0 штрафная функция, задаваемая обратной функцией, положительна. Логарифмическая штрафная функция положительна при 1  g ( x)  0 и отрицательна при g ( x)  1 ,т.е.

внутренним точкам области отдается предпочтение перед граничными точками.Начальная точка задается только внутри множества Х. На каждой k-й итерацииищется точка x  ( r k ) минимума вспомогательной функции F x , r k при заданном пара-метре r k с помощью одного из методов безусловной минимизации. Полученная точкаx  ( r k ) используется в качестве начальной на следующей итерации, выполняемой приуменьшающемся значении параметра штрафа. При r k  0 последовательность точекx  ( r k ) стремится к точке условного минимума x  .

Барьерные функции как бы препятствуют выходу из множества Х, а если решение задачи лежит на границе, то процедураметода приводит к движению изнутри области к границе.Заметим, что согласно описанной процедуре точки x  ( r k ) лежат внутри множества допустимых решений для каждого r k . Этим объясняется то, что метод барьерныхфункций иногда называется методом внутренних штрафов.53З а м е ч а н и я.rk.C 0 обеспечивается сходимость, однако с уменьшением r k функция1. Обычно выбирается r 0  1,10,100 , параметр C  10;12;16 , а r k 1 2. При r kF x, r kстановится все более «овражной».

Поэтому полагать r k малым числом сразунецелесообразно.В. КОМБИНИРОВАННЫЙ МЕТОД ШТРАФНЫХ ФУНКЦИЙПостановка задачиДаны дважды непрерывно дифференцируемые целевая функция f ( x)  f  x1,, xn и функции ограничений g j ( x)  0 , j  1,  , m ; g j ( x)  0 , j  m  1,  , p , определяющие множество допустимых решений Х .Требуется найти локальный минимум целевой функции на множестве Х , т.е. такуюточку x   X , чтоf ( x  )  min f ( x) ,xXгде X   xj  1, , m; m  n .j  m  1, , pg j ( x)  0,g j ( x)  0,Стратегия поискаДля ограничений типа равенств применяется метод штрафов (внешних штрафов), адля ограничений-неравенств – метод барьерных функций (внутренних штрафов).Задача на условный минимум сводится к решению последовательности задач поиска минимума смешанной вспомогательной функции:F x, rkm  f ( x)  2r k j 1 [ g j ( x) ]12rkp1j  m 1 g j ( x )илиF x, r k  f ( x ) 12r km [ g j ( x) ] 2  r kj 1pj  m 1ln[  g j ( x) ] ,где r k  0 – параметр штрафа.Начальная точка задается так, чтобы ограничения-неравенства строго выполнялись: g j ( x)  0 , j  m  1,  , p .

На каждой k-й итерации ищется точка x  ( r k ) миниму-ма смешанной вспомогательной функции при заданном параметре r k с помощью одногоиз методов безусловной минимизации. Полученная точка x  (r k ) используется в качестве начальной на следующей итерации, выполняемой при уменьшающемся значении па-54раметра штрафа. При r k  0 последовательность точек x  (r k ) стремится к точке условного минимума x  .АлгоритмШаг 1. Задать начальную точку x 0 так, чтобы g j ( x)  0 , j  m  1,  , p ; начальное значение параметра штрафа r 0  0 ; число C  1 для уменьшения параметра штрафа;малое число  для остановки алгоритма.

Положить k  0 .Шаг 2. Составить смешанную вспомогательную функцию:F x, rkm  f ( x)  2r k j 1 [ g j ( x) ]12rkp1 f  x   P x, r kj  m 1 g j ( x )илиF x, rkm  f ( x)  2r k j 1 [ g j ( x) ]12rkpj  m 1ln[  g j ( x) ]  f  x   P x, r k .Шаг 3. Найти точку x  (r k ) минимума функции F x , r k с помощью какого-либометода поиска безусловного минимума с проверкой выполнения справедливости неравенств: g j ( x)  0 , j  m  1,  , p . При этом задать все требуемые выбранным методомпараметры.

В качестве начальной точки взять x k .Шаг 4. Вычислить P x  (r k ), r k и проверить условие окончания:а) если P x  (r k ), r k   , процесс поиска закончить:x   x  (r k ),б) если P x  (r k ), r kf ( x  )  f x  (r k ) ;  , то положить r k 1 rk,Cx k 1  x  (r k ),k  k 1 иперейти к шагу 2.З а м е ч а н и я.1. Метод предложен Фиакко и Мак-Кормиком (Fiacco, McCormick). Они рекомендуют r 0  1, C  4 .2.

Можно использовать разные параметры штрафа для внешних и внутреннихштрафов.55.