\section{Saddle Point Criteria}\label{S:SaddlePoints}
\setcounter{progress_ck_counter}{0}

\noi Unfortunately, many NLPs fail to be convex, in which case a KKT point, $\vecx_0$, need not
be an optimal solution. For example, the NLP given by

\begin{align}\label{E:SaddlePointsExample}
 \mbox{ minimize }  & f(\vecx )=x_1^2-6x_1+x_2^2-4x_2   \\
	\mbox{ subject to} \notag\\
	g_1(\vecx)&=x_1^2+x_2^2-9 \leq 0 \notag\\
    g_2(\vecx)&=x_1^2-x_2^2 \leq 0 \notag\\
    g_3(\vecx)&=x_2-2 \leq 0 \notag\\
    g_4(\vecx)&=2x_1+x_2-8 \leq 0, \notag
	\end{align}
is a non-convex NLP since $g_2$ is not a convex function. Straightforward calculations, which
we leave as an exercise, show that
(\ref{E:SaddlePointsExample}) has two KKT points, $\ds \vecx_0 = \begin{bmatrix} 2 \\ 2 \end{bmatrix}$,
along with multiplier vector, $\ds \lambdavec_0 = \begin{bmatrix} 0 \\ 1/2 \\ 2 \\ 0 \end{bmatrix}$,
and
$\ds \vecx_0 = \begin{bmatrix} 1/2 \\ -1/2 \end{bmatrix}$ together with
$\ds \lambdavec_0 = \begin{bmatrix} 0 \\ 5 \\ 0 \\ 0 \end{bmatrix}$. As we shall discover, only the
first of these KKT points forms a solution to (\ref{E:SaddlePointsExample}).


\subsection{The Restricted Lagrangian}\label{SS:SaddlePointsRestrictedLagrangianIntro}

\noi Throughout the ensuing discussion, we assume that $\vecx_0$ is a KKT point of (\ref{E:LagrangianGeneralNLP}) having
corresponding multiplier vectors, $\lambdavec_0$ and $\muvec_0$.  We may assume, by relabeling if necessary, that the
first $k$ components of $\vecg$, where $1 \leq k \leq m$, are \emph{binding}\index{binding constraint} at $\vecx_0$. By this, we
mean that $g_i(\vecx_0)=0$ for $1 \leq i \leq k$ and $g_i(\vecx_0) < 0$ for $k+1 \leq i \leq m$. With
components of $\vecg$ labeled in this manner, we define the vector-valued function,
$\widetilde{\vecg}: \R^n \to \R^m$ given by
$\ds \widetilde{\vecg}(\vecx)=
\begin{bmatrix} g_1(\vecx) \\ g_2(\vecx) \\ \vdots \\ g_k(\vecx) \\
0 \\ \vdots \\ 0 \end{bmatrix}$.


\noi Note that $\widetilde{\vecg}(\vecx_0)=\zerovec$ and that, due to complementary slackness conditions,
$\lambda_{0,i}=0$ for $k+1 \leq i \leq m$.


\begin{definition}\label{Th:SaddlePointsRestrictedLagrangian}\index{Lagrangian function!restricted}
The \emph{restricted Lagrangian function}\index{restricted Lagrangian} corresponding to a
KKT point, $\vecx_0$, of NLP (\ref{E:LagrangianGeneralNLP}) is the function
% $\widetilde{L}:S \times \R_+^m \times \R^p \to \R$ defined by
\begin{align}\label{E:SaddlePointsRestrictedLagrangian}
\widetilde{L}(\vecx, \lambdavec,\muvec)&= f(\vecx)+\lambdavec^t \widetilde{\vecg}(\vecx)+ \muvec^t \vech(\vecx) \\
&= f(\vecx)+\sum_{i=1}^k \lambda_i g_i(\vecx)
+\sum_{j=1}^p \mu_jh_j(\vecx), \notag
\end{align}
where $\vecx$ belongs to $S$, $\lambdavec$ and $\muvec$
are vectors in $\R^m$ and $\R^p$, respectively, with $\lambdavec \geq \zerovec$.
\end{definition}

