Opt_book_1

где m < n. Относительно функции f(x) и вектор-функции g(x) считаем, что они непрерывно дифференцируемы. Считаем также, что в решении этой задачи точке x¤ выполняются необходимые условия Каруша-Куна-Таккера для классической функции Лагранжа. Обозначим d = n ¡ m.

Разобьем вектор x на две компоненты y 2 Rm и z 2 Rd. Для простоты считаем, что вектор y состоит из первых m компонент вектора x, а вектор z из последующих d компонент. Тогда x = [y; z], f(x) = f(x; y) и g(x) = g(x; y).

Возьмем некоторую точку x¤ = [y¤; z¤]. Если матрица Якоби gy(y¤; z¤) неособая, то по теореме о неявной функции можно указать некоторую окрестность ¢(z¤) точки z¤, в которой существует

причем y(z¤) = y¤. Поэтому, если точка x¤ является решением задачи (3.2.35), то точка z¤ является минимумом функции f~(z) = f(y(z); z).

Вычислим градиент функции f~(z). Дифференцируя сложную функцию, приходим к

f~z(z) = fz(y(z); z) + yzT (z)fy(y(z); z):

Из тождества (3.2.36) после его дифференцирования получаем

gy(y(z); z)yz(z) + gz(y(z); z) = 0:

Так как, по предположению, матрица gy(y(z); z) неособая в точке z¤, то в силу непрерывности она будет оставаться неособой и в окрестности ¢(z¤). Поэтому

yz(z) = ¡gy¡1(y(z); z)gz(y(z); z):

После подстановки имеем

К выражению (3.2.37) для производной функции f~(z) можно прийти, используя функцию Лагран-

жа

L(y; z; u) = f(y; z) + hu; g(y; z)i; u 2 Rm:

Если продифференцировать L(y; z; u) по z и y соответственно и приравнять производную по y нулю, то имеем

Вычислим на основании второго равенства (3.2.39) множитель u и подставим его в (3.2.38). Тогда получаем то же самое выражение для производной f~z(z), если положить y = y(z). Таким образом,

f~z(z) = Lz(y(z); z; u); Ly(y(z); z; u) = 0m:

Отметим, что вектор u есть фактически функция от z. В решением задачи (3.2.35) точке x¤ = [y¤; z¤], где y¤ = y(z¤), дополнительно выполняется равенство

f~z(z¤) = Lz(y¤; z¤; u¤) = 0d:

Исходная задача (3.2.35) входит в это семейство при b = 0m.

Обозначим через x¤(b) решение задачи (3.2.40). Нас будет интересовать вопрос, как решение задачи (??) зависит от b, а точнее, как изменяется оптимальное значение целевой функции при малом изменении параметра b, т.е. когда b принадлежит в некоторой окрестности начала координат.

Если опять, учитывая связь g(x) = b, перейти к задаче с меньшим числом переменных, то теперь вместо зависимости y(z) у нас появится зависимость y(z; b) и будет выполняться тождество

g(y(z; b); z) ¡ b ´ 0m:

Функция f~ теперь становится функцией двух параметров,т.е. f~(z; b) = f(y(z; b); z). Используя примененный выше формализм Лагранжа для подсчета производной функции, аргументы которой связаны равенством, мы можем также подсчитать и производную функции f~(z; b) по b. Имеем теперь

где

L(y; z; b; u) = f(y; z) + hu; g(y; z) ¡ bi; u 2 Rm:

Вектор u в (3.2.41) удовлетворяет системе Ly(y; z; b; u) = 0m. Из (3.2.41) следует, что f~b(z; b) = ¡u =

¡u(y; z).

Если для каждого b из окрестности 0m найти решение задач (3.2.40) точки z¤ = z¤(b) и y¤ = y¤(b) = y(z¤; b), то поскольку f¤(b) = f(y¤(b); z¤(b)), мы получаем:

