Computational methods in optimization

David Gleich

Purdue University

Spring 2012

Course number CS 52000

Tuesday and Thursday, 12:00-1:15pm

Lawson 1106

Homework 3

$\newcommand{\eps}{\varepsilon} \newcommand{\kron}{\otimes} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\trace}{trace} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator*{\minimize}{minimize} \DeclareMathOperator*{\maximize}{maximize} \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{\MINthree}[5]{\begin{array}{ll} \minimize_{#1} & {#2} \\ \subjectto & {#3} \\ & {#4} \\ & {#5} \end{array}} \newcommand{\MAX}[2]{\begin{array}{ll} \maximize_{#1} & {#2} \end{array}} \newcommand{\MAXone}[3]{\begin{array}{ll} \maximize_{#1} & {#2} \\ \subjectto & {#3} \end{array}} \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}} \newcommand{\vlambda}{\vecalt{\lambda}}$

Please answer the following questions in complete sentences in a typed manuscript and submit the solution to me on blackboard on February 1st, 2012, by 5pm.

Homework 3: Optimality and Constraints

• Version 2: 2013-01-28 – check problem 1 parts 5 and 6 for some clarifications

Problem 0: List your collaborators.

Please identify anyone, whether or not they are in the class, with whom you discussed your homework. This problem is worth 1 point, but on a multiplicative scale. (Note that collaboration is not allowed on the bonus question below.)

Problem 1: Optimization software and optimality

We’ll be frequently using software to optimize functions, this question will help familiarize you with two pieces of software: Poblano and the Matlab optimization toolbox.

The function we’ll study is the Rosenbrock function:

$$f(x) = 100(x_2 - x_1^2)^2 + (1-x_1)^2.$$

I briefly talked about this function in class and called it the banana function. Now it’s your turn to look at it!

1. Show a contour plot of this function

2. Write the gradient and Hessian of this function.

3. By inspection, what is the minimizer of this function? (Feel free to find the answer by other means, e.g. looking it up, but make sure you explain why you know that answer must be a global minimizer.)

4. Explain how any optimization package could tell that your solution is a local minimizer.

5. Use Poblano to optimize this function starting from a few different points. Be adversarial if you wish. Does it always get the answer correct? Use a table or figure to illustrate your findings if appropriate. Show your code to use Poblano. Your code should have comments to explain what it is doing and you should explain any difficulties in implementing this test.

6. Read about Matlab’s fminunc function and determine how to provide it with Hessian and Gradient information. Use this toolbox to optimize the function starting from a few different points. Show your code to use this function and explain any differences (if any) you observe in comparison to using Poblano.

Problem 2: Log-barrier terms

The basis of a class of methods known as interior point methods is that we can handle non-negativity constraints such as $\vx \ge 0$ by solving a sequence of unconstrained problems where we add the function $b(\vx; \mu) = -\mu \sum_i \log(x_i)$ to the objective. Thus, we convert

$$\MINone{}{f(\vx)}{\vx \ge 0}$$

into

$$\MIN{}{f(\vx) + b(\vx; \mu).}$$

1. Explain why this idea could work. (Hint: there’s a very useful picture you should probably show here!)

2. Write a matrix expression for the gradient and Hessian of $f(\vx) + b(\vx; \mu)$ in terms of the gradient vector $g(\vx)$ and the Hessian matrix $\mH(\vx)$ of $f$.

Problem 3: Do constraints always make a problem hard?

Let $f(\vx) = (1/2) \vx^T \mQ \vx - \vx^T \vc$. Recall that if $\mQ$ is positive-semi-definite than $f(\vx)$ is convex.

1. Construct and illustrate an example in $\RR^{2}$ to show that that $f(\vx)$ is non-convex if $\mQ$ is indefinite.

2. Now, suppose we consider the problem:

$$\MINone{}{f(\vx)}{\mA \vx = \vb.}$$

For this problem, show that any local minimizer is a global solution, even if $f(\vx)$ is non-convex.

1. Is there always a local minimizer? Prove that there is, or show a counter-example. (Hint, there may be some ambiguity in this problem, if so, I’m looking for a discussion and what you think the right answer is, so your reasoning is more important than your actual answer.)

2. Write down and test an algorithm to solve these problems and find a global minimizer.

Problem 4: Constraints can make a non-smooth problem smooth.

Show that

$$\MIN{}{\normof{\mA \vx - \vb}_{\infty}}$$

can be reformulated as a smooth, constrained optimization problem.