\begin{progress_ck}
Calculate the restricted Lagrangian for NLP (\ref{E:SaddlePointsExample})
at each of its two KKT points.
\end{progress_ck}

\noi
To understand how the restricted Lagrangian compares to the original, note that
if $\vecx$ is feasible, then $\ds \lambda_i g_i(\vecx) \leq 0$ for
$\lambda_i \geq 0$ and $1 \leq i \leq m$, so that
\begin{align*}
\widetilde{L}(\vecx, \lambdavec,\muvec)&=f(\vecx)+\lambdavec^t \widetilde{\vecg}(\vecx)+ \muvec^t \vech(\vecx) \\
&=f(\vecx)+\sum_{i=1}^k \lambda_i g_i(\vecx)
+\sum_{j=1}^p \mu_jh_j(\vecx) \notag \\
&\geq f(\vecx)+\sum_{i=1}^m \lambda_i g_i(\vecx)
+\sum_{j=1}^p \mu_jh_j(\vecx) \\
&= L(\vecx, \lambdavec,\muvec).
\end{align*}

\noi
Furthermore, suppose $\vecx_0$ is a KKT point of NLP (\ref{E:LagrangianGeneralNLP}) with corresponding multiplier vectors,
$\lambdavec_0$ and $\muvec_0$. Since $\lambda_{0,i}=0$ for $k+1 \leq i \leq m$,
$\ds \jacobian_{\widetilde{\vecg}}(\vecx_0)^t \lambdavec_0=\jacobian_{\vecg}(\vecx_0)^t \lambdavec_0$.
Therefore,
\begin{align}\label{E:SaddlePointsRestrictedLagrangianGradient}
\nabla \widetilde{L}(\vecx_0,\lambdavec_0, \muvec_0)
&= \nabla f(\vecx_0) + \jacobian_{\widetilde{\vecg}}(\vecx_0)^t \lambdavec_0 + \jacobian_{\vech}(\vecx_0)^t \muvec_0  \\
&= \nabla f(\vecx_0) + \jacobian_{\vecg}(\vecx_0)^t \lambdavec_0 + \jacobian_{\vech}(\vecx_0)^t \muvec_0 \notag \\
&= \nabla L( \vecx_0,\lambdavec_0, \muvec_0) \notag \\
&= \zerovec. \notag
\end{align}
Thus $\vecx_0$ is a KKT point of the $\widetilde{L}$ with multiplier vectors
$\lambdavec_0$ and $\muvec_0$.


\newpar
The restricted Lagrangian, $\widetilde{L}$ has the special property that if $\vecx_0$ is a KKT point of NLP (\ref{E:LagrangianGeneralNLP}) with corresponding multiplier vectors,
$\lambdavec_0$ and $\muvec_0$, then the gradient of $\widetilde{L}$ with respect to all three vector variables, $\vecx$, $\lambdavec$, and $\muvec$, must vanish at $(\vecx_0,\lambdavec_0,\muvec_0)$.
In other words, $(\vecx_0,\lambdavec_0,\muvec_0)$ is a critical point of $\widetilde{L}$. To see why this is
so, first note from (\ref{E:SaddlePointsRestrictedLagrangianGradient})
that
\begin{equation}\label{E:LagrangianCP1}
\left. \frac{\partial \widetilde{L}}{\partial x_k} \right|_{(\vecx_0,\lambdavec_0,\muvec_0)} =0 \quad
\mbox{for $1 \leq k \leq n$.}
\end{equation}
Moreover, since $\vecx_0$ is a feasible solution of NLP (\ref{E:LagrangianGeneralNLP}), constraints $g_i(\vecx)$ are binding
at $\vecx_0$ for $i=1,2,\ldots,k$, so that
\begin{align*}
\left.
\frac{\partial \widetilde{L}}{\partial \lambda_i} \right|_{(\vecx_0,\lambdavec_0,\muvec_0)} &= g_i(\vecx_0) \\
&=0 \qquad \mbox{for $1 \leq i \leq k$.}
\end{align*}
This result, along with the fact $\widetilde{L}$ is independent
of $\lambda_{k+1}, \lambda_{k+2},\ldots, \lambda_m$, leads
to
\begin{equation}\label{E:LagrangianCP2}
\left.
\frac{\partial \widetilde{L}}{\partial \lambda_i} \right|_{(\vecx_0,\lambdavec_0,\muvec_0)} =0
\quad \mbox{for $1 \leq i \leq m$.}
\end{equation}

