Optimization, Programming Assignment #2
Due Wednesday November 20thNovember 10, 2013

Description
In this assignment, you will experiment with the log-barrier 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 answer
the questions (in particular, talk about what your plots mean)! Your grade will be based far more on this document
than on your source code.

1Log-barrier function

The matlab les objective_quadratic.m, algorithm_gd.m, algorithm_newton.m and line_search_backtracking.mare (lled-in) versions of the quadratic objective, gradient descent, Newton's method, and backtracking line search
implementations of the previous programming assignment.
The function in objective_log_barrier.m takes as parameters an objective function f0 , a constraint function φ(which has the same calling convention as the objective function), a vector x, and a scaling parameter t, and returns
the value, gradient and Hessian of the log-barrier objective:f (x, t)=tf0 (x) + φ (x)Make sure that you understand the contents of all of these les.

1.1

Implementation

The le objective_quadratic_log_barrier.m implements an objective function, and computes the value, gradientand Hessian of:f (x, t)= t

 X
1 Tx Qx + v T x −log (ai,: x + b)
2i

this is the log-barrier objective function f (x, t) = tf0 (x) + φ (x) for a quadratic objective f0 , and log-barrier fuction

φ for the linear constraints Ax + b  0.
Fill in this function.

1.2Experiments

The matlab script main_quadratic.m minimizes a quadratic objective subject to three linear constraints, witht = m, m being the number of constraints, in this case 3 (this is an extremely small value of t), and plots theiterates of gradient descent and Newton's method. What do you observe? Remember that you can zoom in on theplots!
The main_quadratic2.m script plots the number of iterations required by gradient descent and Newton's method
for t between 1/8 and 2 (once more, these are extremely small values of t, but the performance of gradient descentshould give you a clue as to why we didn't use larger t). What do you observe?

12

Log barrier method

2.1

Implementation

One of the most appealing properties of the log-barrier method is that, with constraints of the form fi (x) ≥ 0, andgiven oracle access to each constraint fuction fi and its rst and second derivatives, we may calculate the value, gradient and Hessian of the log-barrier function gi (x) = − log fi (x). The matlab le objective_scalar_constraints.mP
implements this. It takes as parameters a cell array of constraint functions fi and a point x, and returns
i gi (x),
PP 2
∇g(x)
and
∇
g(x)
.
Each
constraintfunction
takesxasaparameter,
andreturns
f(x)
,
∇f(x)
andiiiiii∇2 fi (x).
A cell array is a matlab data structure which may be treated similarly to a matrix. The main dierence is that it
may contain any object (not just scalars), including, as we have already seen, function handles. The notation foraccessing the elements of a cell array is the same as that for matrices, with curly braces substituted for parentheses:
for a one-dimensional cell array a, the ith element is a {i} (instead of a (i), as it would be for a vector), and for a
two-dimensional cell array, the i, j th element is a {i, j}.
Fill in objective_scalar_constraints.m .
The le constraint_quadratic.m implements a constraint function which returns the value, gradient and Hessianof:fi (x)=1 T
x Qx + v T x + c
2

which will be used to implement the constraint fi (x)≥ 0.

This constraint function is almost identical to thequadratic objective functionthe only dierence is the presence of a constant term c.
Fill in constraint_quadratic.m .
The le algorithm_log_barrier.m contains a mostly-complete implementation of the log-barrier method, algorithm
11.1 of Boyd and Vandenberghe. This function takes (among other things) a cell array of constraint functions as aparameter, and constructs the log-barrier objective f (x, t) = tf0 (x)−P

i log fi (x) using objective_log_barrier.m

and your lled-in version of objective_scalar_constraints.m.
Fill in algorithm_log_barrier.m .

2.2

Experiments

The script main_linear.m optimizes a linear program:
minimize: vT xsubject to: ai x ≥ bi

The particular LP which you solve is the personnel scheduling example of:• Hillier and Lieberman. Operations Research. McGraw-Hill. 2005
A description of (and motivation for) this LP may be found on pages 56-58 (eighth edition).
The parameter µ controlls how quickly the log-barrier scaling parameter t changes between inner Newton optimizations. The generated plot shows the total number of Newton iterations performed for a run of the log-barrier
method for various values of µ, and t0 = 1.
Describe the dependence which you expect to see here.
Does the plot meet your expectations?
What is the solution which is found for this LP?

33.1

Matrix constraints (optional)
Implementation

You will now extend the implementation of the log-barrier method to handle matrix constraints of the formfi (x)  0, which constrain the matrix fi (x) to be positive semidenite, rather than constraining the scalar2fi (x) to be nonnegative (for scalars, these notions are equivalent, so in particular your lled-in version of constraint_quadratic.m will continue to work ne, once you've completed this problem).
Becausefi is in general matrix-valued, the gradient and Hessian which are returned by matrix constraintfunctions must return matrix derivatives. We will represent these using three- and four-dimensional matrices, with
the indices chosen such that, for g the 3D matrix of rst derivatives and H the 4D matrix of second derivatives,
2∂
fj,k and Hi,j,k,` = ∂x∂i ∂xj fk,` .
gi,j,k = ∂x
iThe le objective_matrix_constraints.m, analagously to objective_scalar_constraints.m, calculates the value,
gradient and Hessian of the log-barrier function gi (x) = − log |fi (x)| (here,|·| denotes the determinant).

Thedierence from the function which you lled-in earlier is that this one must handle the 3D and 4D matrices ofderivatives returned by matrix constraint functions.
The code makes use of the matlab permute function, which simply permutes the indices of a matrix. For example,
if y= permute (x, [4, 3, 2, 1]), then yi,j,k,l = x`,k,j,i .

You might want to read the matlab documentation of thisfunction (or anything else with which you are unfamiliar).
Fill in objective_matrix_constraints.m .
You may nd it helpful to use the product rule for matrix dierentiation:

dABdx

=dAdB
B+Adx
dx

as well as the following identities:

dlog |A| =dx
dtr (A)
=dx
d −1
A=dx

Atr−1 dA

dx
dAtrdx
dA −1−A−1Adx
The le constraint_sdp.m implements a constraint function which returns the value, 3D matrix of partial rstderivatives, and 4D matrix of partial second derivatives, of:f (x)=A + diag (x)Fill in constraint_sdp.m .
In order to make use of matrix constraints in the log-barrier implementation, you must modify algorithm_log_barrier.mby replacing the call to objective_scalar_constraints with a call to objective_matrix_constraints. Make thischange.

3.2

Experiments

Re-run main_linear.m, using the new version of algorithm_log_barrier.m (which now handles matrix constraints), and ensure that the results are the same as they were when you used the scalar-constraint code path.
Include the plot, and the solution to the LP, in your submission.
You will now optimize an instance of the SDP contained in equation 11.47 (page 603) of Boyd and Vandenberghe:

1T x

minimize:subject to: A + diag (x)  0The matrix A is contained in matrix.csv.
Run main_sdp.m, and report the solution which is found for this SDP.

3