Solutions to the End-of-Chapter Excercises in

\Interior-Point Algorithm: Theory and

Analysis"
Yinyu Ye
November 1997
 1

c 1997
By

Yinyu Ye, Professor

Department of Management Sciences
The University of Iowa
Iowa City, IA 52242-1000
Phone: (319) 335-1947
E-mail: yinyu-ye@uiowa.edu
2
Chapter 1

Introduction and
Preliminaries
1.1 Exercises

1.1Let Q 2 Rnn be a given nonsingular matrix, and a and b be given

R vectors. Show
n

(Q + abT ) 1 = Q 1 T 1
1 + bT Q 1a Q ab Q :
1 1

This formula is called the Sherman-Morrison-Woodbury formula.

Solution 1.1

(Q + abT )(Q 1 T 1
1 + bT Q 1 a Q ab Q )
1 1

= I 1 T 1 T 1 1 T 1 T
1 + bT Q 1 a ab Q + ab Q 1 + bT Q 1 a ab Q ab Q
1

= I 1 ab T Q 1 + abT Q 1 bT Q 1 a abT Q 1
1 + bT Q 1 a 1 + bT Q 1 a
= I:
1.2 Prove that the eigenvalues of all matrices Q 2 Mnn are real. Fur-
thermore, show that Q is PSD if and only if all its eigenvalues are non-
negative, and Q is PD if and only if all its eigenvalues are positive.
Solution 1.2

3
4 CHAPTER 1. INTRODUCTION AND PRELIMINARIES
1.3 Using the ellipsoid representation in Section ??, nd the matrix Q
and vector y that describes the following ellipsoids:
1. the 3-dimensional sphere of radius 2 centered at the origin;
2. the 2-dimensional ellipsoid centered at (1; 2) that passes the points
(0; 2), (1; 0), (2; 2), and (1; 4);
3. the 2-dimensional ellipsoid centered at (1; 2) with axes parallel to the
line y = x and y = x, and passing through ( 1; 0), (3; 4), (0; 3),
and (2; 1).
Solution 1.3 1.
0 1=4 0 0
1
Q = @ 0 1=4 0 A ; y = 0;
0 0 1=4
2. 1 0

Q= 0 1=4 ; y = (1; 2);
3.  5=16 3=16

Q= 3=16 5=16 ; y = (1; 2):
1.4 Show that the biggest coordinate-aligned ellipsoid that is entirely con-

tained in Rn+ and has its center at xa 2Rn+ can be written as:
E (xa ) = fx 2 Rn : k(X a) 1 (x xa )k  1g:
Solution 1.4 The coordinate-aligned ellipsoid that has its center at xa is
given by
fx 2 Rn : (x xa )T Q(x xa )  1g;
where Q is a positive diagonal matrix. The inequality can be written as
X
n
qjj (xj xaj )2  1:
j =1
In order to have it entirely contained in Rn+ , we must have pqjj  x1aj for
Q
all j = 1; : : : ; n. Since the volume of the ellispod is nj=1 pq1jj , the biggest
must be pqjj = x1aj for j = 1; : : : ; n.
1.1. EXERCISES 5

1.5 Show that the non-negative orthant, the positive semi-denite cone,
and the second-order cone are all self-dual.
Solution 1.5 For a cone C  E , the dual of C is the cone
C  := fy : hx; yi  0 for all x 2 C g;
where h
;
i is an inner product operation for space E .
For C = Rn+ ,
C  := fy : xT y  0 for all x 2 Rn+ g:
In paticular, for any y 2 C  we let x = 0 except x1 = 1. Then, we must
have y1  0. Similary, we have yj  0 for all j = 1; : : : ; n. Thus, C  = C .
For C = Mn+ ,
C  := fY : X  Y  0 for all X 2 Mn+ g:
In paticular, for any Y 2 C  we let X = vvT where v, kvk = 1, is an
eigenvector of Y with eigenvalue . Then, we have  = vT Y v = X  Y  0.
Similary, we shall have all eigenvalues of Y nonnegative. Therefore, C  =
C.
For C = f(t; x) 2 Rn+1 : t  kxkg,
C  := f(s; y) : (t; x)T (s; y)  0 for all (t; x); t  kxkg:
In paticular, for any (s; y) 2 C  we rst let (t; x) = (1; 0) and have s  0.
Furthermore, let (t; x) = (kyk; y). Then, we must have skyk  kyk2 which
implies s  kyk. Thus, C  = C .
1.6 Consider the convex set C = fx 2 R2 : (x1 1)2 + (x2 1)2  1g
and let y 2 R . Assuming y 62 C ,
2

