Optimization, Programming Assignment #1
Due Monday October 28thOctober 15, 2013

Description
In this assignment, you will experiment with gradient descent, conjugate gradient, BFGS and Newton's method.
The included archive contains partial matlab code, which you must complete. Areas that you will ll in are marked
with TODO comments.
You should turn in an archive containing all of your source code, and a document containing all plots, and answers
to underlined questions.
Please remember to turn in a complete and readable document which contains your plots, and in which you answerthe questions (in particular, talk about what your plots mean)! Your grade will be based far more on this document
than on your source code.

This problem set draws heavily from the following text, although everything you need should also be present inyour class notes:• Jorge Nocedal and Stephen Wright. Numerical Optimization. Springer, 1999.

1Algorithms

The BFGS algorithm (algorithm 8.1 of Nocedal and Wright), and an exact line search (using the bisection method)
are implemented in algorithm_bfgs.m and line_search_bisection.m, respectively. You should understand thecontents of these les (refer to your class notes on BFGS).

1.1

Backtracking line searchComplete the implementation of the backtracking line search in line_search_backtracking.m. This is algorithm
9.2 of Boyd and Vandenberghe.

1.2

Gradient descent and Newton's method

Complete the implementations of gradient descent and Newton's method in algorithm_gd.m and algorithm_newton.m.
Gradient descent is algorithm 9.3 of Boyd and Vandenberghe, and Newton's method is algorithm 9.5. Your imple-2

mentation of gradient descent should terminate once k∇f (x)k2 ≤ , and your implementation of Newton's methodshould terminate once the squared Newton decrement λ1.32T∇2 f (x)(x) = (∇f (x))

−1(∇f (x)) satises λ2 (x) ≤ .

Conjugate gradient

There are several dierent ways in which the linear conjugate gradient algorithm can be modied to work on a
non-quadratic function, all of which are equivalent for a quadratic objective. Algorithm 1 contains pseudocode for
the Fletcher-Reeves method. In your written assignment, you encountered the Polak-Ribière method, which diers(k+1)

from Fletcher-Reeves in the calculation of β , where βP RT=(∇f (x(k+1) )) (∇f (x(k+1) )−∇f (x(k) )).
T(∇f (x(k) )) ∇f (x(k) )Pay special attention to lines 8 and 9. These lines restart the conjugate gradient algorithm every m steps (wherem is the dimension of the problem), since by setting βF R = 0, the search direction ∆x will be set to the negative1

Algorithm 1 Pseudocode for the Fletcher-Reeves conjugate gradient method (algorithm 5.4 of Nocedal and Wright)

ConjugateGradient x(0),m ← dim x(0)∆x(0) ← −∇f x(0)k←0Loopt(k) ← line_search f, x(k) , ∆x(k)x(k+1) ← x(k) +t(k) ∆x(k)2
If ∇f x(k+1) 2 ≤  then terminate
If k + 1 ≡ 0 mod m then(k+1)βF R←0ElseT(∇f (x(k+1) )) ∇f (x(k+1) )T(∇f (x(k) )) ∇f (x(k) )(k+1)∆x(k+1) ← −∇f x(k+1) + βF R ∆x(k)k ←k+1(k+1)βF R←gradient on line 12, eectively causing the algorithm to start over from the current location. Nocedal and Wrightmotiviate restarting with the following intuition: because the conjugate gradient method converges in m iterations
for a quadratic objective, if we assume that there is some neighborhood of the optimum in which the objective isvery close to being quadratic, then provided that we start over at some point once we've entered this region, wewill converge to the optimum m iterations later.
It is also worth noting that it is not obvious that ∆x will always be a descent direction. In fact, while it is possible
to guarantee this property by placing certain conditions (called the strong Wolfe conditions) on the line search,
backtracking line search does not satisfy them (algorithm 3.2 of Nocedal and Wright is an example of a line searchwhich does). In practice, at least on this homework, this is not an issue, but it's something to keep in mind.
Complete the implementation of the Fletcher-Reeves conjugate gradient method by lling in algorithm_cg.m .

1.4

