Главная  Методы условной оптимизации 

[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.2.2. МЕТОДЫ НЕГЛАДКИХ ШТРАФНЫХ ФУНКЦИЙ

Как указано в разд. 6.2.1.1, дифференцируемые штрафные функции страдают плохой обуслоапенностью даже для гладких, хорошо поставленных задач. Это отрицательно сказывается иа характеристиках соответствующих методов и приводит к тому, что в них приходится решать длинные серии подзадач безусловной минимизации. В то же время можно строить недифференцируемые, но хорошо обусловленные штрафные функции с локальным минилтумом в искомой точке X*. Тогда поиск х* сведется к однократной безусловной минимизащги. Данный подход представляется более естественным, по крайней мере в отношении задач, которые сами содержат негладкие функции. Конструкцию и свойства недифференцируемых штрафных функций мы рассмотрим в разд. 6.2.2.1, а их приложение к негладким задачам - в разд. 6.2.2.2.

6-2.2.1, Абсолютная штрафная функция. Наиболее распространенной среди недифференцируемых штрафных функций является так называемая абсолютнаи штрафная функция:

Рл(х, p) = f (х) + р i:,\c,(x)lF{x) + pfc(x)\\,. (6.8) 16/

Здесь через с~{х) обозначен вет<тор нарушенных в х ограничений, а через / - список их индексов. (Напомним, что =21 № .)

Первые производные от (х, р) разрывны в .любой точке, где хотя бы одна из функций с; (х) обращается в нуль; тактгм образом, х* будет точкой гладкости Р только в том случае, если все ограничения в х* неактивны. Функция Р. помимо прочего принципиально отличается от Pq тем, что при нормальных условиях для построения с ее помощью искомого решения х неограниченно увеличивать р не нужно; существует конечное пороговое значение р, такое, что х будет точкой безусловного минимума Pj при любом р> р. По этой причине штрафные функции типа Pj иногда называют точными (в противовес дифференцируемым штрафным функциям, для которых х*(р) не совпадает с X* нн при одтюм конечном р). Другие точные штрафные функции упоминаются в замечаниях к разд. 6.4,

Чтобы проиллюстрировать эффект негладкого штрафа, вернемся к задаче нз примера 6.1:

Для нее

найти min х** при ограничении .

-1 = 0.

Ра(х. р) = х-1-рх-1.

(6.9) -

и нетрудно проверить, что х*=1 является точкой безусловного минимума (6.9) при любом р>2. Графики F(x) и Ра (х, р) с р=4 изоб-

ражены на рис. бе штриховой и сплошной линиями. Видно, что в X* реализуется локальный минимум Рл.

Рассмотрим принципиальную схему решения гладкой задачи ус-.повной минимизации с применением недиференцируемой штрафной функции (схема для негладких задач описана в разд. 6.2.2.2). В соответствии с ней, задав начальное приближение Хо, положительное целое К, параметр штрафа р и сделав присвоение А-.-О, надо выполнить следующие действия.

Алгоритм ЕР {Модельная схема с точной штрафной функцией)

EPI. [Проверка соблюдения условий окончания счета.] Если Xj удов.летворяет условиям оптима.пьностн илн к> К, вычисления прекратить. В первом случае х берется в качестве решения; во втором выдается признак неудачи.

ЕР2. [Увеличение параметра штрафа.] Если А>0, увеличить р. ЕРЗ. [Минимизация штрафыой функции.] Использовав х в каче-


1.3 а:

Рис. бе. Штриховая линия - график целевой функции из примера6.1, F{x)-x, сплошная- график абсолютной штрафной функции Рл 1хЛ)х+Щх-Ц.

стве начальной точки, применить алгоритм решения задачи найти rain Р., (X, р), (6.10)

правила останова которого должны предусматривать возможность неограниченности Р снизу; лучшее из найденных приближений взять в качестве х ,. ЕР4. [Перевод счетчика итераций.] Сделать присвоение k-\-l и вернуться к шагу ЕР1.

В силу сказанного ранее при любом «достаточно большом» начальном р итерации будут прерваны при к=1.

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



ками, и иа случай, если они подведут, необходимо предусмотреть возможность корректировки р (шаг ЕР2 общей схемы). При этом неудачный выбор параметра штрафа чреват серьезными осложнениями. Если значение р занижено, штрафная функция либо может оказаться неограниченной снизу, либо «область притяжения» точки х* будет очень малой. Если же взять р слишком большим, подзадача (6.10) окажется плохо обусловленной.


Рис. 6f. Липни уровня абсолютных штрафных функций Ра[.х. р) с р=1.2, р=5 и р-10 для примера 6.2.