1. nd the point in C that is closest to y;

2. nd a separating hyperplane vector as a function of y.
Solution 1.6 1.
x := e + ky 1 ek (y e):
2.
a := x y = kyky ekek 1 (e y);
Note that ky ek > 1.
6 CHAPTER 1. INTRODUCTION AND PRELIMINARIES
1.7 Using the idea of Exercise 1.6, prove the separating hyperplane theo-
rem ??.
Solution 1.7 Let
 = min
x2C
ky xk > 0
and x^ 2 C such that ky x^k = . Such a x^ exists since ky xk achieves
its minimum over any closed and bounded set that can be the intersection
of C and the ball of radius  + 1 centered at y.
For any x 2 C and 0    1, the point x^ + (x x^) 2 C and thus
kx^ + (x x^) yk2  kx^ yk2 :
Expanding,
2(^x y)T (x x^) + 2 kx x^k2  0:
Considering the inequality as  ! 0, we have
(^x y)T (x x^)  0
or
(^x y)T x  (^x y)T x^ = (^x y)T (y + x^ y) = (^x y)T y + 2 :
The theorem is proved after setting a = x^ y.
1.8 Given
P an m  n matrix A and a vector c 2 Rn , consider the function
n
B(y) = j=1 log sj where s = c AT y > 0. Find rB(y) and r2 B(y) in
terms of s.
Solution 1.8
rB(y) = eT S AT 1

and
r B(y) = AS AT ;
2 2

where
S = diag(s):
1.9 Prove that the level set of a quasi-convex function is convex.
Solution 1.9 For some z let the level set
L(z ) = fx : f (x)  z g;
where f (x) is a quasi-convex function, i.e., for 0    1
f (x + (1 )y)  max[f (x); f (y)]:
1.1. EXERCISES 7

Suppose x; y 2 L(z ), then

f (x + (1 )y)  max[f (x); f (y)]  z
which implies that x + (1 )y 2 L(z ) and thus L(z ) is a convex set.
1.10 Prove Propositions ?? and ?? for convex functions in Section ??.
Solution 1.10 Since f is a convex function over a convex set
, for any
x; y 2
and 0 <  < 1
f (x + (y x))  (1 )f (x) + f (y):
Thus
f (y) f (x)  f (x + (y  x)) f (x) :
Furthermore, if f 2 C 1 , then from the Taylor expansion theorem we have
for some 0    1
f (x + (y x)) = f (x) + rf (x + (1  )(y x))(y x):
Combining the above two we have
f (y) f (x)  rf (x + (1  )(y x))(y x):
Letting  ! 0+ give the rst result.
If f 2 C 2 , then for any x; y 2
, from the Taylor expansion theorem
there is 0    1 such that
f (y) = f (x) + rf (x)(y x) + (1=2)(y x)T r2 f (x + (1 beta)y)(y x):
From the rst result, we have
(y x)T r2 f (x + (1  )y)(y x)  0:
In particular, for any x 2
let y = x + d 2
for all possible direction
d 6= 0 and  > 0. Then we have
dT r2 f (x + (1  )d)d  0:
Let  ! 0+. Then
dT r2 f (x)d  0;
that is, the Hessian matrix r2 f (x) is positive semi-denite throughout
.
1.11 Prove the Harmonic inequality described in Section ??.
8 CHAPTER 1. INTRODUCTION AND PRELIMINARIES
Solution 1.11 We prove the inequality using mathematical inductiion. It
is clearly true when n = 1. Suppose it is true for n  1. Then,
nX
+1 nX +1
1)
( xj )(
j =1 j =1 xj
X n X n X n
= ( xj )( x1 ) + xn+1 ( x1 )
j =1 j =1 j j =1 j
X n
+( xj )j ) x 1 + 1
j =1 n+1
X n
 n2 + ( xnx+1 + xxj ) + 1
