lopt6 (1013499)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция 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.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций