Методы оптимизации. Азарнова Т.В - 48 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

50
0yxg
T
j
<∇ )( ,
)
(
x
I
j
∈
,
где
)
(
x
I
- множество активных в точке
x
ограничений.
Возможное и подходящее направление, удовлетворяющее данной
системе неравенств , определяется из решения задачи линейного
программирования
z
→
zyxf
T
≤∇ )( ,
(
)
,,)( xIjzyxg
T
j
∈≤∇
n1i1y1
i
,, =≤≤− .
Заметим, что
)
,
(
)
,
(
0
0
z
y
=
удовлетворяет всем ограничениям задачи ,
следовательно, ожидаемый результат
0
z
≤
*
. Если
0
z
<
*
, то система (1)
имеет решение
y
. В этом случае строится новая точка
y
x
α
+
. При этом
α
выбирается таким образом, чтобы
y
x
α
+
была допустимой точкой ,
например,
(
)
m10k
β
β
β
α
,...,,min
=
где
0
β
выбирается из условия )(min)(
kk
0
k
0
k
yxfyxf ββ
β
+=+
>
, а
m1j
j
,,
=
β
- максимально возможное перемещение из точки
x
вдоль
направления
y
с учетом
i
-го ограничения, которое найдено из условия
0yxg
ij
=
+
)(
β
.
Если
0
z
=
*
, то система (1) несовместна, т.е. все возможные в точке
x
направления не являются подходящими . Это означает, что в точках
h
допустимого множества, достаточно близких к
x
, выполняется неравенство
)
(
)
(
x
f
h
f
≥
, т.е.
x
-точка локального минимума
)
(
x
f
на допустимом
множестве . Но для выпуклой функции
)
(
x
f
на выпуклом множестве этот
минимум является и глобальным. Таким образом, точка
x
есть решение
задачи .
Алгоритм
Шаг 1. Задать начальную точку
x
0
, характеристику точности алгоритма
ε
>
0
. Положить
0
k
=
.
Шаг 2. Найти )(
k
xf ∇ . Если ε≤∇ )(
k
xf , то вычисления прекратить и
положить
k
x
x
=
*
, иначе перейти к шагу 3.
Шаг 3. Подставить
k
x
в неравенства и определить множество индексов
активных ограничений )(
k
xI .
Шаг 4. Если ∅= )(
k
xI , то положить )(
kk
xfy −∇= , иначе определить
k
y из решения задачи
min
→
k
z
                                             50
                T
       ∇ g j ( x) y <0 , j ∈I (x) ,
где I (x) - множество активных в точке x ограничений.
       Возможное и подходящее направление, удовлетворяющее данной
системе неравенств, определяется из решения задачи линейного
программирования
                                       z → min
                                    ∇ f ( x ) y T ≤z ,
                                ∇ g j ( x) y T ≤z, j ∈I (x ),
                                    −1 ≤ y i ≤1, i =1, n .
Заметим, что        ( y, z ) =(0,0 ) удовлетворяет всем ограничениям задачи,
следовательно, ожидаемый результат z * ≤0 . Если z * <0 , то система (1)
имеет решение y . В этом случае строится новая точка x +αy . При этом α
выбирается таким образом, чтобы x +αy была допустимой точкой,
например,
                        α k =min (β0 , β1 ,..., βm )
где    β0   выбирается     из      условия        f ( x k +β0 y k ) =min f ( x k +βy k ) ,   а
                                                                     β >0
β j , j =1, m - максимально возможное перемещение из точки x вдоль
направления y с учетом i -го ограничения, которое найдено из условия
g j ( x +βi y ) =0 .
       Если z * =0 , то система (1) несовместна, т.е. все возможные в точке x
направления не являются подходящими. Это означает, что в точках h
допустимого множества, достаточно близких к x , выполняется неравенство
 f (h) ≥ f ( x) , т.е. x -точка локального минимума f (x) на допустимом
множестве . Но для выпуклой функции f (x) на выпуклом множестве этот
минимум является и глобальным. Таким образом, точка x есть решение
задачи.

                                 Алгоритм
    Шаг 1. Задать начальную точку x 0 , характеристику точности алгоритма
ε >0 . Положить k =0 .
    Шаг 2. Найти ∇ f ( x k ) . Если ∇ f ( x k ) ≤ε , то вычисления прекратить и
положить x * =x k , иначе перейти к шагу 3.
    Шаг 3. Подставить x k в неравенства и определить множество индексов
активных ограничений I ( x k ) .
      Шаг 4. Если I ( x k ) =∅ , то положить y k =−∇ f ( x k ) , иначе определить
y k из решения задачи
                                        z k → min

Страницы