15.093: Optimization Methods
15.093: Optimization Methods
15.093: Optimization Methods
1 Outline
Slide 1
Dx � d
x integer
� X � fx integer j Dx � dg
� Optimizing over X can be done e�ciently
2.1 Formulation Slide 3
� Consider
Z (�) � min c0x + �0
(b � Ax) (D)
s:t: x2X
� For �xed �, problem can be solved e�ciently
� �
� Z (�) � mini�1;:::;m c0 xi + �0 (b � Axi ) :
� Z (�) is concave and piecewise linear
2.2 Weak Duality Slide 4
If problem (D) has an optimal solution and if � � , then Z (�) � Z
0 IP
ZD
Z(p)
p* p
� ZD � ZIP
� We need to maximize a piecewise linear concave function
Slide 6
3 Strength of LD
3.1 Main Theorem Slide 7
X � fx integer j Dx � dg: Note that CH(X ) is a polyhedron. Then
ZD � min c0 x
s:t: Ax � b
x 2 CH(X )
2
x2
CH(X)
3 . .
xD
2 .
x IP
. .
c
xL P
1 . .
0
.
1
.
2 x1
X � (1; 0); (2; 0); (1; 1); (2; 1); (0; 2);
Slide 9
For p � 0, we have
Slide 10
� �
(x ;x )2X 1 2
8
�2 + p; �
� 0 � p � 5�3;
Z (p) � � 3 � 2p; 5�3 � p � 3;
:
6 � 3p; p � 3:
�
p � 5�3, and ZD � Z (5�3) � �1�3 Slide 11
� �
Slide 12
� xD � 1�3; 4�3 , ZD � �1�3
� �
� ZLP � ZD � ZIP
Slide 13
Z(p)
0
p
CH(X ) � x j Dx � d
� � �
� If� x j Dx � d , has integer extreme points, then CH(X ) � x j Dx �
d , and therefore Z � Z D LP
4 Solution of LD
� � Slide 15
� Z (�) � mini�1;:::;m c0xi + �0 (b � Axi ) ; i.e.,
� 0 ��:
Z (�) � i�1min
;:::;m
hi + f i
4
f (x *) +s' (x -x *)
f (x)
x* x
Z (p)
f2
s
f1
p* p
f (x ) � f (x� ) + s0 (x � x� );
for all x 2 �n .
� Let f be a concave function. A vector s such that
f (x ) � f (x� ) + s0 (x � x� );
t p
t
s
t
( t)
Z p
1 5:00
�3 �9 00
:
2 2:60
�3 �1 80
:
3 0:68
1 �1 32
:
4 1:19
1 �0 81
:
5 1:60
1 �0 40
:
6 1:92
�2 �0 84
:
7 1:40
1 �0 60
:
8 1:61
1 �0 39
:
9 1:78
�2 �0 56
:
10 1:51
1 �0 49
:
t and go to Step 2.
� �
3a If � � 0, ptj+1 � max ptj + �t stj ; 0 ; 8 j:
4.2.1 Step sizes
Slide 20
� Z (pt) converges to the unconstrained maximum of Z (�), for any stepsize
sequence �t such that
1
X
� t � 1; and lim � � 0:
t!1 t
t�1
� Examples �t � 1�t
� �t � �0 �t; t � 1; 2; : : :;
� �t � Z^Djj�sZjj(2p ) �t; where � satis�es 0 � � � 1, and Z^D is an estimate of
t
t
MIT OpenCourseWare
http://ocw.mit.edu
For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.