Главная Методы условной оптимизации [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [ 53 ] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] Вектор множителей Лаграижа г] в задаче (6.41) определяется заведомо совместной системой вида kPk + ek = knk- (6.45) Формулы (6.42), (6.43) и (6.44) корректны при любой невырожденной матрице Zj/fjZ, но дают оптимальный для (6.41) вектор только в том случае, если ZlHZ положительно определена. Когда у нее имеются отрицательные собственные значения, конечного минимума в задаче (6.41) просто не существует. Важно отметить, что при описанном способе построения определенность ZHZf, т. е. содержательность подзадачи (6.41), можно выяснить по ходу вычислений. Для оптимального вектора в задаче (6.41) существует много математически эквивалентных выражений. Например, Pk можно рассматривать как составляющую решения совместной системы линейных уравнений относительно Рй и (6.46) которая есть не что иное, как условия оптимальности первого порядка. Заметим, что уравнения (6.46) аналогичны используемым в методах ранг-пространства для оптимизации при линейных ограничениях (см. (5.54) в Рис. em. Три первые точки, выданные разд. 5.4). для примера 6.2 методом спроектированного лагранжиана с квадратичной подзада- Свойства локальной схо-чей; каждая-является точкой минимума димости. Если В качестве квадратичной ап роксимации функции мятпитгу W -яппппк Лаграижа при линейном ограничении- ратъ матрицу И/-аппрок-равенстве. симацию матрицы Гессе функции Лагранжа в д:*, ?*, построенную по аналитическим значениям производных, т. е. H, = W, = C{x,)--E{\), С,(х.), (6.47) то нетрудно доказать, что алгоритм SQ будет локально сходящимся. В частности, при таком выборе из условий (i) (х„ ?.„) мало отличается от (х*, X*), (ii) в х* вьшолнены достаточные условия оптимальности из разд. 6.4 и (iii) X+i берется равньш r]j из (6.45) следует квадратичная сходимость генерируемой алго- ритмом SQ последовательности к (х*, X*). Как и в случае с алгоритмом SP из разд. 6.5.2.2, первый порядок точности оценок мноаителей не снижает скорости сходимости до линейной; если Ijx,-х*] и - Х*-величины порядка е, то аналогичные нормы с Xft+i и Xj+, будут пропорциональны е". На рис. 6т изображены трн первых приближения, полученные алгоритмом SQ с из (6.47) в задаче примера 6.2. Вычисления были начаты с Хо=(-1.5, -1.6) и \ = 0. Заметим, что точки очень близки к показанным на рис. 61, иллюстрирующем работу алгоритма SP, но теперь никаких «внутренних» итераций не подразумевается. Правда, на каждом шаге требуется вычисление матриц Гессе всех функций задачи. Числовые значения норм {xt-х*.,}, А=1, .... 4. таковы: 2.03x10". 1.4IxI0- 8.18x10-", 4.95x10-». Квадратичную сходимость алгоритма SQ при сформулированных предположениях можно пояснять, если интерпретировать Ph и 4ft-Xft из решения подзадачи (6.41) как шаг по х и ?. метода Ньютона для поиска решения системы не/шнейных уравнений g(x») -Л(хТХ* = 0 (6.48а) с(х*)=0. (6.48Ь) представляющей собой условия оптимальности х* в исходной задаче. В самом деле, чтобы получить для (6.48) формулу расчета ньютоновского шага, надо линеаризовать функции (6.48) в окрестности (Xft, Xft), продифференцировав их, и это даст систему (6.46) с ft- = lFft. К сожалению, подобно упрощенному алгоритму SP в разд. 6.5.2.2, алгоритм SQ хорош только при наличии хорошего начального приближения, а если запустить его с пары (ао, d), значительно отличающейся от (х*, %*), он скорее всего не сойдется. Здесь снова уместно сослаться на его интерпретацию как результата применения классической ньютоновской схемы к уравнениям (6.48) - ведь известно, что последняя ненадежна даже в одномерном случае (см. разд. 4.1 и 4.4). Свойства ее локальной сходимости идеальны, но в отношении глобальной ничего хорошего сказать нельзя. Ниже рассматриваются модификации алгоритма SQ, позволяющие повысить его надежность. 6.5.3.3. Использование функции выигрыша. Приступая к выводу алгоритма SQ, мы подчеркнули, что высказываемые соображения ориентированы на малую окрестность оптимума. Если же точка Хй удалена от х* (или вектор существенно отличен от %*), целесообразность шага, определяемого подзадачей (6.41), представляется сомнительной. Область применимости этой подзадачи существенно расширится, если ее решение считать ие шагом, а направле-чнем поиска, шаг вдоль которого еще предстоит выбрать. Тогда очередным приближением будет i,+i=Xk+a,fik. (6.49) где jDft- оптимальный вектор из (6.41), а - длина шага вдоль р. Значеине а;, подбирают так, чтобы обеспечить «существенное убывание» (см. разд. 4.3.2.1) некоторой функции выигрыша, являющейся средством оценивания качества приближений. Впредь функции выигрыша будем обозначать через В роли Ф„ предлагалось использовать разные функции, и в том числе квадратичную штрафную (разд. 6.2.1.1), абсолютную штрафную (разд. 6.2.2) и модифицированную функцию Лагранжа (разд. 6.4.1). Свойства, которые требуются от фд,, состоят в следующем. Во-первых, Ф.„ должна быть разумной мерой близости к решению. Во-вторых, всегда должна существовать возможность уменьшить Фи положительным шагом вдоль р. Это означает определенную привязку Ф„ к порождающей pj подзадаче, причем следует отметить, что ради повышения надежности метода бывает целесообразно использовать подзадачи, отличные от (6.41). В-третьих, подсчет значения Ф.„ не должен быть чрезмерно трудоемкой процедурой. И наконец, желательно, чтобы условие убьшания не ограничивало скорости сходимости метода. К примеру, если в качестве берется Wt, квадратичная сходимость при использовании Фд, возможна лишь тогда, когда это условие допускает последовательность шагов {cxft}, достаточно быстро стремящуюся к единице. * 6.5.3.4. Другие постановки квадратичной подзадачи. Поскольку формулировка задачи (6.41) связана с условиями оптимальности, т е. с соотношениями, которые выполнены только в х*, ожидать, что (6.41) будет иметь большой смысл в далекой от х* точке Xj, не приходится. Ниже кратко рассмотрены постановки подзадачи, которые вдали от X* могут существенно отличаться от (6.41). Подзадача, орнентированная на свойства квадратичной штрафной функции. Допустим, что Хк лежит на траектории {x*(p)}, порождаемой методом квадратичных штрафных функций (см. разд. 6.2.1.1). Тогда прн необременительных предгюложениях устанавливается, что шаг р нз Xft в другую точку х*(р) этой траектории, отвечающую большему значению р, приблизительно совпадает с решением задачи найти minglp + pH при ограничениях Лдр = - - .i-j Х. (6.50) Здесь - аппроксимация матрицы Гессе функции Лагранжа, а Xj - текущая оценка Х*. Таким образом, можно предложить алгоритм, в котором Рй определяется из (6.50), а в качестве Фд используется квадратичная штрафная функция. Заметим, что при бесконечном р подзадача (6.50) переходит в (6.41). Следует также подчеркнуть, что никакой плохой обусловленности при больших р здесь (в отличие от методов разд. 6.2.1.1) не возникает. В подзадаче (6.50) значение штрафного параметра назначают в соответствии с оценкой расстояния до л* и неограниченно увеличивают по мере приближения к оптимуму. Подзадача, ориентированная на свойства логарифмической барьерной функции. Когда ограничения исходной задачи являются неравенствами и важно выдержать допустимость всех приближений, квадратичные подзадачи для расчета Рй строят, опираясь на свойства траектории точек х*{г), из метода барьерных функций (см. разд. 6.2.1.2). Если х принадлежит этой траектории и выполнены некие естественные условия, шаг р в точку х*{г), отвечающую мень. шему значению г, будет аппроксимироваться решением задачи найти min р1 р +рНа> РЕЯ" при ограничениях Af,p = -Cj + bj, (6.51) где Нк - приближение матрицы Гессе функции Лагранжа, а вектор 6,, вычисляется гю формуле {bk)i=rlQk)i. в которой - текущая оценка X*. Следовательно, определяя pj из (6.51) и используя в качестве Ф.,, при выборе Kft в (6.49) логарифмическую барьерную функцию, можно получить алгоритм, который при допустимом начальном приближении Хо будет генерировать только допустимые точки X,,. Значение г для (6.51) должно отражать степень близости х,, к X*. Когда параметр г равен нулю, подзадача (6.51) совпадает с (6.41). Отметим, что никакой плохой обусловленности при малых г не возникает. Интерпретация предлагаемых подзадач. Хорошую формулировку ограничений подзадачи метода последовательного квадратичного программирования отличают два свойства. Во-первых, по мере приближения Xfe к х* опредетяемые ею ограничения достаточно быстро стремятся к (6.40), и это обеспечивает методу наилучшие характеристики локальной сходимости. Во-вторых, она является до. статочно гибкой, т. е. пригодна для различных ситуаций, которые могут возникать по ходу решения. В подзадачах (6.50), (6.51) подобная гибкость достигается введением в правые части линеаризованных ограничений специфических сдвигов. Общие соображения в пользу таких сдвигов пртшедены ниже. Траектории методов квадратичных штрафных и логарифмических барьерных функций не косательны к допустимому множеству в X*. При этом, если х» - точка, лежащая на какой-то из них, то единичный шаг вдоль вектора Рй, полученного решением (6.50) или (6.51), будет короче, чем требуется для обнуления линеаризованных функций ограничений. Учитывая оба указанных об1тоятельства, МОЖНО говорить о том, что введение сдвигов повышает надежность линейной аппроксимации ограничений, на основе которой выбирается Ph- Для иных точек целесообразность сдвигов обосновывается по-другому. Обозначим через С; функцию ограничения, которое на основе некого разумного прогноза (см. разд. 6.5.5) предполагается активным в искомом решении, и пусть в текушрй точке х значение Ci очень близко к нулю, хотя ясно, что до X* ешр далеко. Тогда делать шаги с сохранением почти нулевого Ct скорее всего неэффективно: это было бы «отслеживанием нелинейной границы линейными средствами», что чревато суш,ественным замедлением сходимости (см. замечания к разд. 6.3). Именно так работал бы метод с (6.41), в то время как подзадачи (6.50) и (6.51) в этой ситуации дадут направления, уводящие от границы. *6.5.4. СТРАТЕГИИ ДНЯ ДЕФЕКТНЫХ ПОДЗ.адАЧ Ни одна из упомянутых выше формулировок подзадачи для метода спроектированного лагранжиана не исключает возможности, что эта подзадача окажется дефектной. На такие случаи надо иметь альтернативные формулировки. Краткий обзор их приводится ниже; более подробные сведения читатель найдет по ссыпкам, данным Б замечаниях. *6.5.4.1. Несовместные линейные ограничения. Описьшая в гл. 5 методы минимизации при линейных ограничениях, мы ие обсуждали проблемы несовместности условий подзадач для выбора направлений поиска, поскольку такая несовместность означала бы отсутствие допустимых точек из исходной задачи, и поэтому обсуждать здесь просто нечего. По-иному дело обстоит в случаях с нелинейными ограничениями: допустимое множество подзадачи типа (6.37) или (6,38) может оказаться пустым и тогда, когда нелинейные ограничения совместны. Это предполагает линейную зависимость строк матрицы At (т. е. наличие у нее дефекта ранга или превышение числа ее сгрок под числсм столбцов) и на практике, к сожалению, не является редкостью. Если ограничения Др = подзадачи метода спроектированного лагранжиана оказались несовместными, в качестве р, можно взять, например, вектор, минимизирующий норму ЦАр-d,,]]. Он будет удовлетворять набору возмущенных равенств с «минимальной» поправкой е. Таков один из способов разрешения проблемы несовместности модификацией ограничений подзадачи. Есть и другие. В частности, можно переопределять вектор с,, непосредственно контр олируя линейную независимость градиентов включаемых в него функций. Если исходная задача имеет хорошо обусловленное решение, подобные модификации потребуются только вдали от х* и потому не повлияют на асимптотическую скорость сходимости метода. Неразрешимость подзадачи с матрицей Л, имеющей лпнейно зависимые строки, служит признаком того, что при плохо обусловленной А возможны осложнения, В действительности их два: становится ненадежным вычисляемое значение составляющей направления поиска из ранг-пространства А,, т. е. вектора ру в (6.43); теряют точность оценки множителей Лагранжа (разд. 6.6). * 6.5.4.2. Плохая аппроксимация функции Лагранжа. Вторая вероячпан форма дефектности подзадачи выбора р/, - это неограниченность ее решения. При реализации метода, подобного рассмотренному в ра.зд. 6.5.2, угрозу отсутствия у подзадачи (6.37) (или подобной ей) конечного оптимума можно учесть лишь специальными пунктами в правилах останова применяемого к ней алгоритма. В частности, следует предусмотреть его прерывание после выполнения некоторого числа итераций. Больше здесь ничего сделать нельзя, так как не существует конечной процедуры, которая в общем случае позволила бы установить, ограничено решение (6.37) или нет. С представленными выше методами последовательного квадратичного программирования картина яснее. Квадратичная подзадача будет иметь бесконечное решение тогда, когда матрица Zft/ftZJ не является знакоопределенной. Тут ситуация аналогична возникающей в методах нькгтоновского типа для поиска минимума без ограничений и с линейными ограничениями. Аналогичен и набор средств, пригодных для модификации подзадачи. Например, Рд. можно строить по генерируеьюй на основе ZtWZj положительно определенной матрице (разд. 4.4.2). Правда, как и в ньютоновских методах, полученный в результате вектор не будет огмасштабированным, причем дело осложняется тем, что его образует не только связанный с ZJWjZ вектор р, но и ру, который от этой матрицы не зависит и полностью определяется линеаризованными ограничениями. Поэтому есть опасность, что плохо отмасштабированный р;г «подавит» впо.чне разумный ру (или наоборот). Проблема несоразмерности масштабов р и ру возникает при любом способе .модификации подзадачи. *6.5.5. ПОСТРОЕНИЕ АКТИВНОГО НАБОРА В этом разделе речь пойдет о формировании подзадач выбора р в методах спроектированного лагранжиана для отыскания минимума при ограничениях-неравенствах. Будем считать, что полная [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [ 53 ] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] 0.0011 |