General problem of mathematical programming

1.

General problem of mathematical programming
f ( y) min, y Q R N
(1)
Q { y D : g j ( y ) 0, 1 j m}
(2)
D { y R N : yi [ai , bi ], 1 i N }
(3)
h( y) 0 ~ h( y) , 0
h( y ) 0,
h( y ) 0
h(y) 0,
0, y Q,
(Q)
1, y Q,
- характеристическая функция множества Q
(Q ) 0
Nested optimization scheme
1

2.

Auxiliary functions and sets
Feasibility function G ( y ), y D :
G ( y ) 0, y Q,
(4)
G ( y ) 0, y Q.
G( y) max{ g1 ( y),..., g m ( y)}
(5)
G( y) max{ 0; g1 ( y),..., g m ( y)}
(6)
ui ( y1 , , yi ), vi ( yi 1 , , y N ), 1 i N 1,
(7)
u N y, i N ,
v0 y, i 0.
S1 Q,
Si 1 (ui ) {vi R
N i
: (ui , vi ) Q}, 1 i N 1
i 1 (ui ) { yi 1 R1 : ( yi 1 , vi 1 ) Si 1 (ui )}
Nested optimization scheme
(8)
(9)
2

3.

Sections and projections
2 (u1 )
2 (u1 )
Nested optimization scheme
3

4.

Reducing the feasibility function
G N ( y ) G( y )
(10)
Di {ui Ri : y j [a j , b j ], 1 j i}
(11)
LEMMA 1
Gi (ui ) min{ G(ui , vi ) : y j [a j , bj ], i 1 j N}
Projecting Q onto coordinate axes
y1 , , yi :
Qi {ui R i : (ui , vi ) Q}, 1 i N .
(12)
(13)
(14)
LEMMA 2
Qi {u i R i : G i (u i ) 0}
(15)
LEMMA 3
i 1 (ui ) { yi 1 [ai 1 , bi 1 ] : G i 1 (ui , yi 1 ) 0}
Nested optimization scheme
(16)
4

5.

Nested optimization scheme
f N ( y) f ( y)
f i (ui ) min{ f i 1 (ui , yi 1 ) : yi 1 i 1 (ui )}, ui Qi
(17)
Main relation
min f ( y) min min ...
y Q
y1 1 y2 2 ( u1 )
min
y N N ( u N 1 )
f ( y)
(18)
f 1 ( y1 ) min, y1 1 R1
1 { y1 [a1 , b1 ] : G 1 ( y1 ) 0}
f 2 ( y1 , y2 ) min, y2 2 ( y1 ) R1 ,
2 ( y1 ) { y 2 [a 2 , b2 ] : G 2 ( y1 , y 2 ) 0}
f 3 (u2 , y3 ) min
. . .
f N (u N 1 , y N ) f (u N 1 , y N ) min, y N N (u N 1 ).
Nested optimization scheme
5

6.

Nested optimization scheme
f i (ui 1 , yi ) min, yi i (ui 1 )
(19)
ui 1 Qi 1 fixed
extr extr ...
y1 1 y2 2 ( u1 )
extr ( y)
yN N ( uN 1 )
y2
Example
f ( y1 , y2 ) ( y1 1) 2 ( y2 1) 2
g1 ( y) y1 y2 1
1
0 y1 2, 0 y2 2
1
Nested optimization scheme
y1
6

7.

Nested optimization scheme
G 2 ( y ) y1 y2 1
G1 ( y1 ) min{ y1 y2 1, y2 [0, 2]} y1 1
2 ( y1 ) { y2 [0, 2] : y1 y2 1 0} [0, 1 y1 ]
1 { y1 [0,2] : y1 1 0} [0, 1]
f 2 ( y1 , y2 ) ( y1 1) 2 ( y2 1) 2
f 1 ( y1 ) min{( y1 1) 2 ( y2 1) 2 : y2 2 ( y1 ) [0, 1 y1 ]}
Функция ( y1 1) 2 ( y2 1) 2 достигает минимума по y2 в единице,
а слева от 1 убывает, поэтому на отрезке [0, 1 y1 ] ее минимум
достигается в точке y2 1 y1 , а значение равно 2 y12 2 y1 1 , т.е.
f 1 ( y1 ) 2 y12 2 y1 1
Ее минимум на отрезке [0,1] достигается в точке y1* 1 / 2
f 2 (0.5, y2 ) 1 / 4 ( y2 1) 2
Т.к. 2 (1/ 2) [0,1 1/ 2] [0,1/ 2] , где f
*
убывает, то y2 1 / 2
Nested optimization scheme
2
7