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

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

гя. 3. Условия оптимальности

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

3.3.2.2. Линейное программирование. Особый класс оптимизационных задач с линейными ограничениями составляют задачи, в которых линейными являются и целевые функции. Их принято называть задачами линейного программирования или сокращенно LP-задачами. Таким образом, для LP-задачи

3.3. Оптимизация при линейных ограничениях

(3.19)

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

Еспи с-нену.певой вектор, функция (3.19) не ограничена снизу: ее значение может быть сде.пано скспь угодно бо.пьшим по моду.пю отрицательным чиспом за счет движения вдо.пь .чю-бого ненулевого х, д.пя которого сх < 0. Спедовательно, чтобы задача минимизации такой функции имела конечное решение, в ней обязате.пьно дспжны присутствовать какие-то ограничения.

Поскольку компоненты вектора с и матрицы ограничений обычно выбираются независимо, равенство с--Ак*- из необходимых усповии оптима.пьности чаще всего выполнимо только при невырожденной матрице А (она состав.пена из коэффициентов ограничений-равенств и сдерживающих неравенств). В таких случаях искомый минимум достигается в единственной точке х*, представляющей собой решение невырожденной системы линейных уравнений вида Ах*=Ь. Если же усповие с = ЛЯ* (при неотрицательности множителей неравенств) выполнится для матрицы А, строковый ранг которой меньше п, то одно и то же минимальное значение функции сх будет достигаться на це-.пом множестве точек х*. Например, в задаче, минимизации F (JC) = Зх,--Зжа при единственном ограничении х,-\-х - 1 опти-ма.пьное значение це.певой функции равно 3, а решением будет .пюбой вектор вида (Vz-Ь, 4g-\-lif.

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

задачу) так, что множители Лагранжа в Р будут частью решения D, а множители Лагранжа из D будут содержаться в решении Р.

Сейчас нас интересует спедующая прямая задача линейного программирования:

найти rain Л

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

где А есть т X «-матрица. Ниже показано, что отвечающая ей двойственная задача выглядит так:

найти maxij;

при ограничениях Аус,

Ранее мы условились связывать множители Лагранжа только с активными ограничениями, но здесь при анализе двойственности удобно приписывать множители Лагранжа и неактивным ограничениям, полагая их по определению нулевыми. Не умаляя общности, можно считать, что активными в решении х* прямой .чадачи являются первые i ограничений и их множители Лагранжа положительны. Тогда расширенный вектор у* множителей Лагранжа равен (X.», 0)", где Х*>0.

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

Пусть Д-матрица активных, а Л -матрица неактивных ограничений прямой задачи в ее решении х*. Тогда из усповий оптима.пьности этого решения имеем

с = Ж= (ЛЛ») (о*)=Л V.

