Computational methods in optimization

David Gleich

Purdue University

Spring 2012

Course number CS 59000-OPT

Tuesday and Thursday, 3:00-4:15pm

Lawson B134

Course project

$\newcommand{\eps}{\varepsilon} \newcommand{\kron}{\otimes} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\trace}{trace} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\minimize}{minimize} \DeclareMathOperator{\subjectto}{subject to} \newcommand{\mat}[1]{\boldsymbol{#1}} \renewcommand{\vec}[1]{\boldsymbol{\mathrm{#1}}} \newcommand{\vecalt}[1]{\boldsymbol{#1}} \newcommand{\conj}[1]{\overline{#1}} \newcommand{\normof}[1]{\|#1\|} \newcommand{\onormof}[2]{\|#1\|_{#2}} \newcommand{\MIN}[2]{\begin{array}{ll} \minimize_{#1} & {#2} \end{array}} \newcommand{\MINone}[3]{\begin{array}{ll} \minimize_{#1} & {#2} \\ \subjectto & {#3} \end{array}} \newcommand{\OPTone}{\MINone} \newcommand{\itr}[2]{#1^{(#2)}} \newcommand{\itn}[1]{^{(#1)}} \newcommand{\prob}{\mathbb{P}} \newcommand{\probof}[1]{\prob\left\{ #1 \right\}} \newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}} \newcommand{\spmat}[1]{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)} \newcommand{\sbmat}[1]{\left[\begin{smallmatrix} #1 \end{smallmatrix}\right]} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\eye}{\mat{I}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mF}{\mat{F}} \newcommand{\mG}{\mat{G}} \newcommand{\mH}{\mat{H}} \newcommand{\mI}{\mat{I}} \newcommand{\mJ}{\mat{J}} \newcommand{\mK}{\mat{K}} \newcommand{\mL}{\mat{L}} \newcommand{\mM}{\mat{M}} \newcommand{\mN}{\mat{N}} \newcommand{\mO}{\mat{O}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mT}{\mat{T}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mPbar}{\bar{\mP}} \newcommand{\ones}{\vec{e}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vf}{\vec{f}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vj}{\vec{j}} \newcommand{\vk}{\vec{k}} \newcommand{\vl}{\vec{l}} \newcommand{\vm}{\vec{l}} \newcommand{\vn}{\vec{n}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\vpi}{\vecalt{\pi}}$

The course project is worth 30% of your final grade.

It will involve weekly status reports on

• April 10th
• April 17th
• April 24th

The final project is due May 2nd.

The weekly status reports should be 2-3 pages long and discuss the work you have done that week on the project. They are equally weighted and worth 1/3rd of the project grade in total (i.e. 10% of your final grade). This makes them worth slightly less than a homework (25% of final grade for homework/6 homeworks).

The final project should be 15-20 pages, single spaced, in a readable typeset manuscript. It should describe what you did, why you did itm, and what your results mean or say about your ideas. I like to think of a course report like this as equivalent to “1/3rd” of a research paper. The difference is that you should describe everything you did in the course project, whereas you’d only describe the successful ideas in a paper.

You may collaborate with one, and only one, other person on this project and submit a joint writeup. You must identify this collaborator in your first report. You may not share code, ideas, or discuss with any other project group outside of your partner.

There are three choices for the project.

Project 1: Optimization on the surface of the (hyper)-sphere

A classic problem in physics is: how do charged particles distributed themselves on the surface of the sphere? The case for a 2-sphere – a circle – is simple, the particles appear at equally spaced points. However, for the 3-sphere (the standard sphere), there is no “closed form” solution, and indeed, little to go on besides a few well understood special cases. Finding the global minimum is a particularly tough problem known as the Thompson problem. While the Thompson problem uses the energy term:

$$\frac{1}{\normof{\vx_i - \vx_j}}$$

you should look at the “easier” energy:

$$\frac{1}{\normof{\vx_i - \vx_j}^2}$$

as well as study solutions on higher dimensional spheres. Consequently, the optimization problem is:

$$\MINone{}{\sum_{i \not= j} \frac{1}{\normof{\vx_i - \vx_j}^2} }{ \vx_i \in \RR^{k}, \normof{\vx_i} = 1 \qquad 1 \le i \le n.}$$

Dimensions: $k$ is the dimension of the sphere (k = 3, is the standard sphere. $n$ is the number of points. Consequently, there are $nk$ variables.

In this project, you will study the Thompson problem, as well as the question of: how does a graph embed on a sphere of hypersphere. This problem occurs in a reformulation of the celebrated Goemanns-Williamson SDP-based MAXCUT approximation algorithm as a low-rank SDP. The low-rank SDP is really just an optimization problem on the surface of the sphere. See fixing two weakenesses of the spectral method for an example of why this is interesting. Also seek some notes that I wrote out this http://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202006%20-%20wom.pdf (Section 4.3). For these problems, we may also need the additional constraint that all the points are distinct. This usually corresponds to a constraint such as $\mX^T \ve = 0$.

Both of these problems have the following type of objective function:

$$\MINone{}{f(\vx_1, \ldots, \vx_n)}{\vx_i \in \RR^{k}, \normof{\vx_i} = 1 \qquad 1 \le i \le n.}$$

Each $\vx_i$ represents the coordinates of the $i$h charge or node in the graph. As a shorthand, we can place all of these variables into a $k \times n$ matrix as follows:

$$\mX = \bmat{ \vx_1 & \vx_2 & \cdots & \vx_n }.$$

Using this shorthand, note that the objective and constraint are now:

$$\MINone{}{f(\mX)}{\mX \in \RR^{k \times n}, \diag( \mX \mX^T) = \ve}.$$

Possible project approaches:

1) Focus on large scale objectives

2) Focus on highly accurate solutions

3) Focus on convex reformulations

