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

[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.58)

совместна, минимум в (6.57) равен нулю. Однако в отсутствие равенства с (х,) = О вектор X, и в этом случае останется лишь оценкой для X*. Мы подчеркиваем это, поскольку соемеатость системы (6.58) автоматически обеспечивается некоторыми алгоритмами. В частности, она гарантирована, если х, выбирается как точка минимума модифицированной функции Лагранжа (6.24); тогда Х совпадает с из (6.27). (Оценкой первого порядка, сггражающен отличие Cj от нуля, может послужить Х,-C\i)~Ct.)

Как и для задач с линейными ограничениями (разд. 5.1.5), наряду с Xj оценкой X* первого порядка будет решение Ху системы уравнений

V4,, = g. (6.59)

где V есть невырожденная < х -подматрица At, а g,,-вектор, набранный из соответствующих компонент gj. Если система (6.58) совместна, Х, и Х совпадают.

В предположении полноты ранга матрицы А (х*) нетрудно доказать, что для близких к х* точек Xf, нормы [X-Х* и [[Х,.--Х*К соразмеримы с (jx-а*[1. Отсюда и термин-01{енки первого порядка. При этом уклонения Х и Ху от X*, грубо говоря, пропорциональны числам обусловленности wV соответственио. Кроме того, оишбки X, и Х[. зависят от кривизны функций задачи. Пример, иллюстрирующий характер представленных оценок, читатель найдет в разд. 5.1.5.

6.6.2. ОЦЕНКИ ВТОРОГО ПОРЯДКА

Как и в случае с линейными ограничениями (см. разд. 5.1.5.2), при определенных условиях X* удается оценивать с ошибкой, пропорциональной квадрату расстояния от Хд до х*. Обозначим (неизвестный) шаг из в X* через q. Тогда (6.54) можно переписать так;

g(x„ + q) = Aix,-\-qrX.

Разлагая левую и правую части этого равенства по Тейлору, получим

& + И» (•) q=l>-Ч-О (1 ? 1(6.60)

где П7»(Х) - матрица Гессе функции Лагранжа с множителем X. т. е.

W»W = C(Xt)-2 X,G,(x,).

Непосредственно оценить X* по равенству (6.60) нельзя, поскольку второе слагаемое в его левой части содержит неизвсстньн") вектор q, который к тому же умножается иа матрицу, вычисляемую по X*. Однако, имея приближение р для q и какую-то предварительную оценку X пли X*, из (6.60) нетрудно в1>шести соотношение, которое подскажет формулу уточнения X;

e, + W,(X)p=AlX + 0{\qr-\X-X4\q\ + lp-q\S,. (6.61)

На основании (6.61) в качестве оценки ц. для X* естественно предложить реи]ение задачи

найтн min I Л?г,- (g. -ь (Х)р)11. (6.62)

Если Лд имеет полный ранг, то можно добиться, чтобы при (? = 0(в) норма Ihii-Х* была пропорциональна е, т. е. -ц, была оценкой второго порядка. Для этого достаточно обеспечить соотношения Х-Х* = 0(е), р-q\0{e,), т. е. подбирать X и р как оценки по меньшей мере первого поридка для X* и второго дг1я 9 соответственно.

В разд. 5.1.5.2 представлен пример задачи с линейными ограничениями, в которой аналогичная т] нз (6.62) оценка оказалась крайне ненадежной; разумеется, такое случается и при нелинейных ограничениях.

Когда в качестве р используется решение квадратичной подзадачи вида

найти min gp-pW„(X)p

"я" (6.63)

при ограничениях A„p = dt,

то независимо от выбора dj минимум в (6.62) будет нулем, причем 11 из (6.62) оказывается точным вектором множителей Лагранжа задачи (6.63). Если к тому же = -с, при определенных условиях (как уже было отмечено в разд. 6.5.3,2) можно утверждать, что р-I/[1 = 0(6") и. следовательно, iij является оценкой второго порядки. Этим обусловлена квадратичная сходимость q к нулю в алгоритме SQ, а из нее вьпекает квадратичная сходимость к X*. Последняя хорошо иллюстрируется набором значений -ХТ, полученным применением алгоритма SQ к задаче из примера 6.2 (см. рис. 6т): первые четыре значения в этом наборе равны 2.22х10->, 2.12x10-», 2.23x10- и 1.12x10-.

Оценки X* второго порядка порождаются и методами спроектированного лагранжиана, рассмотренными в разд. 6.5.1. В них таковыми служат векторы XJ множителей Лагранжа подзадач типа (6.37). Как указано в разд. 6.5.2.2, при некоторых предположениях последовательность Х сходится к X* квадратично, и это есть следствие того, что для Xj, близких к х*, уклонение



Xt от X* пропорционально квадрату нормы \\х„-д-». Квадратичная сходимость Xt к X отчетливо проявляется на последователь-но<Ти оценок, генерируемых алгоритмом SP в задаче из примера 6.2 (см. рис. 61): значения \Xk - X\, k = 0, 3, равны 1.46х10->, 1.02x10-», 1.85х10-« и 7.25x10-».

♦6.6.3. оценки множителей для ограничений-неравенств

Компоненты вектора X*, отвечающие тем ограничениям исходной задачи, которые являются неравенствами, неотрицательны (см. ра:зд. 3.4.2). Более того, обычно они оказываются положительньши, и тогда соответствующие компоненты Х и Ху для достаточно близких к X* точек Xt наверняка будут иметь правильные знаки. Однако даже в таких случаях вдали от х* аналогичных гарантий дать нельзя. В то же время для некоторых методов неотрицательность оценок множителей неравенств существенна. Значит, здесь нужно как-то изменить способы оценивания.

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

найти min ЛХ-g,, 11

при ограничениях X, >0, igj?".

(6.64)

где через S обозначен список индексов учитываемых в неравенств; для решения (6.64) надо использовать метод типа описанного в разд. 5.3.3. Фактически переход на (6.64) приводит к «выводу» неравенств с отрицательными оценками множителей нз рабочего списка.

В методах минимизации при ограничениях-неравенствах оценки для X* второго порядка (см. разд. 6.6.2) обычно определяются как множитетш Лагранжа из подзадач типа (6.37) или (6.63), условия которых соответствуют прогнозу активного набора для исходной задачи. Кагталось бы, чтобы обеспечить правильность знаков оценок, логичнее использовать подзадачи с неравенствами. Однако, хотя при этом неотрицательность оценок гарантирована, их надежность еще остается под вопросом. Они будут точны только при соблюдении ряда требований, н, в частности, нужна близость используемого для построения целевой функции подзадачи вектора Хд к X*. Но такая близость предполагает, что выявлен правильный список активных ограничений, а тогда подзадача с равенствами должна дать тот же результат. Если же верность прогноза активных ограничений сомнительна, полагаться на оценки множителей из подзадачи с неравенствами нельзя.

6.6.4. проверки состоятельности

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

Оценка X* второго порядка, построенная в точке xt, обычно имеет смысл приближения оценки первого порядка в Xt+i. Вьиислпв последнюю независимым образом (в соответствии с каким-то прогнозом активного набора в x,,+i), мы получаем возможность выявить качество этого приближения и тем самым состоятельность обеих оценок (и та и другая в идеале должны совпадать с X*). Подобный контроль состоятельности особенно полезен при прогнозировании активного набора.

Чаще всего оценки X* второго порядка в оказываются хуже, чем оценки первого порядка в Xft.I, Поэтому, если расчет последних ие требует серьезных дополнительных затрат, именно их стоит использовать в роли параметров целевых функций подзадач. Эта рекомендация относится, например, к методам с построением направлений поиска на основе 7,(2-разложения Л r: в них ценой ничтожных дополнительных усилии можно вычислять Xt.

Важно подчеркнуть, что оценки первого порядка сходятся к X* с той же скоростью, что и х к х*, причем, как уже было отмечено ранее, применетше таких оценок в методах спроектированного лагранжиана скорости сходимости этих методов не снижает. В частности, при определенных условиях приближения jxj[, полученные алгоритмом SQ (см. разд. 6.5.3.2), сходятся к X* квадратично, и тогда последовательность вычисляемых в Хц оценок первого порядка тоже будет квадратично сходящейся. Для иллюстрации сказанного приведем начальный отрезок последовательности уклонений от Х* оценок (XJj, полученных прн решении алгоритмом SQ задачи из примера 6.2, Здесь условия квадратичной сходимости {х} выполнены и значения {\JX,)i,-X\\, k = l, .... 4, таковы: 8.57x10-», 7.67x10-=, 4.02x10-5 и 1.36x10-" (ошибки оценок % для той же задачи и в тех же точках даны в разд. 6.6.2; обратите внимание на то, что (XJ всякий раз оказывается точнее, чем (tiJj.i).

В заключение отметим, что разумные оценки множителей Лагранжа информативны и в далеких от ретпения точках. Так, например, компоненты вектора Xj, из (6.57), будучи коэффициентами приближенного представления в виде линейной комбинации гра-ииентов ограничений рабочего списка, позволяют судить о чувствительности целевой функции к вариациям в ограничениях.



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

Пу6,1икации, специально посвященные процедурам оценивания множителей Лагранжа, можно пересчитать по пальцам. Обычно же эти процедуры описываются в качестве блоков алгоритмов условной оптимизации. В частности, какой-то способ построения оценок множителей определен в каждой из упомянутых в замечаниях к разд. 6.3, 6.4 и 6.5 работ.

Различные оценки множителей Лагранжа, а также методы их вычисления и проверки состоятельности подробно рассмотрены в статье Гилла и Мюррея (1979b).

6.7. ЗАДАЧИ БОЛЬШОЙ РАЗМЕРНОСТИ

В дайнам разделе обсуждаются задачи вида найти min F (х)

при ограничениях Ах = Ь,

"W {}о. (6.65)

г<х<и.

Здесь А есть miXn-матрица, а с(х) - вектор дважды непрерывно дифференцируемых функций {с,(х)}, i=l, . . ., m. Будем считать, что переменных и ограничений в (6.65) <шиого» (т. е. обычные методы нз-за дефицита машинных ресурсов неприменимы), что процент нелинейных ограничений мал и что матрица А разрежена.

Описываемые ниже методы опираются на стандартную технику линейного программирования, а она предполагает задание ограничений общего вида в форме равенств (см. разд. 5.6.1). Именно поэтому в постановке (6.65) все линейные ограничения, кроме простых, представлены равенствами.

В начале разд. 5.6.2 были изложены некие общие соображения относительно задач большой размерности с линейными ограничениями. Они справедливы и для (6.65).

*6.7.1. использование подзадачи с линейными ограничениями

Существование развитого аппарата решения больших задач оптимизации при линейных ограничениях (см. разд. 5.6.2) наводит иа мысль положить в основу поиска минимума в (6.65) подзадачи именно этого сорта. В частности, можно воспользоваться каким-нибудь методом спроектированного лагранжиана типа рассмотренного в разд. 6,5.2. Чтобы проиллюстрировать данный подход, вкратце опишем один из соответствующих алгоритмов.

Пусть Xft и Xft - текущее приближение искомой точки х* и текущая огненна отвечающего ей вектора .множителей Лагранжа; индекс k у других величии означает, что они вычислены в х,,. В качестве следующего приближения Xh+i предлагается брать решение подзадачи вида

иайти min F (x) - r.lc(x) + c(xYc (х)

лей"

при ограничениях Лх = Ь,

4ft(X-X,){}-C„ (6.66)

Z<x<«.

В данном случае через с(х) обозначен вектор, составленный не-которы.\ш из разностей (с(х)-с-(х-х)),.

Целевая функция в (6.66) имеет форму модифицированной функции Лагранжа и строится с учетом только нелинейных ограничений, причем не всех, а лишь тех, которые считаются активными на /i-й итерации. В то же время в Л t и Cft включаются градиенты и значения функций всех нелинейных ограничений. Штрафной терм в (6.66) введен для улучшения работы метода при его запуске с плохой начальной точки. Когда становится ясно, что искомое решение близко, параметр штрафа р обнуляют; тем самым удается достигать квадратичной сходимости.

В рассматриваемом методе очередное приближение Xj определяется как результат серии «внутренних» итераций поиска минимума в подзадаче (6.66). Этот поиск можно вести любой из универсальных процедур решения больших задач с линейными ограничениями. Надо позаботиться только о том, чтобы в правилах останова процедуры было предус.мотрсно безусловное прерывание гю выполнении определенного числа итераций. Ведь если хорошее тибли-жение к оптимуму в (6.66) не удается получить достаточно быстро, то продолжать поиск скорее всего бессмысленно: дсшгие блуждания уведут далеко от точки Xs, а там не годятся ни оценки X,,, ни параметры линеаризованных в Хь ограничений. Эффективность метода в конкретных случаях сильно зависит от выбора величины р. Соображения, которыми надо руководствоваться при назначении р, аналогичны высказанным ранее в отношении метода модифицированных функций Лагранжа (см. разд. 6.4.2.2).

В качестве Х для (6.66) можно брать вектор оценок множителей Лагранжа из пpeдF)Iдyщeй по.азадачи, полученной на последней итерации процесса ее решения. Если эта итерация стала последней потому, что удалось удовлетворить условиям оптимальности, компоненты Х,„ отвечающие неравенствам, будут неотрицательны. Отметим, что рассматриваемый вектор Х связан со «старой» матрицей Якоби Ль 1, т. е. вычисляется не по самым свежим данным и потому



[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