Функция f¤(b), определяемая согласно (3.2.40), носит название функции чувствительности. Она указывает на влияние правой части в равенстве g(x) = b на решение задач оптимизации (3.2.40).

Из необходимого условия Lx(x¤; b¤; u¤) = 0n, вытекает в частности, что Ly(y¤; z¤; 0m; u¤) = 0m. Поэтому множитель Лагранжа u¤ в (3.2.42) на самом деле является тем же самым множителем

Лагранжа, который входит в систему условий Каруша-Куна-Таккера для задачи (3.2.35). Формула (3.2.42) показывает, что данный множитель u¤ есть антиградиент функции чувствительности. Таким образом, любая компонента ui¤ вектора u¤ указывает на влияние соответствующей компоненты вектора-возмущения bi на решение задачи (3.2.40) .

Аналогичную интерпретацию множителей Лагранжа можно получить для задачи c ограничениями типа неравенства g(x) · b. Понятно, что если решение x¤ таково, что для какой-то компоненты gi(x) имеет место строгое неравенство gi(x¤) < bi¤, то для соответствующего множителя ui¤ в силу условия дополняющей нежесткости выполняется ui¤ = 0. С точки зрения вышесказанного это означает, что изменение i-го ресурса (компоненты bi), совершенно не существенно для решения задачи.

3.2.2. Условия оптимальности для задач выпуклого программирования

Обратимся теперь к выпуклой задаче математического программирования

в которой предполагается, что ¦ µ Rn выпуклое замкнутое множество и что f(x) и все компоненты вектор-функции h(x) = [h1(x); : : : ; hk(x)] выпуклые функции на Rn. Относительно компонент вектор-функции g(x) = [g1(x); : : : ; gl(x)] считается, что они линейные функции на Rn. Данную задачу принято называть задачей выпуклого программирования. Важно, что если она регулярная, то условия теоремы 3.2.3 оказываются не только необходимыми, но и достаточными, для того, чтобы точка x¤ оказалась ее глобальным решением. Составим для задачи (3.2.43) регулярную функцию Лагранжа

L(x; u; v) = f(x) + hg(x); ui + hh(x); vi:

Теорема 3.2.4. Пусть в выпуклой задаче математического программирования (3.2.43) функ-

ции f(x) и h(x) дифференцируемы. Тогда, если в точке x¤ 2 X при некоторых u¤ 2 Rl и v¤ 2 Rk+ выполнены условия

то x¤ глобальное решение задачи (3.2.43).

Доказательство. При сделанных предположениях функция L(x; u¤; v¤), где u¤ и v¤ фиксированы, выпукла по x на ¦. Более того, согласно (3.2.44), точка x¤ есть решение вариационного неравенства (3.1.23) с отображением F (x) = Lx(x; u¤; v¤). Поэтому в силу необходимых и достаточных условий теоремы 3.1.15 x¤ есть точка минимума функции L(x; u¤; v¤) на множество ¦, т.е.

Так как g(x¤) = 0l, то hg(x¤); u¤i = 0. Кроме того, поскольку для активных ограничений hj(x¤) = 0, а для неактивных ограничений v¤j = 0, то на основании (3.2.45) имеем hv¤; h(x¤)i = 0. Тогда неравенство (3.2.46) переписывается в более подробном виде как

Учтем теперь, что g(x) = 0l и h(x) · 0k для всех x 2 X, а также, что v¤ ¸ 0k. Тогда hu¤; g(x)i = 0, hv¤; h(x)i · 0, если x 2 X. Поскольку X µ ¦, то из (3.2.47) получаем

f(x¤) · f(x) + hu¤; g(x)i + hv¤; h(x)i · f(x) 8 x 2 X:

Таким образом, точка x¤ является глобальным решением задачи (3.2.43). ¥

Утверждение теоремы 3.2.4 сохраняется и при более слабых требованиях относительно функций f(x) и h(x). Приведем его для случая, когда ¦ = Rn, т.е. когда дополнительное ограничение x 2 ¦ фактически отсутствует.

