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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

54
mibxf
cx
i
i
T
,1,)(:
max
=≤Ω
→
(1)
Замечание 1. Любая задача выпуклого программирования может быть
записана в виде (1).
Действительно, если есть задача с нелинейной целевой функцией
,,1,)(
max
)
(
mibxf
x
ii
=≤
→
ϕ
то она может быть переписана следующим образом
mibxf
x
ii
,1,)(
0)(
max
=≤
≤−
→
ϕµ
µ
Метод секущих плоскостей основан на приближении всех нелинейных
функций )( xf
i
линейными с использованием разложения по формуле
Тейлора.
T
iii
xxxfxfxf ))(()()(
000
−∇+≈
Рассмотрим задачу
mibxxxfxf
cx
i
T
ii
T
,1,))(()(:
max
000
1
=≤−∇+Ω
→
(2)
Если множество
1
ограничено, то задача (2) всегда разрешима (в
противном случае может оказаться , что +∞=
Ω
T
cx
sup
1
, даже если задача (1)
разрешима)
Так как функции )( xf
i
выпуклы вниз, справедливо неравенство
i
T
iii
bxxxfxfxf ≤−∇+≤ ))(()()(
000
. Следовательно
1
⊆
. Пусть
1
x
-
решение задачи (2).
1) Если точка
1
x
допустима в задаче (1), то она является оптимальным
решением этой задачи (поскольку это экстремум той же целевой функции
на более широком множестве).
2) Если
Ω∉
1
x
, то в задаче (2) добавляются новые линейные ограничения:
})({:,))(()(
1111
iii
T
ii
bxfibxxxfxf >≤−∇+
. Эти ограничения обладают
следующими свойствами :
a) точка
1
x
не удовлетворяет этим ограничениям;
b) во всех точках множества
они выполняются .
Таким образом, получаем новое множество
2
, такое что
12
⊆
⊆
.
Далее итерационный процесс повторяется . Доказано, что генерируемая таким
образом последовательность {
k
x
} решений ЗЛП сходится к оптимальной
точке исходной задачи . Алгоритм метода имеет следующий вид. 
                                                 54
                         T
                      cx → max
                                                                                                  (1)
                   Ω : f i ( x) ≤bi , i =1, m
За ме ча н и е 1 . Любая задача выпуклого программирования может быть
записана в виде (1).
Действительно, если есть задача с нелинейной целевой функцией
                                    ϕ ( x) → max
                            f i ( x) ≤bi , i =1, m,
то она может быть переписана следующим образом
                            µ → max
                            µ −ϕ ( x) ≤0
                                      f i ( x) ≤bi , i =1, m
Метод секущих плоскостей основан на приближении всех нелинейных
функций f i (x) линейными с использованием разложения по формуле
Тейлора.
                          f i ( x) ≈ f i ( x 0 ) +∇ f i ( x 0 )( x −x 0 ) T
Рассмотрим задачу
                                 cx T → max
                                                                            (2)
         Ω1 : f i ( x 0 ) +∇ f i ( x 0 )( x −x 0 ) T ≤bi , i =1, m
     Если множество Ω1 ограничено, то задача (2) всегда разрешима (в
противном случае может оказаться, что                 sup   cx T =+∞, даже если задача (1)
                                                       Ω1
разрешима)
     Так как функции f i (x ) выпуклы вниз, справедливо неравенство
 f i ( x) ≤ f i ( x 0 ) +∇ f i ( x 0 )( x −x 0 ) T ≤bi . Следовательно Ω ⊆ Ω1 . Пусть x 1 -
решение задачи (2).
                              1
1) Если точка x допустима в задаче (1), то она является оптимальным
       решением этой задачи (поскольку это экстремум той же целевой функции
       на более широком множестве).
2) Если x1 ∉Ω , то в задаче (2) добавляются новые линейные ограничения:
        f i ( x 1 ) +∇ f i ( x 1 )( x −x 1 ) T ≤bi , i : { f i ( x 1 ) >bi } .Эти ограничения обладают
       следующими свойствами:
       a) точка x 1 не удовлетворяет этим ограничениям;
       b) во всех точках множества Ω они выполняются.
Таким образом, получаем новое множество Ω 2 , такое что Ω ⊆ Ω 2 ⊆ Ω1 .
Далее итерационный процесс повторяется. Доказано, что генерируемая таким
образом последовательность { x k } решений ЗЛП сходится к оптимальной
точке исходной задачи. Алгоритм метода имеет следующий вид.

Страницы