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

[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, где с(л-) - векторная функция. Через А (х) ниже обозначается матрица, чья i-я строка есть градиент от с,(х).

Мы рассмотрим два «крайних» подхода к формированию подзадач; разумеется, можно предложить и массу промежуточных. Первый состоит в том, чтобы ставить подзадачи, все ограничения которых имеют вид линейных равенств и каждый раз отражают какую-то часть исходных ограничений. Предыдущий материал разд. 6.5 относится именно к этому гюдходу. С другой стороны, можно ставить гюдзадачи с линейными неравенствами, всегда учитывая все исходные ограничения.

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

В методах минимизации при линейных ограничениях, изложенных в гл. 5, основным признаком, по которому ограничения отбираются в рабочий список, служит обращение их в равенства. Для методов спроектированного лагранжиана этот признак не годится: в них нелинейные ограничения могут стать равенствами лишь в пределе. Поэтому здесь прн составлении рабочего списка приходится пользоваться более сложными критериями. Типичная стратегия прогнозирования активного набора исходит нз стремления добиться, чтобы выделяемые ограничения удовлетворяли в текущей точке Xft тем требованиям, которым активные в х* ограничения должны удовлетворять в окрестности х*. Можно учитывать также свойства функции выигрыша ф„; например, если в качестве Ф.„ используется квадратичная штрафная функция (6.1), то активные в х* ограничения разумно будет искать среди нарушенных (см. разд. 6.2.1.1). Иногда для очередного прогноза активного набора удзется нсггользовать множители Лагранжа из предыдущей подзадачи. Наконец, применяют «двухступенчатые» правила, когда сначала выбирается некий пробный список, а затем по множителям Лагранжа соответствующей подзадачи определяется окончательный. Здесь происходит нечто подобное «выводу ограничении из рабочего списка» в методах минимизации при линейных неравенствах.

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

выигрыша (см. разд. 6.5.3.3) всегда должны быть отражены все ограничения, а ие только те, которые гюпали в рабочий список.

*6.5.5.2. Подзадачи с ограничениями-неравенствами. На основе любой из упомянутых выше в разд. 6.5 постановок естественно определяется соответствующая подзадача расчега р с ограничениями вида

AkP>dk, (6.52)

где через А обозначена матрица А (х). В данном случае можно говорить о прогнозировании списка активных в х* ограничений активным набором решения подзадачи.

При некоторых предположениях доказано, что подзадача метода спроектированного лагранжиана, построенная в близкой к х* ючке Xft и содержащая в качестве ограничений систему неравенств (6.52) с -С/,, будет иметь тот же набор активных в решении ограничений, что и исходная задача. Это гюзволяет распространить на методы, использующие условия (6.52), сформулированные ранее теоремы сходимости, т. е. обосновать их. Однако любая разумная стратегия прогнозирования активного набора в мало отличающейся or X» точке Хй тоже даст правильный результат. Поэтому сам по себе указанный факт не является основанием, чтобы предпочитать методы с условиями (6.52). Надо еще выяснить, могут ли последние правильно определять активный набор там, где иные стратегии его прогнозирования ошибаются (см. комментарии в разд. 6.6.3).

Рассмотренная в разд. 6.5.4 проблема дефектности гюдзадач с равенствами сохраняется и в подзадачах с неравенствами, причем пути ее разрешения усложняются. В частности, для определения совместности ограничений (6.52) потребуется итерационная процедура, и не ясно, как лучше всего модифицировать их, когда они несовместны.

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

Идею линеаризации ограничений эксплуатируют многие алгоритмы поиска условного оптимума (в том числе и описанные в рззд. 6.3 методы типа приведенных градиентов). Одно из ее первых воплощений - метод Гриффита и Стюарта (1961), в котором на каждом шаге решается подзадача LP, формулируемая на основе линейной аппроксимации исходных ограничений и целевой функции. Подобные методы называют методами последовательного линейного программирования. Их общий дефект состоит в том, что решение подзадачи LP всегда является вершиной линеаризованного допустимого множества, в то время как искомая точгча х* аналогичной особенностью скорее всего обладать не будет. Чтобы «сгладить» это несоответствие, в подзадачу приходится вводить дополнительные условия (например, двусторонние ограничения на переменные).



По принципу последовательного решения подзадач с линейными ограничениями, аппроксимирующими исходные, работакп- также методы отсекающих плоскостей (см., например, Келлн {1%0), Топ-кис и Вайнот (1967)), относящиеся к арсеналу выпуклого программировании (очень коротко о задачах выпуклого программирования будет сказано в разд. 6.8.2.1). Надо заметить, что в настоящее время их практически не используют: они медленно сходятся и к тому же страдают численной неустойчивостью из-за ухудшения от ите-рании к итерации обусловленности линейных ограничений подзадачи.

Методы, основанные на подзадачах типа (6.33) с целевыми функциями общего вида, предлагались Розеном и Кройзером (1972) и Робинсоном (1972). Доказательства их квадратичной сходимости (при определенных ycjmBHHX) приведены в статьях Робинсона (1972, 1974). Розен (1978) предложил также двухфазную схему, в которой сначала методом квадратичных штрафных функций отыскивается разумное приближение искомой точки х*, а затем происходит переключение на метод спроектированного лагранжиана с подзадачей (6.37). В работе Беста и др. (1981) описана схема такого же типа, но допускающая возврат к первой фазе, если вторая не дает ожидаемой скорости сходимости. Муртаф и Сондерс (1980) разработали алгоритм, в котором целевая функция подзадачи подобна модифицированной функции Лагранжа (6.24); о нем еще будет говориться в разд. 6.7.

Методы спроектированного лагранжиана с последовательной минимизацией при ограничениях-равенствах, выбираемых на основе стратегии прогнозирования активного набора, читатель найдет в статьях Ван-дер-Хука (1979), Беста и др. (1981).

Насколько нам известно, идея применения квадратичной подзадачи для поиска минимума при нелинейных ограничениях впервые была высказана Уилсоном (1963) в его неопубликованной диссертации. Впоследствии метод Уилсона был описан и проинтерпретирован Билом (1967b). В этом методе на каждой итерации решается подзадача с линейными ограничениями-неравенствами вида

АкР-с. (6.53)

Ее квадратичная целевая функция представляет собой аппроксимацию функции Лагранжа и строится по точным матрицам Гессе для F и {Cj}, причем множители Лагранжа из предыдущей подзадачи используются в качестве оценок компонент X* для последующей. Очередное приближение определяется как сумма х+р, где р, есть решение подзадачи k-й итерации. Таким образом, одномерный поиск в методе Уилсона отсутствует.

Подобная (6.50) подзадача с ограничениями-неравенствами, ориентированная на предельные свойства траектории точек минимумов квадратичных штрафных функций, была построена Мюрреем (1969а, Ь). Он предложил для нее несколько вариантов определения

Hi,, включая квазиньютоновскую аппроксимацию, и несколько способов вьиисления оценок множителей. Выдвигалась также идея «частично» решать подзадачу, т. е. выполнять несколько (возможно, всего лишь о;шу) итераций процедуры ее решения; при этом линеаризованные неравенства с отрицательными оценками множителей должны «исключаться» из рабочего списка. Решение подзадачи в методе Мюррея используется в качестве направления поиска. Шаг вдмь него выбирается из соображений минимизации квадратичной штрафной функции (которая служит «функцией выигрыша»).

Битс (1972, 1974, 1975) предложил модификацию метода Мюррея, основанную на подзадачах вида (6.50) с ограничениями-равенствами. Он тоже описал некоторые специальные способы оценивания множителей.

Среди методов спроектированного лагранжиана с квадратичной подзадачей есть немало использующих квазиньютоновскую технику. Так, например, Гарсиа Паломарес и Маигасарьян (1976) вывели метод такого сорта, применив эту технику для решения системы нелинейных уравнений (6.48). Еще один пример - метод Хана (1976, 1977а, Ь). Возвращаясь к идее расчета направления поиска решением квадратичной подзадачи с неравенствами типа (6.53), он предложил матрицу ее целевой функции строить как квазиньютоновское приближение матрицы Гессе функции Лагранжа и дал соответствующие формулы пересчета. При этом делалось предпоггажение, что сама матрица Гессе функции Лагранжа будет всюду положительно определенной. В методе Хана множители Лагранжа предьщущей подзадачи служат оценками Х* для последующей. При некоторых условиях доказана его сверхлинейная сходимость. В качестве функции выигрыша в процедуре одномерного поиска Хан использовал негладкую «точную» штрафную функцию Р., из (6.8).

Процедура с последовательным решением квадратичных подзадач с неравенствами, аналогичная методу Хана, но обеспечивающая сохранение положительной определенности квазиньютоновской аппроксимации матрицы Гессе функции Лагранжа и тогда, когда эта матрица не является знакоопределенной, описана Пауэллом (1977b, 1978). При некоторых предпшюжениях она тоже сходится сперхлинейно.

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



их работоспособность. О них можно прочесть, например, в работах Пауэлла (1977Ь), Мюррея и Райт (1978) и Шиттковского (1980).

Некоторые вопросы, связанные с выбором в качестве функции выигрыша абсолютной штрафной функции Рд, обсуждаются в работе Чемберлеиа и др. (1980). Определенные трудности, к которым может привести такой выбор, описаны Маратосом (1978) и Чембер-леном (1979). Сопоставление достоинств разных фopмyJШpoвoк квадратичной подзадачи для метода спроектированного лагранжиана проведено Мюрреем и Райт (1980).

Метод «допустимой точки» с подзадачей (6.51) изложен в диссертации Райт (1976) и работе Мюррея и Райт (1978). Реализация процедур, конструируемых на основе (6.50), (6.51) для задач со смесью линейных и нелинейных ограничений, oi5cyждaeтcя в опубликованном докладе Гилла и др. (1980).

KsK уже было сказано в замечаниях к разд. 6.2, многие методы минимизации недифференцируемой штрафной функции организованы тюдобно методам спроектированного лагранжиана с квадратичной подзадачей, и направление поиска определяется в них в виде (6.42). В частности, таковы методы Колемана (1979) и Колемана и Конна (1980b, с).

Идея расщепления направления поиска на две ортогональные составляющие, как в (6.42), эксплуатируется многими ajrropHTMaMH минимизации при нелинейных ограничениях, например методами Барда и Гринтптадта (1969), Леибергера (1974), Мэйна и Полака (1976) и Хита (1978). Она реализуется и в методах типа приведенных градиентов, обсуждавшихся в разд. 6.3.

Подход к решетшю задач с нелинейными ограничениям, основанный на применении метода Ньютона к последовательности систем нелинейных уравнений (см. (6.48)), обсуждается в статьях Тапиа (1974а, Ь).

В качестве обзорных работ по методам спроектированного лагранжиана можно порекомендовать статьи Флетчера (1974, 1977) и Мюррея (1976).

6.6. ОЦЕНКИ МНОЖИТЕЛЕЙ ЛАГРАНЖА

Эффективность методов из разд. 6.3, 6.4 и 6.5 в значительной степени определяется качеством фигурирующих в них оценок множителей Лагранжа. Напомним, что в задачах с линейными ограничениями оценки множителей, как правило, используются, только если среди этих ограничении есть неравенства, и привлекаются, когда нужно выяснить, стоит ли сокращать рабочий список и каким образом это можно сделать; целевая функция подзадачи их не включает, и на асимптотической скорости сходимости поиска они не сказьшаются. Значительно большая роль отводится оценкам множителей в методах минимизации прн нелинейных ограничениях с применением функций Лагранжа (типа рассмотренных в разд. 6.3,

6.4 и 6.5). Здесь они нужны, даже если все ограничения являются равенствами, входят в определение целевой функции подзадачи и, как уже было отмечено, сильно влияют на скорость сходимости.

Вектор множителей Лагранжа образуется коэффициентами разложения g(x*) по градиентам вектор-функции с активных в х* ограничений:

g (ж) = А (х«)1 I. (6.54)

Здесь А - составленная из этих градиентов матрица. По определению

с(х) = 0, (6.55)

и ясно, что X* будет решением, а Я.* - отвечающим ему вектором множителей Лагранжа в задаче

найти mill F (х)

(6.56)

при ограничениях с (х) = 0. (Она совпадает с исходной, еслн в той ист неравенств.) Поскольку при нелинейных F, с левая часть и матрица в (6.54) суть функции от X* (что и отражено в обозначениих), не зная х*, найти вектор К* нельзя. В произвольной точке х можно построить лишь его оценку К-

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

I 6.6.1. оценки первого порядка

Здесь и в ра.зд. 6.6.2 через су, и А,, будем обозначать вычисленный в Xj вектор функций ограничений, которые предполагаются активными в X, и матрицу их градиентов; имеется в виду, что при Xft, близких к X*, прогноз активных в х" ограничений верен.

Исходя нз равенства (6.54) в качестве оценки в Хд для \ можно . предложить решение Я.. задачи о наименьших квадратах вида f найти mmfAll-gli. (6,57)

(Оиа аналогична (5.27), ио сейчас Лзависит от Xj.) Такая оценка всегда определена и состоятельна в смысле (5.26); правда, решение (6.57) будет единственным, только если строки Л линейно независимы. (Численно усгшчивые методы расчета описаны в разд. 2.2.5.3.)



[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