Solutions #2

Solutions #2
Dual of general LP.
Find the dual function of the LP
minimize cT x
subject to Gx h
Ax = b.
Give the dual problem, and make the implicit equality constraints explicit.
Solution.
1. The Lagrangian is
L(x, λ, ν) = cT x + λT (Gx − h) + ν T (Ax − b)
= (cT + λT G + ν T A)x − hλT − ν T b,
which is an affine function of x. It follows that the dual function is given by
−λT h − ν T b c + GT λ + AT ν = 0
g(λ, ν) = inf L(x, λ, ν) =
x
−∞
otherwise.
2. The dual problem is
maximize g(λ, ν)
subject to λ 0.
After making the implicit constraints explicit, we obtain
maximize −λT h − ν T b
subject to c + GT λ + AT ν = 0
λ 0.
Piecewise-linear minimization.
We consider the convex piecewise-linear minimization problem
minimize maxi=1,...,m (aTi x + bi )
(1)
with variable x ∈ Rn .
1. Derive a dual problem, based on the Lagrange dual of the equivalent problem
minimize maxi=1,...,m yi
subject to aTi x + bi = yi ,
i = 1, . . . , m,
with variables x ∈ Rn , y ∈ Rm .
2. Formulate the piecewise-linear minimization problem (1) as an LP, and form the dual of the
LP. Relate the LP dual to the dual obtained in part (a).
1
3. Suppose we approximate the objective function in (1) by the smooth function
!
m
X
f0 (x) = log
exp(aTi x + bi ) ,
i=1
and solve the unconstrained geometric program
Pm
T
minimize log
i=1 exp(ai x + bi ) .
(2)
A dual of this problem is given by (5.62). Let p?pwl and p?gp be the optimal values of (1)
and (2), respectively. Show that
0 ≤ p?gp − p?pwl ≤ log m.
4. Derive similar bounds for the difference between p?pwl and the optimal value of
minimize (1/γ) log
Pm
T
i=1 exp(γ(ai x
+ bi )) ,
where γ > 0 is a parameter. What happens as we increase γ?
Solution.
1. The dual function is
g(λ) = inf
max yi +
x,y
i=1,...,m
m
X
!
λi (aTi x + bi − yi ) .
i=1
P
= 0. To minimize over y we note that
0
λ 0, 1T λ = 1
T
inf (max yi − λ y) =
y
−∞ otherwise.
i
The infimum over x is finite only if
i λi ai
To prove this, we first note that if λ 0, 1T λ = 1, then
X
X
λT y =
λ j yj ≤
λj max yi = max yi ,
j
j
i
i
with equality if y = 0, so in that case
inf (max yi − λT y) = 0.
y
i
If λ 6 0, say λj < 0, then choosing yi = 0, i 6= j, and yj = −t, with t ≥ 0, and letting t go to
infinity, gives
max yi − λT y = 0 + tλk → −∞.
i
Finally, if
1T λ
6= 1, choosing y = t1, gives
max yi − λT y = t(1 − 1T λ) → −∞,
i
if t → ∞ and 1 < 1T λ, or if t → −∞ and 1 > 1T λ.
2
Summing up, we have
g(λ) =
P
bT λ
i λi ai = 0,
−∞ otherwise.
λ 0,
1T λ = 1
The resulting dual problem is
maximize bT λ
subject to AT λ = 0
1T λ = 1
λ 0.
2. The problem is equivalent to the LP
minimize t
subject to Ax + b t1.
The dual problem is
maximize bT z
subject to AT z = 0,
1T z = 1,
z 0,
which is identical to the dual derived in (a).
3. Suppose z ? is dual optimal for the dual GP (5.62),
P
maximize bT z − m
i=1 zi log zi
subject to 1T z = 1
AT z = 0.
Then z ? is also feasible for the dual of the piecewise-linear formulation, with objective value
T
b z=
p?gp
+
m
X
zi? log zi? .
i=1
This provides a lower bound on p?pwl :
p?pwl ≥ p?gp +
m
X
zi? log zi? ≥ p?gp − log m.
i=1
The bound follows from
inf
1T z=1
m
X
zi log zi = − log m.
i=1
On the other hand, we also have
max(aTi x + bi ) ≤ log
i
X
exp(aTi x + bi )
i
for all x, and therefore p?pwl ≤ p?gp .
In conclusion,
p?gp − log m ≤ p?pwl ≤ p?gp .
3
4. We first reformulate the problem as
P
minimize (1/γ) log m
i=1 exp(γyi )
subject to Ax + b = y.
The Lagrangian is
m
X
1
L(x, y, z) = log
exp(γyi ) + z T (Ax + b − y).
γ
i=1
L is bounded below as a function of x only if AT z = 0. To find the optimum over y, we set
the gradient equal to zero:
eγyi
Pm γy = zi .
i
i=1 e
This is solvable for yi if 1T z = 1 and z 0. The Lagrange dual function is
g(z) = bT z −
m
1X
zi log zi ,
γ
i=1
and the dual problem is
maximize bT z − (1/γ)
subject to AT z = 0
1T z = 1.
Pm
i=1 zi log zi
Let p?gp (γ) be the optimal value of the GP. Following the same argument as above, we can
conclude that
1
p?gp (γ) − log m ≤ p?pwl ≤ p?gp (γ).
γ
In other words, p?gp (γ) approaches p?pwl as γ increases.
Suboptimality of a simple covering ellipsoid. Recall the problem of determining the minimum volume ellipsoid, centered at the origin, that contains the points a1 , . . . , am ∈ Rn (problem (5.14), page 222):
minimize f0 (X) = log det(X −1 )
subject to aTi Xai ≤ 1, i = 1, . . . , m,
with dom f0 = Sn++ . We assume that the vectors a1 , . . . , am span Rn (which implies that the
problem is bounded below).
1. Show that the matrix
m
X
Xsim =
!−1
ak aTk
,
k=1
is feasible. Hint. Show that
Pm
T
k=1 ak ak
T
ai
ai
1
0,
and use Schur complements (§A.5.5) to prove that aTi Xai ≤ 1 for i = 1, . . . , m.
4
Solution.
Pm
T
k=1 ak ak
T
ai
ak
1
T
k6=i ak ak
P
=
0
0
0
+
ai
1
ai
1
T
is the sum of two positive semidefinite matrices, hence positive semidefinite. The Schur
complement of the 1, 1 block of this matrix is therefore also positive semidefinite:
!−1
m
X
1 − aTi
ak aTk
ai ≥ 0,
k=1
which is the desired conclusion.
2. Now we establish a bound on how suboptimal the feasible point Xsim is, via the dual problem,
Pm
T
T
maximize log det
i=1 λi ai ai − 1 λ + n
subject to λ 0,
P
T
with the implicit constraint m
i=1 λi ai ai 0. (This dual is derived on page 222.)
To derive a bound, we restrict our attention to dual variables of the form λ = t1, where
t > 0. Find (analytically) the optimal value of t, and evaluate the dual objective at this λ.
Use this to prove that the volume of the ellipsoid {u | uT Xsim u ≤ 1} is no more than a factor
(m/n)n/2 more than the volume of the minimum volume ellipsoid.
Solution. The dual function evaluated at λ = t1 is
!
m
X
g(λ) = log det
ai aTi + n log t − mt + n.
i=1
Now we’ll maximize over t > 0 to get the best lower bound. Setting the derivative with
respect to t equal to zero yields the optimal value t = n/m. Using this λ we get the dual
objective value
!
m
X
T
g(λ) = log det
ai ai + n log(n/m).
i=1
The primal objective value for X = Xsim is given by
m
X
− log det
!−1
ai aTi
,
i=1
so the duality gap associated with Xsim and λ is n log(m/n). (Recall that m ≥ n, by our
assumption that a1 , . . . , am span Rn .) It follows that, in terms of the objective function,
Xsim is no more than n log(m/n) suboptimal. The volume V of the ellipsoid E associated
with the matrix X is given by V = exp(−O/2), where O is the associated objective function,
O = − log det X. The bound follows.
Dual problem.
Derive a dual problem for
PN
2
minimize
i=1 kAi x + bi k2 + (1/2)kx − x0 k2 .
The problem data are Ai ∈ Rmi ×n , bi ∈ Rmi , and x0 ∈ Rn . First introduce new variables yi ∈ Rmi
and equality constraints yi = Ai x + bi .
5
Solution. The Lagrangian is
L(x, z1 , . . . , zN ) =
N
X
i=1
N
X
1
kyi k2 + kx − x0 k22 −
ziT (yi − Ai x − bi ).
2
i=1
We first minimize over yi . We have
inf (kyi k2 + ziT yi ) =
yi
0
kzi k2 ≤ 1
−∞ otherwise.
(If kzi k2 > 1, choose yi = −tzi and let t → ∞, to show that the function is unbounded below. If
kzi k2 ≤ 1, it follows from the Cauchy-Schwarz inequality that kyi k2 + ziT yi ≥ 0, so the minimum is
reached when yi = 0.)
We can minimize over x by setting the gradient with respect to x equal to zero. This yields
x = x0 +
N
X
ATi z.
i=1
Substituting in the Lagrangian gives the dual function
PN
P
T
2
(Ai x0 + bi )T zi − 12 k N
i=1 Ai zi k2 kzi k2 ≤ 1, i = 1, . . . , N
i=1
g(z1 , . . . , zN ) =
−∞
otherwise.
The dual problem is
maximize
PN
i=1 (Ai x0
+ bi )T zi − 12 k
PN
T
2
i=1 Ai zi k
subject to kzi k2 ≤ 1, i = 1, . . . , N.
Robust linear programming with polyhedral uncertainty.
minimize cT x
subject to supa∈Pi aT x ≤ bi ,
Consider the robust LP
i = 1, . . . , m,
with variable x ∈ Rn , where Pi = {a | Ci a di }. The problem data are c ∈ Rn , Ci ∈ Rmi ×n ,
di ∈ Rmi , and b ∈ Rm . We assume the polyhedra Pi are nonempty.
Show that this problem is equivalent to the LP
minimize cT x
subject to dTi zi ≤ bi , i = 1, . . . , m
CiT zi = x, i = 1, . . . , m
zi 0, i = 1, . . . , m
with variables x ∈ Rn and zi ∈ Rmi , i = 1, . . . , m. Hint. Find the dual of the problem of
maximizing aTi x over ai ∈ Pi (with variable ai ).
Solution. The problem can be expressed as
minimize cT x
subject to fi (x) ≤ bi ,
i = 1, . . . , m
if we define fi (x) as the optimal value of the LP
maximize xT a
subject to Ci a d,
6
where a is the variable, and x is treated as a problem parameter. It is readily shown that the
Lagrange dual of this LP is given by
minimize dTi z
subject to CiT z = x
z 0.
The optimal value of this LP is also equal to fi (x), so we have fi (x) ≤ bi if and only if there exists
a zi with
dTi z ≤ bi ,
CiT zi = x,
zi 0.
7

Download Report