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

[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.22) удовлетворит любой вектор вида р = (0, 6). В то же время допустимых дуг здесь попросту ие существует, так как начало координат-единственная точка, где Cj и Cj обращаются в нуль одновременно.

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

Начнем с необходимых усповий первого порядка. Понятно, что x* может быть оптима.пьной точкой только тогда, когда функция F стационарна в х* вдоль любой допустимой дуги, т. е. когда VF (а(е))е=11 =0. Отсюда по правилу дифференцирования спож-ной функции получим, что

g(x*)p = 0 (3.23)

при любом р, удов.петворяющем (3.22).

Пусть далее 2 (x*) -матрица, чьи столбцы формируют базис подпространства векторов, ортогональных всем строкам А (х*). Тогда из того, что равенство (3.23) справедливо при .пюбых р, подчиняющихся (3.22), следует, что

Z(xYgix-) = 0. (3.24)

Это условие аналогично условию (3.12) для задач с линейными ограничениями, но только теперь матрица Z зависит от х*. Вектор Z{x*yg{x*), как и в .пинейном случае, называют спроектированным градиентом от F в х*.

Рассуждая точно так же, как это делалось при выводе необходимых условий для задач с линейными равенствами, нетрудно показать, что равенство (3.24) эквива-пентно требованию, чтобы вектор g(x*) был линейной комбинацией строк матрицы А(х*): g(x*):=A{xfK: (3.25)

Здесь к* - некоторый -мерный вектор множителей Лагранжа.

Введем функцию Лагранжа

L(x, k) = F(x)-{->.-S{x)

(3.26)

с независимыми аргументами х и мерным X. Тогда условие (3.25) становится утверждением о стационарности (по х) этой функции в точке x* при 1=1*.

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

(<х(е))е=„>0. (3.27)

Чтобы вывести отсюда конструктивное условие оптимальности, надо найти выражение производной dF/dQ- через исходные функции задачи. При этом в соответствии с правилом дифференцирования сложных функций формула вычисления производной dFldQ будет содержать два слагаемых: одно - с матрицей Гессе функции F а второе - со второй производной д\ги da/dO, и именно это второе слагаемое надо заменить чем-то без da/d6. Здесь надо привлечь равенство (3.25) и учесть постоянство всех функций на любой допустимой дуге. В результате этих преобразований из (3.27) получается следующее необходимое условие оптимальности второго порядка: для всех р, удовлетворяющих (3.22), должно выполняться соотношение

рЧС(х«)-2 ;;с,(х«))р>о.

(3.28)

Отметим, что центральную роль в этом условии минимума для задач с нелинейными ограничениями играет матрица, которая есть не что иное, как матрица Гессе функции Лагранжа. Ее принято обозначать через W(x, к), т. е.

47 (x, Я)=С(х)- Ё ЯД.(х).

Требование соблюдения неравенства (3.28) для всех р, подчиняющихся (3.22), равносильно требованию положительной папуопреде-ленности матрицы

Z (x-f (g (х*) - klG, (х>)) Z (x*). (3.

Ее принято называть спроектированной матрицей Гессе функции Лагранжа.



Еще раз подчеркнем, что в условии оптимальности второго порядка для задачи с нелинейными ограничениями фигурирует специфическая комбинация матриц Гессе для целевой функции и функций ограничений. Таким образом, существенное значение имеет кривизна последних, и это проиллюстрировано на рис. 3j. Он относится к задаче с линейной целевой функцией, кривизна которой по определению равна нулю. Видно, что точка х удовлетворяет (3.24), но не является оптимальной именно потому, что кривизна функции ограничения имеет не тог знак.

урм F(x)

с(4 = 0

Рис. 3]. Роль кривизны ограничения в условиях оптимальности.

Итак, если ограничения в х* удовлетворяют требованию регулярности, необходимые условия оптима.пьности х* для задачи NEP будут состоять в следующем:

Необходимые условия минимума для задачи NEP К1. с (х«) = 0.

К2. Z(x«)g(x*) = 0, или, что эквивалентно, g{x) = A(x)k. КЗ. Матрица Z (хУ 47 (х*, Z (х*) положительно полуопределена.

Используя аналогичную технику доказательства, можно получить также условия, достаточные для того, чтобы точка х* была точкой сильного .покального минимума для NEP. Они формулируются следующим образом:

Достаточные условия минимума для задачи NEP L1. (x*)=0.

L2. Z(x*)g(x*) = 0, или, что эквивалентно, g(x*) = /4 (х*)Х. L3. Матрица Z (х*) W (х", I) Z (х") положительно определена.

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

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

NIP иайти min F(x)

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

Как и в случае с .чинейными неравенствами, надо выделять те из ограничений, которые обращаются в анализируемой точке х* в равенства. Их будем называть активными в х*, а остальные ограничения - неактивными. Таким образом, i-e ограничение активно в X*, если Ci(x*)0, и неактивно, если с,.(х*)>0. Возможности перемещения в окрестности точки х» определяются только активными ограничениями, а неактивные будут выполнены при .пюбых достаточно малых уклонениях от х*.

Вывод условий оптимальности для задачи NIP опирается на понятия удерживающих и неудерживающих перемещений (разд. 3.3.2.1) и на понятие дуги, допустимой относительно нелинейного ограничения (разд. 3.4.1). На этой основе строится опреде.пение допустимых удерживающих и неудерживающих дуг, которое играет центральную роль в соответствующих доказательствах.

Чтобы получить консгруктивные усповия оптима.1и>ности для задачи NIP, снова, как и в предыдущем разделе, требуется предположение о регулярности ограничений в х*. Только теперь оно будет относиться не ко всем, а лишь к активным ограничениям. Состав.тенный из их функций (-мерный вектор ниже обозначается через с{х), а матрица, строками которой являются транспонированные векторы градиентов этих функций, будет обозначаться через А (х*). В качестве условия регулярности ограничений в X* можно выставить требование пспиоты строкового ранга этой матрицьг. Здесь опять же надо отметить, что это требование существенно только для случая с нелинейными ограничениями.

В предположении, что строки А (х*) линейно независимы, можно, комбинируя докаэате.пьства из разд. 3.3.2,1 и 3.4.1, вывести следующие необходимые усчовия существования в х* локального минимума:

Необходимые условия минимума для аадачи NIP Ml, с (х*) > О, причем с (х*) = 0.

М2, Z(x*)g(x) = 0, или, что эквивалентно, е (х*) =/С (х*)Я. МЗ. V>0. i=l, ...,t.

М4. Матрица Z (хУ W {х*, ?.*)Z(x*) положительно полуопределена.



Гл. 3. условия оптимальности

Достаточные условия оптимальности, как и в случае с линейными неравенствами, представим в двух вариантах. Это снова связано с проблемой нулевых множителей Лагранжа. Первый набор условий получается если снять эту проблему, потребовав, чтобы все множители Лагранжа были положительны. Тогда достаточными условиями существования в х* сильного локального минимума в задаче NIP будут следующие соотношения:

Достаточные условия минимума для задачи NIP N1. c(x*)>0, причеж с(х*)=0.

N2. Z{xy g(x)~0, или, что эквивалентно, g(х") = А (x*Y. N3. К > О, 1 = 1.....t.

N4. Матрица Z(x*fW(x*, I) Z (х*) положительно определена. ,

Можно получить и другие, допускающие наличие нулевых множителей Лагранжа достаточные условия. В них требования к матрице Гессе должны быть усилены таким образом, чтобы была гарантия положительности кривизны F вдоль любой допустимой дуги, которая является удерживающей относительно активных ограничений с ненулевыми множителями и может быть неудерживающей по отношению к остальным активным ограничениям. Условия данного типа представлены ниже. В ннх через Z+{x*) обозначена матрица, чьи столбцы образуют базис подпространства, ортогонального векторам градиентов функций активных ограничений с положительными множителями Лагранжа.

Достаточные условия минимума для задачи NIP (с нулевыми множителями Лагранжа)

01. с(х)>0, причем с(х)=0.

02. Z {xf g (X*) = О, или, что эквивалентно g (х«) = Л (х*) к.

03. ?.;>о, 1=1, ...,t.

04. Матрица Z. (xf W (х*, Я) Z+ (х*) положительно определена. Замечания н избранная библиография к разд. 3.4

Условия оптимальности для задачи с ограничениями, рассмотренные в этой главе, часто называют усчовиями Куна - Таккера (см. Кун и Таккер (1951) и Кун (1976)). Их бо.пее полное и подробное изложение читатель найдет, например, в книгах Фиакко и Мак-Кормика (1968), Авриеля (1976) и в работе Пауэлли (1974).

Выше были представлены только такие условия оптимальное] и в нелинейных задачах, которые либо необходимы, либо достаточны. Условия же, являющиеся и необходимыми, и достаточными, в общем случае необычайно сложны - даже для задач на безусловный экстремум. Поэтому они не были включены в текст книги, тем более что их практическая проверка возможна .пишь в исключительных ситуациях. Интересное обсуждение условий такого сорта для задач без ограничений дано в книге Ге и Томаса (1968).

ГЛАВА 4

МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ

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

Джон Драйдея (1607)

В гл. 4, 5 И 6 представлена некоторая выборка из обширного семейства методов оптимизации, разработанных к настоящему времени для различных категорий задач. Изложение носит обзорный характер, причем приводятся мотивы, по которым казалось целесообразным включить б него тот или иной метод. Кроме того, обсуждаются отдельные теоретические и вычислительные особенности рассматриваемых схем.

Набор методов, описанных в этой и двух последующих главах, довольно ограничен. Дело в том, что исчерпывающий обзор занял бы слишком много места; только методов безусловной минимизации хватило бы на отдельную книгу. К тому же наряду с обзором оптимизационных схем мы хотели обсудить целый ряд сугубо практических вопросов, связанных с их эксплуатацией. Они вынесены в гл. 7 и 8, где даны советы, как формализовать нестандартные задачи, как анализировать причины отказа или неэффективной работы алгоритмов и как добиваться от оптимизационных программ математического обеспечения наи.пучших показателей. Некоторые из этих рекомендаций имеют общий характер и могут быть отнесены ко всем методам. Однако наибольшее значение они все же имеют для тех алгоригмов, к которым адресуются.

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

4.1. МЕТОДЫ ДЛЯ ФУНКЦИЙ одной ПЕРЕМЕННОЙ

4.1.1. ПОИСК НУЛЯ ФУНКЦИИ одной ПЕРЕМЕННОЙ

В разд. 3.2-1 установлено, что для существования в точке х* безусловного минимума гладкой функции f{x) необходимо наличие равенства f (х)*=0. Таким образом, задачи поиска минимума и нуля



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