Влияние величины р проиллюстрировано рис. 61, где изображены линии уровня Р,, для задачи из примера 6.2 при трех значениях р(р=1.2, р=5, р=10). Так как абсолютный штраф «слабее» квадратичного, проблемы, связанные с неограниченностью, стоят для Р.4 острее, чем для Pq. В частности, хотя первая из показанных на рис. 61 функций достигает в х* локального минимума и в окрестности X* хорошо обусловлена, процедуре ее безусловной минимизации удастся найти х* лишь при условии, что поиск начнется с очень хорошего приближения. (Кстати сказать, Ра примера 6.2 не ограничена снизу ни при одном р.) Ухудшение обусловленности Ра с увеличением р отчетливо проявляется иа третьем фрагменте рис. 61.

Поскольку функция Р,1, как правило, недифференцнруема даже в точке минимума, стандартные методы оптимизации без огранп-чений, рассчитанные на гладкие функции, применять к ней напрямую не следует. Для минимизации Ра в случаях, когда исходные функции дифференцируемы, разработаны специальные алгоритмы; ссылки на них даны в замечаниях. Эти алгоритмы в полной мере учитывают специфику Ра Д.1я гладких задач. Для повышения эффективности поиска минимума недифференцируемой штрафной функции и выбора разумного значения р может использоваться информация об исходной задаче и в том числе оценки миожитепей .-Лагранжа.

6.2.2.2. Метод решения негладких задач общего вида. Если какие-то из функций задачи NEP или N1P разрывны, или имеют разрывные производные, абсолютная штрафная функция уже не будет

композицией гладких составляющих. Поэтому для поиска ее минимума скорее всего придется использовать какой-нибудь универсальный метод негладкой оптимизации типа метода многогранника из разд. 4.2.2; правда, дня некоторых задач с известной структурой разрывов удается разработать более эффективные специальные методы (см. разд. 6.8).

Подбирая параметр штрафа в Ра, с одной стороны, желательно получить функцию, достаточно хорошо обусловленную в окрестности искомой точки х", а с другой стороны, обеспечить этой точке хорошую область притяжения (которая, вообще говоря, тем шире, чем больше р). Данный принцип воплощен в предлагаемой ниже схеме решения негладких задач с произвольными структурами разрывов. Хотя она похожа на алгоритм ЕР (см. разд. 6.2.2.1), между ними есть и с>ществе1Шые различия; проверки, выполняемые в новой схеме (например, оценка «удовлетворительности минимума»), должны бьггь ориентированы на конкретную задачу. Кроме того. XI. принимается в качестве решения только в том случае, если дополнительная попьпка улучшить х ие увенчалась успехом.

Итак, задав начальную точку x„, начальное значение параметра штрафа р, положительные р,,, и y(v>l) н сделав присвоение *-<-0, ретпение негладкой задачи можно искать следующим образом.

Алгоритм ND {Модельная схема решения негладких задач с ограничениями)

ND1. [Решение безусловной подзадачи.] Начиная с Xf,, делается попытка найти приближение минимума функции Р (х, р) методом многогранника из разд. 4.2.2. Чтобы гарантировать остановку метода, вводится ограничение сверху на число обращений к процедурам расчета функций задачи. В качестве х+, берется лучшая из просмотренных точек. ND2. [Увеличение параметра штрафа.] Ес.пи fe>0, осуществляется переход к шагу ND3. Если р > р,,,,,,, вычисления прекращаются и выдается сообщение о неудаче. Если на предыдущем шаге удов.тетворительного минимума Р найти не удалось или точка х,,+ недопустима, выполняется присвоение рTP и осуществляется переход к шагу NDI. В npoTiiBHOM случае выполняется шаг ND4. ND3. [Выяснение возможности уменьшить параметр штрафа.] Если Aft+i не «намного предпочтительнее», чем х, вычисления прекращаются и лучшая из точек х,+ и Xj берется в качестве решения. ND4. [Уменьшение параметра штрафа.] Делаются присвоения р-ь-р/у, k-b-k+l И осуществ.чяется возврат к шагу ND1. Разрывность производных Ра в точке минимума для метода .многогранника - обстоятельство полезное. Поэтому именно он использован в предлагаемой схеме. Правда, маловероятно, что в х* будут разрывны производные от Рд по всем направлениям, и, зна-



чит. есть определенный риск, что метод многогранника «замкнется в подпространстве», т. е. в некоторых направлениях минимизация будет выполнена очень неточно. Как средство, которое, возможно, поправит депо, в схеме предусмотрена возможность уменьшения параметра штрафа в шаге ND4.

Замечания и избранная библиография к разделу 6.2

