Metody_optimizatsii

cxT ® max

54

(1)

i

i W =

,m1

£,i :b)f (x

i

£ i

=

m

, ,i1 b,f x( )

то онаможетбы тьперепи санаследую щ и м образом

μ → max

μ - ϕ x £ 0( )

£ i

=

,i (b)f x

i

, m1

М етод секущ и х

плоскостей

основан на при бли жени и

всех

нели нейны х

функц и й

fi (x)

ли нейны ми

с и спользовани ем разложени я по формуле

Т ейлора.

0

0 T

0

( x f )f x(

( )

i

i

- x

») x

xÑ+)(f

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

i

cxT

® max

(2)

0 0 T

i 0 =

1

i

i

, m1

£,i

b -W)

x )(x Ñ+x( f

:)f x(

Е сли

множество Ω1 ограни чено, то задача(2) всегдаразреш и ма(в

проти вном случаеможетоказаться, что sup cxT

= +¥, дажеесли задача(1)

разреш и ма)

Ω1

fi (x)

Т аккакфункц и и

вы пуклы вни з, справедли во неравенство

i i

0

0

)

T

0

1

-

i

£ bi . )(Следовательно-x(£ x )xÑ+f(Ω ( )Ωx1 . fПустьf x x

2) Е сли

x1 ÏW, то взадаче(2) добавляю тся новы ели нейны еограни чени я:

T

1

1 1

1

+тxÑ)(f (f x( )

i

i

> b }.Э xти) fограни( i {:£чениb ,

я -обладаюx ) x

ii

i

57

r k → ∞, k → ∞ должно вы полняться

2) при невы полнени и ограни чени й и

услови е P(x, r k ) ® ¥ .

В

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

k

r k

é

m+ p

2

m

+

2 ù

g

)gx(

) =r, Px(ê

å

j

+ å

j

ú, ) x(

2

ë j=m+1

j=1

û

где

g +j (x) = max{0, g j (x)}.

Д анная

функц и я

удовлетворяет

всем

требовани ям, предъ являемы м

к

ш трафны м

функц и ям,

и

является

ди фференц и руемой. Ч то

позволяет

при

безусловной

опти ми зац и и

Ш аг 1. Задать начальную

точку

x0,

начальное значени е параметра

ш трафа r 0 , чи сло C > 1 для увели чени я параметра,

характери сти каточности

алгори тмаε > 0.

Ш аг2. Положи ть k = 0.

F(x, r k ) .

Ш аг3.

Состави тьвспомогательную функц и ю

Ш аг 4. И спользуя заданны енаш аге1

параметры

данного алгори тма,

реш и ть

задачу

безусловной

ми ни ми зац и и

F(x,r k ) → min одни м

и з

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

Ш аг 5. В ы чи сли ть значени е функц и и

P(x* (r k ), r k ) в полученной на

ш аге 4 точке ми ни мума x* (r k ).

Ш аг 6. Е сли

P(x* (r k ),r k )£ ε ,

то

проц есс пои ска закончи ть и

положи ть x* = x* (r k ), f (x* ) = f (x* (r k )) .

В

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

r k +1 = Cr k

xk +1 = x*

r k

k = k + 1 и перейти кш агу 3.

,

(

),

В

данном

методе,

как прави ло,

вы би раю т

r 0 = 0; 0,01; 0,1; 1,

а

C [4;10].

При

этом

не

рекомендуется

пы таться

реш и ть

одну

вспомогательную

задачу,

беря

сразу очень больш ое значени е параметра

ш трафа

r0 ,

поскольку

при

больш ом

значени и

данного

параметра

вспомогательная

функц и я

при обретает

явно

вы раженную

овражную

структуру.

x* (r k ), k = 0,1,...,

Последовательность

генери руемая

данны м

методом невсегдасходи тся креш ени ю

x* .

Д ля частны х случаев,

напри мер,

когда x*

-

локальное еди нственное реш ени е и

функц и и

f (x)

и

g j (x)

x* (r k ), k = 0,1,...

сходи тся к x* .

С ростом параметра r k генери руемы е

алгори тмом точки

при бли жаю тся

к x* и звне множества допусти мы х

При

r k ® ¥ и меем

lim

4 + rk

= 1 = x* .

Е сли

бы в этой задаче положи ть

2 + rk

r k →∞

r k

ε = 0,01,

то

алгори тм

закончи т свою

работу

при

= 1000 ,

так как

P(x* (r k ), r k )£ ε .

В

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

*

= ( ,00199) .

1

x

1000

П р имер 2. Н айти ми ни мум в задаче

x12 + x22 ® min

−

1 +

=x0

1

1 +

2 −

≤ 0

2x

x

Реш ени е.

В

данной

задаче одно ограни чени е равенство

и

одно

ограни чени е

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

т.е.

m = 1, p = 1.

Состави м

вспомогательную

функц и ю :

r k

k

2

2

2

2

1

x

2

x

[[

Fr x ]

[

{

1

2

- 2)}]+ x].

x

0(,

+ xmax=- 1 +

2

1

С помощ ью

необходи мы х

услови й

найдем

безусловны й

и

достаточны х

ми ни мум

Fr kx) .(

, В ы пи ш ем

необходи мы е

услови я

безусловного

экстремума:

¶

k

ì

1

k

1

k