Файл: Иоффе, А. Д. Теория экстремальных задач [учеб. пособие].pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 148

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

§ 1.2. ГЛАДКИЕ ЗАДАЧИ

85

ношение (29) эквивалентно равенству (18) в теореме 3. Далее, поскольку Ф (* * )е £ /, из определения опорной функции следует, что

(</*, Ф (* „)> < sup (у\ u)=s(y*\U),

lie U

т. е. (г/\ Ф (х,)) — s (у' |U) < 0. С другой стороны,

(0, Ф (х.)> — s (01£/) = 0.

Поэтому

0

<

шах ((2 *. Ф (*.)) - s (2 * |У)) =

(у\ Ф (*.)> -

s {у* |U) < 0,

 

 

2 *

 

 

 

 

откуда

(у*. Ф( х,))=з( у*\и) .

 

 

 

 

 

 

Полученный результат означает, что

 

 

 

inf

( у\ — и) = — sup {у\ и) =

 

 

 

uel/

веЦ

 

 

 

 

 

 

= — s (р* I и) =

(у*,

— Ф ( x j ) = (Уо> — и,)>

и мы сразу получаем соотношение (19) из

теоремы

3.

 

Совершенно аналогичным образом можно записать и теорему

Куна — Танкера. Для этого, обозначив

через

R™ множество векто­

ров

из

R" с неположительными

компонентами, введем функцию

 

 

п

V i (*) + б (х |Л) — s (я, I R1),

 

& (х, Л0, Л) = X0f0 (х) + 2

 

 

i=l

 

 

 

 

где Л = (Xi.........Л„). Предоставляем читателю проверить, что тео­

рема 2 равносильна следующей теореме.

о с е д л о в о й

т о ч к е .

Т е о р е м а

К у н а — Т а к к е р а

Пусть выполнены условия теоремы 2, включая условие Слейтера. Для того чтобы вектор х* был решением задачи (9)— (11), необ­ ходимо существование таких не равных одновременно нулю числа Яо 5* 0 и вектора Л е Rn, что

min 3! (х, Ло, Л) = 3 (х „ Ло, Л) == шах 3! (х,, Л0. р).

§ 1.2. Гладкие задачи.

Правило множителей Лагранжа

Сформулированное в предыдущем параграфе пра­ вило множителей Лагранжа содержит условие локаль­ ного экстремума. Поэтому его доказательство строится на использовании метода вариаций. Элементарный характер ограничений в гладких задачах позволяет

 

 

 

 

 

 

 

§ 1.2. ГЛАДКИЕ ЗАДАЧИ

 

 

 

87

существует такое целое число I,

21 ^

п,

что

 

 

 

 

 

 

б/(* .,

/0 = 0,

. . . .

 

 

 

А) =

0,

 

 

 

 

 

 

 

 

 

б<2'>f (х„ А) > 0

 

 

 

 

 

для всякого вектора h е

X.

 

 

 

 

 

 

 

 

 

Д о к а з а т е л ь с т в о

 

сразу

следует

из определения

п-й вариации и соответствующей теоремы для функций

одного переменного.

 

 

X — банахово

 

 

 

 

С л е д с т в и е .

Пусть

пространство.

Предположим, что функция f дважды дифференцируема

по Фреше в точке л:*'. Тогда,

если х * — точка локального

минимума функции f, то

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Г ( Х , ) > 0.

 

 

 

 

 

 

 

Последнее соотношение означает, что квадратичная

форма х —►/" (х*) (х, х)

неотрицательно

определена.

 

1.2.2.

 

Гладкие задачи с ограничениями типа равенств.

Доказательство

правила

 

множителей

Лагранжа.

По

условию

теоремы

1 множество

L =

F'(x*)X

является

замкнутым подпространством пространства Y. Воз­

можны два случая: регулярный,

когда L = Y ,

и вырож­

денный, когда L есть собственное подпространство про­

странства

Y.

 

сначала

 

регулярный

случай.

Если

г}

Рассмотрим

 

L =

Y, то

отображение

F удовлетворяет в точке х* ус­

ловиям теоремы Люстерника и, следовательно,

про­

странство,

касательное

с

к

множеству

{х е

X |F(x) — 0}

в точке х*, совпадает

 

ядром оператора F'(х*). Если

h <= Кег Е'(х*),

то

в соответствии

с определением

каса­

тельного

вектора

мы

 

можем

 

построить

вариацию

x ( t , h ) = x , +

th +

r(t)

точки х* такую,

что

 

 

 

 

 

F (х (/,

А)) =

0

при

— е < / < 8 ,

е > 0 ,

 

 

 

 

 

 

/ _1 II7 (О II->0

при

/-> 0 .

 

 

 

В

этом

случае

функция

<р(/) =

f(x(t, h))

достигает ло­

кального минимума в точке / =

 

0. Поэтому

 

 

 

 

 

 

 

 

ф'(0) =

</'(*.),

л> =

0.

 

 

 

 

Это

равенство

должно

 

выполняться

 

для

всякого

h <= КегЕДх*). Поэтому

 

 

 

 

 

 

 

 

 

 

/'( x ,) e ( K e r E 'W ) X.

88

ГЛ. 1. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА

По лемме об аннуляторе из § 0.1 найдется такой эле­ мент у* е У*, что

откуда

/'( * .) +

(*.)£* = о.

Итак, правило множителей Лагранжа в регулярном случае доказано. В процессе доказательства мы сразу получили, что Яо Ф 0. Однако в регулярном случае кон­ станта Яо и не может равняться нулю. Действительно, если Я0= 0, то

(у*, F'{xt)x) = (F'*(x.) f , х} = 0

для всех х ^ X, что в силу условия регулярности влечет равенство у* == 0, а это противоречит требованию тео­ ремы, согласно которому все множители Лагранжа не должны обращаться в нуль одновременно.

*•) Обратимся к вырожденному случаю. Поскольку L — собственное замкнутое подпространство пространства У, аннулятор подпространства L содержит ненулевые эле­ менты (согласно следствию 2 из теоремы Хана — Ба­ наха). Пусть у* — такой элемент. Тогда для всех х е X

0

= ( f ,

F'{xt)x) = {Fr'(xt)y\ х),

т. е. (если Я0 =

0)

 

& х (х„ 0, f ) = F ' ' ( x , ) f = 0.

Правило множителей Лагранжа

полностью доказано.

§ 1.3. Выпуклые задачи. Доказательство теоремы Куна — Танкера

Этот параграф построен по схеме § 1.2. Как и там, начнем с изучения простейших вариантов задач выпук­

лого программирования.

Пусть X — локально

1.3.1.

Задачи без ограничений.

выпуклое

линейное топологическое

пространство и f —

выпуклая функция на X. Рассмотрим задачу о безус­

ловном минимуме функции f:

 

 

f (.х) ->■ inf.

( 1)

§ 1.3.

ВЫПУКЛЫЕ ЗАДАЧИ

89

П р е д л о ж е н и е

1. Для того чтобы функция f

до­

стигала минимума в точке х*, необходимо и достаточно,

чтобы выполнялось соотношение

 

 

Ое=<Э/(*,).

 

Последнее соотношение есть аналог теоремы Ферма

из § 1.2 для гладких задач без ограничений.

определе­

Д о к а з а т е л ь с т в о следует прямо из

ния субдифференциала.

 

1.3.2.

Задачи с ограничениями типа равенств. Пусть

снова X — локально выпуклое линейное топологическое

пространство, f — выпуклая функция на X

и М ■— ли­

нейное многообразие, параллельное подпространству L.

Задачу

/(* ) —> inf;

(2)

 

 

 

(3 )

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

П р е д л о ж е н и е 2. Для того чтобы точка х* была решением задачи (2), (3), достаточно, а если функция f непрерывна в некоторой точке из М, то и необходимо, чтобы

df СО ПL1 Ф 0 .

Д о к а з а т е л ь с т в о .

Достаточность

сразу следует

из определений. Для

доказательства

необходимости

рассмотрим функцию

 

 

&(x) =

f(x) + b(x\M).

 

Очевидно, х* будет решением задачи (2), (3) в том и только том случае, когда в точке х* функция S дости­ гает минимума. Сопоставив предложение 1 с теоремой Моро — Рокафеллара (см. § 0.3), получим

0 е df(xt) + d6(x, IМ).

Остается заметить, что дЬ ( x * ] M ) = L i . Предложение доказано.

90

ГЛ. 1. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА

С л е д с т в и е . Пусть

х\, . . . ,

х*п — конечный набор

линейных

функционалов

из X*,

аи . .. , а п — действи­

тельные числа и

 

 

М = [х <= X |(x*t, x) = ai, i = l , . . . . л}.

Пусть, далее, f(x) — выпуклая функция на X, непрерыв­ ная в некоторой точке множества М. В этих предполо­ жениях точка х* доставляет минимум функции f на мно­ жестве М тогда и только тогда, когда существуют такие числа %i.........%п, что

v ; + . . .

+ v ; e

* /(* ).

 

Это точный аналог правила множителей Лагранжа

для выпуклых задач.

В силу

следствия

из леммы

Д о к а з а т е л ь с т в о .

об аннуляторе L1 есть

линейная

оболочка

множества

к........... < } •

1.3.3.Задачи с ограничениями типа неравенств. До­

казательство теоремы Куна — Таккера. Обратимся к за­ даче (9) — (П ) из § 1.1. Пусть х , — ее решение. Рас­ смотрим в Rn+1 множество С, чьими элементами яв­ ляются те и только те векторы (ро, •••, p „ ) e R n+I, Для каждого из которых найдется такой вектор т е Д, что

h (* ) — /о ( * . ) <

Р о!

Ы

* Х H i.............fn М < I1*-

 

Внутренность

множества

С не

пуста, ибо оно содер­

жит внутренность

неотрицательного

ортанта

в

Rn+1.

(Если ро >

0, . . . ,

рп >

0, то

ро >■ Ы **)— fo(x*) — 0

и рi > f i ( x t)

при i —

1......... п.)

Далее,

С — выпуклое

множество, поскольку

функции

fiy

i —

0, . . . , п,

вы­

пуклы. Наконец, 0 ф. С,

ибо, если 0 <= С,

то существует

такой х ^ А ,

что Ы *) <

Ы**) и f i ( x ) ^ 0, i =

1, .. ., п,

т. е. х* — не решение задачи.

По теореме отделимости множество С можно отде­ лить от нуля ненулевым линейным функционалом, т. е.

существуют не

равные одновременно нулю числа

U, . . . . Хп такие,

что

Смотрите также файлы