4) Focus on solving a sequence of relaxed constraints

5) Focus on a large number of nodes/molecules

6) Focus on high dimensional problems, n ~ k, and k large.

7) Investigate optimization software on the full constrained problem.

8) Studying the local minima computed via different typed of structured initial conditions.

9) Trying to find the best points possible.

10) Formulate a homotopy method or a multi-resolution approach for the problem.

11) Study augmented Lagrangian methods.

Your goal is to say SOMETHING about the project. That is, you must go beyond just using an optimization software package to solve the objectives (although, that’s “good enough” for a B.)

Project 2: An interior point LP solver

Throughout the class, we’ve stressed (when possible) some of the details that make real optimization software run. In this project, you’ll be responsible for implemeting the most robust interior point LP solver you can.

You should read about interior point solvers in Primal-dual interior-point methods by Stephen J. Wright, SIAM 1997.

You must do this in Matlab. (If you don’t think this will be appropriate, let me know and we can discuss alternatives, but you must do so by April 15th.)

There is less flexibility here, but two focuses are:

1) Focus on robustness (solve all the problems)

2) Focus on speed (don’t solve everything, but be very fast when you do solve it.)

The test problems all come from the University of Flordia Sparse Matrix repository: http://www.cise.ufl.edu/research/sparse/matrices/LPnetlib

• LPnetlib/lp_afiro
• LPnetlib/lp_25fv47
• LPnetlib/lpi_chemcom (this one is infeasible!)

These matrices can be downloaded using the UFget.m file in Matlab.

Specific requirements

Your code must be written in the spirit of reproducible research. The final evaluation will take into account my ability to download and run your code. Also, I will evaluate it on additional problems from the LPnetlib collection and compare the solutions against the Clp simplex code.

Project X: Your own research

These projects are discouraged, but if there is a natural fit between your research and the objectives of the class, you may propose a project. In your proposal (to me), you must detail what you plan to do, how it compares with Project 1 and 2.

No collaboration will be allowed on project on your own research.