j =1 j n+1
X n
 n +(
2
2) + 1
j =1
= n2 + 2n + 1 = (n + 1)2 :

1.12 Prove Farkas' lemma ?? for linear equations.

Solution 1.12 Let A 2 Rmn and b 2 Rm . If the system fx : Ax = bg
has a solution, say x, then for any y such that AT y = 0 we have
bT y = xT AT y = xT 0 = 0:
On the other hand, if the system has no solution, then b is an exte-
rior point of the convex set fAx : x 2 Rn g. Thus, from the separating
hyperplane theorem there must be a vector y such that
yT b  yT (Ax) = (yT A)x for all x 2 Rn :
Since (yT A)x is bounded from below for all x 2 Rn , we must have yT A = 0.
Hence yT b < 0.
1.13 Prove the linear least-squares problem always has a solution.
Solution 1.13 We need nd an y 2 Rm such that kAT y ck is minimized.
It is sucient to minimize ks ck where s = AT y is in the intersection
of the space fAT y : y 2 Rm g and the ball centered at c with radius kck.
This intersection is a closed and bounded set. Thus, there must exist an
s = AT y such that it is closest to c.
1.1. EXERCISES 9

1.14 Let P = AT (AAT ) 1 A or P = I AT (AAT ) 1 A. Then prove

1. P = P 2 .
2. P is positive semi-denite.
3. The eigenvalues of P are either 0 or 1.
Solution 1.14 1.
P 2 = (I AT (AAT ) 1 A)(I AT (AAT ) 1 A)
= I 2AT (AAT ) 1 A + AT (AAT ) 1 A = I AT (AAT ) 1 A:
2. For any d we have
dT Pd = dT P 2 d = kPdk2  0;
which implies that P is a PSD matrix.
3. Let  be an eigenvalue of P . Then there is a vector v such that
Pv = v. Therefore,
v = Pv = P 2 v = 2 v
or  = 2 . Thus,  is either 1 or 0.
1.15 Using the separating theorem to prove Farkas' lemmas ?? and ??.
Solution 1.15 For proving the rst lemma let A 2 Rmn and b 2 Rm . If
the system fx : Ax = b; x  0g has a feasible solution x, then for any y
such that AT y  0 we have
bT y = xT AT y = xT (AT y)  0:
On the other hand, if the system has no solution, then b is an exte-
rior point of the convex set fAx : x 2 Rn+ g. Thus, from the separating
hyperplane theorem there must be a vector y 6= 0 such that
yT b < yT (Ax) = (yT A)x for all x 2 Rn+ :
Thus, yT b < 0 or bT y > 0. Since ( yT A)x is bounded from below for all
x 2 Rn+ , we must also have yT A  0.
For proving the second lemma let A 2 Rmn and c 2 Rn . If the system
fy : AT y  cg has a solution y, then for any x such that Ax = 0 and x  0
we have
cT x = (c AT y)T x  0:
10 CHAPTER 1. INTRODUCTION AND PRELIMINARIES
On the other hand, if the system has no solution, then c is an exterior
point of the convex set fs : s  AT y for some y 2 Rm g, which contains
all nonnegative vectors. Thus, there is an x 6= 0 such that
xT c < xT s for all s  AT y:
Since xT s is bounded from below, we must have x  0. It must also be true
that Ax = 0, since
xT c < xT AT y for all y 2 Rm :
Moreover, we have cT x < 0.
1.16 If a system AT y  c of linear inequalities in m variables has no
solution, show that AT y  c has a subsystem (A0 )T y  c0 of at most m + 1
inequalities having no solution.
Solution 1.16 If the system AT y  c is infeasible, then we have a certi-
cate x  0 such that Ax = 0 and cT x = 1. Thus, vector (0; 1) 2 Rm+1
is in the cone((a1 ; c1 ); :::; (an ; cn )). Since any basis of these vectors has at
most m + 1 vectors, from Caratheodory's theorem we have
(0; 1) 2 cone((ai1 ; ci1 ); :::; (aid ; cid ))
and d  m +1. Thus its associated subsystem (A0 )T y  c0 is also infeasible,
where A0 = (ai1 ; : : : ; aid ) and c0 = (ci1 ; : : : ; cid ).
1.17 Prove the LP fundamental theorem ??.
Solution 1.17 The proof of (i) can be drawn directly from Caratheodory's
theorem. We include a complete proof here. Suppose 0  x 2 Rn is a
feasible point such that Ax = b, i.e.,
X
n
a:j xj = b:
j =1
Assume that p of the variables xj are positive, and for convenience, that
they are the rst p variables. Thus
X
p
a:j xj = b:
j =1
There are now two cases, corresponding as to whether the set a:1 ; : : : ; a:p is
linearly dependent or not.
1.1. EXERCISES 11

