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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

47
Заметим, что если в задаче отсутствуют ограничения-равенства
и в рассматриваемой точке
x
нет активных ограничений (т.е. точка
x
является внутренней ), то в качестве подходящего направления можно взять
)
(
x
f
y
−∇
=
. В противном случае построение подходящих направлений
можно осуществить в виде минимизации функции yxf
T
)(∇ при условиях
0Cy0yA
1
=
≤
, . Однако если существует такой вектор
y
, такой , что
0yxf
T
<∇ )( , 0Cy0yA
1
=
≤
, , то минимальное значение функции
T
yxf )(∇
при такой минимизации не существует ( −∞→∇
T
yxf )(inf ), так как любой
вектор
y
, где
- сколь угодно большое число, также удовлетворяет
условиям 0yC0yA
1
=
≤
, . Таким образом, в задачу минимизации должно
быть включено условие, которое ограничивало бы вектор
y
, например,
условие
n1i1y
i
,,
=
≤
. Итак, возможное и подходящее направление ищется
в виде решения следующей задачи линейного программирования
min)( →∇
T
yxf
0Cy0yA
1
=
≤
,
1y1
i
≤
≤
−
, n1i ,
=
.
Алгоритм
Шаг 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))(( →∇
Tkk
yxf
0Cy0yA
kk
1
=≤ ,
1y1
k
i
≤≤−
,
n1i ,
=
.
Шаг 5. Если
0yxf
Tkk
=∇ ))((
, то задача решена точно и
k
x
x
=
*
. Иначе -
для найденного вектора
k
y
определить
)(
:
minarg
kk
yx
k
yxf
kk
α
α
α
α
+
Ω∈
=
+
.
Шаг 6. Найти очередное приближение
k
k
k1k
yxx α +=
+
.
Пример 1. Решить рассмотренным методом следующую задачу
min)()(),( →−+−=
2
2
2
1
2x4xyxf 
                                        47
      Заметим, что если в задаче отсутствуют ограничения-равенства
и в рассматриваемой точке x нет активных ограничений (т.е. точка x
является внутренней), то в качестве подходящего направления можно взять
y =−∇ f (x) . В противном случае построение подходящих направлений
можно осуществить в виде минимизации функции ∇ f ( x) T y при условиях
A1 y ≤0, Cy =0 . Однако если существует такой вектор y , такой, что
∇ f ( x ) y T <0 , A1 y ≤0, Cy =0 , то минимальное значение функции ∇ f ( x) y T
при такой минимизации не существует ( inf ∇ f ( x ) y T → −∞ ), так как любой
вектор λy , где λ - сколь угодно большое число, также удовлетворяет
условиям A1 λy ≤0, Cλy =0 . Таким образом, в задачу минимизации должно
быть включено условие, которое ограничивало бы вектор y, например,
условие y i ≤1, i =1, n . Итак, возможное и подходящее направление ищется
в виде решения следующей задачи линейного программирования
                                 ∇ f ( x) y T → min
                                 A1 y ≤0, Cy =0
                               −1 ≤ y i ≤1 , i =1, n .
                                     Алгоритм
    Шаг 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 из решения задачи линейного
программирования
                               ∇ f ( x k )( y k ) T → min
                                 A1 y k ≤0, Cy k =0
                               −1 ≤ y ik ≤1 ,   i =1, n .
   Шаг 5. Если ∇ f ( x k )( y k ) T =0 , то задача решена точно и x * =x k . Иначе -
для найденного вектора y k определить
                          α k = arg min f ( x k +α y k ) .
                               α: x k +α y k ∈Ω
   Шаг 6. Найти очередное приближение x k +1 =x k +α k y k .

Пример 1. Решить рассмотренным методом следующую задачу
                   f ( x, y ) =( x1 −4 ) 2 +( x 2 −2) 2 → min

Страницы