\noi Finally,
\begin{align}\label{E:LagrangianCP3}
\left.
\frac{\partial \widetilde{L}}{\partial \mu_j} \right|_{(\vecx_0,\lambdavec_0,\muvec_0)} &= h_j(\vecx_0) \\
&=0 \qquad \mbox{for $1 \leq j \leq p$}.\notag
\end{align}

\newpar
Combining (\ref{E:LagrangianCP1}), (\ref{E:LagrangianCP2}), and (\ref{E:LagrangianCP3}),
we conclude $(\vecx,\lambdavec,\muvec)=(\vecx_0,\lambdavec_0,\muvec_0)$ is a critical point of $\widetilde{L}$.

\subsection{Saddle Point Optimality Criteria}\label{SS:SaddlePointOptimalityCriteria}

\noi That the restricted Lagrangian, $\widetilde{L}$, has a critical point at
$(\vecx_0,\lambdavec_0,\muvec_0)$ proves quite useful for establishing
$\vecx_0$ is a solution of NLP  (\ref{E:LagrangianGeneralNLP}).
The specific conditions for which this occurs are phrased in terms of the following definition.

\begin{definition}\label{Th:SaddlePointsSaddleDefinition}\index{restricted Lagrangian!saddle point}
Suppose the triple $(\vecx_0,\lambdavec_0,\muvec_0)$ is a critical point
of the restricted Lagrangian, $\widetilde{L}$, where $\vecx_0$ is a KKT point of
(\ref{E:LagrangianGeneralNLP}) with multiplier vectors, $\lambdavec_0$ and $\muvec_0$,
where $\lambdavec_0 \geq \zerovec$.
Then we say that $\widetilde{L}$ satisfies the \emph{saddle point criteria}\index{saddle point criteria} at
 $(\vecx_0,\lambdavec_0,\muvec_0)$ if and only if
 \begin{equation}\label{E:SaddlePointsSaddleDefinitionInequality}
\widetilde{L}(\vecx_0,\lambdavec,\muvec) \leq \widetilde{L}(\vecx_0,\lambdavec_0,\muvec_0)
\leq \widetilde{L}(\vecx,\lambdavec_0,\muvec_0)
\end{equation}
for all $\vecx$ in $S$, all $\lambdavec$ in $\R^m$ satisfying $\lambdavec \geq \zerovec$,
and all $\muvec$ in $\R^p$.
\end{definition}

\newpar
We leave it as an exercise to show that for a convex NLP, any triple,
$(\vecx_0,\lambdavec_0,\muvec_0)$, where $\vecx_0$ is a KKT point with
corresponding multiplier vectors, $\lambdavec_0$ and $\muvec_0$, is a saddle
point of $\widetilde{L}$. Thus a KKT point for a convex NLP is
a solution of the NLP and also corresponds to a saddle point of the restricted
Lagrangian.

\newpar The following result is significant in that it applies to the non-convex
setting and shows how a KKT point of an NLP, which corresponds to a saddle point of the restricted Lagrangian, yields a solution of the NLP.

\begin{theorem}\label{Th:SaddlePointsMainTheorem}
Suppose $\vecx_0$ is a KKT point of
(\ref{E:LagrangianGeneralNLP}) with multiplier vectors, $\lambdavec_0$ and $\muvec_0$.
If $(\vecx_0,\lambdavec_0,\muvec_0)$ is a saddle point of $\widetilde{L}$,
then $\vecx_0$ is a solution of the NLP.
\end{theorem}