Case I: If the set of vectors is linearly independent. Then, p  m. If

p = m, the solution is basic. If p < m, then since A has rank m, we can
add m p vecrtors, chosen from the remaining a:(p+1) ; : : : ; a:n, to the set
such that the m vectors are linear independent. Assigning the value 0 to the
corresponding m p varaibles yields a (degenerate) basic feasible solution.
Case II: If the set of vectors is linear dependent, then there is d 6= 0 in
the null-space of a:1; : : : ; a:p , i.e.,
X
p
a:j dj = 0:
j =1
Without of loss of generality, let min(d) < 0. Then we can set
x+ = x + d
where  = minfxj =jdj j : dj < 0g such that x+  0 and at least one
component of x+ is zero. Thus, x+ has at most p 1 positive variables.
Repeating this process if necessary, we can eliminate positive variables until
we have the corresponding columns are linearly independent.
The proof of (ii) of the theorem is similar to the proof above. Here we
let x be an optimal feasible solution. Case 1 is identical, while in Case II
we have to show that the objective does not change, i.e., cT d = 0. Since
x + d and x d are feasible solutions for a positive value of . Thus we
have to have cT d = 0 for otherwise x is not optimal.
1.18 If (LP) and (LD) have a nondegenerate optimal basis AB , prove that
the strict complementarity partition in Theorem ?? is
P  = B:
Solution 1.18 Since AB is a nondegenerate optimal basis, we have AB xB =
b and XB > 0 for the primal, and ATB y = cB and cN ATN y > 0. Thus,
(B; N ) is a strictly complementary partition. Since such partition is unique,
we have P  = B .
1.19 If Q is positive semi-denite, prove that x is an optimal solution
for (QP) if and only if x is a KKT point for (QP).
Solution 1.19 A KKT point x of (QP) satises
 x   s 
M y T
0 = q; x s = 0;
12 CHAPTER 1. INTRODUCTION AND PRELIMINARIES
where Q AT
  c 
M= A 0 and q = b :
Let x be any feasible point of (QP), then
A(x x) = 0;
and
q(x) q(x) = 12 xT Qx 1 T T
2 x Qx + c (x x)
= 12 xT Qx 1 T T T
2 x Qx + (s Qx + A y) (x x)
= 12 xT Qx 21 xT Qx + (s Qx)T (x x)
= 12 (x x)T Q(x x) sT x  0:
Thus, x is a minimizer.
Next, let x be a minimizer and let xi = 0 for i = 1; : : : ; t, t  n. Let d
be in the null space of   A
I0
where I is the t  t identical matrix. Withou loss of generality, we assume
that this matrix has full row rank. Then x() = x + d is a feasible point
for (QP) for any      for a suciently small positive . Since
q(x)  q(x()) for any  2 [ ; ], we must have dT (Qx + c) = 0 since
otherwise we can select a small , jj  , such that q(x()) < q(x), a
contradiction. This fact implies that Qx + c is orthogonal to the null space
of the above matrix, or equivalently, Qx + c is in the row space of the matrix,
i.e.,
Qx + c AT y s = 0
for some y 2 Rm and s 2 Rn where si = 0 for i = t + 1; : : : ; n. Thus, we
have xT s = 0.
It remains to be shown that si  0, i = 1; : : : ; t. Suppose not, say st < 0.
Then let d be in the null space of
 A 
I0
where I is the (t 1)  (t 1) identical matrix and satisfy dt > 0. (This
is possible since the above two matrices have full rwo rank and the second
1.1. EXERCISES 13

one is a submatrix of the rst.) Thus, x + d is feasible for any suciently

