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

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

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

D2. Матрица G (х«) положительно определена.

Из того, что в некоторой точке х выполнено условие D1, следует возможность разложения (3.5). Если к тому же ма-фица 0(х*) положительно определена, можно (опираясь на непрерывность функции G(x)) утверждать, что матрица в правой части (3.5) тоже будет положительно определенной, если только точка x*-i-tf)p попадет в некую окрестность х*. Но она наверняка попадет туда прн любом р и достаточно малом по модулю е. Поэтому для любого р при малых ненулевых t справедливо неравенство pG (х*+ебр)р>0. С учетом (3.5) последнее означает, что F (х*) меньше, чем значение F в любой несовпадающей с х* точке из некоторой окрестности x*, т. е. X*- точка сильного локального минимума.

3.2.3. СВОЙСТВА КВАДРАТИЧНЫХ ФУНКЦИЙ

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

Пусть Ф (.т) - квадратичная функция вида

0(x) = cx + -xGx. (3.6)

где с и О-фиксированные вектор и симметричная матрица. Тогда значения Ф(л:) и Ф{х+ар) при произвольных векторах х, р и любом числе а связаны между собой так:

Ф {X -Н ар) = Ф (х) + хрг (Gx -)- с) -Н i apTGp.

(3.7)

В соответствии с общим определением точку х* назовем стационарной точкой функции Ф, если Ф(х*) = Ох*--с = 0. Таким образом, любая стационарная точка х* является решением системы линейных уравнений вида

Gx = c. (3.8)

Несовместность системы (3.8), т. е. невозможность представить вектор с линейной комбинацией столбцов О, означает, что функция Ф не имеет стационарных точек. В дашюм случае она не ограничена ни сверху, нн снизу. Еслн же система (3.8) совместна, то по крайней мере одна стационарная точка найдется, причем она 63дет единственной, если матрица G невырожденна.

Если x*- стационарная точка Ф, из (3.7) и (3.8) следует, что

Ф(хЧ-ар) = Ф(х*)--4-«0р, (3-9)

т. е. поведение Ф в окрестности х* зависит только от матрицы G. Обозначим через и ее /-е собственное значение и отвечающий ему собственный вектор. Тогда Gu,=XjUj (причем в силу симметричности G векторы {и,}, /=1...../!, всегда можно подобрать так,

чтобы они бЬЕЛн ортонормальными; см. разд. 2.2.3.4), и, положив в (3.9) вектор р равным Uj, получим

Ф(х*--аи,) = Ф(х»)

Таким образом, характер изменения Ф при движении из х* вдоль направления Uj полностью определяется знаком Еслн Xj больше нуля, с ростом а значение Ф будет увеличиваться. Если Kj меньше нуля, то с увеличением а значеннеФ будет5бывать. Наконец, если равно нулю, при движении из х* вдоль uj функция Ф будет постоянной; более того, в этом случае из (3.7) видно, что Ф ведет себя как линейная функция на любой прямой, параллельной вектору Uj.

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

На рис. 3/ изображены линии уровня трех квадратичных функций с тремя разными комбинациями знаков собственных чисел G:

(i) два положительных собственных числа

=(з г) ""-з.!

(ii) одно положительное собственное число н одно нулевое

(iii) одно положительное собственное число и одно отрицатель-



Локальнее сходство лювой гладкой функции F с квалоятич

ска"за~в\«нГТ™-"Р"™= cXrHHrriLalrT ™-«

. г.. 1инии уровня: (1) положительно определенной квадратичной функции; (ii) положительно юлуопределеннон квадратичной функции; (iJi) знаконеопре-деленной квадратичной функции.

окажется близким к нулю, то можно ожидать, что при движении из X* вдоль соответствтощего собственного вектора функция F будет почти постоянной.

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

В большинстве прикладных оптимизационных постановок приемлемыми являются не все мыслимые значения переменных. Соответственно приходится вводить какие-то ограничения. В том числе нередко исполь;*уются ограничения в виде требований, чтобы некоторые линейные ф1/нкции переменных были равны нулю, неотрицательны или неположительны. При эюм линейной мы называем функцию вида 1{х)ах~, где - некоторая вектор-строка, а Р - число. Градиент от 1(х) постоянен и равен а.

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

(i) ал-р=0 (ограничение-равенство);

(ii) ал:-р>0 (офаничение-неравенство).

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

Понятно, что ограничение ах-РО третьего типа всегда можно заменить эквивалентным неравенством -ax--P>0. В соответствии с общепринятой формой записи линейные ограничения (i) и (ii) в дальнейшем будут фигурировать в виде соотношений ax = p и axfi.

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

(iii) л:,. = р (X. фиксируется на Р);

(iv) х,.>р (Р есть верхняя граница для х,);

(v) х,-Р (Р есть нижняя граница для х,.).

Условия (iv) и (v) принято иазьсвать простыми ограничениями на переменную х,.

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

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

LEP найти minf (х)

хеШ"

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

Здесь А есть тх/г-матрица, а b является т-мерным вектором. Коэффициентами i-ro ограничения являются компоненты i-й строки матрицы Л. Впредь эту строку будем обозначать через aJ:

