УМК (1013374), страница 9
Текст из файла (страница 9)
Для уменьшения числа обращений матрицы Гессе применяетсяупрощенный метод Ньютона, в котором обращение осуществляется один раз – в началь-ной точке x 0 :( ) ( )x k +1 = x k − t k H −1 x 0 ∇f x k , k = 0, 1,… .В. МЕТОД МАРКВАРДТАСтратегия поискаСтратегия метода Марквардта (Marquardt) состоит в построении последовательности точек x k , k = 0,1, … , таких, что f x k +1 < f x k , k = 0,1, … .
Применяется в слу-{ }() ( )чаях, когда на какой-либо итерации (итерациях) выполняется условие det H ( x k ) ≈ 0 , чтоприводит к значительным погрешностям вычисления обратной матрицы.{ }Точки последовательности x k вычисляются по правилу[ ( )x k +1 = x k − H x k + μ k E] ∇f (x ) , k = 0,1,… ,−1kгде точка x 0 задается пользователем, E – единичная матрица, μ k – последовательность[ ( )положительных чисел, таких, что матрица H x k + μ k E]−1положительно определена.Как правило, число μ 0 назначается как минимум на порядок больше, чем самый( )E ) ∇f (x )⎞⎟ < f (x ),⎠большой элемент матрицы H x 0 , а в ряде стандартных программ полагается μ 0 = 104 .( ( )−1μkkkто μ k +1 =. В противном случаеf ⎛⎜ x k − H x k + μ k2⎝μ k +1 = 2μ k . Легко видеть, что алгоритм Марквардта в зависимости от величины μ k накаждом шаге по своим свойствам приближается либо к алгоритму Ньютона, либо к алгоритму градиентного спуска.Если50Лекция 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 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
