\section{Convex NLPs}\label{S:ConvexNLPs}	
\setcounter{progress_ck_counter}{0}

\noi Theorem \ref{Th:KKTTheorem} is useful insofar as guaranteeing the existence of Lagrange multipliers
corresponding to the solution of NLP (\ref{E:LagrangianGeneralNLPVectorForm}) under appropriate
hypotheses. It gives necessary conditions that must hold at a minimum, but these conditions alone
are not sufficient. The following Waypoint provides an example demonstrating this fact.

\begin{progress_ck}
Show that $\ds \vecx_0=\begin{bmatrix} 0 \\ 0 \end{bmatrix}$ is a regular KKT point, yet not
a solution of the NLP
\begin{align*}
 \mbox{ minimize }  & f(\vecx )=x_1^2-x_2^2  \notag \\
	\mbox{ subject to} \notag\\
	g_1(\vecx)&=x_1 \leq 0 \notag\\
g_2(\vecx)&=x_2 \leq 0. \notag\\
	\end{align*}

\noi
Then explain why the NLP is unbounded.
\end{progress_ck}

\subsection{Solving Convex NLPs}\label{SS:SolvingConvexNLPs}

\noi The previous Waypoint illustrates that a regular KKT point, $\vecx_0$, is merely a candidate for
a solution. Different means exist for determining whether $\vecx_0$  is also a solution NLP (\ref{E:LagrangianGeneralNLPVectorForm}). One such tool involves convexity. Recall from Theorem
\ref{Th:convexity_FOC_linear_approx_inequality} that if
$\ds S \subseteq \R^n$ is convex
and $\ds f:S \to \R$ is differentiable at each point in $S$,
then $f$ is convex on $S$ if and only if for every $\vecx_0$ in $S$,
\begin{equation}\label{E:ConvexNLPsConvexityTheoremInequality}
f(\vecx )\geq f(\vecx_0 )+ \nabla f(\vecx_0)^t ( \vecx-\vecx_0 ) \mbox{ for all } \vecx \in S.
\end{equation}

\noi
This result, which arose in the context of unconstrained NLPs, is essential for proving
the following theorem.

\begin{theorem}\label{Th:ConvexNLPsMainResult} Suppose $\ds S \subseteq \R^n$ is convex
and that the function $f$ from the NLP (\ref{E:LagrangianGeneralNLPVectorForm}),
as well as each component of $\vecg$, are continuously differentiable on
$S$.
Assume that $f$ is convex on $S$, as is each component, $g_i$, of $\vecg$. Suppose $\vech(\vecx)=A\vecx-\vecb$ for some $p$ by $n$ matrix $A$ and some vector $\vecb$ in $\R^p$.
Then any regular KKT point, $\vecx_0$,
of the NLP is a solution.
\end{theorem}
\noi
Remark: An NLP of the form described above is called a \emph{convex} NLP.\index{convex NLP}

\begin{proof}
\noindent
By Theorem \ref{Th:KKTTheorem}, there exist multiplier vectors,
$\lambdavec_0$ in $\R^m$ and $\muvec$ in $\R^p$ satisfying conditions
(\ref{E:NonnegativityFritzJohnFormula}), (\ref{E:LagrangianFritzJohnFormula}),
and (\ref{E:LagrangianFritzJohnComplementarySlackness}).
Reordering the inequality constraints if necessary, we may assume
that the first $k$ constraints, where $1 \leq k \leq m$, are binding at $\vecx_0$.
Hence $g_i(\vecx_0)=0$ for $1 \leq i \leq k$, and, by complementary slackness,
$\lambda_{0,i}=0$ for $k+1 \leq i \leq m$.

\newpar
Each function $g_i$ is differentiable
and convex on $S$; therefore, Theorem \ref{Th:convexity_FOC_linear_approx_inequality} yields, for $1 \leq i \leq k$
and for all $\vecx \in S$,
\begin{align}\label{E:ConvexNLPsMainResultEQ1}
\nabla g_i(\vecx_0)^t ( \vecx-\vecx_0 ) &\leq g_i(\vecx )-g_i(\vecx_0)  \\
&= g_i(\vecx) \notag \\
& \leq 0. \notag
\end{align}