small  > 0. Note
q(x) q(x + d) = 2 dT Qd sT d
2
= 2 dT Qd s d ;
2 t t
which could be positive for any small  > 0. This contradicts to that x is
the munimizer, since, for a suciently small  > 0, x + d is feasible and
q(x) q(x + d) > 0.
1.20 Show that M of (??) is monotone if and only if Q is positive semi-
denite.
Solution 1.20 Since Q AT

M= A 0 ;
for any vectors (u; v) 2 Rn+m , (u; v)T M (u; v) = uT Qu. Thus, (u; v)T M (u; v) 
0 if and only if uT Qu  0 for any vector u 2 Rn . This implies that Q is
PSD.
1.21 Prove the monotone linear complementarity theorem ??.
Solution 1.21 (i)) First, we prove that if a quadratic function q(x) =
1
2
xT Qx + cT x is bounded from below in a convex feasible region F , then it
must have a nite (local) minimizer. Without loss of generality, we assume
that 0 2 F . Let
q = inf fq(x) : x 2 Fg:
Suppose there is no nite x 2 F such that q(x) = q . Then there is a
sequence fxk 2 Fg, k = 1; : : :, such that kxk k ! 1, q(xk ) > q , and
q(xk ) ! q . Let yk = xk =kxk k and y be a limit point of fyk g. Then,
consider the sequence fk y g where k = kxk k. We must also have k y 2
F , q(k y ) > q , and q(k y ) ! q . But
T 
q(k y) = (y ) 2 Qy (k )2 + (cT y)k
has a nite  to attain its minimal value. That is, there is a nite  such
that q( y) = q , which is a contradiction.
Now consider the monotone LCP problem
(LCP ) minimize xT s
subject to Mx s = q; x; s  0;
14 CHAPTER 1. INTRODUCTION AND PRELIMINARIES
or
(LCP ) minimize xT (M + M T )x=2 + qT x
subject to Mx  q; x  0;
T
where M + M is a positive semi-denite matrix. This is a convex quadratic
minimization problem over a convex polyhedron, and its objective value is
bounded from below by 0. Thus, it has a nite minimizer x which must also
be a KKT point satisfying
yT (Mx + q) + xT ((M + M T )x + q M T y) = 0;
for some y such that
y  0; and (M + M T )x + q M T y  0:
Note that from the last two inequalities
yT q  yT (M + M T )x yT M T y:
Thus,
0  xT (Mx + q) = xT (Mx + q) yT (Mx + q) xT ((M + M T )x + q M T y)
= xT M T x yT q
 xT M T x + yT (M + M T )x yT M T y
= 21 (x y)T (M + M T )(x y)
 0:
That is, we have xT (Mx + q) = 0 which is a solution to the original LCP.
[ii)] Let (x1 ; s1 ) and (x2 ; s2 ) be two solutions for the LCP. We now
prove for any  2 (0; 1), (x1 + (1 )x2 ; s1 + (1 )s2 ) is also a solutin
for the LCP. First, we have
s1 +(1 )s2 = (Mx1 + q)+(1 )M (Mx2 + q) = M (x1 +(1 )x2 )+ q;
and
x1 + (1 )x2  0 and s1 + (1 )s2  0:
Moreover,
0  (x1 + (1 )x2 )T (s1 + (1 )s2 )
= (1 )((x2 )T s1 + (x1 )T s2 )
= (1 )((x1 )T s1 + (x2 )T s2 (x1 x2 )T (s1 s2 ))
 (1 )((x1 )T s1 + (x2 )T s2 )
= 0
1.1. EXERCISES 15

[iii)] Since the number of positive components in x + s of any solution

