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

[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 прилагаются рис. 6Ь и 6с. На левом фрагменте рис. 6Ь изображены линии уровня целевой функции и граница допустимого множества (выпуклая вниз кривая). Кре-


Рис. 6Ь. На левом фрагменте изображены линии уровня функции F{x)=XiXi и граница допустимого множества ограничения 2-xJ-л>0; крестиком отмечена точка оптимума (-0.81650, -1.1547). На правил фрагменте изображены линии Уровня соответствующей функции Лагранжа L{x, X*).

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


Рис. 6с. Линии уровня квадратичных штрафных функций Pq{x, р) с р= 1 и р= 100 для примера 6.2.

отвечающих ей квадратичных штрафных функций с р=1 и р=100 показаны на рис. 6с. Первая обусловлена неплохо - ее линии уровня напоминают окружности. При р=100 картина совсем иная; здесь уже явственно проявляется плохая обусловленность, сопутствующая большим значениям параметра штрафа.

По мере того как с увеличением р обусловленность матрицы Гессе штрафной функции ухудшается, минимум последней в нуль-пространстве градиентов активных ограничений становится все менее отчетливо выраженным. Поэтому, если сразу взять «очень большой» параметр штрафа, даже надежный алгоритм безусловной минимизации, как правило, будет испытывать во время поиска х* (р) очень серьезные затруднения (см. разд. 8.3). Таким образом, при использовании гладких штрафных функций в задачах NEP или NIP приходится решать последовательность задач безусловной минимизации, постепенно увеличивая параметр р. Обычно точку х* (р), полученную лдя предыдущего значения р, используют в качеспве начального приближения для минимизации штрафной функции со следующим р. В конце концов должна быть найдена точка, удовлетворяющая выбранному критерию останова, и в ней вычисления будут прекращены.

Итак, чтобы отыскать решение задачи с нелинейными ограничениями методом гладких штрафных функций, надо, задав начальное значение параметра штрафа ро, положительное целое число /С и начальную точку Хо и сделав присвоение А-*-0, выполнить следующие действия:

Алгоритм DP (Модельная схема минимизации с использованием гладкой штрафной функции) DPI. [Проверка соблюдения условий окончания счета.] Если

удовлетворяет условиям оптимальности или k> К, вычисления прекратить. (В первом случае вьщается признак успешного окончания счета, во втором - признак неудачи.) DP2. [Минимизация штрафной функции.] Взяв в качестве начального приближения, применить алгоритм решения подзадачи безусловной минимизации

найти min Pq {х, рь).

(6.3)

в котором должны быть приняты предосторожности на случай, если Pq окажется неограниченной снизу. Он выдаст очередную точку х+х-DP3. [Увеличение параметра штрафа.] Взять в качестве р+, некоторое превосходящее р число, сделать присвоение и вернуться к шагу DPI.

Плохая обусловленность подзадач безусловной минимизации при 0«</1 и больших р является первой из общих особенностей методов гладких штрафных функций. Пришло время поговорить о двух .других

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



локальных минимумов. Глобальный же минимум может быть бесконечным (нетрудно привести примеры, когда Pq не ограничена снизу при любом р). В таких случаях обеспечить сходимость процедуры безусловной минимизации в нужную точку бывает непросто: итерации поиска могут вывести за пределы ее «области притяжения». Сказанное означает, что применять к подзадачам метода штрафных функций стандартные схемы минимизации типа рассмотренных в гл. 4 следует с осторожностью. Последние предполагают ограниченность функции снизу и в ее отсутствие могут расходиться. Таким образом, нх никак нельзя использовать в методах штрафу ных функций как «черный ящик». Алгоритм, предназначенный для решения соответствующих подзадач, должен включать средства, позволяющие выявить неограниченность и, если возможно, нейтрализовать ее влияние (на что и указано в п. DP2 общей схемы).

Возможность оценивания множителей Лагранжа. В силу специальной структуры штрафной функции, объединяющей в себе все функшти задачи, носче довательность jjt* (р)} содержит много по.пезной информации. В частности, по ней можно строить оценки множителей .Пагранжа (когда эти множители существуют). В точке x* (р), доставляющей безусловньш минимум функции Pq, должно выполняться равенство

§--рЖс = 0. Отсюда видно, что величины

г,(Р)=-рс,((р)) (6-4)

играют Б x* (р) ту же роль, что и множители .Пагранжа в искомой точке х": они служат коэффициентами разложения градиента g по строкам матрицы Л. При естественных предположениях можно доказать, что

lim ?.,(p) = /.;, (6.5)

Р-.со

причем II?.*->.(р) = 0(1/р). Так, в примере 6.1, где К = 2, формула (6.4) дает \{р) = 2рЦр + 2).

Допустим, что метод штрафных функций используется для решения задачи с неравенствами и в ней ?.>0. Тогда из (6.4) и (6.5) следует, что в точках минимумов Pq(x, р) с достаточно большими р 1-е активное ограничение будет нарушено. Данное свойство позволяет идентифицировать набор активных в х" ограничений и, по существу, означает, что для метода штрафных функций «рабочий список» есть «нарушенный список». Оно исключает возможность применения метода в случаях, когда важна допустимость генерируемых приближений.

6.2.1.2. Логарифмическая барьерная функция. Методы штрафных функций идут к решению извне допустимого множества. Поэтому они не годятся для задач NIP, требующих соблюде1ШЯ огра-

