% this is file s1.tex {\bf INDEFINITE TRUST REGION\\ SUBPROBLEMS,\\ INTERIOR POINT METHODS,\\ AND MAX-MIN EIGENVALUE PROBLEMS} Henry Wolkowicz \\ Department of Combinatorics and Optimization \\ University of Waterloo\\ ~\\ ~\\ ~\\ ~\\ work with Ron Stern (Concordia University), Svata Poljak (Charles University), Franz Rendl (University of Graz), Bob Vanderbei (Princeton University) % this is file s1a.tex \begin{center} OUTLINE \end{center} \begin{itemize} \item extend trust region theory in two ways: \\ indefinite and 2-sided constraints \item applications to bounds for 0-1 quadratic programming \item interior point numerical algorithm over the positive semidefinite cone of matrices \end{itemize} % file is s2.tex {\bf TRUST REGION METHODS} \[ \min_{x\in \Re^n} f(x) \] Newton's Method (possible indefinite Hessians)\\ model based (at current estimate $x_c$) \[f(x) \approx \] \[ m_{c}(x):= f(x_{c})+g_{c}^{t}(x-x_{c})+\frac{1}{2}(x-x_{c})^{t}B_{c}(x-x_{c})\] \[ B_c \approx \nabla^2 f(x_{c}),~~ g_c = \nabla f(x_{c}) \] TRUST REGION SUBPROBLEM \[ \min q_c(d) := g_c^t d + \frac{1}{2} d^tB_cd \] \[ \mbox{subject to~} ||D_c d || \leq \delta_c \] (unlike Newton's method - not scale invariant) % file is s3.tex {\bf Special Case} \[ \mu = \min_{||x || = 1} x^tBx \] \[L(x,\lambda)=x^tBx-\lambda(x^tx-1)~~\mbox{(Lagrangian)}\] \[ \nabla_x L(x,\lambda) = 0 = Bx-\lambda x \] \[ \Longrightarrow Bx = \lambda x ~~\mbox{(eigenvalue-eigenvector)}\] \[ \mu = x^tBx = \lambda x^tx = \lambda \rightarrow \min \] We get the smallest eigenvalue. Nonconvex problem {\bf IFF} characterization of {\bf GLOBAL} minimum Local Minima? (NONE) % file is s4.tex General Trust Region Subproblem: \[ (P)~~~~~~~\begin{array}{cll} \mu^* :=\min ~~ \mu(y) & := & y^tBy-2\psi^ty \\ {\rm subject~to} & \beta \leq &y^tCy \leq \alpha,~ y \in \Re^n \end{array} \] $B$, $C$ symmetric, possibly indefinite \[ -\infty \leq \beta \leq \alpha \leq \infty \] \begin{itemize} \item {\bf characterize} global min \item concave max dual problem with no duality gap \item ( can characterize local min )\\ (connections to eigenvalue perturbation problems) \end{itemize} % file is s5.tex {\bf THEOREM} $y$ feasible point and CQ: \[ Cy = 0~\mbox{implies}~\beta < 0 < \alpha. \] Then $y$ \underline{global} minimum\\ \underline{iff}\\ there exists $\lambda \in \Re$ such that \[ (B-\lambda C)y = \psi \mbox{~(stationarity)}, \] \[ B-\lambda C \geq 0 \mbox{~(Hessian~nonneg~def)}, \] and \[ \lambda (\beta - y^tCy) \geq 0 \geq \lambda( y^tCy-\alpha ) ~\left( \begin{array}{c} \mbox{compl~slack} \\ \mbox{mult~sign~} \end{array} \right) \] ~\\ \[ B-\lambda C >0~\mbox{implies unique min} \] % file s6.tex necessary condition for optimality: \[ \exists~ \hat{\lambda} \in \Re~~ {\rm s.t.}~~ B-\hat{\lambda} C \geq 0. \] {\bf Define}:\\ {\em \underline{regular case}} or the {\em \underline{positive definite pencil case}} \[ \exists ~ \hat{\lambda} \in \Re~{\rm s.t.}~ B-\hat{\lambda} C > 0 \] Ignore the irregular case since: \begin{itemize} \item (i) The set of $t$ where $B-tC$ is positive definite is an open interval which is bounded if and only if $C$ is indefinite. \item (ii) In the irregular case with the function $\det(B-tC)$ not identically 0 in $t$, there is only one value $\hat{\lambda}$ such that $B-\hat{\lambda} C \geq 0$ holds. \end{itemize} % file is s7.tex Existence or boundedness\\ {\bf equivalent to}\\ positive semidefinite pencil {\bf THEOREM (EXISTENCE-BOUNDEDNESS)} $C$ nonsingular \begin{itemize} \item $(P)$ possesses a minimizing point and\\ $\max\{|\alpha|,|\beta|\}>0$ implies positive semidefinite pencil condition holds. \item Conversely, positive semidefinite pencil condition and regular implies minimizing point exists \end{itemize} % file is s8.tex {\bf DUALITY} We now present a {\bf dual problem} for (P) which is a true {\bf concave maximization} programming problem. This illustrates that (P) is an {\bf implicit convex program} and shows why the {\bf global minimum} can be {\bf characterized} and found efficiently. Note that if $y^*$ solves (P) with optimal Lagrange multiplier $\lambda^*$, then being in the {\bf easy case} implies that $y^*=(B-\lambda^*C)^{-1}\psi$. % file is s9.tex {\bf THEOREM (DUALITY)} \begin{itemize} \item $y^*$, $\lambda^*$, $\mu^* = \mu(y^*)$ optimal \item Lagrangian function \[ L(y,\nu,\omega) = \mu(y) + \nu (\alpha - y^tCy) + \omega( y^tCy - \beta) \] \item Lagrange dual functional \[ \phi ( \nu,\omega) = \inf L(y,\nu,\omega) \] \item quadratic dual functional \[ h(\nu,\omega) = \nu \alpha - \omega \beta - \psi^t (B-\nu C + \omega C)^{-1} \psi \] \end{itemize} Then \[ \begin{array}{rcl} \mu^* &= & \max_{\nu \leq 0,\omega \leq 0} \phi (\nu,\omega)\\ & = & \sup_{\stackrel{B - \nu C + \omega C > 0}{\nu \leq 0,\omega \leq 0}} h(\nu,\omega) \end{array} \] %where the latter equality requires that the regular case holds. %Moreover, the first equality is attained by %\[ % \nu^* = -(-\lambda^* )_+ {\mbox ~and~} % \omega^* = -(\lambda^* )_+ %\] % file is s10.tex {\bf Proof} If $B-\nu C + \omega C > 0$, then $\phi(\nu,\omega)$ is finite. Moreover, $L(y,\nu,\omega) = \phi(\nu,\omega)$ for $y=(B-\nu C + \omega C)^{-1}\psi$. Substituting for $y$ in $L$ yields \[ h(\nu,\omega)=\phi(\nu,\omega). \] Now if $z$ is feasible for (P), then for all nonpositive $\nu,\omega$ we have $\phi(\nu,\omega) \leq L(z,\nu,\omega) \leq \mu(z)$. We now have \[ \begin{array}{rcl} \mu^* &=& \min_{z~feasible} \mu(z) \\ &\geq& \sup_{\nu \leq 0,\omega \leq 0} \phi(\nu,\omega),\\ &=& \sup_{\stackrel{B - \nu C + \omega C \geq 0}{\nu \leq 0,\omega \leq 0}} \phi(\nu,\omega)\\ &\geq& \sup_{\stackrel{B - \nu C + \omega C > 0}{\nu \leq 0,\omega \leq 0}} h(\nu,\omega). \end{array} \] %file is s11.tex Now, from the optimality conditions, there exists an optimal multiplier $\lambda^*$. Let $\nu^*$ and $\omega^*$ be chosen as in the statement of the Theorem. Then \[ \begin{array}{rcl} \mu^* & = & L(y^*,\nu^*,\omega^*) \\ &=& \phi(\nu^*,\omega^*) \\ & \leq & \max_{\nu \leq 0,\omega \leq 0} \phi(\nu,\omega), \end{array} \] i.e. this and the previous equations imply that the first equality holds. If the easy case holds, i.e. $y^* = (B-\lambda^* C)^{-1} \psi$, then \[ h(\nu^*,\omega^*) = L(y^*,\nu^*,\omega^*) = \mu^*. \] The conclusion follows. %file is s12.tex Now suppose that the hard case holds, i.e. $B-\lambda^* C$ is singular. Equivalently, $D-\lambda^* S$ is singular, where $T^tBT = D$ and $T^tCT=S$ are both diagonal, $T$ nonsingular. Let $\bar{y} = T(D-\lambda^*S)^{\dagger}T^{t}\psi$, where $\dagger$ denotes the Moore-Penrose generalized inverse. From the optimality conditions, we have that $\psi \in R (B-\lambda^*C).$ Let $\lambda_k \rightarrow \lambda^*$ with $B-\lambda_kC$ positive definite. Let $\nu_k,\omega_k$ correspond to $\lambda_k$ as $\nu^*,\omega^*$ corresponds to $\lambda^*$. Then, from the simultaneous diagonalization, we conclude that \[ y_k = (B-\lambda_kC)^{-1}\psi = T(D-\lambda_kS)^{-1}T^{t} \psi \rightarrow \bar{y}. \] % file is s13.tex Moreover, $y^* = \bar{y} + z$ for some $z$ in the null space of $B-\lambda^*C$, and we also have $z \perp \psi$. Now $L(y,\nu,\omega) = y^t(B-\nu C - \omega C)y - 2 \psi^t y + \nu \alpha - \omega \beta.$ So \[ h(\nu_k,\omega_k) = L(y_k,\nu_k,\omega_k) \rightarrow L(\bar{y},\nu^*,\omega^*) \] and this equals \[ L(y^*,\nu^*,\omega^*)=\mu^*. \] Attainment follows directly from the optimality conditions.\\ \hspace*{4.5in} $\Box$ % file is s14.tex duality result with only one multiplier {\bf COROLLARY} \[ \bar{h}(\lambda) = -(-\lambda)_+ \alpha + (\lambda)_+ \beta - \psi^t (B-\lambda C )^{\dagger} \psi, \] where $$(\lambda)_+ = \left\{ \begin{array}{cc} \lambda & {\mbox if~} \lambda \geq 0 \\ 0 & \mbox{ otherwise.} \end{array} \right. $$ Then \[ \mu^* = \max_{B-\lambda C > 0} \bar{h}(\lambda). \] % file is slide15.tex Standard trust region subproblem {\bf COROLLARY} $C=I$, $\beta < 0 < \alpha$ \[ \bar{g}(\lambda) = \lambda \alpha - \psi^t (B-\lambda C )^{\dagger} \psi. \] Then \[ \mu^* = \sup_{B-\lambda C > 0,~\lambda \leq 0} \bar{g}(\lambda). \] In addition, in the hard case, \[ \mu^* = \sup_{B-\lambda C > 0,~\lambda \leq 0} \bar{g}(\lambda) = \max_{B-\lambda C \geq 0,~\lambda \leq 0} \bar{g}(\lambda). \] % file is s16a.tex {\bf LOCAL-NONGLOBAL MINIMA}\\ (extension of results of Mario Martinez) {\bf LEMMA} Suppose that $y^*$ is a local-nonglobal minimizer of (P) and suppose that the pencil $B-\lambda C$ is regular and that the constraint qualification \[ Cy^* \neq 0 \] holds. Then \[ \lambda_{n-1}(B-\lambda^*C) > 0 > \lambda_{n}(B-\lambda^*C). \] There are at most two local-nonglobal minima.\\ The existence of lngm implies easy case.\\ A local duality theory exists. % file is s17.tex {\bf $\pm 1$ QUADRATIC PROGRAMMING} \begin{itemize} \item \[ \begin{array}{c} ~~~(P)~~~\mu^*:=\max ~ q(x):=x^tQx+c^tx,\\ x \in F := \{-1,1\}^n, \end{array} \] $Q$ $n \times n$ symmetric matrix, $c \in \Re^n$. \item Relaxed Problem - $K \supset F$ \[ \begin{array}{c} (RP)~~~f(u) = \max_{x \in K} q_u(x):=\\ x^t(Q - \diag(u))x + u^te +c^tx, \end{array} \] \item Solve Tractable Problem \[ B:= \min_{u \in L} f(u) \] \item Upper Bound \[\mu^* \leq B \] \end{itemize} % file is s18.tex {\bf Three Relaxations}\\ -------------------------------\\ relaxed problem \[ ~~(RP_v^1)~~~f_1(v) := \max_{-1 \leq x \leq 1} q_v(x). \] bound \[ B_1 := \min_{Q-\diag(v) \leq 0} f_1(v). \] ------------------------------\\ relaxed problem \[ ~~(RP^2_u)~~~f_2(u) := \max_{||y||^2=n} q_u(y). \] bound \[ B_2 := \min_{u^te=0} f_2(u) = \min_{u} f_2(u). \] % file is s19.tex \[ Q^c := \left[ \begin{array}{cc} 0 & \frac 12 c^t \\ \frac 12 c &Q \end{array} \right]. \] \[ q^c_u(y) := y^t( Q^c-\diag(u))y+u^te \] -----------------------------------------\\ relaxed problem \[ \begin{array}{c} ~~(RP^3_u)~~~~f_3(u) := \max_{||y||^2=n+1} q^c_u(y)\\ = (n+1) \lambda_{\max} (Q^c - \diag (u) ) + u^te. \end{array} \] bound \[ B_3 := \min_{u^te=0} f_3(u) = \min_{u} f_3(u). \] % file is s20.tex BOUND 1 - Convex Quadratic Programming Consider the shifted function \[ q_v(x) := x^t(Q - \diag(v))x + v^te +c^tx, \] and the relaxed problem \[ ~~(RP_v^1)~~~f_1(v) := \max_{-1 \leq x \leq 1} q_v(x). \] Then a bound for (P) is \[ B_1 := \min_{Q-\diag(v) \leq 0} f_1(v). \] % file s21.tex Properties for Bound $B_1$. \begin{enumerate} \item $ \mu^* \leq B_1. $ \item $f_1$ is convex, finite valued, with subdifferential \[ \begin{array}{c} \partial f_1(v) = \conv \{ z=(1-x^2_i) \in \Re^n:\\ x=(x_i) \in \Re^n -1 \leq x \leq 1,~f_1(v)=q_v(x)\}. \end{array} \] \item $B_1$ is attained for some $v \in \Re^n$ such that $\lambda_{max}(Q - \diag(v))=0.$ \item \[B_1 = \inf_{Q-\diag(v) < 0} f_1(v). \] \end{enumerate} % file is s22.tex Lagrangian \[ L_1(v,\Lambda) :=f_1(v) + \trace \Lambda (Q-\diag(v)), \] where $\Lambda$ is a symmetric, positive semidefinite Lagrange multiplier matrix. Optimality conditions: \[ \begin{array}{c} 0 \in \partial f_1(v) - \diag(\Lambda)~~~\mbox{ (stationarity)}\\ \trace \Lambda (Q-\diag(v)) = 0~~~ \mbox{ (complementary~slack)}\\ \Lambda = \Lambda^t \geq 0~~~ \mbox{ (multiplier~sign)}. \end{array} \] % file is s23.tex BOUND 2 - Optimization Over Sphere\\ \[ q_u(y) := y^t(Q-\diag(u))y+u^te+c^ty, \] the second relaxed problem \[ ~~(RP^2_u)~~~f_2(u) := \max_{||y||^2=n} q_u(y). \] Now a bound for (P) is \[ B_2 := \min_{u^te=0} f_2(u) = \min_{u} f_2(u). \] %file is s24.tex Properties for bound $B_2$. \begin{enumerate} \item $ \mu^* \leq B_2.$ \item $f_2$ is convex, finite valued, with subdifferential \[ \begin{array}{c} \partial f_2(u) = \mbox{conv} \{ z=(1-y^2_i) \in \Re^n: \\ y=(y_i) \in \Re^n,~||y||^2=n,~f_2(u)=q_v(y)\}. \end{array} \] \item The bound $B_2$ is attained for some $u \in \Re^n$. Moreover, if $B_2 > \mu^*$, then the hard case holds for $(RP^2_u).$ \end{enumerate} % file is s25.tex THEOREM\\ The bound $B_1 = B_2$. In fact: \[ \begin{array}{ccl} f_2(u)&=& q_u(y_u) \\ &\geq& \max_{(-1\leq y \leq 1)} q_{(u+\lambda e)}(y)\\ & = & f_1(u+ \lambda e) \\ \end{array} \] and\\ $B_2=f_2(u)$, with Lagrange multiplier $\lambda$ for $(RP^2_u)$ if and only if $B_2=f_2(u)=f_1(u+\lambda e)=B_1$. % file s26.tex THEOREM\\ Suppose that $f_4(v) := \max_{-1 \leq x \leq 1} q^c_v(x)$ and \[B_4 := \min_{Q^c-\diag(v) \leq 0} f_4(v).\] Then \[ B_1 = B_2 = B_3 = B_4. \] COROLLARY Let $B$ be an $(n-1)\times(n-1)$ real symmetric matrix, and consider the perturbation of $B$ given by \[ A=\left( \begin{array}{cc} B & -\alpha\\ \alpha^t & t \end{array} \right), \] where $\alpha$ is a real $(n-1)$-vector. Define \[ \mu(x) = x^tBx-2\alpha^tx. \] Let \[ \mu_1 = \max\{\mu(x)~:~x^tx = 1\} \label{mu1} \] and \[ \mu_k = \min\{\mu(x)~:~x^tx = 1\}. \label{mu2} \] Then either of the conditions \[ t \geq \mu_1 \label{geek} \] or \[ t \leq \mu_k \] are sufficient for the spectrum of $A$ to be real. COROLLARY A sufficient condition for the spectrum of $A$ to be real is \[ \parallel B \parallel + 2\parallel \alpha \parallel \leq |t|. \] THEOREM Suppose that $\lambda \in \Lambda$; that is, $\lambda$ is a Lagrange multiplier of $\mu(\cdot)$ with respect to $S_{n-1}$. Then $x \in S_{\mu}(\lambda)$ if and only if $\lambda$ is an eigenvalue of $A$ with $t=\mu(x)$, in which case an associated eigenvector is \[ \left( \begin{array}{c} x\\ 1 \end{array} \right). \] % file is s29.tex The {\em max-min eigenvalue problem} is: \[ ~~~(MMP)~~~\omega^*:=\max_{v^te=0} \lambda_{\min} (C - \Diag(v)). \] It can be formulated as: \[ \omega^*=\max \{\omega : v^te=0,~C - \Diag(v) \succeq \omega I \}. \] With $y=v+\omega e,$ an equivalent problem is: \[ \max \{e^ty: ~C - \Diag(y) \succeq 0 \}. \] The dual is the min-max of the Lagrangian \[ \min_{X^a \succeq 0} \max_{y} ~e^ty+ \trace X(C-\Diag(y)). \] or: \[ \begin{array}{llll} \min & \trace CX& \\ {\rm subject~to} & \diag(X)= e \\ & ~X\succeq 0. \end{array} \] % file is s30.tex We get the dual pair of ``linear type programs'' \[ \begin{array}{llll} \max & e^ty&\\ {\rm subject~to} & C - \Diag(y) -Z= 0 \\ & ~Z\succeq 0. \end{array} \] ~\\ ~\\ \[ \begin{array}{llll} \min & \trace CX& \\ {\rm subject~to} & \diag(X)= e \\ & ~X\succeq 0. \end{array} \] % file is s31.tex PRIMAL-DUAL INTERIOR POINT METHOD\\ The primal-dual log-barrier problem is then \[ ~~~(B)~~~~\begin{array}{llll} \omega^*_\mu= \max & e^ty + \mu \log \det (Z) &\\ {\rm subject~to} & C-\Diag(y) -Z = 0. \end{array} \] The Lagrangian $L(y,Z,X)$ is \[ e^ty + \mu \log \det (Z) + \trace X(C-\Diag(y) -Z),\] while the optimality conditions $F(y,Z,X)=0$ are: \[ \begin{array}{rcl} e- \diag(X) &=& 0~~\mbox{(primal feasibility)}\\ -X + \mu Z^{-1} &=& 0~~\mbox{(complementary slackness)}\\ C-\Diag(y) -Z &=& 0~~\mbox{(dual feasibility)}\\ Z \succeq 0,~ X \succeq 0. \end{array} \] % file is s32.tex Apply Newton's method: \[ \left[ \begin{array}{ccc} 0 & 0 & \diag(\cdot) \\ 0 & \mu Z^{-1} \cdot Z^{-1} & I \\ \Diag(\cdot) & I & 0 \end{array} \right] \left( \begin{array}{c} \delta y \\ \delta Z \\ \delta X \end{array} \right) = \] \[\left( \begin{array}{c} ( e- \diag(X))\\ ( -X + \mu Z^{-1})\\ (C-\Diag(y) -Z ) \end{array} \right). \] simplify with $Z=C-\Diag(y)$: \[ \begin{array}{ccc} \delta y& = & (\mu Z^{-1} \circ Z^{-1} )^{-1} (e- \mu \diag(Z^{-1}) );\\ \delta Z& =& - \Diag(\delta y); \\ X+\delta X &= &\mu Z^{-1} ( Z + \Diag(\delta y))Z^{-1}\nonumber. \end{array} \]