lopt6 (Лекционный курс)
Описание файла
Файл "lopt6" внутри архива находится в папке "Лекционный курс". PDF-файл из архива "Лекционный курс", который расположен в категории "". Всё это находится в предмете "теория оптимизации и численные методы" из 4 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "теория оптимизации и численные методы" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Лекция 65. ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА УСЛОВНОГО ЭКСТРЕМУМАА. МЕТОД ШТРАФОВПостановка задачиДаны дважды непрерывно дифференцируемые целевая функция 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.