I иичеиин в течение всего процесса поиска; тут нужны методы допу-I стимой точки, порождающие только допустимые приближения. I Таковы, в частности, методы барьерных функций, рассматриваемые 1 в данном разделе (другие будут представлены в разд. 6.3 и 6.5.3.4). \ Основная область применения методов допустимой точки - задачи, некоторые (или все) функции которых не определены или плохо ; определены за пределами допустимого множества. Кроме того, они предпочтительны тогда, когда не нужна высокая точность до-стяжения оптимума, но ограничения важно выдержать,- в этой \ ситуации иные методы (скажем, метод с квадратичной штрафной функцией) сэкономить время не позволяют, так как при прерывании вдали от решения дают существенно недопустимые точки.

Методы барьерных функций работают по тому же принципу, что и методы штрафных функций, описанные выше: х* ищется как предел последовательности точек безусловных минимумов гладких модифицированных целевых функций Ф,. Однако в них Ф, устроены так, что эти точки ложатся строго внутрь допустимого множества: добавки в Фц к F служат «барьерами», удерживающими процедуру минимизации Ф„ от нарушения ограничений. В качестве таких «барьеров» используют взвешенные суммы непрерывных

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

Характерные черты всех методов барьерных функций мы обсудим на примере одного из них, а именно метода логарифмической барьерной функции

В (x, r)F (х)-г 2 In (с,. (x)).

(6.6)

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

Чтх*(г)=х*.

Пример 6.3. Рассмотрим эффект барьерного преобразования для вадачи

найти min х

при ограничении х-10.



В данном случае

В (X, г)=х-г 1п (х-1)

х(г) = - + -\Т+Тг.

Истинным решением является х* = 1.

У методов барьерных н гладких штрафных функций есть много общих свойств. Это видно и из представленного ниже перечня наиболее существенных особенностей метода с логарифмической барьерной функцией.

Плохая обусловленность. Пусть t - число ограничений задачи, активных в X*, и 0<С/<С«. Тогда по мере приближения г к нулю матрица Гессе барьерной функции в х* (г) будет все хуже и хуже


Рнс. 6d Линии уровня логарифмических барьерных функций В(х. г) с /=0.2 и f=0.001 дан примера 6.2.

обусловленной, и в пределе ее число обусловленности становится бесконечным. На рис. 6d (зображены линии уровня логарифмических барьерных функций для задачи из примера 6.2 с л=0.2 и j r=O.OOI. Поскольку вне допустимого множества эти функции не определены, там никаких линий не нарисовано. Отметим, что на правом фрагменте, отвечающем меньшему значению г, линии уровня почти парэ.п.пельны, т. е. отчетливо проявляется плохая обуслов- i ленность. Из-за трудностей, возникающих прн поиске безусловного минимума функций (6.6) с «очень малым» г, к искомому решению х* приходится идти, последовательно минимизируя барьерные функции с постепенно уменьшаемыми значениями.

Локальность минимума. .Погарифмическое барьерное преобразование, вообще говоря, порождает во внутренности допустимого множества лишь .локальный минимум. При этом функция (6.6) может оказаться неограниченной снизу. Правда, такая вероят-

ность существует только в случаях, когда не ограничено допустимое множество. И все же ее нельзя сбрасывать со счетов, т. е. оиа должна быгь учтена в методе, применяемом для безусловной минимизации (6.6).

Трудности одномерного поиска. Из-за того что барьерные функции определены не во всех точках и имеют особенности, применять в алгоритмах их минимизации стандартные процедуры одномерного поиска, как правило, неэффективно. Во-первых, эти процедуры предполагают юзможиость вычисления функции в любой точке и активно используют все пробные значения. Значит, обращаясь к какой-нибудь из них, придется доопределить барьерну]0 функш1Ю в недопустимой области и смириться с тем, что соответствующие бессмысленные значения смогут запутывать вычисления. В то же время находить для каждого из генерируемых направлений шаг до границы допустимой области и ставить его в качестве порога для одномерного поиска (как это делается в алгоритмах решения задач с линейными ограничениями) в общем случае невозможно. Во-вторых, традиционный способ построения очередной оценки длины оптимального шага исходя из одномерной поли(юмиальной аппроксимации (см. разд. 4.1.2.3), для барьерных функций скорее всего будет работать плохо (особенно при малых значениях параметра рьера, когда поиск идет вблизи особых точек). Короче говоря, здесь нужны специальные процедуры минимизации по направлению, и, к счастью, поскапьку характер особенностей барьерных функций ивестен заранее, эти процедуры удается сделать довольно эффективными (см. замечения).

Оценки множителей Лагранжа. Точки {х*(г)} минимумов логарифмических барьерных функций с малыми г несут информацию о множителях Лафанжа исходной задачи. В х" (г) будет вьшолнено равенство

.-1

(6.7)

т. е. градиент функции F в х" (г) есть неотрицательная линейная комбинация градиентов всех ограничений. Таким образом, коэффициенты при а, в (6.7) играют в х* (г) ту же роль, что и множители .Пагранжа в х*. При слабых предположениях можно доказать, что для неактивных в х* ограничений с уменьшением г онн стремятся к нулю, а если i-e ограничение в х* активно, то

.0 W)

Огметим сугличие (6.7) от (6.4), где фигурируют только нарушенные в X* (р) ограничения.



[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