Козлов В.Н. Системный анализ и принятие решений

Подождите немного. Документ загружается.

(, ) ( , )

(, )

=−

bp x Ap

pAp

алгоритм метода опряженных градиентов.

с р О

ставл

бирается произвольная точка

ассмотренные соотношения, позволяют сформулировать

2. Алгоритм метода опряженных г адиентов. сновные

шаги алгоритма пред яются следующей последовательностью:

Шаг 1. Вы

∈

ℜx , полагается

Шаг 2. Вычисляется вектор

0k =

()

′

−ϕ = −ϕpx

, используя

Шаг 3. Если , то переходим к 4, иначе – если

квадратичный , то далее - переход к шагу 8, а и

соотношения (1).

01kn<<−

функционал

ый

шагу

()ϕ x

есл

()ϕ x

– произвольн выпуклый функционал, то - к шагу 7.

Шаг 4. Вычисляется

1kkkk

+xx

, где множитель

определяется из условия

(, ) ( , )

(, )

=−

bp x Ap

pAp

если – квадратичная;

()ϕ x

, если

()

произвольная, причем

такое, что

min

{

()

}

kkk

αα

ϕ+ ≥xp

Шаг 5. Вычисляется направление

()

111kkkk

+++

′

−ϕ +

, где

)

111

(, )/(,)(,

kkkkkkk 1

)/(,

+++

′

′′′ ′

=−ϕ ϕ −ϕ ϕ = ϕ ϕ

−−

′′′

ϕ ϕ

Шаг 6. Полагается 1kk

+ и далее - переход к шагу 3.

Шаг 7. Так как

()ϕ x

произвольный выпукл нкционал, то ый фу

если

−

′′

ϕ≥>

, положим

100 1

,(),

−−

′

=−ϕ =xxp x

перех .

ов.

Метод позволяет найти минимум квадратичной положительно

определенной функции за число итераций, не превышающих .

одим к шагу 3, иначе – к шагу 8

Шаг 8. Остан

101

Сход ционарной

функ

Н м квадратичной

имость к ста точке произвольной (но выпуклой)

ции асимптотическая.

Проиллюстрируем работу алгоритма на примере.

Пример. айти миниму функции

⎛

) ( ) ( 4, 6) 18

xxx

⎛⎞ ⎛⎞

⎞

ϕ( = + − − +

⎜⎟ ⎜⎟

⎜⎟

⎝⎠

⎝⎠ ⎝⎠

Решение. Для нахождения минимума можно воспользоваться

ющи

ыбирается , полагаем .

аг 3. Так как , то - переход к шагу 4.

Шаг 4. Вычисляется вектор первого приближения решения

следу м алгоритмом:

(4,0 , 8,0)

=x 0k =

Шаг 1. В

Шаг 2. Вычисляется направление

)

(4,0, 10,0

′

=ϕ = − −p

02kn=<=

1000

=xx+

, где

0 00 00

( , )] / ( , ) 0,5