Quadratic objectiveThe matlab script main_quadratic.m creates a contour plot for the following objective (contained in objective_quadratic.m):

f (x)

1 T
x Qx + v T x
2=for:

10



00

Q =v

=030




and overlays this contour plot with the iterates of each of our four algorithms, using exact line search, starting from:

x0

=40.3



How many iterations does each algorithm take to converge?
Why do conjugate gradient, BFGS and Newton take this number of iterations?
What is the relationship between consecutive directions in gradient descent, conjugate gradient and BFGS?
Play around with dierent values of Q and v , and explore the impact of various choices on the performance ofgradient descent. Describe your results.

2

1.5

Sum-exp objective

The matlab script main_sum_exp.m creates a contour plot for the following objective (contained in objective_sum_exp.m):f (x)X=exp aTi x + biifor ai and bi chosen as in equation 9.20 (pg 470) of Boyd and Vandenberghe. It then overlays this contour plot withthe iterates of each of our four algorithms, using backtracking line search with α = 0.4 and β = 0.9. Describe theperformance of the four algorithms (it may be helpful to zoom in on the region of the plot containing the optimum).

2

Logistic regression

Suppose that we have a list of feature vectors xi ∈ Rnand corresponding class labels yi ∈ {−1, 1}. We will assume

that the log-odds of a sample being in each of the two classes are a linear function of X . That is, that:log

P (Y = 1 | X)
P (Y = −1 | X)

wT X=(1)This assumption, combined with the fact that probabilities must sum to one, gives that:
TP (Y | X)

=eY w X
1 + eY w T X

We will nd a weight vector w which maximizes the log-likelihood of the data under the assumption that the labels
are conditionally independent given the features:

L (w | x, y)

=logn
Y

P (Y = yi | X = xi )i=1=n 
X
Tyi wT xi − log 1 + eyi w xi

(2)

i=1
You may wish to derive equation 2 from equation 1, but this is optional.
For more on logistic regression, refer to:• Trevor Hastie, Robert Tibshirani and Jerome Friedman. The Elements of Statistical Learning. Springer,
2001.

2.1

Convexity, gradient and Hessian

Maximizing the log-likelihood in the logistic regression model is clearly equivalent to the following:

minimize:n XT−yi wT xi + ln 1 + eyi w xi

i=1z

Prove that this function is convex (hint: start out by proving that ln (1 + e ) is convex as a function of z , and thenuse the results from section 3.2 of Boyd and Vandenberghe).
Calculate the gradient and Hessian (with respect to w ) of this objective function.
Fill in objective_logistic.m with this objective function, and the gradient and Hessian which you just calculated.

2.2Experiments

You are provided with two synthetic datasets for logistic regression: logistic_small.csv, which contains one thousand 10-dimensional examples, and logistic_large.csv, which contains one thousand 50-dimensional examples. The3matlab script main_logistic.m loads one of these les, and plots the log-suboptimality versus the elapsed runtime
for each of the four algorithms, using backtracking line search with α = 0.4 and β = 0.9. Plot the performance of
the algorithms for both datasets.
Which algorithms perform better on the low-dimensional dataset than on the high?
Can you explain this behavior?
Modify the script to plot the iteration number, rather than elapsed time, on the horizontal axis. Plot the performanceof the algorithms for both datasets.
What happens to the apparent relative performance of the algorithms?
Recall the denitions of linear and quadratic convergence. Imagine that we plot log-suboptimality against iteration
number for an ideal algorithm which exhibits linear convergence.
What should be the shape of the plot?
What about for quadratic convergence?
What does this tell you about the empirical rates of convergence of the four algorithms, on logistic_large.csv ?

3

Play around (optional)

Experiment on these objectives (or any others you are interested in) with:dierent settings of the line searchparameters, dierent line search algorithms (algorithm 3.2 of Nocedal and Wright would be a good choice), ordierent variants of the nonlinear conjugate gradient algorithm (Polak-Ribière, for example). Try repeating problems
1.4 and 1.5 with dierent choices of parameters (Q, v , ai and bi ) for the objective functions. Report your results
and conclusions.

4