\noi This inequality, along with the facts $\lambda_{0,i} \geq 0$
for all $1 \leq i \leq k$ and $\lambda_{0,i} = 0$ for $k+1 \leq i \leq m$, lead to
\begin{align}\label{E:ConvexNLPsMainResultEQ2}
\lambdavec_0^t \jacobian_{\vecg}(\vecx_0)(\vecx-\vecx_0)
&= \left(\sum_{i=1}^m \lambda_{0,i} \nabla g_i(\vecx_0)^t \right)( \vecx-\vecx_0 )  \\
&=\sum_{i=1}^m \lambda_{0,i} \left(\nabla g_i(\vecx_0)^t (\vecx-\vecx_0)\right) \notag \\
&\leq 0.\notag
\end{align}

\noi For equality constraints, we note that
$\jacobian_{\vech}(\vecx)=A$. Hence, for feasible $\vecx$,
\begin{align}\label{E:ConvexNLPsMainResultEQ3}
\muvec_0^t \jacobian_{\vech}(\vecx_0)(\vecx-\vecx_0) &= \muvec_0^t (A\vecx-A\vecx_0)  \\
&= \muvec_0^t \left((A\vecx-\vecb)-(A\vecx_0-\vecb)\right) \notag \\
&=0. \notag
\end{align}

\newpar
We now combine the results of (\ref{E:ConvexNLPsMainResultEQ2})
and (\ref{E:ConvexNLPsMainResultEQ3}), together with
(\ref{E:LagrangianFritzJohnFormula}), which states
\begin{equation*}
\nabla f(\vecx_0) + \jacobian_{\vecg}(\vecx_0)^t \lambdavec_0
+ \jacobian_{\vech}(\vecx_0)^t \muvec_0 = \zerovec.
\end{equation*}

\noi
Fix $\vecx$ in $S$. Then, by the convexity of $f$,
along with inequalities (\ref{E:ConvexNLPsMainResultEQ2})
and (\ref{E:ConvexNLPsMainResultEQ3}), we obtain the following:
\begin{align*}
f(\vecx)-f(\vecx_0) &\geq \nabla f(\vecx_0)^t (\vecx-\vecx_0) \\
&=-\left(\jacobian_{\vecg}(\vecx_0)^t \lambdavec_0 +
\jacobian_{\vech}(\vecx_0)^t \muvec_0 \right)^t (\vecx-\vecx_0) \\
&= -\left( \lambdavec_0^t \jacobian_{\vecg}(\vecx_0)(\vecx-\vecx_0) +
\muvec_0^t \jacobian_{\vech}(\vecx_0)(\vecx-\vecx_0) \right) \\
&= - \lambdavec_0^t \jacobian_{\vecg}(\vecx_0)  (\vecx-\vecx_0) \\
&\geq 0.
\end{align*}
Thus $f(\vecx_0) \leq f(\vecx)$ for all $\vecx \in S$, so $\vecx_0$ is a solution of NLP (\ref{E:LagrangianGeneralNLPVectorForm}).
\end{proof}

\newpar
Theorem \ref{Th:ConvexNLPsMainResult} provides the tools for solving a
wide range of problems, including the \emph{ConPro Manufacturing Company} NLP:

\begin{align}\label{E:ConvexNLPsConProNLP}
 \mbox{minimize } f(x_1,x_2)&= -1400 x_1^{\frac{1}{2}}x_2^{\frac{1}{3}} +350x_1+200x_2 \\
	\mbox{ subject to} & \notag\\
	g_1(\vecx) &= 350x_1+200x_2 -40000 \leq 0 \notag\\
	g_2(\vecx) &= x_1-3x_2 \leq 0  \notag\\
    g_3(\vecx) &= -x_1 \leq 0 \notag \\
    g_4(\vecx) &= -x_2 \leq 0. \notag
	\end{align}	
\noi
In this case, $\ds S=\R_+^2=\left\{(x_1,x_2) \mid x_1, x_2 >0 \right\}$. Recall in Section \ref{S:optimality_sufficient_SOC} that we
established $f$ is convex on $S$ by using Theorem \ref{Th:optimality_sufficient_SOC_convex_PD}.
Each constraint function, $g_i(\vecx)$, from
(\ref{E:ConvexNLPsConProNLP}) is an \emph{affine transformation}
and, hence, is convex on $S$. (See Section \ref{S:convexity_FOC_ConvexDefintion}). Thus
(\ref{E:ConvexNLPsConProNLP}) is a convex NLP, so finding its solution reduces to
finding its regular KKT points.

