...

Semidefinite and Second Order Cone Programming Seminar Fall 2001 Lecture 3

by user

on
Category: Documents
1

views

Report

Comments

Transcript

Semidefinite and Second Order Cone Programming Seminar Fall 2001 Lecture 3
Semidefinite and Second Order Cone
Programming Seminar
Fall 2001
Lecture 3
Instructor: Farid Alizadeh
Scribe: Ge Zhang
9/24/2001
1
Overview
First we give the Separating Hyperplane Theorem and Weak Duality Theorem.
Secondly, the Generalized Farkas Lemma is presented. Finally, we provide the
Duality Theorem and its proof.
2
Farkas Lemma
The following theorem is probably the fundamental theorem of convex analysis.
There are many variations of it. Here we present the conic version.
Theorem 1 (The Separating Hyperplane Theorem) Let K be a proper
cone (closed in particular), let a be a point and a 6∈ K, then ∃ b such that
b> x ≥ 0, ∀x ∈ K and b> a < 0.
The theorem may be proved using the Weierstrass theorems in analysis. The
discussion of this theorem is presented in most books on non-linear programming.
A consequence of the Separating hyperplane theorem is the following
Lemma 1 If K is proper, then (K∗ )∗ = K.
Proof: If x ∈ K, then ∀z ∈ K ∗ x> z ≥ 0. This implies K ⊆ (K∗ )∗ . On the
other hand, suppose that K ⊂ K∗ but K 6= K∗ , then ∃z ∈ (K ∗ )∗ , but z 6∈ K.
Therefore, by the Separating Hyperplane Theorem, ∃b such that b> z < 0 and
b> x ≥ 0 for all x ∈ K. This implies b ∈ K∗ . So ∀a ∈ (K∗ )∗ , b> a ≥ 0, but
b> z < 0. We get a contradiction. Hence, (K∗ )∗ = K.
1
scribe:Ge Zhang
Lecture 2
Date: 9/24/2001
Lemma 2 z ∈ K∗ iff z> x ≥ 0, ∀x, extreme rays of K.
Proof: (⇒) It is trivial.
P
(⇐) u ∈ K ⇒ u
= αi xi where xi ’s are the extreme rays of K and αi ≥ 0. So
P
clearly z> u = αi z> xi ≥ 0.
Some Properties of the Dual of Cone
If K1 and K2 are proper cones, then the following hold
1. K1 ⊕ K2 = {(x, y) : x ∈ K1 , y ∈ K2 } is a proper cone.
2. K1 + K2 = {x + y : x ∈ K1 , y ∈ K2 } is a proper cone.
3. K1 ∩ K2 is a proper cone.
4. (K1 + K2 )∗ = K1∗ ∩ K2∗ , conversely, (K1 ∩ K2 )∗ = K1∗ + K2∗ .
The Weak Duality Theorem
Let A ∈ <m×n , x, c & s ∈ <n , b & y ∈ <m , K is a proper cone, m ≤ n and A
is a full rank matrix, then the standard form of K-LP problem is
Primal
min
s.t.
Dual
max
s.t.
c> x
Ax = b
x K 0
b> y
A> y + s = c
s K∗ 0
Theorem 2 (Weak Duality Theorem) If x is feasible for Primal and (y, s)
is feasible for Dual, then c> x ≥ b> y.
Proof: c> x − b> y = c> x − (Ax)> y = x> (c − A> y) = x> s ≥ 0 The last
inequality follows from the fact that x ∈ K and s ∈ K∗ .
Lemma 3 (Generalized Farkas Lemma) Let K ⊆ <n be a proper cone and
let A ∈ <m×n such that A(K) is closed, then for every b ∈ <m
Either: ∃x ∈ Rn , x K 0, and Ax = b;
Or: ∃y ∈ <m , A> y K∗ 0 but b> y < 0.
Remark 1 Note that A(K)—the linear transformation of K by A, that is
A(K) = {Ax : x ∈ K}—is also a convex and pointed cone if K is convex
and pointed. However, it may not be a closed cone even if K is. If K is a
closed polyhedral cone (for example the non-negative orthant), then A(K) will
always be closed. This is the reason why the stipulation that A(K) be closed
is not necessary in the usual Farkas Lemma. An example of a closed cone is
2
scribe:Ge Zhang
Lecture 2
Date: 9/24/2001
{(x0 , x1 , x2 ) | x1 , x2 ≥ 0, and x1 x2 ≥ x0 }. This is essentially one branch of
the hyperbola embedded in the hyperplane x0 = 1 and then extended into a
cone by extending rays from the origin. Now if we apply the linear transformation that projects this cone to say the x2 coordinate, we see that the projected
cone is {x2 | x2 > 0} which is not closed since it does not contain the origin.
This occurs because the cone above has an asymptote, that is a hyperplane that
is tangent to it at infinity. Since infinity is not a real number, this causes exclusion of some points of the boundary of the projected cone. The existence
of asymptotes is essentially the only reason why A(K) might not be closed in
general. Polyhedral cones do not have asymptotes, thus for them the issue of
closedness under linear transformations never arises.
Proof: Either, b ∈ A(K), which is equivalent to ∃x ∈ <n , x K 0, Ax = b
or, b 6∈ A(K). In the former case if A> y ∈ K∗ then 0 ≤ x> A> y = b> y. In
the latter case, by the Separating Hyperplane Theorem, we must have y where
y> b < 0 and y> z ≥ 0 for all z ∈ A(K). This implies y> Ax ≥ 0 for all x ∈ K.
So y> A K∗ 0. and y> b < 0.
As can be seen, compared with Farkas Lemma in LP, Generalized Farkas Lemma
requires one more condition that is A(K) is closed. This condition is indeed
necessary. The example below shows that without this condition Generalized
Farkas Lemma is no longer true.
Counterexample to Generalized Farkas Lemma
Consider a matrix
0 1
1 u
This matrix is not positive semi-definite for any value of u because a diagonal
entry of a positive semidefinite matrix is always non-negative; furthermore, if a
diagonal Xii = 0, then the entire row i and column i are zero. (If Xij 6= 0 then
set a = (ei ± ej )> X(ei ± ej ) = ±2Xij , and choosing − sgn(Xij ) in place ± will
make a negative.)
But

