Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

§ 4}

Метод возможных направлений

77

(:w — и, v — оу) > 0 при всех v£.U

(11)

лсества:

a)

£/ =

{и : а£ < гУ < р£, i = 1,2, . . .

, т};

б) U = { u : \и— и1\< /?};

в)

£/= {и: (с1г и — иг) =

0}; г) U =

{« :

(сх, и — иг) < 0 } ;

д)

U =

{« : (сх, и — щ) =

0, (с2, и — и2) <

0},

где точки

ии и2, векторы

С\Фб, с2Ф 0,

числа R, щ, Pi. £ = 1, 2,..., т

считаются известными.

3.

Пусть С\, с2, ..., ср — линейно-независимая система/п-мерных

векторов,

ии и2,..., ир —

заданные точки

евклидова

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

Е т. Пусть

U = { v :

(с,, у—щ ) = 0 , i = 1, 2, ...,

/^— пересече­

р

w =

u + ' £ 'kfj,

/=>

где Я.1, Я,2, .... Ар определяются

из следующей линейной алгебраиче­

ской системы уравнений:

р

h (С/, Ci) = (Cit щ — и), i = 1,

, р.

2

2, . ..

7=1

У к а з а н и е .

Воспользоваться неравенством

(11).

4. Описать метод проекции градиента для минимизации функ­

ций из упраленений 1.15— 16 на мнолеествах

U из упражнений 2,3.

функции J (и)

на мнолеестве О ф Е т, близкий по своей идее к ме­

тоду проекции

градиента. Будем предполагать, что мнолсество U

§ 4]

Метод возможных направлений

79

gi (и* +

ар*) = gi (и* +

ар*) — g£ (и*) =

a (gi (и* -f Qap*),

р*) <

а - у - < 0

при

ге/ *,

а

при

i(£ I* g i(u * + ар*) < 0

для

всех

достаточно

малых

а > 0 . Кроме того,

(с,

р*) =%:£*<0. Существование подходя-

. щего направления р* в точке и* противоречит тому,

что и* — точ­

ка минимума. Следовательно,

£* = 0.

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

Пусть

при

некотором

и* 6

U

выяснилось,

что Г ф

0

и minv (а) = £* = 0.

Покажем,

что и *— точка

минимума'

J (и) на_и.

А

и £

U,

Пусть

это

не так.

Тогда

существует такая

точка

что J (и) <^J(u*). Можем считать,

что и — внутренняя

точка

множе­

ства

U,

так

как

по условию существует внутренняя точка и0 и, сле­

довательно,

точки

v =

и +

а (п0 — и),

0 <£ а

1,

являются

внутрен­

ними (см.

упражнение

5.1)

и

неравенство

/ (и*) >

J (и) = J (и) +

-j-а (с,

и0 — и) сохранится

при всех достаточно малых а > 0 .

Однако

если

и — внутренняя точка

U

и J (и) <£/ (и*),

[то

точка

a =

(|,

р),

где р =

и — и*,

принадлежит множеству А при некоторых £<£’0.

В^самом деле,

(с,

р) — J {и)

J (и*) <

0,

(gi (и*),

р) = (gi (и*),

и — и*) <

<

Si (“) — gi (“*) =

gi (й) <

0J

при t£ / *,_ и остается

взять

£ = max{(c, р);

(g\(u*), р)

(t £ / *)}< ().

Тогда

v (a) =

=

|* =

inf v (а).

Противоречие.

Следовательно,

и* — точка минимума J

А

Д

(и) на U.

2.

Опишем метод возможных направлений, предполагая,

множество U удовлетворяет условиям теоремы 1. На каждом шаге

итераций находятся точка u ^ U

и число б *> 0. В качестве началь­

ного приближения выбираются произвольная точка u0^ U

и произ­

вольное число 6о>0, например бо=1

(о выборе и0 см. ниже). Пусть

для некоторого /гГ^О точка

u.h<=U

и число

б/г> 0

уже

найдены.

Тогда следующее приближение ищем так.

1.

Сначала

определяем

множество

индексов

Д =

{ i : 1

^

— bh<.gi(u-k) =^0}. Из определения

1к

следует,

что

gi(uk