   
%  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}
\]