E11 • X = 0,

0 1
21
0 ⇐⇒
( E12 +E
) • X = 1,
2
1 u

X 0.
where Eij is the elementary matrix with entry Eij = 1, other entries being 0;
X is a 2 × 2 matrix. Stretch X to 1 × 4 vector, we get the equivalent system:



x11





1
0
0
0 
0

 x12  =

,


0 1/2 1/2 0  x21 
1



x
22


(∗)
x11



 x12 







 x21  0.



x22
3
scribe:Ge Zhang
Lecture 2
Date: 9/24/2001
0 1
is never positive semi-definite, system (*) has no solution. If we
1 u
want to apply the Generalized Farkas Lemma, we get
0
E12 +E21
∃(y1 , y2 ) such that y1 E11 + y2 (
) 0, (y1 , y2 )
< 0,
2
1
y 1 y2
in particular y2 < 0. This implies
0, with y2 < 0. Clearly, this
y2 0
is impossible since by the fact y22 = 0 we must have y2 = 0. Therefore, we get
a counterexample. The reason this happened is that for this example A(K) is
not closed. In this case,
1 0
0
0
A=
, and K = P2×2 .
0 1/2 1/2 0
Since
Therefore,




1
A(K) =
0



0
0
1/2 1/2

 


x
 
0 
y  | x y < 0 = (x, y) | x y < 0
0 y 
y z
y z