\begin{proof}
Assume $(\vecx_0,\lambdavec_0,\muvec_0)$ is a saddle point of $\widetilde{L}$
and that $\vecx$ in $S$ is feasible. Then
\begin{align}\label{E:SaddlePointsMainTheoremProof}
f(\vecx_0) &= f(\vecx_0) + \lambdavec^t \widetilde{\vecg}(\vecx_0) +\muvec^t \vech(\vecx_0)  \\
&= \widetilde{L}(\vecx_0,\lambdavec,\muvec) \notag \\
&\leq \widetilde{L}(\vecx_0,\lambdavec_0,\muvec_0) \notag \\
&\leq \widetilde{L}(\vecx,\lambdavec_0,\muvec_0) \notag \\
&= f(\vecx) + \lambdavec_0^t \widetilde{\vecg}(\vecx) +\muvec_0^t \vech(\vecx) \notag  \\
&\leq f(\vecx)
\end{align}

\noi
Thus $\vecx_0$ is a solution of NLP (\ref{E:LagrangianGeneralNLP}).
\end{proof}

\noi
To test whether a KKT point and its multiplier vectors satisfy the
saddle point criteria\index{saddle point criteria}, we first define
$\ds \phi(\vecx)= \widetilde{L}(\vecx, \lambdavec_0,\muvec_0)$ and establish
that
$\ds \phi(\vecx_0) \leq \phi(\vecx)$
for all feasible $\vecx$ in $S$. For when this holds, feasibility
requirements along with the condition $\lambdavec \geq \zerovec$, yield
\begin{align*}
\widetilde{L}(\vecx,\lambdavec_0,\muvec_0) &\geq \widetilde{L}(\vecx_0,\lambdavec_0,\muvec_0) \\
&= f(\vecx_0) + \lambdavec_0^t \widetilde{\vecg}(\vecx_0)+ \muvec_0^t \vech(\vecx_0) \\
&\geq f(\vecx_0) + \lambdavec^t \widetilde{\vecg}(\vecx_0)+ \muvec^t \vech(\vecx_0) \\
&= \widetilde{L}(\vecx_0,\lambdavec,\muvec),
\end{align*}
which implies that $(\vecx_0,\lambdavec_0,\muvec_0)$
is a saddle point of $\widetilde{L}$.

\newpar
We can apply this technique to the non-convex NLP (\ref{E:SaddlePointsExample}).
At $\ds \vecx_0 = \begin{bmatrix} 2 \\ 2 \end{bmatrix}$, the second and third constraints
are binding. Since $\ds \lambdavec_0 = \begin{bmatrix} 0 \\ 1/2 \\ 2 \\ 0 \end{bmatrix}$,
we obtain
\begin{align*}
\phi(\vecx) &= \widetilde{L} (\vecx,\lambdavec_0) \\
&= f(\vecx)+\frac{1}{2} g_2(\vecx) + 2 g_3(\vecx) \\
&= \frac{3}{2} x_1^2-6x_1+\frac{1}{2} x_2^2-2x_2-4.
\end{align*}
An elementary exercise establishes that $\nabla \phi$ vanishes
precisely at $\ds \vecx_0 = \begin{bmatrix} 2 \\ 2 \end{bmatrix}$ and that
the Hessian of $\phi$ is constant and positive definite. Thus, $\phi$ has
a global minimum at $\vecx_0$ so that $\vecx_0$ is a solution
of NLP (\ref{E:SaddlePointsExample}).

\newpar
At the second KKT point, $\ds \vecx_0 = \begin{bmatrix} 1/2 \\ -1/2 \end{bmatrix}$,
only the second constraint is binding. In this case, $\phi(\vecx_0) = x_1^2 - x_2^2 $
has a saddle point at $\vecx_0$. Thus, we may not conclude $\vecx_0$ is also a solution
of NLP (\ref{E:SaddlePointsExample}). In fact, $\ds f \left( \frac{1}{2},-\frac{1}{2}\right) =-.5$,
whereas $\ds f(2,2)=-12$.

\section*{Exercises Section \protect\ref{S:SaddlePoints}}

\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_SaddlePoints}	
\endinput 