Convex Optimization
Problem set 4
Due Friday November 29th
1. Consider the quadratic program:
1 0x Qx + c0 x
2s.t. Hx ≤ gAx = bminimize(QP)

where Q ∈ Sn , H ∈ Rm×n , g ∈ Rm , A ∈ Rp×n and b ∈ Rp .
(a) Write down the KKT conditions for (QP), with the complimentary slackness constraint
relaxed to a centering constraint with parameter t, as in the central path and primal-dual
interior point methods.
(b) Consider the Newton iterations when using the central path method to solve the quadraticprogram. Using the relaxed KKT conditions you wrote, explicitly derive the linear
equations defining the Newton search direction 4x, as a function of the current iterate
x and the centering parameter t. Explain how these can be obtained from the relaxed
4x
KKT conditions. Write the equations explicitly as M= v with an explicit matrixν
M and vector v.
(c) Now consider using the primal-dual interior point method presented in class. Write
down the linear equations defining the search direction (4x, 4λ, 4ν) as a function ofthe current
iterate (x, λ, ν) and the centering parameter t. Write the equations explicitly 
4x
as M 4λ = v with an explicit matrix M and vector v.
4ν
2. Consider the primal-dual method presented in class and let (x(k) , λ(k) , ν (k) be the iterates
obtained at each iteration of the method. Recall that as in the central-path method, theprimal and dual inequality constraints are maintained at each iteration, and we have:fi (x(k) ) < 0and(k)λi>0for all i at every iteration k. However, the primal equality constraints can be violated, allowing us to start at an infeasible starting point, and the dual objective g(λ(k) , ν (k) ) might1

be infinite, i.e. (λ(k) , ν (k) ) might be dual infeasible. In this question we will investigate theprimal and dual feasibility of the iterates.
(a) Prove that if some iterate x is primal feasible, then the next iterate x+ will also beprimal feasible. Conclude that if some iterate x(k) is primal feasible then all subsequent
0iterates x(k ) , k 0 > k, will also be primal feasible, and in particular if we start from aprimal feasible point x(0) , we never loose primal feasibility.
(b) Recall that at each iteration of the primal-dual method we calculate a search direction(4x, 4λ, 4ν) by solving the linearized KKT conditions, and then take a step witha step-size determined by backtracking line-search. Prove that regardless of the feasibility of the iterate x, if we take a step with step-size one, then the new iterate x+
will be primal feasible (this happens if the initial step-size choice of one satisfies thebacktracking line-search exit condition, as in the quadratic convergent phase of Newton’s method, and it also satisfies the inequality constrains fi (x) < 0 and λi > 0).
That is, even if we start at an infeasible point, after taking a step with step-size one, allsubsequent iterations will be primal feasible.
(c) Now consider the primal-dual method applied to the quadratic programing problem(QP). Prove that after a step with step-size one is taken, and in all subsequent iterations,the dual point (λ, ν) is feasible, i.e. g(λ, ν) if finite. (Hint: prove that after such a step,∇x L(x, λ, ν) = 0 and use this to obtain an explicit expression for g(λ, ν)).
(d) What changes if the problem has a non-quadratic objective or non-linear constraints?
Will (λ, ν) still be dual-feasible after a step with step-size one? Why or why not? If
the dual-feasibility residual is zero for some iterate, rdual (x, λ, ν) = 0, will it stay zero?
Why or why not?
3. Multi-Criterion Optimization Consider the dual-criterion problem:
minimize F1 (x), F2 (x)s.t. fi (x) ≤ 0 i = 1, . . . , m,(M)and for any b ∈ R consider the constraint problem:
minimize F1 (x)s.t. fi (x) ≤ 0 i = 1, . . . , m.
F2 (x) ≤ b(Mb )(a) Is (Mb ) always feasible?
(b) Is every optimum of (Mb ), for every b ∈ R, Pareto optimal? Prove your answer orprovide a counterexample.
(c) Is every Pareto optimal point an optimum of (Mb ) for some b ∈ R? Prove your answer
or provide a counterexample.

2