Computational methods in optimization

David Gleich

Purdue University

Spring 2012

Course number CS 59000-OPT

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

Lawson B134

Homework 5

$\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}}$

Homework 5

Please answer the following questions in complete sentences in a typed manuscript and submit the solution to me in class on February 21th, 2012.

The previous homework was focused heavily on implementations and studying these methods in a practical setting. In this homework, we will return our focus back to theory.

Problem 0: List your collaborators.

Please identify anyone, whether or not they are in the class, with whom you discussed your homework.

Problem 1: Solving the trust region problem (Griva, Nash, and Sofer, 11.6.6)

In class, your professor mentioned that any solution to the trust region sub-problem,

$$\MINone{\vp}{f(\vx_k) + g(\vx_k)^T \vp + 1/2 \vp^T \mH(\vx_k) \vp \quad = \quad m_k(\vp)}{\normof{\vp} \le \Delta,}$$

could be characterized as follows:

• $(\mH(\vx_k) + \lambda \mI) \vp^* = -\vg$
• $\lambda (\normof{\vp^*} - \Delta) = 0$
• $\mH(\vx_k) + \lambda \mI \succeq 0$ (it’s positive semi-definite).

Use these conditions to show that, if $\lambda \not= 0$, then $\vp$ solves:

$$\MINone{\vp}{f(\vx_k) + g(\vx_k)^T \vp + 1/2 \vp^T \mH(\vx_k) \vp}{\normof{\vp} = \Delta.}$$

Hint First show that $m_k(\vp^*) \le m_k(\vp) + 1/2 \lambda (\vp^T \vp - {\vp^*}^T \vp^*)$ for any $\vp$.

Problem 2: Advantages and disadvantages

Is a dog-leg method or a subspace minimization method better when using a trust region method on a convex optimization problem? Discuss and explain why.

Problem 3: Read and prove

Read the proof of Lemma 4.2. There is one missing step. Let $\mB$ be symmetric positive definite. Prove the inequality:

$$\frac{(\vg^T \vg)^2}{\vg^T \mB \vg \vg^T \mB^{-1} \vg} \le 1.$$

(Hint: Use Cauchy-Schwarz!) Can you remove any of the conditions from this proof? When do you have equality?