\newpar
At $\vecx_0$,
the gradient of the Lagrangian must vanish. Hence,
\begin{align}\label{E:ConvexNLPsConProLagrangian}
\nabla L(\vecx_0)
&= \nabla f(\vecx_0) + \sum_{i=1}^4 \lambda_i \nabla g_i(\vecx_0) \notag \\
&=0. \notag \\
\end{align}
The complementary slackness conditions require that
\begin{align}\label{E:ConvexNLPsConProComplementarySlackness}
\lambda_1 g_1(\vecx_0) &=0 \notag \\
\lambda_2 g_2(\vecx_0) &=0 \notag \\
\lambda_3 g_3(\vecx_0) &=0 \notag \\
\lambda_4 g_4(\vecx_0) &=0. \notag \\
\end{align}

\noi That $\ds \nabla L(\vecx)= \zerovec$ provides two equations; complementary slackness\index{complementary slackness} provides the remaining
four. Hence we must solve a system of six equations in six unknowns,
$x_1, x_2, \lambda_1, \lambda_2, \lambda_3, \lambda_4$.

\newpar
This task is best accomplished using Maple\index{KKT Point!calculating with Maple}. Here is a sample worksheet, \textbf{Computing KKT Points.mw}, illustrating how to carry out this process:

\begin{maplelist}
\item \mf{with(VectorCalculus):with(LinearAlgebra):}
\item \mf{f:=(x1,x2)-> -1400*x1\^{}(1/2)*x2\^{}(1/3)+350*x1+200*x2: \newline
\# Enter objective function.}
\item \mf{g1:=(x1,x2)->350*x1+200*x2-40000:}
\item \mf{g2:=(x1,x2)->x1-3*x2:}
\item \mf{g3:=(x1,x2)->-x1:}
\item \mf{g4:=(x1,x2)->-x2:}
\item \mf{g:=(x1,x2)-><g1(x1,x2),g2(x1,x2),g3(x1,x2),g4(x1,x2)>:}
\newline
\mf{\# Enter vector-valued constraint function.}
\item \mf{g(x1,x2);} 
\mo{(350x_1+200x_2-40000)\vece_{x_1} + (x_1-3x_2)\vece_{x_2}  -x_1\vece_{x_3}  -x_2\vece_{x_4}}
\item \mf{lambda:=<lambda1,lambda2,lambda3,lambda4>:} \newline
\mf{\# Create vector of multipliers.}
\item \mf{L:=unapply(f(x1,x2)+Transpose(lambda).g(x1,x2),\newline
    [x1,x2,lambda1,lambda2,lambda3,lambda4]):\newline
 \# Create Lagrangian Function.}
\item \mf{LG:=Gradient(L(x1,x2,lambda1,lambda2,lambda3,lambda4), \newline
[x1,x2,lambda1,lambda2,lambda3,lambda4]):
\newline \# Create Lagrangian Gradient.}
\item \mf{CS:=seq(g(x1,x2)[i]*lambda[i]=0,i=1..4):
\newline\# Create complementary slackness equations.}
\item \mf{solve(\{CS,LG[1]=0,LG[2]=0\}, \{x1,x2,lambda1,lambda2,
\newline lambda3,lambda4\}); \newline
\# Solve system of equations to determine KKT point 
\newline and multipliers.}
\end{maplelist}

\newpar
We have omitted the output produced by the last command, due to the fact Maple
returns several solutions. However, only one of these satisfies the feasibility conditions
along with the sign restriction on the multipliers. The resulting values are
$\ds x_1 =\frac{480}{7} \approx 68.57$, $\ds x_2=80$,
$\ds \lambda_1 = \sqrt{\frac{7}{120}}\sqrt[3]{80}-1 \approx .04$, and $\lambda_2=\lambda_3=\lambda_4=0$.
Thus the sole KKT point is $\ds \vecx_0=\begin{bmatrix} \frac{480}{7} \\ 80 \end{bmatrix} \approx \begin{bmatrix} 68.57 \\ 80 \end{bmatrix}$. Only the first constraint,
$g_1(\vecx)=350x_1+200x_2-40,000 \leq 0$, is binding at $\vecx_0$. Thus,
the regularity condition is trivially satisfied, so that $\vecx_0$
is a regular KKT point and, therefore, is the solution of the
\CMC NLP (\ref{E:ConvexNLPsConProNLP}).

\newpar
In this section we have developed a tool for solving a wide range of NLPs. In the next section,
we develop means of solving certain non-convex NLPs.

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

\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_ConvexNLPs}	
\endinput