Теорема 3.2.5. Пусть в задаче (3.2.52), в которой ¦ = Rn, функция f(x) и вектор-функция h(x) дифференцируемы, а вектор-функция g(x) линейная. Пусть, кроме того, f(x) является псевдовыпуклой функцией на Rn и все компоненты вектор-функции h(x) квазивыпуклы. Тогда, если в

то x¤ глобальное решение задачи (3.2.43).

Доказательство. Из квазивыпуклости всех компонент вектор-функции h(x) следует, что допустимое множество X выпукло. Поэтому, если взять любую точку x 2 X, то отрезок, соединяющий x с x¤ целиком принадлежит этому множеству и, следовательно, вектор s = x ¡ x¤ является возможным направлением в точке x¤ 2 X относительно множества X. Но тогда согласно утверждению

??

hhjx(x¤); x ¡ x¤i · 0; j 2 J0(x¤);

и поскольку v¤j ¸ 0, j 2 J0(x¤), то

X

v¤jhhjx(x¤); x ¡ x¤i · 0: (3.2.50)

j2J0(x¤)

Кроме того, из-за линейности вектор-функции g(x) вытекает равенство

На основании (3.2.48) справедливо представление

Xk

fx(x¤) = ¡gxT (x¤)u¤ ¡ v¤jhjx(x¤);

j=1

которое с учетом условия дополняющей нежесткости (3.2.49) можно переписать как

X

fx(x¤) = ¡gxT (x¤)u¤ ¡ v¤jhjx(x¤):

j2J0(x¤)

Отсюда и из (3.2.50) и (3.2.51) приходим к неравенству

Так как функция f(x) псевдовыпуклая, то выполнение данного неравенства означает, что f(x) ¸ f(x¤). Таким образом, x¤ точка глобального минимума функции f(x) на Rn. ¥

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

где f(x) и все компоненты h(x) выпуклые функции, ¦ µ Rn выпуклое замкнутое множество.

Условие регулярности ограничений Слейтера. Существует такая точка x¹ 2 ¦, что h(¹x) < 0k.

(3.2.55) градиенты hjx(x¤) неактивных в точке x¤ ограничений с множителями v¤j = 0, j 2 J¡(x¤). Тогда (3.2.55) переходит в неравенство (3.2.54).

Если J0(x¤) = ;, то точка x¤ 2 ¦ оказывается внутренней относительно множества X1 = fx 2 Rn : h(x) · 0kg. Задача (3.2.52) становится задачей минимизации выпуклой дифференцируемой функции на выпуклом множестве X = X1 \ ¦, причем в точке минимума x¤ конус возможных направлений относительно множества X совпадает с конусом возможных направлений относительно выпуклого множества ¦. Тогда, по теореме 3.1.15, hfx(x¤); x ¡ x¤i ¸ 0 для всех x 2 ¦. Данное условие совпадает с неравенством (3.2.53), если в нем положить v¤ = 0k. ¥

3.2.3. Достаточные условия второго порядка

Нами были получены условия оптимальности первого порядка для задач математического программирования (3.2.1) и (3.2.4). Условия (3.2.15), (3.2.16), как и в случае задачи безусловной минимизации (3.1.2), не зависят от того, какая из задач на минимимум или максимум рассматривается. Если бы в (3.2.1) вместо минимума целевой функции искался бы ее максимум, то условия оптимальности для этой задачи оказались бы фактически теми же самыми (поменялись бы только знаки у множителей Лагранжа, соответствующих ограничениям типа неравенства). Выделить те точки, где действительно реализуется миниминум целевой функции на допустимом множестве, а не максимум, позволяют условия второго порядка. Мы рассмотрим здесь только достаточные условия второго порядка, причем для задачи математического программирования (3.2.1). Как правило, при обосновании сходимости численных методов решения задач оптимизации обычно используются именно более сильные достаточные условия.

