3-duality.pdf duality slides on methodss

S

1. Lagrangian duality
Mauro Passacantando
Department of Computer Science, University of Pisa
[email protected]
Optimization Methods
Master of Science in Embedded Computing Systems { University of Pisa
http://pages.di.unipi.it/passacantando/om/OM.html
M. Passacantando 1 / 13 {

2. Lagrangian relaxation
Consider the general optimization problem
8
<
:
minf(x)
g(x)0
h(x) = 0
(P)
wherex2 Dand the optimal value isv(P).
Lagrangian functionL:D R
m
R
p
!Ris
L(x; ; ) :=f(x) +
m
X
i=1
igi(x) +
p
X
j=1
jhj(x)
M. Passacantando 2 / 13 {

3. Lagrangian relaxation and dual function
Denition
Given0 and2R
p
, the problem

minL(x; ; )
x2 D
is called Lagrangian relaxation of (P) and'(; ) = inf
x2D
L(x; ; ) is the
Lagrangian dual function.
Dual function'
Iis concave because inf of linear functions w.r.t (; )
Ican be1
Ican be not dierentiable
M. Passacantando 3 / 13 {

4. Lagrangian relaxation and dual function
Theorem
Given0 and2R
p
, we have
'(; )v(P):
Proof.Ifx2, i.e.g(x)0;h(x) = 0, then
L(x; ; ) =f(x) +
m
X
i=1
igi(x)f(x);
hence
'(; ) = min
x2D
L(x; ; )min
x2
L(x; ; )min
x2
f(x) =v(P)
M. Passacantando 4 / 13 {

5. Lagrangian dual problem
Denition
The problem

max'(; )
0
(D)
is called Lagrangian dual problem of (P).
Dual problem consists in nding the best lower bound ofv(P).
Dual problem is a convex problem, even if (P) is not convex.
M. Passacantando 5 / 13 {

6. Lagrangian dual problem
Example 1 - Linear Programming.
Primal problem:

minc
T
x
Axb
(P)
Lagrangian function:L(x; ) =c
T
x+
T
(bAx) =
T
b+ (c
T

T
A)x
Dual function:
'() = min
x2R
n
L(x; ) =
(
1ifc
T

T
A6= 0

T
bifc
T

T
A= 0
Dual problem:

max'()
0
!
8
<
:
max
T
b

T
A=c
T
0
(D)
is a linear programming problem.
Exercise.What is the dual of (D)?
M. Passacantando 6 / 13 {

7. Lagrangian dual problem
Example 2 - Least norm solution of linear equations.
Primal problem:

minx
T
x
Ax=b
(P)
Lagrangian function:L(x; ) =x
T
x+
T
(Axb).
Dual function:'() = minx2R
nL(x; ).
L(x; ) is quadratic and strongly convex w.r.tx, thus
rxL= 2x+A
T
= 0()x=
1
2
A
T
;
hence'() =
1
4

T
AA
T
b
T
.
Dual problem:

max
1
4

T
AA
T
b
T

2R
p (D)
is an unconstrained convex quadratic programming problem.
M. Passacantando 7 / 13 {

8. Lagrangian dual problem
Exercise.Find the dual problem of a generic quadratic programming problem

min
1
2
x
T
Qx+c
T
x
Axb
(P)
whereQis a symmetric positive denite matrix.
M. Passacantando 8 / 13 {

9. Weak duality
Theorem (weak duality)
For any optimization problem we havev(D)v(P).
Strong duality, i.e.,v(D) =v(P), does not hold in general.
Example 1.
8
<
:
minx
2
x10
x0
v(P) =1
L(x; ) =x
2
+1(x1)2x,
'() = min
x2R
L(x; ) =1 8 2R
2
;
hencev(D) =1.
M. Passacantando 9 / 13 {

10. Weak duality
Example 2.

min 2x
4
+x
3
20x
2
+x
x
2
2x30−1 −0.5 0 0.5 1 1.5 2 2.5 3
−40
−30
−20
−10
0
10
Primal problem:      min 2x
4
+x
3
−20x
2
+x    s.t.    x
2
−2x−3 <= 0 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
−70
−65
−60
−55
−50
−45
−40
−35
Dual problem
Primal optimal solutionx

'2:0427,v(P)' 38:0648.
Dual optimal solution

'2:68,v(D)' 46:0838.
M. Passacantando 10 / 13 {

11. Strong duality
Theorem (strong duality)
If the problem
8
<
:
minf(x)
g(x)0
h(x) = 0
is, there exists an optimal solutionx

, and ACQ holds atx

, then KKT
multipliers (

;

) associated tox

are an optimal solution of the dual problem
andv(D) =v(P).
Proof.L(x; ; ) is convex with respect tox, thus
v(D)'(

;

) = min
x
L(x;

;

) =L(x

;

;

) =f(x

) =v(P)v(D)
M. Passacantando 11 / 13 {

12. Strong duality
Strong duality can hold also for some nonconvex problems.
Example.

minx
2
1
x
2
2
x
2
1
+x
2
2
10
v(P) =1
L(x; ) =x
2
1x
2
2+(x
2
1+x
2
21) = (1)x
2
1+ (1)x
2
2:
'() =
(
1if <1
if1
hence

= 1 is the dual optimum andv(D) =1.
M. Passacantando 12 / 13 {

13. Exercises
Exercise 1.Consider the problem
8
>
>
<
>
>
:
min
nP
i=1
x
2
i
nP
i=1
xi1
IDiscuss existence and uniqueness of optimal solutions
IFind the optimal solution and the optimal value
IWrite the dual problem
ISolve the dual problem and check whether strong duality holds
Exercise 2.Givena;b2Rwitha<b, consider the problem

minx
2
axb
IFind the optimal solution and the optimal value for anya;b
ISolve the dual problem and check whether strong duality holds
M. Passacantando 13 / 13 {