(x; s) is at most n, the LCP has a maximal complementary solution (x1 ; s1 ).
Let its support be
P 1 = fj : x1j > 0g and Z 1 = fj : s1j > 0:g
Suppose there is another maximal solution (x2 ; s2 ) and it has a dierent
support from (x1 ; s1 ). Since the solution set is convex, (x1 =2+ x2 =2; s1=2+
s2 =2) is also a solution to the LCP. However, the number of positive compo-
nents in x1 =2+ x2 =2+ s1=2+ s2 =2 is more than that in x1 + s1 , contradicting
to that (x1 ; s1 ) is a maximal solutioin.
Pm
1.22 Let P (y ) = C + i yi Ai , where C and Ai , i = 1; : : : ; m, are given
symmetric matrices. Formulate the minimization of the max-eigenvalue of
P (y) as a (PSD) problem. What does its primal problem look like?
Solution 1.22 The problem can be formulated as a PSD
sup t P
subject to tI m
i yi Ai + S = C; S  0:
The primal is
inf C X
subject to I  X = 1; Ai  X = 0; i = 1; 2; :::; m; X  0:
1.23 Prove X  S  0 if both X and S are positive semi-denite matrices.
Solution 1.23 Without losing generality, we may assume that X has an
inverse.
X  S = trXS = trX 1=2XSX 1=2 = trX 1=2 SX 1=2  0:
1.24 Prove that two positive semi-denite matrices are complementary to
each other, X  S = 0, if and only if XS = 0.
Solution 1.24 Let T T T = X where diagonal matrix  contains the
eigenvalues of X and T is its orthonormal eigenvector matrix. Then,
XS = T T T S = T (T T ST )T T :
Thus, X  S =   T T ST . Without losing generality, assume
D 0
= 0 0 ;
16 CHAPTER 1. INTRODUCTION AND PRELIMINARIES
where D is a positive diagonal matrix. Then,
 D(T T ST ) 
T T ST = D 0
0 0
and (T T ST )D is a principle leading submatrix of T T ST . If X  S =
0, then trD(T T ST )D = 0 which implies that every diagonal component
of (T T ST )D is zero. But (T T ST )D is a PSD matrix, so we must have
(T T ST )D = 0. Hence, T T ST = 0 so that XS = 0.
1.25 Prove Farkas' lemma ?? for positive semi-denite programming.
Let Ai 2 Mn , i = 1; :::; m, have rank m, i.e., m
P
Solution 1.25 i yi Ai = 0
implies that y = 0. If there exists a symmetric matrix X  0 with
Ai  X = bi ; i = 1; :::; m;
P y A  0 and Pm y A 6= 0, we have
then for any y such that m i i i i i i
X
m X
m
bT y = yi Ai  X = h yi Ai ; X i < 0:
i=1 i
Otherwise, b is either a boundary or exterior point to the closed cone S :=
fs : si = Ai  X; i = 1; : : : ; m; x  0g. Thus, there is an y 6= 0 such that
X
m
yT b  yT s = h yi Ai ; X i for all X  0:
i
Thus, we must have bT y  0 or bT y  0. Since Pm ytheA right-hand is
bounded from below for all X
P y A 6= 0 since y 6= 0.  0 , we must have i i i  0 . More-
over, m i i i
1.26 Let both (LP) and (LD) for a given data set (A; b; c) have interior
feasible points. Then consider the level set

(z ) = fy : c AT y  0; z + bT y  0g
where z < z  and z  designates the optimal objective value. Prove that
(z )
is bounded and has an interior for any nite z < z , even Fd is unbounded.
Solution 1.26 Let y be an optimal solution and y0 be any interior point
of Fd. Then for any  2 (0; 1], y() = (1 )y + y0 is an interior point.
Let  be suciently small but positive such that bT y() > z . Then, y() is
an interior-point of
(z ).
1.1. EXERCISES 17

Let x0 > 0 be an interior-point of Fp . For any point in

(z ) let s =
c AT y  0. Then,
sT x0 = cT x0 bT y  cT x0 z:
Thus, s must be a bounded vector. Since A has full row rank, y must be
also bounded.
1.27 Given an (LP) data set (A; b; c) and an interior feasible point x0 ,
nd the feasible direction dx (Adx = 0) that achieves the steepest decrease
in the objective function.
Solution 1.27 It is the negative of the projection of c onto the null space
of A:
dx = (I AT (AAT ) 1 A)c:
1.28 Let (LP), (QP) and (LCP) have feasible points (x0 ; y0; s0 ) 2 (Rn+ ; Rm ; Rn+ ),
(x ; y ; s0 ) 2 (Rn+ ; Rm ; Rn+ ) and (x0 ; s0 ) 2 (Rn+ ; Rn+ ), respectively. Ignor-
0 0

