20Дифференциальные условия оптимальности в задаче математического программирования

Введем ф-ю Лагранжа задачи (3:1)

n

L(x; 0; ) = 0f(x) + P igi(x) (3:6)

i=1

0 11

B 2C

где x 2 P 0 > 0 = B::: C 2 Qn

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

Теорема 3 (Принцип Лагранжа). Пусть в задаче (3:1) множество P выпукло. Ф-и f; g1; :::; gk дифференцируемы в точке x 2 X, gk+1; :::; gm непрерывно дифференцируемые в некоторой окрестности x . Если x - локальное решение задачи (3:1), то существует число

0 > 0

такое, что

0 1 1

B 2 C

= B C 2 Q

@ ::: A

m

< L0x(x; 0; ); x x >> 0 x 2 P (3:8)

i gi(x ) = 0 i = 1; 2; :::; k (3:9)

Любая точка x 2 X при некоторых 0 > 0 2 Q. Принцип Лагранжа утверждает, что при указанных предположениях любое локальное решение задачи (3:1) является стационарной точкой. Обратное гарантируется лишь при дополнительных предположениях о задаче (3:1). Например, предположение о выпуклости задачи (3:1).

Задача (3:1) называется задачей выпуклого программирования, если множество P выпукло, ф-и f; g1; :::gk выпуклы на множестве P , а gk+1; :::gm - линейны. Для задачи выпуклого программирования соотношения (3:8) и (3:9) являются не только необходимыми, но и достаточными условиями оптимальности.

Теорема 4. Пусть в задаче (3:1) множество P - выпукло. Ф-и f; g1; :::gk выпуклы на множестве P и дифференцируемые в точке x 2 P , а gk+1; :::gm - линейны. Если при

0 = 1

и некотором 2 Q выполняются условия (3:8) и (3:9), то точка x - глобальное решение задачи (3:1) (Без док-ва).

Заметим, что выпуклая ф-я имеет только один локальный минимум, следовательно локальный минимум выпуклой ф-и является и глобальным минимумом этой ф-и.

35

20.1Теорема Куна-Таккера

Частный случай для дифференцируемых ф-ий. Пусть дана задача нелинейного программирования: Найти максимальное значение ф-и f(x1; :::; fn) при gi(x1; :::; xn) > 0 i = 1; 2; :::; m x1; :::; xn > 0 (3:10) (ф-я вогнута)

Теорема 5. Локальные условия Куна-Таккера. Вектор x тогда и только тогда является решением задачи (3:10) (глобальным максимумом), когда выполняются следующие условия

m

L(x; ) = f(x) + P igi(x)

i=1

ф-я Лагранжа.

Пример. Выполнение условий (3:11) и (3:12) в экстремальной точке. Найти максимум ф-и

такой что в точке экстремума выполняются условия (3:11) и (3:12) для ф-и L(x; )

L(x; ) = x21 x22 + 1(2x1 + x2 2) + 2(8 2x1 x2) + 3(6 x1 x2)

Находим производные ф-и Лагранжа

36

21Численные методы минимизации ф-и многих переменных при ограничениях-равенствах и ограничениях-неравенствах

Как и ранее общая задача минимизации будет формулироваться так: найти минимум ф-и f(x1; :::; xn) при ограничениях

Как и ранее

X= fx 2 P jgi(x) 6 0; i = 1; :::; k; gi(x) = 0; i = k + 1; :::; ng (4:1 )

21.1Проекция точки на выпуклое n-мерное пространство

Пусть X - некоторое множество пространства En. Проекцией точки u 2 En на X называется ближайшая к u точка ! 2 X и

ju !j 6 ju xj x 2 X (4:2)

Условию (4:2) эквивалентно следующее условие

j! uj 6 jx uj x 2 X (4:3)

Проекцию будем обозначать как

! = Px(u)

Теорема 1. Пусть X - выпуклое замкнутое множество пространства En.Тогда

1.всякая u 2 En имеет и при том единственную проекцию на это множество

2.для того, чтобы точка ! 2 X была проекцией u на X необходимо и достаточно выполнения неравенства

<! u; x ! >> 0 x 2 X (4:4)

если X - аффинное множество, то условие (4:4) принимает вид

<! u; x ! >= 0 x 2 X (4:5)

21.2Метод проекции градиента

Рассмотрим задачу

f(x) ! min; x 2 X En (4:6)

где X не совпадает со всем пространством En, непосредственное применение градиентного метода в случае X 6= En может привести к затруднениям так, как точка xn+1 определяемая выражением

xk+1 = xk kf0(xk) (4:7)

может при каком-либо значении k не принадлежать множеству X. Однако эту трудность можно преодолеть, если полученную с помощью формулы (4:7) точку

xk kf0(xk)

при каждом k проектировать на множество X. Этот метод называют методом проекции градиента. Пусть x0 2 X - некоторое начальное приближение. Будем строить последовательность точек fxkg по

правилу

xk+1 = PX(xk kf0(xk)) k = 0; 1; 2; ::: (4:8)

37

где ak > 0

Если X - выпуклое, замкнутое множество, и способ определения чисел k в формуле (4:8) задан, то в силу теоремы 1. последовательность fxkg будет определяться однозначно.

В частности, при X = En метод (4:8) превратится в обычный градиентный метод Если в (4:8) на некоторой итерации оказалось, что

xk+1 = xk

случится

f0(xk) = 0

то процесс (4:8) прекращают. В этом случае, точка xk удовлетворяет необходимому условию оптимальности

xk = PX(xk kf0(xk)) k = 0; 1; 2; :::

Для выяснения того, является ли в действительности точка xk решением задачи (4:6) необходимо провести дополнительное исследование поведения f(x) в окрестности точки xk.

21.3Проекция точки на гиперплоскость

Пусть

X = fx 2 En :< c; x >= g

гиперплоскость. Здесь c 2 En- вектор, не равен 0, = const

Пользуясь геометрическими соображениями проекцию точки u 2= X на множество будем искать в виде

Покажем, что точка !, определяемая (4:9) действительно принадлежит множеству X. Для этого вычислим < c; ! >. Если , то принадлежит.

при всех x 2 X, то согласно теореме 1 найденная точка ! если проекция точки u на X. В координатной форме выражение (4:9) записывается следующим образом

!j = uj + <c;u> cj j = 1; 2; 3; ::: (4:10)

jcj2

21.4Проекция точки на аффинное множество

Определение. Множество

X = fx 2 En :< ai; x >= bi; i = 1; 2; :::; mg (4:10 )

где

0 1 ai1

Bai2C ai = B C @ ::: A

ain

заданный вектор пространства En

38