Штрафные и барьерные функции имеют долгую историю. По-видимому, они испапьзовались при решении инженерных проблем задолго до того, как получили официальное признание у математиков. У этих функций есть много разных форм, и в конкретных приложениях им часто дают специальные названия. К примеру, в кристаллографических расчетах квадратичный штраф добавляется к целевой функции как «сдерживающий фактор», гарантирующий, что решение оптимизационной задачи «не слишком сильно» нарушит ограничения. Абсолютная штрафная функция многие годы применяется в строительном и машинном проектировании.

Самым фувдаментальным изданием, посвященным гладким штрафным и барьерным функциям, является книга Фиакко и Мак-Кормика (1968) «Не.пииейное программирование. Методы ностедова-тельной безусловной минимизацию. В ней просуммированы и развиты результаты из серии статей, опубликованных Фиакко и Мак-Кормиком в журнале Management Science. Эта книга служит главным источником сведений по методам штрафных и барьерных функций

Квадратичная штрафная функция впервые появилась в матема-мической литературе в работе Куранта (1943). Автором логариф. мической барьерной функции считается Фриш (ig,").")); Кэррол (1959, I96I) предложил так называемую «обратную» барьерную функцию

В,(х, r)F(x)-\-r

с,{х)-

Розенброк (1960) построил метод с модификацией целевой функции, аналогичной барьерному преобразованию, но не создающей особенностей на границе допустимого множества.

Общий обзор штрафных и барьерных функций можно найти в работах Зангвилла (1965, 1967а) и Райана (1974).

Больше всего о методах штрафных и барьерных функций гово. рплось в 60-х годах. Это объясняется появлением в то время мощных агоритмов безусловной минимизации (техника поиска безусловного эксгремума обсуждается в гл. 4). Программа SUMT, разработанная Фиакко и Мак-Кормиком, была тогда, пожалуй, самым широко употребляемым универсальным средством решения нелинейных задач на условный минимум.

Неизбежная плохая обусловленность матриц Гессе в методах гладких штрафных и барьерных функций впервые была отмечена Мюрреем (1967). Подробное обсуждение этого явления производится в работах Мюррея (1969а, 1971b) и Лутсма (1969, 1970, 1972).

Специальные процедуры одномерного поиска для алгоритмов минимизации штрафных и барьерных функций читатель найдет, например, у Флетчера и Д\ак-Канна (1969), Мюррея (1969а), Лэсдона, Фокса и Ратнера (1973), Мюррея и Райт (1976).

Методы И1трафных и барьерных функций инотда используют в качестве предварительных в «гибридных» схемах. Они дают непло-XTie приближения, которые затем уточняются какими-нибудь методами иного сорта с хорошими свойствами локальной сходимости. В частности, Райан (1971) и Осборн и Райан (1972) комбинировали таким образом методы квадратичной штрафной функции и модифицированной функции Лагранжа (см. разд. 6.4), а Розен (1978) и Ван-дер-Хук (1979) предложили применять метод штрафной функции как средство поиска хорошего начального приближения для метода спроектированного лагранжиана (см. разд. 6.5).

Идея построения недифференцируемой штрафной функции, для которой искомое решение х* было бы точкой безусловного минимума при конечном значении параметра штрафа, впервые в неявной форме высказана Э&поу и Брайхемом (1955), а затем пропагандировалась в отношении выпуклых задач Петшиковским (1962) и Зангвил.пом (1965, 1967а). Обзор общих свойств абсолютной штрафной функции приведен в работе Петшиковского (1969). Среди других публикации, посвященных свойствам точных штрафных функций данного типа, можно назвать работы Эванса, Гу.17да и Толле (1973), Хоува (1973), Бертсекаса (1975а), Караламбуса (1978). Хана и Ман-гасарьяна (1979), Колемана и Конна (1980а).

Методы недифференцируемых штрафных функций поначалу считали непрактичными, так как обычные алгоритмы безусловной мниимизации (предполагающие гладкость) в них применять нельзя, а других эффективных алгоритмов не было. Однако к настоящему времени для негладких штрафных функций (и других функций с известной структурой разрывов производных) разработано немало хороших специальных схем. Их описания можно найти в статьях Зангвилла (1967b), Конна (1973), Конна и Петшиковского (1977), .Пенарешаля (1975), Мнффлнна {Ш7), Маратоса (1978), Колемана (1979), ЛЬйна и Маратоса (1979). Во многих из этих схем направления поиска определяются из тех же соображений, что и в методе спроектированного лагранжиана с квадратичной подзадачей, рассматриваемом в разд. 6.5.3.

Лбсатютиую штрафную функцию иногда используют в качестве функции выигрыша в методах спроектированного .пагранжиана (см. разд, 6.5.3.3), причем некоторые из этих методов явно ориентированы иа ее минимизацию. О них еще будет сказано в замечаниях к разд. 6.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.001