Следовательно, ограничения-равенства двойственной задачи для У* выполнены. Кроме того, в силу тех же условий оптимальности !/*>0, т. е, выполнены и двойственные неравенства. Значит, у* - допустимая точка двойственной задачи.

Теперь оста.пось установить, что у* удовлетворяет усповиям оптимальности первого порядка. Для этого прежде всего отметим, что каждой положительной компоненте вектора у* (т. е. каждому элементу V) отвечает неактивное ограничение неотрицательности в двойственной задаче, а каждой нулевой - активное. Следовательно, все активные в у* двойственные ограничения образуют систему



Гл. 3. Условия рптилшльноспш

равенств вида

(f f)(o>(o)-

Учитывая полученное описание набора активных в у* ограничений и имея в виду эквивалентность задачи максимизации функции Ьу задаче минимизации -Ьу, можно утверждать, что необходимым и достаточным условием оптимальности j/ будет соблюдение векторного равенства

ЗЛ. Оптимизация при линеНиш ограничениях

при некоторых а, а, причем вектор одолжен быть неотрицательным. Здесь а состоит из множителей Лагранжа ограниченин-ра-веиств двойственной задачи, а "а-из множителей активных в У неравенств. Проверяемое соотношение расгадаетси на два равенства. Первое имеет вид Лст = -fi и выполняется при а= -X*. Чтобы удовлетворить и второму, надо взять сг-= Лх*-6. Поскольку X* удовлетворяет всем (в частности, неактивным) ограничениям прямой задачи, в даииом случае а>0. Таким образом, достаточные условия оптимальности У* выпспиены, т. е. у*-решение двойственной задачи. Прн этом х* оказывается вектором множителей Лагранжа двойственных ограничений-равенств.

3.3.2.3. Квадратичное программирование. Еще один специальный lijiacc задач с линейными ограничениями составляют задачи квадратичного программирования. В них целевыми функциями являются квадратичные формы вида

(х) = Л+-хСх,

(3.20)

где с и G суть фиксированные вектор и симметричная матрица. Градиент функции (3.20) равен Ох+с, а ее матрица Гессе равна G.

К квадратичным задачам, как и к .чинейным. применимо понятие «двойственность». Пусть исходная (прямая) задача ставится так:

найти min6x-f--i хСх

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

Тогда .дюйственной к ней задачей будет следующая:

найти max {у, w) =by-YwGw

прн ограничениях Ay=-Gw + c, У>0.

Если у* - расширенный вектор множителей Лагранжа, отвечающих решению х* прямой задачи, то пара {у*, w*), где w* =х*, будет допустимой и удовлетворит необходимым условиям оптимальности первого порядка для двойственной задачи. Доказывается это в точности по той же схеме, что и в линейном случае. Для того чтобы можно было гарантировать оптимальность {у*, w*), нужно потребовать две вещи: невырожденщжть матрицы G и положительную полуопределенность AGA.

3.3.2.4. Оптимизация при простых ограничениях на переменные.

На практике нередко встречаются задачи LIP, в которых допустимые значения вектора х определяются только простыми офаииче-ниями на его компоненты:

i.",-. 1=1. п.

(3.21)

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

Специфика рассматриваемых задач приводит к значительным упрощениям в условиях оптимальности. Формально эта специфика выражается в том, что матрица активных ограничений А всегда будет состоять только из столбцов единичной матрицы, взятых со знаками «плюс» или «минуо>. При этом активносгь ограничения означает, что соответствующая переменная принимает свое граничное значение, а потому вместо термина «активное ограничение» здесь часто употребляют термин зафиксированная переменная. Векторы, составленные из величин, относящихся к переменн1,ш, зафиксиро-Ба1Шым иа нижних границах, принято помечать нижним индексом L, а на верхних - индексом С. Так, например, через Xi и Ху обозначают векторы, набранные из тех комп01[ент х, которые зафиксированы на нижних и верхних границах соответственно. В силу специфики матрицы А множитель Лагранжа для активного ограничения на переменную X, равен gt(x*), если Xi = Z,-, и равен - g,(x*), если Xi =Uj (поскольку ограничение Xju, можно переписать как

-Х,>- Ui)-

Далее, матрицу Z можно составить из сто.пбцов единичной матрнць!, отвечающих тем переменным, которые не приняли граничных значений (их называют свободными, обозначая набранный из них вектор через Xf). Тогда спроектированный градиент Zg (х*) окажется не чем иным, как вектором, составленным из компонент g (х*), отвечающих свободным переменным, а спроектированной матрицей Гессе будет матрица, скомпонованная из соответствующих им элементов С (х*). Поэтому, обозначив вектор через gp, а матрицу через 0>д, мы можем выписать следующие достаточные усповия существования в х* сильного локального минимума функции f (х) при ограничениях (3.21);



Достаточные условия минимума при простых ограничениях Л. /<х*<и, KxpR<u. J2. gF„ = 0. J3. Й>0, g<0. J4. Gfn положительно определена.

Легче всего проверять эти условия в одномерном случае, когда требуется найти минимум функции одной переменной f на отрезке {I, и\. Например, для того чтобы этот минимум достигался в точке х*=1, достаточно соблюдение неравенства f{t)>0 (заметьте, что свободных переменных здесь нет).

3.4. ОПТИМИЗАЦИЯ ПРИ НЕЛИНЕЙНЫХ ОГРАНИЧЕНИЯХ

Ограничения, налагаемые на переменные, далеко не всегда содержат только линейные функции. Часто равенства и неравенства, определяющие допустимую область задачи, содержат нелинейности. Такими задачами мы и займемся в данном разделе. Точнее говоря, речь пойдет о задачах с ограничениями вида (i)c, (X) =0 (ограничение-равенство),

(ii) с,- (х) > о (ограничение-неравенство),

где d (х) - некоторая нелинейная функция. Понятно, что неравенства d (хХО можно не рассматривать, заменяя их эквива.аентными неравенствами - Сг (х)0.

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

3.4,1. ЗАДАЧИ С ОГРАНИЧЕНИЯМИ ТИПА НЕЛИНЕЙНЫХ РАВЕНСТВ

Анализ условий оптимальности при нелинейных ограничениях мы начнем со случая, когда все они имеют вид равенств:

NEP найти min F(x)

,6 ж"

при ограничениях с, (х) = О, i=l, t.

Вектор градиента функции с,{х) будем обозначать через а,.(х), а ее матрицу Гессе-через б,(х). Кроме того, нам потребуется матрица Якоби для набора функций ограничений {с,, (х)}, 1 = 1.....t. Так называют <хп-матрнцу Л(х), i-я строка которой равна al (х).

Для исследования допустимой точки х* задачи NEP иа оптимальность необходимо конструктивно описать не нарушающие ограничений перемещения из х*. Тогда на основе анализа пове-

дения функции F при таких перемещениях можно будет сделать какие-то выводы. Когда ограничения были линейными, допустимые перемещения описывались в терминах подпространства возможных направлений (см. разд. 3,3.1), Для нелинейных ограничений столь простое описание невозможно, так как если функция С; нелинейна, то даже при наличии равенства с,(х*) = 0 направлений р. таких, что с,(х* + ар)=0 при достаточно малых [к], вообще говоря, не существует.

Чтобы сохранить допустимость, надо двигаться из х* по до-пустимой дуге (дуга-это направленная кривая в 9i", параметризованная скалярной переменной 6). Например, в случае с двумя перемеиньгаи и единственным ограничением роль такой дуги играет линия уровня функции ограничения с, отвечающая ее нулевому значению. Впредь дугу будем обозначать через к (6), считая, что а(0) = х«; производная от а по 6 в точке х", представляющая собой касательный к дуге вектор, ниже обозначается через р.

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

с,, (а (е))е=0 = Vc,. (а (о))р = а] (х*ГрО.

Значит, если дуга допустима относительно всех ограничений задачи NEP, то касательный к ней вектор р до.пжен удовлетворять равенству

Л(х«)р = 0. (3.22)

В ситуации с .чинейными ограничениями аналогичное (3.22) равенство (3.10) полностью характеризовало допустимые перемещения: любое возможное направление должно было удовлетворять (3.10) и все направления, удовлетворяющие (3.10), были возможными. Теперь же условие (3.22) служит только необходимой характеристикой допустимых перемещений н не является достаточной: оио должно выполняться для любого вектора р, касательного к какой-нибудь допустимой дуге, но не любому удовлетворяющему (3.22) вектору р отвечает допустимая дуга, по отношению к которой ои был бы касательным.

Поясним сказанное на простом примере. Для этого рассмотрим в двумерном случае два ограничения! (х) = (х,-1)»--х?-1 и c2(x) = (.rj-(-l)»-i-.v-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