Далее будем предполагать, что функции, определяющие задачу (3.2.1), дважды непрерывно дифференцируемы на Rn. Через Lxx(x; u; v) будем обозначать матрицу вторых производных функции Лагранжа (3.2.28) относительно переменной x, которая составлена для задачи (3.2.1).

Ниже нам потребуются также следующее разбиение множества индексов активных ограничений J0(x) на два подмножества:

J0+(x; v) = ©j 2 J0(x) : vj > 0ª; J00(x; v) = ©j 2 J0(x) : vj = 0ª

и следующее условие, уточняющее условие дополняющей нежесткости.

Условие строгой дополняющей нежесткости. Мы скажем, что в точке [x; v] выполнено условие строгой дополняющей нежесткости, если в точке [x; v] выполнено условие дополняющей нежесткости и множество J00(x; v) пусто, т.е. J0(x) = J0+(x; v).

Введем в рассмотрение конус K(x; v), который есть пересечение двух линейных подпространств и конуса, а именно,

Если в точке [x; v] выполнено условие строгой дополняющей нежесткости, то K(x; v) = K1(x) \ K2(x; v) и фактически конус K(x; v) оказывается линейным подпространством, зависящим только от x.

Покажем, что s¹ 2 K(x¤; v¤) = K1(x¤) \ K2(x¤; v¤). Действительно, из (3.2.62) следует, что s¹ 2

K1(x¤). Далее, если хотя бы для одного индекса j 2 J0(x¤) = J0+(x¤; v¤) выполнялось бы hhjx(x¤); s¹i < 0; то из-за того, что для этого же индекса v¤j > 0, строгое неравенство выполнялось бы и в (3.2.63),

т.е.

Но строгое неравенство (3.2.64) не может иметь места, поскольку согласно (3.2.59) Lx(x¤; u¤; v¤) =

0n. Таким образом, s¹ 2 K(x¤; v¤).

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

Добавим во вторую сумму нулевые слагаемые v¤jhjxx(x¤), j 2 J¡(x¤), и перейдем к пределу при k ! 1, в результате получим неравенство:

hs;¹ Lxx(x¤; u¤; v¤)¹si · 0:

Но, как было выяснено, s¹ 2 K(x¤; v¤). Поэтому данное неравенство противоречит условию (3.2.60).

¥

Для задач без ограничений конус K(x¤; v¤) есть Rn и условия теоремы 3.2.7 переходят в обычное достаточное условие второго порядка (3.1.25) локального минимума функции f(x) на всем пространстве Rn.

Достаточные условия оптимальности (3.2.59) (3.2.60) можно представить в более симметричном виде, если от функции Лагранжа (3.2.28) перейти к ее простейшей модификации. Данная модификация позволяет также единым образом учитывать как ограничения типа равенства, так и ограничения типа неравенства.

Пусть m = l+k общее число ограничений в задаче математического программирования (3.2.1). Перепишем ее, используя единые обозначения и единую нумерация для равенств и неравенств,

Таким образом, первые l компонент вектор-функции

g(x) = £g1(x); g2(x); : : : ; gm(x)¤

соответствуют ограничениям-равенствам, а последующие k = m ¡ l компонент ограничениямнеравенствам.

Введем вектор u 2 Rm

(3.2.69)

Для любого u 2 Rm все компоненты pi(u), l < i · m являются неотрицательными. Используя (3.2.69), составим функцию Лагранжа

В случае задачи (3.2.2), содержащей только ограничения типа равенства, данная функция полностью совпадает с классической функцией Лагранжа L(x; u) = f(x) + hu; g(x)i.

Применительно к функции (3.2.70) условие дополняющей нежесткости и условие строгой дополняющей нежесткости может быть переформулировано следующим образом.

Определение 3.2.1. В точке [x¤; u¤] выполнено условие дополняющей нежесткости, если gi(x¤)pi(u¤) = 0, l < i · m. Если, помимо того, pi(u¤) > 0 при i 2 J0(x¤), то в точке [x¤; u¤] выполнено условие строгой дополняющей нежесткости.