z
It is easy to see that A(K) = {(0, 0)} ∪ {(x, y) : x > 0, y ∈ <}; it is essentially
the right half plane x > 0 with (0, 0) added, but none of the other boundary
points (0, y) for y 6= 0 are in it. Clearly, this is a convex cone; but it is not a
closed set.
3
Strong Duality Theorem
Again consider the primal-dual pair:
Primal
min
s.t.
Dual
max b> y
s.t.
A> y + s = c
s K∗ 0
c> x
Ax = b
x K 0
Theorem 3 (Strong duality Theorem) Let both Primal and Dual be feasible with finite solution. Furthermore, let z1 be theoptimal
solutionfor Primal
A
b
and z2 the optimal solution for Dual. Let b0 =
and A0 =
, and
z2
c>
assume that A0 (K) is closed. Then z1 = z2 .
Proof: By Weak Duality Theorem, we know that z1 ≥ z2 .
Suppose that z1 > z2 . It implies that Ax = b, c> x = z2 , x K 0 has no
solution. By changing notation, we get that A0 x = b0 , x K 0 has no solution.
Applying the Generalized Farkas Lemma, ∃(y, y0 ) such that (1) A> y + y0 c K∗
0 and (2) b> y + z2 y0 < 0. Now we can prove the theorem in three cases.
4
scribe:Ge Zhang
Lecture 2
Date: 9/24/2001
i. y0 = 0: (1)&(2) become A> y K∗ 0, b> y < 0. Applying the Generalized
Farkas Lemma again, we get that Ax = b, x K 0 is infeasible. This
contradicts that fact that Primal is feasible. (Observation: A0 (K) is closed
implies that A(K) is closed. Therefore, it is no problem to apply the
Generalized Farkas Lemma.)
y
) − c K∗ 0. Primal is feasible and
ii. y0 < 0: Divide (1) by −y0 , get A> ( −y
0
optimal solution is finite. Therefore, ∃x+ such that Ax+ = b, x+ K 0
y
y
) − (x+ )c ≥ 0 ⇒ b> ( −y
) − z1 ≥ 0.
and c> x+ = z1 . Hence, (x+ )> A> ( −y
0
0
This contradicts the fact that z1 > z2 .
y
) + c K∗ 0
3. y0 > 0: Divide both (1) and (2) by y0 , we get that −A> ( −y
0
> y
and −b ( −y0 ) + z2 < 0. This contradicts the optimality of z2 .
Again it is important to assume that A0 (K) is a closed cone, otherwise the
strong duality theorem need not hold. To see a counter example consider the
primal-dual pair:
min x
1
s.t.
0
x1
0
x1
x2
0
max −z
2
z1
 1−z2
s.t.
2
z3

0
0 <0
x1 + 1
1−z2
2
0
z4

z3
z4  < 0
z2
We will see in a minute that they are indeed duals of each other. However, it is
easily seen that the optimal value of the minimization problem is x1 = 0, indeed
this is the only value x1 can have (why?). On the other hand for the dual, the
only possible value for z2 = 1 which makes its optimal value equal −1; we have
a positive gap. If you write this example in standard form and examine A and
A0 we will see that A(P3×3 ) is not closed (try it).
Table of Duality Rules
The relation of constraints and variables is given by the table below.
MIN
Max
K
K∗
Variables
K∗
Constraints
K∗
Unrestricted
=
K
K∗
Constraints
K∗
Variables
K∗
=
Unrestricted
5
scribe:Ge Zhang
Lecture 2
Date: 9/24/2001
Example 1 (Semidefinite and non-negativity constraints) Here
is an example to show how to apply this table.
min c> x = c1 x1 + · · · + cn xn
s.t. x1 A1 + · · · + xn An A0
x1 ≥ 0, x2 ≤ 0
⇔Y
Using the table we get
max A0 • Y
s.t. A1 • Y = C1
· · · A1 • Y ≥ C1
· · · A2 • Y ≤ C2
· · · An • Y = Cn
Y 0
⇔ x1
⇔ x2
⇔ xn
for i = 3, . . . , n
Exercise: Try to use the table and prove the counter example to
strong duality given above is indeed a pair of dual problems.
6
Fly UP