аТх = QfiXi -f ... -f Q,-„x„ = Ь;.

В соответствии с определениями разд. 3.1 допустимая точка х* является точкой локального минимума задачи LEP, если F (х*)

(х) иа множестве всех допустимых х из некоторой окрестности X*. Чтобы вывести отсюда условия оптимальности л:*, необходимо прежде всего найти удобные средства описания подобных множеств.

Когда ограничения задачи LEP несовместны, то допустимых точек не существует, и тут говорить не о чем. Поэтому будем предполагать, что вектор b принадлежит области значений пре-образоваиия А, т. е. система уравнений в LEP разрешима. В данном случае есть откуда выбирать х*, причем если t строк матрицы А линейно независимы, то i степеней свободы при этом выборе будут заблокированы. Так, в двумерной задаче с одним ограничением х, + Xj = О решение выбирается среди точек прямой, изображенной на рис. 3g штриховой линией.

Следует подчеркнуть, что важен ранг системы ограничений, а не нх число. Например, если к ограничению Xi4-X2=0 добавить ограничение 2xi+2x,=0 (линейно зависимое от первого), то ранг сох-



ранится, н допустимое множество при этом никак не изменится Все будет выглядеть совсем иначе, если добавить равенство х,~х = 1 (выделяемое им множество точек изображено на рис. 3g точечной линией). В данном случае ранг системы ограничений увеличится на единицу, и допустимое множество выродится в точку.

Рис. 3g. Ограничения Xi--x-O и -х~1.

Чтобы получить для задачи LEP простое описание всех возможных перемещений из допустимой точки, надо воспользоваться самыми элементарными свойствами линейных подпространств. Рассмотрим вектор х-х, соединяющий две допустимые точки X V X. Так как Ах = Ь и Ах-=Ь, этот вектор будет удовлетворять равенству А (х-х)=0. Поскольку от х н х ничего, кроме допустимости, не требовалось, тем самым установлено, что вектор перемещения р из одной произвольной допустимой точки в другую всегда ортогонален всем строкам матрицы А, т. е.

Йр = 0. (3.10)

Такие векторы р называются возможными направлениями относительно ограничений-равенств задачи LEP и образ5ют линейное подпространство (см. разд. 2.2.2.4). Любой шаг а из любой допустимой точки X вдоль любого из возможных направлений р не нарушит ни одного иэ ограничений, так как Л(х-Ьар) = «=Лх=Ь. Равенство (3.10) полностью характеризует возможные направления-даже бесконечно малый шаг вдоль вектора р, для

которого ЛрО, выведет за пределы допустимого множества. На рис. 3g стрелками указаны возможные направления для ограничения x+x - Q.

Вь[6ерем в подпространстве векторов, удовлетворяющих равенству (3.10), какой-нибудь базис (см. разд. 2.2.2.4), и пусть Z-матрица, столбцами которой являются векторы этого базиса. Тогда AZ = 0, и все возможные направления будут линейными комбинациями столбцов Z. Таким образом, простое описание множества допустимых перемещений получено: это шаги вдоль всевозможных направлений вида p = Zp2, где р-некоторый вектор соответствующей размерности.

Для вывода условий оптимальности допустимой точки х* воспользуемся тейлоровским разложением функции F в окрестности X* вдоль возможного направления р (pZp)

F (х« + eZpz) = F (х«) -1- EpJZ-g(x) -1- eJZG (х« -- евр) Zp. (3.11)

Здесь о удовлетворяет неравенствам 06 1, а е-число произвольного Знака. Рассуждая так же, как и в разд. 3.2.2, на основании (3.11) легко показать, что, когда величина pzg(x*) не равна нулю, каждая окрестность х* будет содержать допустимые точки с меньшими, чем F (х*), значениями функции F. Значит, необходимым условием существования в х* локального минимума LEP является равенство нулю произведения PzZg(x*) при любом рг, что возможно лишь в том случае, если

Z-g(x*) = 0. (3.12)

Вектор Zg(x*) принято называть спроектированным градиентом от F в точке х*. Любую точку, в которой спроектированный градиент обращается в нуль, называют условной стационарной.

Опираясь иа равенство (3.12), можно показать, что градиент gf(x*) должен быть линейной комбинацией строк матрицы А, т. е.

е(хУ

YaiK-

(3.13)

для некоторого вектора X*, именуемого вектором множителей Лагранжа. Множители Лагранжа определяются из (3.13) одно-внанно moAHiO тогда, когда строки А линейно независимы.

Вывод (3.13) из (3.12) несложен. В самом деле, известно, что любой вектор представим в виде линейной комбинации строк А и столбцов Z (см. разд. 2.2.2.4). В частности, при некоторых Х* и g-y имеем g(x*) = A4.*+Zg-y. Умножив это равенство на Z, прн соблюдении (3.12) получим ZZgO, а поскольку матрица Z"Z по определению невырождена, отсюда следует, что = 0, т. е. g{x*) = An*.



[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