Предположим теперь, что все функции f(x) и gi(x), 1 · i · m, непрерывно дифференцируемы. Введем понятие стационарной точки функции Лагранжа (3.2.70).

Определение 3.2.2. Точка [x¤; u¤] называется стационарной точкой функции Лагранжа (3:2:70), если

то любая стационарная точка [x¤; u¤] такова, что в ней имеет место условие дополняющей нежесткости и, кроме того, точка x¤ удовлетворяет ограничениям типа равенства. Стационарную точку

[x¤; u¤] назовем точкой Куна-Таккера, если x¤ 2 X.

Ниже нам потребуются два линейных подпространства

K1(x¤; u¤) = ©y 2 Rn : pu(u¤)gx(x¤)y = 0mª; K2(u¤) = ©z 2 Rm : pu(u¤)z = 0mª:

Приведем достаточные условия второго порядка изолированного локального минимума в задаче (3.2.68). Эти условия являются переформулировкой с помощью функции Лагранжа (3.2.70) соответствующих условий теоремы 3.2.7. В них используются матрицы Lxx(x¤; u¤) и Luu(x¤; u¤) вторых производных функции Лагранжа (3.2.70) по x и u соответственно.

Теорема 3.2.8. Пусть f(x) и gi(x), 1 · i · m, являются дважды непрерывно дифференцируемыми функциями. Пусть, кроме того, точка x¤ с некоторым u¤ 2 2 Rm образуют стационарную точку функции Лагранжа, в которой выполняются следующие два условия:

Тогда в точке [x¤; u¤] выполнено условие строгой дополняющей нежесткости, а точка x¤ является изолированным локальным решением задачи (3:2:68).

Доказательство. Покажем сначала, что при сделанных предположениях точка x¤ является допустимой и в паре [x¤; u¤] выполнено условие строгой дополняющей нежесткости. С этой целью воспользуемся равенством Lu(x¤; u¤) = 0, следующим из определения стационарной точки. Согласно данному равенству, pu(u¤)g(x¤) = 0. Отсюда, с учетом представления (3.2.72) матрицы pu(u¤), получаем

Таким образом, точка x¤ удовлетворяет ограничениям типа равенства и в паре [x¤; u¤] выполнено условие дополняющей нежесткости. Что касается ограничений типа неравенства, то, согласно (3.2.76), gi(x¤) = 0, если ui¤ =6 0, т.е. любое такое ограничение не только выполняется, но и является активным в точке x¤.

Далее, для любого z 2 K2(u¤), z =6 0m, выполнено неравенство (3.2.74). Но диагональная матрица pu(u¤) имеет вид (3.2.72), матрица Luu(x¤; u¤) также является диагональной:

Пусть ui¤ = 0 для некоторого индекса i 2 [l + 1; m]. Возьмем в этом случае в качестве ненулевого вектора z 2 K2(u¤) единичный орт ei, у которого все компоненты, кроме i-й, равны нулю, а i-я компонента равна единице. Тогда, на основании (3.2.74),

hei; Luu(x¤; u¤)eii = gi(x¤) < 0:

Отсюда делаем вывод, что для тех индексов i 2 [l + 1; m], для которых ui¤ = 0, соответствующее ограничение типа неравенства также выполняется, причем как строгое. Поэтому точка x¤ является допустимой и, более того, в точке [x¤; u¤] выполнено условие строгой дополняющей нежесткости.

Оптимальность точки x¤ проверяется так же, как это делается в теореме 3.2.7. ¥

Достаточные условия второго порядка, задаваемые теоремой 3.2.7, могут быть перенесены и на случай общей задачи математического программирования, в которой присутствует дополнительное требование принадлежности решения множеству простой структуры ¦. Приведем их, предполагая для простоты, что в задаче (3.2.4) допустимое множество X помимо простого ограничения определяется только ограничениями-равенствами: