Convex Optimization
Problem set 2
Due Monday November 4th

1

Gradent Decent without Linesearch

In this problem we will consider gradient descent with predetermined step sizes. That is, insteadof determining t(k) by a linesearch method using the objective function, the current iterate x(k) andthe descent direction 4x(k) , it will be set to some pre-determined sequence.
1. For a strongly convex twice-continuously differentiable function f (x) with bounded Hessian, mI 4 ∇2 f (x) 4 M I, κ = M/m, consider gradient descent with a fixed step sizet(k) = M1 . Prove that with this step size, after
k=
log

1


1
1
1− κ


 log

f (x(0) ) − p∗



(1)

iterations, x(k) will be -suboptimal.
How many gradient evaluations are performed to reach an -suboptimal solution? How many
function evaluations?
2. The above choice of step-size requires knowing beforehand a bound on the Hessian. You
will now show that the choice of a fixed (equal for all iterations) stepsize must depend on thefunction (or at least on the magnitude of its Hessian).
For any t, show a twice-continuously differentiable strongly convex function f (x) withbounded Hessian, and an initial point x(0) such that gradient descent with fixed stepsizet(k) = t starting at x(0) yields a sequence of iterates that does not converge to the optimum.
Note that we requrie the Hessian be bounded, i.e. there exists some M s.t. ∇2 f (x) 4 M I
for all x, but the bound M will of course depend on t.
Hint: it is enough to consider scalar (one-dimensional) quadratic functions.
3. If we do not know in advance a bound on the Hessian, we can use a predetermined decreasing
sequence of step-sizes t(k) . Consider a strongly convex twice-differentiable function f :1

Rn → R with bounded Hessian, mI 4 ∇2 f (x) 4 M I. Prove that for any predeterminedsequence of step-sizes obeying
(k)

lim t

k→∞

= 0 and∞Xt(k) = ∞,

(2)

k=0

gradient descent on f (·) with steps of sizes t(k) converges to the optimal value: limk→∞ f (x(k) ) =inf x f (x).
2

Hint: first establish that for large enough k, f (x(k+1) ) ≤ f (x(k) ) − 21 t(k) ∇f (x(k) ) . Next
bound the norm of the gradient in terms of the suboptimality. Now establish that for any ,
we will reach an -suboptimal point after a finite number of iterations.
Note that the choice of step-sizes does not depend on the function or on the magnitude of the
Hessian, and so we can run the method without prior knowledge of a bound on the Hessian.
However, the number of iterations required to reach an -suboptimal solution will depend on
the magnitude of the Hessian.
4. [Extra Credit] Can you bound the number of iterations needed to reach an -suboptimal
solution using the method above? The bound will depend on the Hessian of the function,and on the specific choice of stepsize sequence. Can you suggest a predetermined sequenceof stepsizes, that does not depend on the function to be optimized, and results in an iteration
bound very similar to (1)? This will estbalish that at least from a theoretical worst-caseperspective, the line-search is not really necesairy and we can get similar gurantees evenwith predetermined stepsizes.

2

Newton’s Method
1. In this question we will formaly prove the affine invarience of Newton’s method. Consider
a function f : Rn → R and an affine transform y ∈ Rm 7→ Ay + b where A ∈ Rn×m andb ∈ Rn . Define g(y) = f (Ay + b).
(a) For x = Ay + b, let 4x and 4y be the Newton steps for f (x) and g(y) respectively.
Prove that 4x = A4y.
(b) Prove that for any t > 0, the exit condition for backtracking linesearch on f (x) in
direction 4x will hold if and only if the exit condition holds for g(y) in direction 4y.
(c) Consider running Newton’s method on g(·) starting at some y (0) and on f (·) starting at
x(0) = Ay (0) + b. Use the above to prove that the sequences of iterates obeys x(k) =Ay (k) + b and f (x(k) ) = g(y (k) ).
(d) Prove that Newton’s decrement for f (·) at x is equal to Newton’s decrement for g(·) aty, and so the stopping conditions are also identical.

2(e) Now consider a function h(x) = cf (x) for some scalar c > 0. Prove that the Newton search directions 4x and step sizes are the same when optimizing h(·) and f (·).
Conclude that the sequence of Newton iterates is the same when optimizing h(·) orf (·).
(f) Will the Newton decrement and the stopping condition also be the same for h(·) andf (·)?
2. We defined self-concordance of a scalar function using the condition |f 000 (t)| ≤ 2(f 00 (t))3/2 .
The constant 2 in this definition is arbitrary, and this definition depends on the scaling of thefunction f (t). In this problem, we will consider r-self concordant functions.
For r > 0, we say that a convex scalar function is r-self concordant iff for all t:|f 000 (t)| ≤ r(f 00 (t))3/2
We say f : Rn → R is r-self concordant if t 7→ f (x + tv) is r-self-concordant for all
x, v ∈ Rn .
(a) First, establish that r-self-concordancy is afine invarient. That is, if f (x) is r-self concordant, then g(y) = f (Ay + b) is also r-self concordant.
(b) Show that f (t) = − log t is self-concordant under the simpler definition, but f (t) =− 21 log t is not. For what value of r is it r-self concordant?
(c) What functions are r-self concordant for all r > 0?
(d) If a function f (·) is r-self concordant, for what scaling constant c > 0 is the functionsf˜(x) = cf (x) self-concordant under the simpler definition?
(e) Consider unconstrained minimization of a strictly convex function f (·) that is r-selfconcordant. Provide a bound on the suboptimality f (x) − p∗ in terms of r and the
Newton decrement λ(x), for small enough values of λ(x) (be sure to specify for whatvalues of λ(x) the bound is valid). (See Section 9.6.3 of Boyd and Vandenberghe.
Hint: how do the suboptimality and the Newton decrement scale when the function isscaled?).
(f) Provide a bound on the number of iterations needed to reach an -suboptimal solution
using Newton’s method for a r-self concordant function. (Hint: Establish that the
Newton iterations, that is both the search direction and the line are invarient to scaling

3

Steepest DescentIn this problem, we will define the direction of Steepest Descent with respect to a norm, andinvestigate it for several specific norms. For a norm k·k on Rn , a direction of steepest descent of3

f : Rn → R at x with respect to k·k is given by:def

4x = arg min ∇f (x)T v = arg min lim
kvk=1 t→0

kvk=1

f (x + tv) − f (x)tf (x + tv) − f (x)= lim arg min f (x + v)
t→0
kvk=1
kvk=t
t

≈ lim arg min
t→0

where the ≈ should be interpreted only as an intuitive correspondence, and so the second line
only as a rough intuition (e.g. the arg min might have multiple minimizers, making the limit notproperly defined. It is even possible that some directions of steepest descent, as defined by the
first line, are not the limit point for any sequence of minimizers in the second line). But roughly
speaking, 4x is the direction v in which the greatest decrease in f (x) can be achieved subject toan infinitesimally small constraint on kvk.
A steepest descent method uses the direction of steepest descent as a descent direction at each
iteration, taking a step in this direction with a stepsize chosen by some linesearch method.
1. Show that the direction of steepest descent for the Euclidean `2 norm is 4x = −∇f (x), andthus steepest descent with respect to the Euclidean norm is just gradient descent.
2. For H  0, consider the norm kxk = xT Hx. What is the direction of steepest descent withrespect to this norm?
P
3. What are the directions of steepest descent with respect to the `1 norm kxk =i |xi | ?
Explain how to find these directions, and think of how a steepest descent method w.r.t. the`1 norm would proceed.
4. What are the directions of steepest descent with respect to the `∞ norm kxk = maxi |xi | ?
Explain how to find these directions, and think of how a steepest descent method w.r.t. the`∞ norm would proceed.

4

Conjugate Direction Methods

Recall that v (1) , . . . , v (k) ∈ Rn are H-conjugate iff for every i 6= j we have v (i)That is, ṽ (i) = H 1/2 v (i) are orthogonal.

4.1

T

Hv (j) = 0.

Conjugate Direction Minimization of a Quadratic Objective

Let f (x) = 21 xT Hx − bT x, with H positive semi-definite, be a convex quadratic objective. Let∆x(0) , . . . , ∆x(n−1) be non-zero H-conjugate directions. Consider iterative minimization along
these directions, starting from some x(0) :1. For i = 0 to n − 12.

t(i) ← arg mint f x(i) + t∆x(i)3.

x(i+1) ← x(i) + t(i) ∆x(i)4

4.1.1
Prove that:t(i) =∆x(i)T

Hx(i) − bT(∆x(i) ) H∆x(i)4.1.2
The principal result about conjugate directions is that the current point x(k) at each step k of themethod above minimizes the quadratic objective f (x) over the k-dimensional affine subspacespanned by ∆x(0) , . . . , ∆x(k−1) . That is:x(k) = arg min f (x)

(3)

x∈M k

where

(
Mk =

x | x = x0 +

k−1
X

)
βi ∆x(i) , βi ∈ R

i=0Prove equation (3):T
T
1. Show that for all i < k: ∇f x(k) ∆x(i) = ∇f x(i+1) ∆x(i) . (Hint: write x(k) in termsof x(i+1) , t(i+1) , . . . , t(k−1) and ∆x(i+1) , . . . , ∆x(k−1) )
T

(k) T
2. Show that ∇f x(i+1) ∆x(i) = 0. Conclude
that
∇f
x
∆x(i) = 0 for i < k. (Hint:Consider the derivative of f x(i) + t∆x(i) with respect to t).
P(i)with respect to βi .
3. Prove equation (3) by considering the derivatives of x0 + k−1
i=0 βi ∆x

4.2

Generating Conjugate Directions

Let ∆x(0) , . . . , ∆x(k−1) be H-conjugate and d a non-zero vector which is not spanned by ∆x(0) , . . . , ∆x(k−1) .
Let
k−1
X
dT H∆x(i)(k)∆x = d −∆x(i)(4)(i) )T H∆x(i)
(∆x
i=0
4.2.1
Prove that ∆x(0) , . . . , ∆x(k) are H-conjugate and that they span the same subspace as ∆x(0) , . . . , ∆x(k−1) , d.

4.3

The Conjugate Gradient Method for a Quadratic Function

In the conjugate gradient method for a quadratic function f (x) = 12 x0 Hx − b0 x, each iteration
starts with the negative gradient d = −∇f (x) and applies equation (4) to obtain only the part of dthat is conjugate to all previous directions:51. For i = 0 to n − 12.

d(i) = −∇f x(i)3.

If d(i) = 0 then terminate4.

Calculate ∆x(i) using equation (4)

5.

(i)

t

6.

x(i+1) ← x(i) + t(i) ∆x(i)T(∆x(i) ) (Hx(i) −b)=T(∆x(i) ) H∆x(i)4.3.1
Explain why after running the above method, if the method does not terminate early, than x(n) is
an optimal point. If the method does terminate early, the last iterate is an optimal point.
4.3.2
The key to the conjugate gradient method is that the calculation of the direction ∆x(i) can begreatly simplified. In particular, we have:∆x(k) = d(k) + β (k) ∆x(k−1)
with
β

(k)

=

d(k)

T

d(k)

d(k−1) d(k−1)

(5)

(6)

Prove equation (5):
1. Prove that d(k) is orthogonal to ∆x(0) , . . . , ∆x(k−1) and hence also to d(0) , . . . , d(k−1) . (Hint:
Use the partial optimality property given in equation (3)).
2. Show that t(i) H∆x(i) = d(i) − d(i+1) . (Hint: expand the gradients and consider the update
rule for x(i+1) ).
T
3. Using the above relation and the orthogonality of d(0) , . . . , d(k) , evaluate d(i) H∆x(j) for
j < i. (Hint: For all but one value of j, this will be zero).
T
4. Similarly, evaluate ∆x(j) H∆x(j) .
5. Substitute the above two relations into equation (4) and obtain equation (5), with β (k) expressed in terms of d(k) , d(k−1) and ∆x(k−1) . Now, show that β (k) can be calculated as inequation (6) by expanding ∆x(k−1) using equation (5), the orthogonality of d(k) and d(k−1)
and the orthogonality of ∆x(k−2) and d(k) − d(k−1) .

6

This concludes the proof of equations (5) and (6). We will actually prefer a slightly different
form of equation (6):
T (k)d − d(k−1)
d(k)
(k)
β =
(7)
d(k−1) d(k−1)
6. Show that equation (7) is also valid and equivalent to equation (6) (when minimizing aquadratic function with exact line search).
Each iteration of the method therefore requires only vector-vector operations with computational
cost O (n), once the gradient has been computed. For a quadratic function, the most expansive
operation is therefore computing the gradient which takes time O (n2 ).

5

Optional: Quasi-Newton Methods

You are not require to do this problem. It provides additional detail about BFGSIn quasi-Newton methods the descent direction is given by:∆x(k) = −D(k) ∇f x(k)In the exact Newton method, the matrix D(k) is the inverse Hessian. Quasi-Newton methods avoid
calculating the Hessian and inverting it by updating an approximation of the inverse Hessian using
the change in the gradients. For a quadratic function, the change in gradient is described by:
q (k) = ∇2 f p(k)where p(k) = x(k+1) − x(k) and q (k) = ∇f x(k+1) − ∇f x(k) . We therefore seek an approximation D(k) to the inverse Hessian that approximately satisfies:p(k) ≈ Dq (k)The Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton method updates D(k) by making the smallest change, under some specific weighted norm, that agrees with the latest change in
the gradient: 1(8)
D(k+1) = arg min
W 1/2 D − D(k) W 2
p(k) =Dq (k)where kAkF =

qP

F

(k)
2
= W p(k) .
ij Aij is the Frobenius norm and W is any matrix such that q

5.1
Show that the solution of equation (8) is given by:D(k+1) = D(k) +p(k) p(k)
(k) T

T

(p ) q (k)−D(k) q (k) q (k)
(q
7

(k) T

T

D(k)

) D(k) q (k)+ τ (k) v (k) v (k)

T

(9)

where τ (k) = q (k)TD(k) q (k) , and:
v

(k)

p(k)

D(k) q (k)
=
−
T
τ (k)
(p(k) ) q (k)The BFGS method is therefore given by (ignoring the stopping condition):
1. Start from some x(0) and an initial D(0)2. For i ∈ {0, 1, 2, . . .}

3.

∆x(i) ← −D(i) ∇f x(i)4.

t(i) ← arg mint f x(i) + t∆x(i)5.

x(i+1) ← x(i) + t(i) ∆x(i)6.

Calculate D(i+1) according to equation (9)

5.2
We now consider applying BFGS to a quadratic objective f (x) = 21 x0 Hx − b0 x with x ∈ Rn andH positive definite.
5.2.1
Show that for all i < k ≤ n we have D(k) q (i) = p(i) . That is, for a quadratic objective, theapproximate inverse Hessian matches all the changes in the gradient so far. Conclude that D(n) =H −1 , i.e. after n iterations the correct Hessian is recovered.
5.2.2
Show that ∆x(0) , . . . , ∆x(n−1) are H-conjugate.
5.2.3
Show that with D(0) = I, the sequence of iterates x(i) generated by BFGS is identical to thosegenerated by the conjugate gradient method described above. It is important to note that this holds
only for a quadratic objective, and when exact line search is used. For non-quadratic objectives, orwhen approximate line search is used, the two methods typically differ.

8