[( , )

=− =x Ap p Ap

, так

+bp

как

( ,bp) 116=−

(, 192−xAp

( , ) 232

pAp

Тогда

4,0, 8,0)

= .

Шаг 5. Вычисляется вектор

вектор

,10,0( 0,5( 4,0 ) (2,0, 3,0)

−+− =x

′

−ϕ ( ) +

, где параметр

1 0

1100

(, )/(,

′′ ′ ′

ϕ ϕ −ϕ ϕ ϕ

′

=− =

так а остальные

векто

ния общих задач математического

прогр рен вариант

мето с методом

сопряженных градиентов. Помимо него известны и широко

применяются другие группы методов безусловной ,

обладающие определенными достоинствами.

нтрольные вопросы

выпуклые фун конечномерных

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

как

(0, 0)

′

ϕ=

ры ненулевые.

Таким образом,

, является решением задачи.

Метод сопряженных градиентов и его обобщения положены в

основу алгоритмов реше

аммирования. В частности, далее будет рассмот

да проектирования градиента, согласованный

минимизации

Ко

1. Как определяются кционалы в

102

2. Как формулируются задачи безусловной и минимизаци в

конеч нствах.

метод

выпуклых функционалов.

4. Поясни е структуру и особенности вычислительных схем методов

наиск , Ньютона и сопряженных градиентов.

т сущность исследования сходимости и выбора шага

метод

6. Какова основная идея и с в сходимости

номерных простра

3. Как формулиру я идея метода наискорейшется основна его спуска,

а Ньютона и метода сопряженных градиентов для минимизации

орейшего спуска

5. В чем состои в

е наискорейшего спуска.

с ледо ания и выбора шага в

методе Ньютона.

103

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

ВЫПУКЛЫХ ФУНКЦИОНАЛОВ

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

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

ограничениями. Рассмотрены алгоритмы, использующие

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

оптимизации в виде теоремы Куна-Таккера, итеративные

методы проектирования на допустимые области и численно-

аналитические методы.

4.1. Необходимые, достаточные условия оптимальности и

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

ак уже отмечалось, методы оптимизации можно разделить на

две большие группы: методы прямой минимизации (не

испо ющие необходимые и достаточные условия) и методы,

основанные на необходимых условиях. Применение необходимых

условий экстремума хорошо известно из курса высшей математики

для задач безусловной минимизации. В случае задач на условный

экстремум нами будут даны соответствующие аналоги, в частности,

полученные в теореме Куна-Таккера для задач выпуклого

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

. Общие сведения о задачах выпуклого

программирования. Мы будем устанавливать необходимые и

достаточн

льзу

ые условия для следующей задачи: вычислить

min

{

()

∗

когда

()ϕ

выпуклый функционал, а опустимые множества

выпуклы, замкнуты и задаются системами равенств и неравенств.

Рассмотрим множество

{ |() }, () ( (),..., ())

ff=∈Γ ≥ =xfxbfx x xD ,

(2)

=ϕ∈xxxD

(1)

где

1 m

() , 1, ,

im=x

– вогнутые непрерывные на множестве

Γ – заданное выпуклскалярные функции, ое и замкнутое

104

множество. В частности, Γ может совпадать с пространством

ℜ

з теории множест известно что множество (2)

выпукло, поскольку является пересечением выпуклых множеств

И выпуклых в ,

()

}

∈ℜ ≥xfxb

. Из непрерывности

()

и замкнутости

множества

Γ следует замкнутость множества D .

Пусть сформулирована задача: вычислить

arg min{ ( ) | }

∗

=ϕ∈⊂ℜxxxD ,

(3)

причем

()ϕ x

выпуклый функционал, а удовлетворяет

пров нны ча н ыва

ачей

ярности.

Определение 1.

Если для каждого

еде м условиям. Эта зада аз ется

зад выпуклого

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

Множество

должно удовлетворять условию регул

(1,)i m= существует

точка

, что влечет за собой

x ∈ D

()

ii i

xb>

(4)

D удовлетворяетто множество условию регулярности Слейтера.

Рассмотрим вектор

() ()

−hx b f x

( )

который характеризует невязки в неравенствах, задающи

ограничения.

Определение 2.

Функция

(, ) () (, ())

ϕ+x

hxL

(6)

(,0)∈Γ ≥x

называется функцией Лагранжа

Вект

для задачи

(3).

гранжа. В задачах

выпуклого программирования необходимые и условия

формулируются с помощью седловых точек фу Лагранжа

Определение 3.

Пара

оры

∈ℜy

называются множителями Ла

достаточные

нкции .

∗

называется седловой точкой

функции Лагранжа

(, )x

на множестве

,0y

∈

Γ≥x

, если

105

(,) (, ) (, )

∗∗∗∗

≤

≤x

LL L

(7)

для всех

,0∈Γ ≥xy

. Последнюю формулу можно записать также

следу

еорема 1. Если пара

ющим образом:

( , ) min max ( , ) max m

∗∗

∈Γ

x y xyLL .

in ( , )

∈Γ

≥≥

∗

– седловая точка функции

Лагранжа

(, )x

на множестве

∈

Γ≥xy

, то

∗

– оптимальная

звернутая форма условий (7) с учетом (6)

имеет вид

)

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

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

()(,()) ()(,()) ()(,()

∗

ϕ+ ≤ϕ+ ≤ϕ+x

∗∗∗∗ ∗

hx x

(8)

венства следует, что

∗

Из левого нера

(,())(,())

∗∗

≤

(9)

поскольку и это неравенство имеет место для любого

значения м

∗

≥y

0≥

, то

()0

∗

≤hx

. В частности, (9) имеет есто и для

, т.е

( )) 0

∗

≥x

, а, следовательно (так как

∗

≥y

()0

∗

≤hx

(,())0

(,yh

∗∗

yhx

(10)

и (

Если ∈x D, то из (1) 5) следует, что

()hx 0

, и поэ

будет ь место условие

тому для

∈x D имет

(,())0hx

∗

≤

(11)

Так как (8) имеет место для всех значений

∈

Γx

(10) и

и в частности, для

, то из правого неравенства (8) и из (11) олучаем

неравенства

∈x D

всех

п для

∈D

( ) () ( ,()) ()

∗∗

ϕ≤ϕ+ ≤ϕxx

hx x

106

∗

∈D

(так как ∈Γx и

Но

x ()

∗

≤

) и, следовательно,

∗

–

оптимальна а.

Следующая теорема является необход

я точк

имым и достаточным

услов

еорема Куна-Таккера. Теорема формулируется

следующим образом.

Теорема 2.

Пусть в задаче (3) множество

ием оптимальности.

2. Т

()

}

=∈Γ ≥xfxbD

обладает свойством регулярности Слейтера

и достаточным условием оптимальности

ие такого , обы пара

(4).

является существован

Необходимым

чт

∗∗

была

∗

≥y

седловой то функции Лагранжа

(, )x

чкой

на множестве

,0∈Γ ≥xy

Достат аз на теореме 1.

очность док а в

Необходимость. Пусть оптимален. Рассмотрим в

)(1n

∗

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

ℜ

множества

00 0

()

,(), ,

∗

⎧⎫

≥ϕ

⎪⎪

==∈ℜ

⎨⎬

≤

⎝⎠

⎪⎪

⎩⎭

PSSxz

∪

∈Γ

⎛⎞

∈ℜ

⎜⎟

где определяется для каждого

()Sx

∈

Γx следующим образом

()

⎧⎫

≥ϕ

⎛⎞

⎪⎪

⎨⎬

⎜⎟

≥−

⎝⎠

⎪⎪

⎩⎭

zbfx

Покажем, что множества и выпуклы. Выпуклость

множества очевидна.

Пусть

′

⎛⎞

∈

⎜⎟

′

⎛⎞

∈

⎜⎟

и ,

′

⎝⎠

′′

⎝⎠

и покажем, что и (,)z

00 0

(,)z z

αα

(1 )(,)

TT T

′′

+− ⋅ ∈zzz S для всех

[0,1]

∈

. Так как

(,)

′

z∈S

, то найдется такой

∈

Γx , что

107

(,) (

′

)

′

∈ xzz S

и аналогично

(,) ()

zz x

′′ ′′ ′′

∈S

. Нам остаточно показать, что

(,) ()zz Sx∈

, где

(1 )xx x

′′

=+−

выпуклости

(ϕ ()

′

. Из и

−

следует

(

000

(1 ) ,

zzz

)[ (1)] ()(1)()

[

(1 )()]

[ ( )] (1 )[ ( )]

(1 ) .

() (1 ) ]

[()

αα α

αα

′′′′

ϕ=ϕ +− ≤ϕ +−ϕ

′′

+− =

′′′

=− +− − ≤

′′′

≤+− =

xx x x x

bfx bfx

zzz

αα

′′′

≤+− =

αα

′′′

−=− +− ≤

′

≤−

bfx b x x

′′

≤

Таким образом, .

Теперь тва щих

точек. Здесь

докажем, что множес и

не имеют об

(,)zz∈⊂SS

()

∗

⎧⎫

≥ϕ

⎛⎞

⎪⎪

⎨⎬

⎜⎟

≤

⎝⎠

⎪⎪

⎩⎭

Для каждог

∈x D

ввиду

о оптимальности

∗

будет справедливо

() ( )z

∗

≥ϕ ≥ϕxx

, но в

()z

∗

ϕPx

Для каждого , такого, что ∈Γx

∉

x D, найдется хотя бы один номер

, но в

такой, что

z≥

0 i

() 0

iii

bf− ≥x

Множества и выпуклы и не имею общих точек. По теореме о

еляющей гиперплоскости существует гиперплоскость,

множества, к

нормали, разделяющей гиперплоск

P т

разд

разделяющая эти и существует ненулевой ве тор

ости

⎛⎞

≠

⎜⎟

⎝⎠

(12)

108

такой, что

(13)

для всех

00 0 0

(,) (, )uz uw+≥+uz uw

(,)

∈

zS и

(,)

∈

Поскольку множеству принадлежат точки со сколь угодно

большими по модулю отрицательными компонентами, то

еобходимо должно быть

(

)

,0≥u .

(14)

Неравен

ство (13) остается справедливым и тогда, когда

принадлежит границе поэтому, выб

, по чим для всех

(,)

w w

()=ϕ

лу

; рав

, (), ( ), 0zw

∗

= − =ϕ =xz bfx x

∈Γx

() (, ()) )u(u

∗

ϕ+ − ≥ϕxubfx x

(15)

Убедимся, что . Предположим, что . Тогда

как (см. (14)) и

(15)

0u >

0u =

примет вид

(, ()) 0,−≥∀∈ub f x x

Так

0u > 0u

≠

(см. (13)), а для всех будет

∈x D

справедливо

() 0

−

≤bfx

то при

u >

равенство

() 0

−

будет выполняться для всех

∈

x D; что противоречит свойству

ти Слейтера.

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

регулярнос

Значит

след т, что , а

ротиворечит (12). Итак, .

ь , тогда (15) примет вид

уе это

0=u

0u >

−

∗

=≥yu

Пуст

( ) () ( , ())

∗∗

ϕ≤ϕ+ −xx

bfx

109

ех ∈Γx , и для

∗

=xx

. следует

(

для вс Отсюда

, ())0

∗

−

≥b fxy

(16)

Но , а (так как

∗

≥y

()0

∗

−≤bfx

∗

∈

x D

), поэтому.

(, ())0

∗∗

−

=yb fx

(17)

значения

0≥y

удет спра в

Для любого б ведли о

(, ( )) 0

∗

−

≤yb f x

(18)

Из неравенств (16)-(18) получаем

()(

∗

ϕ+x , ()) ()(, ()) ()(, ())

∗∗∗∗∗

− ≤ϕ+ − ≤ϕ+ −bfx x

bfx x

bfx

для всех или

,0∈Γ ≥xy

(,) , ) (, )

∗∗∗∗

(

≤

≤x

LL L

что соответствует неравенствам седловой точки.

3. Дифференциальные условия Куна-Таккера. ля

енения весьма важен случай

дифференцируемости ограничений.

Теорема 3.

Если функция

практического прим

()x

()

задачи выпуклого

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

(2) непрерывно ифференцируемы на

множестве

0xxΓ= ≥

, то для го, пара то чтобы

}

была

седло гвой точкой функции Ла а в области

0, 0

ранж

≥≥

необходимо и достат выполненияочно следующих условий,

приве в табл.

4.1

Таблица

денных

4.1

∂

⎛⎞

⎜⎟

∂

≥

∂x

∂

⎝⎠

0≥x

∂

≥

∂y

⎛⎞

∂

⎜⎟

∂

⎝⎠

0≥y

110