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

[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]

Итак, для выбора очередного приближения предлагается решать следующую подзадачу:

найти min Ф,,

при ограничениях Лх = - Cj + А,„.

(6.33)

Не исключено, что ее ограничения окажутся несовместимыми, т. е. она будет дефектной. Однако это возможно только тогда, когда Л имеет неполный ранг или когда размерность с превосходит п. Заметим также, что решение подзадачи (6.33) зависит от Xt, так как по х определяются параметры ее ограничений.

Считая, что 1юдзадача (6.33) нормальна, обозначим ее решение и отвечающий ему вектор множите.пей Лагранжа через xJ и \\ соответственно. Они будут подчиняться условиям оптимальности первого порядка:

Лл = -сЧ-Лл (6.34а)

РФ;с (хй = AlXl. (6.34b)

Кроме того, гарантирована положительная полуопределенность матрицы ZJV®;c(x3Zi (через Z, как обычно, обозначена матрица, столбцами которой служат векторы базиса подпространства, ортогонального строкам Л).

Функцию Фц; для- подзадачи (6.33) можно строить по-разному. В двух последующих разделах будут рассмотрены два типа Фьс. порождающие два класса методов спроектированного лагранжиана.

6.5.2. ПОДЗАДАЧА С ЦЕЛЕВОЙ ФУНКЦИЕЙ ОБЩЕГО ВИДА

6.5.2.1. Формулировка целевой функции. Казалось бы, в качестве Ф£,о МОЖНО взять текущую аппроксимацию функции Лагранжа L(x, X*):

f(x)-Хс(х). (6,35)

Если х*=х* и Xj=X*, ее минимум достигается в х*, так что одно из требований к Фо в данном случае выполнено. Однако, поскольку градиент (6.35) с ХХ* в х* обращается в нуль, вектор XJ тоже будет равен нулю (а не X*), т. е. (6.35) в качестве Фс не подходит.

Очень близкая к (6.35) функция, удовлетворяющая всем предъявляемым к ф£.с требованиям, выглядит гак:

Р(х)-Цс(х) + Х1,Ах. (6.36)

Поскольку на допустимом множестве задачи (6.33) она отличается от (6.35) ие зависящим от х слагаемым, при переходе

В (6.33) от (6.35) к (6.36) решение xJ сохранится. Как видно иэ условия (6.34Ь), вектор XJ при этом получит приращение, равное Xj. Соответственно, задавая Фи: в виде (6.36) при х, = х*, Xj -X*, имеем xj"=x*, Xt = X*.

6.5.2.2. Упрощенная модельная схема. Чтобы сделать изложение более предметным, сформулируем упрощенный алгоритм метода спроектированного лагранжиана, который, однако, не следует воспринимать как некую универсальную схему. Ниже будут предложены вариации стратегии поиска, которые приводят к более надежным алгоритмам.

Задав начальную точку х„ и начальный вектор Х„ и сделав присвоение О, точку х* можно попытаться найти следующим

Алгоритм SP {Упрощенная схема спроектированного лагранжиана)

SPI. [Проверка соблюдения правил останова.] Если Xf, удовлетворяет условиям оптимальности, вычисления прекращаются и Хь берется в качестве решения.

SP2. [Решение подзадачи с линейными ограничениями.] Начиная с Xs в качестве исходного приближения, запускается процедура решения подзадачи

найти minf(x) - ?.Гс (х)-1-ХЛ.х

«ея" (6.37)

при ограничениях Лх = - с-ЬбХ;,

защищенная на случай неограниченности. SP3. [Пересчет оценок множителей.] Лучшая из найденных на предыдущем шаге точек берется в качестве х+ц Х*л "о-.чагается равным вектору множителей .Пагранжа пол.задачи (6.37) (здесь считается, что (6.37) - нормальная подзадача), счетчик итераций переводится на единицу, т.е. ft.,- и осуществляется возврат к шагу SP1.

Решение подзадачи. Д.пя поиска оптимума в подзадаче (6.37) можно использовать какой-нибудь из универсальных методов минимизации при линейных ограничениях-равенствах типа описанных в разд. 5.1. Конкретный выбор будет определяться доступностью информации о производных функций (восшожностью и трудоемкостью вычисления аналитических значений производных первого и второго порядков) и размерностью задачи.

В сравнении с методом модифицированных функций Лагранжа, описанным ранее, алгоритм SP может показаться переусложненным - ведь г технической точки зрения подзадача (6.37) сложнее, чем (6.25). Но, во-первых, введение условий-равенств понижает размерность пространства минимизации, и это - положительный



Эффект, а, во-вторых, если среди исходных ограничений есть линейные и они будут обрабатываться приемами гл. 5, то никакого дополнительного усложнения конструкции всего алгоритма при переходе от (6.25) к (6.37) не понадобится. В последнем случае подзадачи класса (6.37) возникают независимо от способа учета нелинейных Ограничений.

Локальная сходимость. В предположении, что иско.мая точка jc* удовлетворяет достаточным условиям оптимальности из разд. 3.4, можно доказать, что для любого мало отличающегося от {х, V) начального приближения (хо, XJ генерируемая алгоритмом SP последовательность {(д:, Х)) квадратично сойдется к (х*, X*). При

этом, если нормы -и IXj-Xll есть величины порядка Е, то аналогичные нормы с Xj+j и Xj+j будут пропорциональны е. Таким образом, применение в (6.37) оценок множителей первого порядка не снижает скорости сходимости до линейной (как в методах модифицированных функций Лагранжа, обсуждавшихся в разд. 6.4.2.2).

На рнс. 61 изображены три первых приближения, полученные алгоритмом SP для задачи нз примера 6.2 при х„ = (-1.5, -1.6) и Х„ = 0. Каждое из них найдено решением соответствующей подзадачи (6.37), т. е. является результатом нескольких «внутренних» итераций. Последние на рисунке не показаны. Значения норм -x*jf,

ft=l.....4, таковы: 2.7x10-". 3.20x10"=, 3.57x10-», 4.50х

X 10-. Уже с первых шагов отчетливо проявляется квадратичная сходимость.

*6.5.2.3. Усовершенствования модельной схемы. Несмотря на великаченные свойства локальной сходимости алгоритма SP из разд. 6.5.2.2, рекомендовать его в качестве полноценного средства решения задач иа условный минимум нельзя, так как он недостаточно надежен. Когда Хо и Хд значительно отличанл-ся от х* н X*, целесообразность применения подзадач (6.37) сомнительна. Вывод (6.37) опирался на условия оптимальности (6.22) и (6.30), а оии выполняются только в X*, X*. Таким образом, разрешимость под-


Рис. 61. Три первые точки, выданные методом спроектированного лагранжиана для задачи нз примера С. 2; каждая есть результат решения подзадачи с .тинейным ограничением.

задачи (6.37) гарантирована лишь в малой окрестности этой нары. При неточных xj, Xj (6.37) может ие иметь решения илн иметь ре-иаение, расстояние от которого до х* больше, чем от х. Таким образом, запуск алгоритма SP в отсутствие хорошего начального приближения Хо, Хщ связан с большим риском аварийного останова илн расходимости.

Доработку алгоритма SP с целью обеспечить сходимость в более широком диапазоне значений х„, Х„ можно осуществлять но-раз-иому. Наиболее распространенный подход заключается в том. чтобы дополнять его специальными средствами отыскания точки, которая подойдет ему в качестве начального нриближения.

Для поиска «подходящего» нриближения можно воспользоваться квадратичной штрафной функцией (см. разд. 6.2.1.1) с относительно небольшим параметром штрафа. Есть надежда, что при разумном р точка ее минимума х* (р) будет неплохой оценкой х*, а хорошую начальную оценку для X* можно будет вычислить либо по формуле (6.4), либо каким-нибудь из способов, описываемых в разд. 6.6. Другой прием - решать на начальных итерациях подзадачи (6.33) с модифицированной функцией Лаграижа (см. разд. 6.4.1) в качестве Фсс\ тогда переключение на алгоритм SP сведется к обнулению параметра штрафа. (Схема такого сорта для задач большой размерности рассмотрена в разд. 6.7.1.)

В обоих случаях важно выбрать «хорошее» значение р. Слишксм малые р не позволят получить приемлемого приближения, а слишком большие порождают обычную проблему плохой обусловленности. Еще один нетривиальный вопрос: когда переключаться с модифицированной функции Лагранжа на функцию (6.36)? Должны быть приняты какие-то меры, страхующие от преждевременного запуска алгоритма.

6.5.3. КВАДРАТИЧНАЯ ПОДЗАДАЧА

6.5.3.1. Обоснование. Подход, изложенный в разд. 6.5.2, обычно критикуют за то, что усилия, затрачиваемые иа поиск решения сложной подзадачи (6.37), далеко не всегда окупаются качеством нового приближения x+t. Причины ясны - если х плохо приближает X*, то ограничения (6.37) плохо описывают допустимую окрестность оптимума, а прн Х, далеком от X», целевая функция (6.37) мало похожа на функцию .Пагранжа в решении.

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



Ниже рассмотрен класс методов, в которых Фиг- квадратичная функция, т. е. методов, для которых (6.33) - задача квадратичного программирования. Решения последних принято выражать в терминах шага из в x+i- Чтобы упростить изложение, предположим, что правильный список активных ограничений известен (обсуждение реальных способов учета неравенств откладывается до разд. 6.5.5). В общем предлагаемая техника расчета очередного приближения применима всегда, когда активный набор можно хорошо спрогнозировать. Она во многом напоминает описанные в в гл. 5 приемы решения задач с линейными ограничениями.

Общий вид подзадачи для А-й итерации теперь будет таким:

найти min dlp-\-\pH,jj при ограничениях С0 = Ь,,.

(6.38а) (6.38Ь)

Методы с подзадачами этого сорта иногда называют методами поспе-довательного квадратичного программирования.

Предполагая, что решение (6.38) существует, обозначим его через Pft. С ним связан вектор множителей Лагранжа гд, удовлетворяющий равенству

HkPk+dkClri. (6.39)

Конкретную формулировку квадратичной подзадачи для точки Xk из малой окрестности х* можно получить, опираясь на те же соображения, которые npHnejm к (6.37). В частности, линейная аппроксимация активных ограничений по тейлоровским разложениям нх функций в окрестности даст набор равенств вида

л,р=-г,. (6.40)

Здесь через обозначен вектор значений в Xj функций активных ограничений, а -матрица их градиентов.

Далее, функция (6.38а) интерпретируется как квадратичная аппроксимация функции Лагранжа. Соответственно будет иметь смысл приближения матрицы Гессе последней. Логично предположить, что при этом в роли в (6.38а) выступит градиент функции Лагранжа gj-АХ, где Х-текущая оценка X*, Однако удобнее взять равным -градиенту F в х„. Решение подзадачи в обоих случаях одно и то же (так как иа множестве р. заданном равенствадш (6.40), функции (6.38а) cd,, = gt - - ЛХд и di = gt отличаются друг от друга нз величину, не зависящую от р), но значения вектора тц (6.39) окажутся разными, прпчем отвечающий второму способу задания d, может служить оценкой вектора X* для исходной задачи.

6.5.3.2. Упрощенная модельная схема. Чтобы иметь основу для последующего изJЮжeния, опишем некий упрощенный алгоритм

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

Задав исходное приближение х„ и начальный вектор множи-те.тей X, и сделав присвоение А--О, поиск х* можно организовать по следующей схеме.

Алгоритм SQ. (Упрошенная схема спроектированного лагранжиана с квадратичной подзадачей)

SQI. [Проверка соблюдения правил останова.] Если х удовлетворяет условиям оптимальности, вычисления прекращаются и Xj берется в качестве решения.

SQ2. (Решение квадратичной подзадачи.] Определяется вектор pj, оптимальный для квадратичной задачи

найти min glp-t-pHi,p

(6.41)

прн ограничениях Лцр = с (Wj зависит от х„ и Х). SQ3. [Пересчет оценки решения.] Выполняется присвоение x,,+l<- *-Xk + Pk< вычисляется Х,,.,, счетчик итераций переводится на единицу, т. е. k-k-\-\, и осуществляется возврат к шагу SQ1.

Решение подзадачи. Оптимальный в подзадаче (6.41) вектор р поддается прямо,му расчету и удобно выражается через матрицы

и Z, первая из которых составлена из векторов базиса ранг-пространства А1, а вторая - нз векторов базиса его ортогонального дополнения. (Методы построения этих матриц обсуждались в разд. 5.13.) Вычисляя р в виде

Рк = УкРг + 2кРх. (6.42)

Ру находят из ограничений (6.41), так как подстановка в них правой части (6.42) дает

Ai,Pi, = AuYkPy = ~S„. (6.43)

Если задача (6.41) разрешима, уравнения (6.43) будут совместными. Обозначим через г ранг А,,; тогда произведение ЛКц должно включать невырождигную /-хг-подчатрнцу и ру однозначно определится любыми г линейно независимыми уравнениями из (6.43). Что же касается вектора р, из второго слагаемого в правой части (6.42), то он должен доставлять безусловный минимум целевой функции (6.41) на соответствующем подпространстве и является решением ньютоновской системы уравнений

2.I.H,Pz = -Zl[g, + HYPy). (6,44)



[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.0015