ing the nonnegativity condition, write the systems of linear equations used
to calculate the Newton steps for nding points that satisfy the optimality
equations (??), (??), and (??), respectively.
Solution 1.28 For LP
S 0 dx + X 0ds = X 0 s0 ;
Adx = 0;
AT dy ds = 0:
For QP
S 0 dx + X 0ds = X 0 s0 ;
Adx = 0;
AT dy + Qdx ds = 0:
For LCP
S 0 dx + X 0ds = X 0 s0 ;
Mdx ds = 0:
1.29 Similar to our discussion on quadratic programming and linear com-
plementarity, demonstrate that nding a KKT point of a convex nonlinear
programming problem can be reduced to solving a monotone complementar-
ity problem with possible \free" variables.
Solution 1.29 Let the problem be
(NP ) minimize f (x)
subject to Ax = b; g(x)  0;
18 CHAPTER 1. INTRODUCTION AND PRELIMINARIES
where f is convex and g is concave. Then its KKT system can be written
as
minimize z0T s 1 0 1
0 rT f (x) AT y rT g(x)z
subject to @ 0 A = @ Ax b A ; s; z  0:
s g(x)
(1.1)
The Jacobian matrix of the right-hand function is
0 r2f (x) rg (x)z AT rT g(x) 1
@ A 0 0 A;
rg(x) 0 0
which is monotone.
1.30 Show that the ball-constrained linear problem (BP) can be written in
the (BD) form and write the KKT conditions for both of them.
Solution 1.30 Consider

(BP ) minimize cT x
subject to Ax = 0; kxk2  1:
We can let B be the orthornomal basis of the null space of A (AB T = 0
and BB T = I ). Then, x 2 fx : Ax = 0 can be written as x = B T z .
Substituting B T z for x we have
minimize cT B T z
subject to kz k2  1:
The KKT condition for (BP) is
c AT y x = 0; and Ax = 0
and
  0; 1  kxk2 ; and (1 kxk2 ) = 0:
The KKT condition for the latter is
Bc z = 0; 1  kz k; and (1 kz k2) = 0:
1.31 Given a scalar  > 0, a positive diagonal matrix S , and an m  n
matrix A, nd the formula for y 2 Rm such that
minimize eT S 1 AT y
subject to kS 1AT yk2  2 :
1.1. EXERCISES 19

Solution 1.31

y =  (s) (AS 2 AT ) 1 AS 1 e;
d
where
q
d (s) = kS 1 AT (AS 2 AT ) 1 AS 1 ek = eT AT S 1 (AS 2 AT ) 1 AS 1 e:
1.32 Show the optimality conditions for the minimizer y of (BD) in Sec-
tion ??:
(Q +  I )y = b;   0; ky k  1;  (1 kyk) = 0;
and
(Q +  I )  0;
are necessary and sucient.
Solution 1.32 We basically prove these conditions are sucient even when
Q is nonconvex. Let (1 ; x1 ) and (2 ; x2 ) both satisfy these conditions. We
have kx1 k = kx2 k = 1. If 1 > 2 (> 0), then Q + 1 I is positive denite.
Thus,
(Q + 1 I ) 1 (Q + 2 I )x2 = (Q + 1 I ) 1 c = x1 ;
which implies
kx1 k = k(Q+1 I ) 1 (Q+2 I )x2 k  k(Q+1I ) 1 (Q+2 I )kkx2 k < kx2 k = 1;
a contradiction. Similarly, we cannot have 1 < 2 . Thus, we must have
1 = 2 .
We furtherprove q(x1 ) = q(x2 ). If Q + 1I is positive denite, then x1 =
x . Hence we only need to be concerned with the case 1 = jj, where  < 0
2

is the least eigenvalue of Q. Then, for any solution x, kxk = 1 and satisfy
(Q + 1 I )x = c, we have x = v + b where v is a homogeneous solution of
(Q + 1 I )v = 0 and b is the minimal-norm solution with (Q + 1 I )b = c.
Note that b is orthogonal to any homogeneous solution v. Then
q(x) = (v + b)( 12 + 1 I )(v + b)
= 12 1 (kvk2 + kbk2) 12 bT (Q + 1 I )b
= 12 1 12 bT (Q + 1 I )b:
This quantity is independent of v. Thus, q(x1 ) = q(x2 ).