%********MAPLE AND EXCEL****************************************************************************
\section{The Lagrangian Function and Lagrange Multipliers}\label{S:Lagrangian}	
\setcounter{progress_ck_counter}{0}

\noi Having focused exclusively on unconstrained NLPs in Chapters
\ref{C:UnconstrainedAlgebraicMethods} and \ref{C:Numeric_Methods}, we now turn our
attention to the constrained NLP, whose general form is given by

\begin{align}\label{E:LagrangianGeneralNLP}
\mbox{ minimize } & f(\vecx )  \\
	\mbox{ subject to} \notag\\
	g_1(\vecx) &\leq 0 \notag\\
	g_2(\vecx) &\leq 0  \notag\\
	\vdots & \notag \\
    g_m(\vecx) &\leq 0  \notag\\
   h_1(\vecx) &= 0 \notag\\
	h_2(\vecx) &= 0  \notag\\
	 \vdots & \notag \\
     h_p(\vecx) &= 0. \notag
	\end{align}
We assume that $S \subseteq \R^n$ is convex and that all functions
are differentiable mappings from $S$ to $\R$. A constraint
involving a function $g_i$, where $1 \leq i \leq m$, is of \emph{inequality type}, whereas
 that involving $h_j$, where $1 \leq j \leq p$, is of \emph{equality type}.
In the spirit of linear programming terminology, we say that $\vecx \in S$ is
a \emph{feasible solution} of (\ref{E:LagrangianGeneralNLP}) if it satisfies all the constraints.

\newpar
Our prototype problem is the constrained \CMC NLP introduced in
Section \ref{SS:ConProNLP}. If $x_1$ and $x_2$ denote the number of units of material and
labor respectively, then the NLP, stated as a minimization problem, is given by

\begin{align}\label{E:LagrangianConProConstrainedNLP}
 \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}	

\newpar
The objective function we used to solve the unconstrained \CM NLP in Chapters \ref{C:UnconstrainedAlgebraicMethods} and \ref{C:Numeric_Methods}. Constraints reflect
the limitation on funds available for purchasing material and labor, the requirement of
adequate labor to produce pipes from acquired material, and sign restrictions on $x_1$
and $x_2$.

\subsection{Some Convenient Notation}

\noi Let $\vecg:S \to \R^m$ and $\vech:S \to \R^p$
be vector-valued functions defined by
$\ds \vecg(\vecx)= \begin{bmatrix} g_1(\vecx) \\ g_2(\vecx) \\ \vdots \\ g_m(\vecx) \end{bmatrix}$
and $\ds \vech(\vecx)= \begin{bmatrix} h_1(\vecx) \\ h_2(\vecx) \\ \vdots \\ h_p(\vecx) \end{bmatrix}$.
Then
(\ref{E:LagrangianGeneralNLP}) can be written more compactly as

\begin{align}\label{E:LagrangianGeneralNLPVectorForm}
 \mbox{ minimize }  & f(\vecx )  \\
	\mbox{ subject to} & \notag\\
	\vecg(\vecx) &\leq \zerovec \notag\\
\vech(\vecx) &= \zerovec. \notag
	\end{align}	

\newpar
The function $\vecg$ is vector-valued function whose components are of the type
discussed in Section \ref{S:diff_Gradient}. Consequently, we define
$\vecg$ to be differentiable at  $\vecx_0$ in $S$ if and only if each component function
$g_i$, where $1 \leq i \leq m$, is differentiable there. When this occurs, we write

\begin{equation}\label{E:KKTdiff_def}
\vecg(\vecx )= \vecg(\vecx_0 )+ \jacobian_{\vecg}(\vecx_0)( \vecx-\vecx_0 )+ \|\vecx -\vecx_0\|\vecR(\vecx,\vecx_0),
\end{equation}
where all components of $\vecR(\vecx,\vecx_0) \in \R^m$ tend to $\zerovec$ as $\vecx \to \vecx_0$ and
where $\jacobian_{\vecg}(\vecx_0)$ is an $m$ by $n$ matrix, called
the \emph{Jacobian}\index{Jacobian} of $\vecg$ evaluated at $\vecx_0$. It is the matrix whose $i$th row, $1 \leq i \leq m$, is given by the gradient vector transpose,
$\nabla g_i(\vecx_0)^t$.

\newpar
The Jacobian matrix yields the linear approximation
\begin{equation}\label{E:LagrangianLocalApproximation}
\vecg(\vecx )\approx \vecg(\vecx_0 )+ \jacobian_{\vecg}(\vecx_0) ( \vecx-\vecx_0 ) \mbox{  for  } \vecx \approx \vecx_0.
\end{equation}

\newpar
Naturally, the preceding analysis can be modified when $\vecg$ is
replaced by $\vech$, in which case $\jacobian_{\vech}(\vecx_0)$ is a $p$ by $n$ matrix.

\newpar
In Maple, the Jacobian is computed using the \mf{Jacobian} command\index{Maple!Jacobian}, located in the
\mf{VectorCalculus} package. It's general form is given by
\begin{equation*}
\mbox{ \mf{Jacobian(\ma{vector of expressions,variable list})}, }
\end{equation*}
and it computes the Jacobian of \ma{vector of expressions} with respect to the variables given in \ma{variable list}. The output of the command
is a matrix. Here is syntax illustrating how to compute the Jacobian of the function
$\vecg$, where $\vecg$ is formed using the four constraints of the \CMC NLP from
(\ref{E:LagrangianConProConstrainedNLP}). In this example, we construct the Jacobian
as a function of the vector, $\ds \vecx = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$.

\begin{maplelist}
\item \mf{with(VectorCalculus):}
\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)>: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{Jg := unapply(Jacobian(g(x1, x2), [x1, x2]), [x1, x2]): Jg(x1,x2);}
\mo{\begin{bmatrix} 350 & 200 \\ 1 & -3 \\ -1 & 0 \\ 0 & -1 \end{bmatrix}}
\end{maplelist}

\subsection{The Fritz-John Theorem}

\noi On the surface, methods for solving unconstrained NLPs might not appear
useful for solving NLP (\ref{E:LagrangianGeneralNLP}). However, this is far from the case. Methods
for solving unconstrained NLPs will prove essential in this new setting. Paramount to making the bridge between these two problem types is the \emph{Lagrangian function}\index{Lagrangian function}.

\begin{definition}\label{Th:LagrangianFunctionDefinition}
The Lagrangian function corresponding to NLP (\ref{E:LagrangianGeneralNLP}) is the function
$L:S \times \R^{m+p} \to \R$ defined by
\begin{align}\label{E:LagrangianFunctionFormula}
L(\vecx, \lambdavec,\muvec)&=f(\vecx)+\sum_{i=1}^m \lambda_i g_i(\vecx)
+\sum_{j=1}^p \mu_jh_j(\vecx)
\notag \\
&=f(\vecx)+\lambdavec^t\vecg(\vecx)+ \muvec^t \vech(\vecx), \notag
\end{align}
where $\vecx$ belongs to $\R^n$ and where $\lambdavec$ and $\muvec$
are vectors in $\R^m$ and $\R^p$ respectively, denoted by
$\ds \lambdavec=\begin{bmatrix} \lambda_1 \\ \lambda_2 \\ \vdots \\ \lambda_m \end{bmatrix}$
and $\ds \muvec=\begin{bmatrix} \mu_1 \\ \mu_2 \\ \vdots \\ \mu_p \end{bmatrix}$.
\end{definition}


\newpar
Note that in each product,
$\ds \lambdavec^t\vecg(\vecx)$ and
$\ds \muvec^t\vech(\vecx)$,
there exists a natural correspondence between each constraint of the NLP
(\ref{E:LagrangianGeneralNLP}) and a component of $\lambdavec$ or $\muvec$. In particular,
a constraint of inequality type (respectively, of equality type) corresponds
to a component of $\lambdavec$ (respectively, to a component of $\muvec$).

\newpar
Our subsequent investigation focuses on the Lagrangian function. Using this
tool, we obtain important information regarding solutions of
(\ref{E:LagrangianGeneralNLP}). The overall process closely resembles
that from Section \ref{S:diff_Gradient} and Section \ref{S:optimality_sufficient_SOC} in that we
first determine necessary conditions $\vecx_0$ in $\R^n$
to be a solution of (\ref{E:LagrangianGeneralNLP}). Then we establish sufficient conditions for
$\vecx_0$ to be a solution of this NLP. These tools, which were developed in the mid 1900's by
Fritz John\index{John,F.}, William Karush\index{Karush, W.}, Harold William Kuhn,\index{Kuhn, H.W.}
and Albert William Tucker, form the basis of constrained optimization theory.

\newpar
Throughout this discussion, unless stated otherwise, we use the notation
$\ds
\nabla L(\vecx,\lambdavec,\muvec)=\nabla_{\vecx}L(\vecx,\lambdavec,\muvec)
$ to denote the gradient of $L$ with respect to the components of $\vecx$. We leave it
as an exercise to show that the gradient of the Lagrangian may be written
\begin{equation}\label{E:LagrangianFunctionGradient}
\nabla L(\vecx,\lambdavec,\muvec)=\nabla f(\vecx) + \jacobian_{\vecg}(\vecx)^t \lambdavec
+ \jacobian_{\vech}(\vecx)^t \muvec.
\end{equation}
\noi
We now state an important necessary condition, in terms of the Lagrangian, for a feasible solution of
 (\ref{E:LagrangianGeneralNLPVectorForm}) to be optimal.
\begin{theorem}\label{Th:FritzJohnTheorem}\index{Fritz John Theorem}
Consider the NLP (\ref{E:LagrangianGeneralNLPVectorForm}) and assume that $f$ and all component
functions of $\vecg$ and $\vech$ are differentiable on
$S$. Suppose that $\vecx_0$ is a solution of the NLP. Then there exist vectors, $\lambdavec_0 \in \R^m$ and
$\muvec_0 \in \R^p$, having the properties
\begin{equation}\label{E:LagrangianFritzJohnFormula}
\nabla L(\vecx_0,\lambdavec_0,\muvec_0)= \zerovec,
\end{equation}
$ \lambdavec_0 \geq \zerovec$, and
\begin{equation}\label{E:LagrangianFritzJohnComplementarySlackness}
\lambda_{0,i}g_i(\vecx_0)=0 \quad \mbox{for } 1 \leq i \leq m.
\end{equation}
\end{theorem}

\newpar
Theorem \ref{Th:FritzJohnTheorem} is often referred to as the Fritz John Theorem\index{John, R.}. We omit its proof, which can be found in other texts.(\cite{Avriel}) Instead, we take a closer look at its meaning.

\newpar
First, entries of the vectors
$\lambdavec_0$ and $\muvec_0$ are referred to as the \emph{Lagrange multipliers}\index{Lagrange multiplier}
associated with the NLP (\ref{E:LagrangianGeneralNLPVectorForm}), and the vectors
$\lambdavec_0$ and $\muvec_0$ as the \emph{multiplier vectors}\index{Lagrange multiplier!vector}.
Second, Theorem \ref{Th:FritzJohnTheorem} has a simple interpretation in
terms of linear dependence. In particular, the theorem asserts
\begin{align}\label{E:LagrangianLinearIndependence}
\zerovec&= \nabla L(\vecx_0,\lambdavec_0,\muvec_0) \\
&= \nabla f(\vecx_0) + \jacobian_{\vecg}(\vecx_0)^t \lambdavec_0
+ \jacobian_{\vech}(\vecx_0)^t \muvec_0 \notag \\
&= \nabla f(\vecx_0) + \sum_{i=1}^m \lambda_{0,i} \nabla g_j(\vecx_0) +
\sum_{j=1}^p \mu_{0,j} \nabla h_j(\vecx_0).
 \notag
\end{align}

\noi
Thus, $\ds \nabla f(\vecx_0)$ is a linear combination of the vectors in
\begin{equation}\label{E:LagrangianLinearIndependenceGradients}
 \left\{ \nabla g_1(\vecx_0),\nabla g_2(\vecx_0),\ldots,\nabla g_m(\vecx_0),
 \nabla h_1(\vecx_0),\nabla h_2(\vecx_0),\ldots,\nabla h_p(\vecx_0)
 \right\},
\end{equation}
with weights determined by the multiplier vectors $\lambdavec_0$ and $\muvec_0$.

\newpar
Finally, an inequality constraint of the form
$\ds g_i(\vecx)\leq 0$ corresponds to the sign restriction $\lambda_{0,i} \geq 0$, whereas
$\ds h_j(\vecx)= 0$ corresponds to a multiplier
$\mu_{0,j}$ that is \emph{unrestricted in sign}\index{unrestricted in sign}. This result suggests
an intriguing connection between the multiplier vectors, $\lambdavec_0$ and $\muvec_0$, and
duality, a connection that is reinforced if we note that the
 condition $\lambda_{0,i}g_i(\vecx_0)=0$ for $1 \leq i \leq m$ corresponds to the complementary
 slackness property, Theorem \ref{Th:Duality_complementary_slackness}, from Section \ref{S:Duality}. Stated
 in simple terms, this condition dictates that at an optimal
 solution, $\vecx_0$, of the NLP, either the multiplier,
 $\lambda_{0,i}$ is zero, or the corresponding constraint, $\vecg_i(\vecx)$,
 is \emph{binding}\index{binding constraint}. Exercise 3 takes a closer look
 at these connections in the context of the \LP LP from Part \ref{P:Linear_Programming}.
As a result of these observations, in subsequent discussions we shall refer to (\ref{E:LagrangianFritzJohnComplementarySlackness})
as the complementary slackness conditions\index{complementary slackness}. Since, for $\lambda_{0,i} \geq 0$
and $g_i(\vecx_0) \leq 0$ for $1 \leq i \leq m$, it follows that this condition can be expressed in matrix-vector
form as $\ds \lambdavec_0 \vecg(\vecx_0)=0$.

\newpar
To understand how the solution of an NLP determines the Lagrange multiplier vectors, we consider
the \CMC NLP (\ref{E:LagrangianConProConstrainedNLP}). In the next section, we will establish that the optimal solution is given
by
\begin{equation}\label{E:LagrangianConProSolution}
\vecx_0 = \begin{bmatrix} 480/7 \\ 80 \end{bmatrix} \approx \begin{bmatrix}  68.57 \\ 80 \end{bmatrix},
\end{equation}
with corresponding objective value, $\ds f(\vecx_0) = -9953.15$. Thus,
using approximately 68.57 units of material and 80 units of labor, \CMC has
a maximum profit of \$ 9953.15, given the constraints dictated in (\ref{E:LagrangianConProConstrainedNLP}).
Observe that this solution differs from that of the unconstrained version of the problem,
which we solved in Section \ref{S:optimality_sufficient_SOC}, and whose
solution was $\ds \vecx_0=\begin{bmatrix} 784/9 \\ 2744/27 \end{bmatrix}
\approx \begin{bmatrix} 87.11 \\ 101.63 \end{bmatrix}$
with corresponding profit approximately equal to \$ 10,162.96.

\newpar
A simple calculation shows that at the optimal solution, only the first
constraint, $g_1(\vecx)=350x_1+200x_2-40000 \leq 0$ is binding. Thus by
(\ref{E:LagrangianFritzJohnComplementarySlackness}),
$\ds \lambda_{0,2}=\lambda_{0,3}=\lambda_{0,4}=0$. The Lagrangian has its gradient
given by

\begin{align}\label{E:LagrangianCMCLagrangianGradient}
\nabla L(\vecx,\lambdavec)&=\nabla f(\vecx) + \jacobian_{\vecg}(\vecx)^t \lambdavec \\
&= - \begin{bmatrix} \frac{ 700x_2^{\frac{1}{3} }}{\sqrt{x_1}}+350
\\  \frac{1400\sqrt{x_1}  }{ 3x_2^{\frac{2}{3} }} +200  \end{bmatrix}
+ \begin{bmatrix} 350 & 1 & -1 & 0 \\ 200 & -3 & 0 & -1 \end{bmatrix}
\begin{bmatrix} \lambda_{1} \\ \lambda_{2} \\ \lambda_{3} \\ \lambda_{4} \end{bmatrix} \notag \\
&= \begin{bmatrix} -\frac{ 700x_2^{\frac{1}{3} }}{\sqrt{x_1}}+350 + 350 \lambda_1 + \lambda_2 - \lambda_3 \\  -\frac{1400\sqrt{x_1}  }{ 3x_2^{\frac{2}{3} }} + 200 + 200\lambda_1 - 3 \lambda_2
-\lambda_4 \end{bmatrix}. \notag
\end{align}

\noi
Evaluating $\nabla L$ at $\ds \vecx_0=\begin{bmatrix} 784/9 \\ 2744/27 \end{bmatrix}$
and $\ds \lambda_{0,2}=\lambda_{0,3}=\lambda_{0,4}=0$ and setting each component of the result
to zero, we obtain
\begin{equation}\label{E:LagrangianCMCLambda1Value}
\lambda_{0,1} = \sqrt{\frac{7}{120}}\sqrt[3]{80}-1 \approx .04.
\end{equation}

\newpar
The results of these calculations indicate that at the optimal solution of NLP (\ref{E:LagrangianConProConstrainedNLP}),
$\ds \vecx_0=\begin{bmatrix} 784/9 \\ 2744/27 \end{bmatrix}$, the Lagrange
multiplier vector is given by $\lambdavec_0 \approx \begin{bmatrix} .04 \\ 0 \\ 0 \\ 0 \end{bmatrix}$.
In light of the linear dependence relation spelled out by
(\ref{E:LagrangianLinearIndependence}), we see that
\begin{align*}
\zerovec &= \nabla f(\vecx_0) + \jacobian_{\vecg}(\vecx_0)^t \lambdavec_0 \notag \\
&= \nabla f(\vecx_0) + \lambda_{0,1} \nabla g_1(\vecx_0) \notag \\
&\approx \nabla f(\vecx_0) + .04 \nabla g_1(\vecx_0) \notag
\end{align*}

\noi
Thus, for the \CMC NLP, at the optimal solution, $\vecx_0$ the gradients of $f$ and the first constraint function, $g_1$, are scalar multiples of one another, where the scaling
factor is approximately $-.04$.

\newpar
Figure \ref{Fi:f09x01x01} illustrates the feasible region for the \CMC NLP,
the optimal solution, $\ds \vecx_0=\approx \begin{bmatrix} 87.11 \\ 101.63 \end{bmatrix}$,
$\nabla f(\vecx_0)$, and $\nabla g_1(\vecx_0)$. Vectors have been scaled for
purposes of visualization.

\begin{figure}[h]
\centering
\psfrag{x1_axis_label}[Bc][Bc]{$x_1$}
\psfrag{x2_axis_label}[Bc][Bc]{$x_2$}
\psfrag{x0}[Bc][Bc]{$\vecx_0$}
\psfrag{del_f}[Bc][Bc]{$\nabla f$}
\psfrag{del_g}[Bc][Bc]{$\nabla g_1$}
\includegraphics[width=.7\linewidth]{images/f09x01x01.eps}
\caption{Feasible region of the \CMC NLP illustrating objective and constraint gradients at
the solution, $\vecx_0$.}
\label{Fi:f09x01x01}
\end{figure}

\subsection{Interpreting the Multiplier}\index{Lagrange multiplier!interpretation}

\noi
The multiplier, $\lambda_{0,1} \approx .04$ in the \CMC NLP has a simple economic interpretation. First, observe that the units
of the Lagrangian function in (\ref{E:LagrangianCMCLagrangianGradient}) are the same as the units of $f$, namely dollars (of profit). Since the units of $g_1$, the only binding constraint in the solution,
are dollars (of available funds for material and labor), the units of  $\lambda_{0,1}$ are dollar of profit per dollar of available material/labor funding. Put another way, the multiplier $\lambda_{0,1}$
is the instantaneous rate of change of the objective, $f$, with respect to the constraint function,
$g_1$. This means that if $g_1$ changes by a small amount, small enough so that it remains a binding constraint, we should notice the value of $f$ at the optimal solution change by an amount approximately equal to the change in $g_1$, multiplied by $\lambda_{0,1}$.

\newpar For example, suppose the funds available to \CMC for material and labor from increases
 by \$100 from \$40,000 to \$4,100. Then the corresponding constraint changes from $\ds 350x_1+200x_2 <=40,000$ to $\ds 350x_1+200x_2 <=40,100 $, or, equivalently, $g_1$ in (\ref{E:LagrangianConProConstrainedNLP})
decreases and becomes
\begin{equation}\label{E:LagrangianNew_g1}
g_1(\vecx) -100 = 350x_1+200x_2 -40100 \leq 0.
\end{equation}
In terms of Figure \ref{Fi:f09x01x01}, such a change corresponds to moving slightly up and to the right the segment on the boundary of the feasible region
that passes through $\ds \vecx_0=\begin{bmatrix} 784/9 \\ 2744/27 \end{bmatrix}$. The multiplier,
$\lambda_{0,1} \approx .04$, indicates, that, under such a change, we should expect to see the objective
value in the solution
of the new NLP to change by $\Delta f \approx .04 (-100)=-4$. This is a fairly good approximation,
for if we replace the original first constraint by that in (\ref{E:LagrangianNew_g1}) and solve
the resulting NLP (with Maple) we obtain a new optimal objective value of
$-9957.21$. This value, less that of  $\ds f(\vecx_0) = -9953.15$, is -4.06. Thus, with
with \$100 more funds available for capital and
labor, \CM's profit increases by a mere \$4.06.

\newpar
In essence, we can view the multiplier as playing a role in sensitivity analysis when we increase the
bound on the right-hand side of a constraint. In fact, if we recall the concept
of a \emph{shadow price}\index{shadow price} introduced in Section \ref{S:Sensitivity_constraint_change}, we see
that the multiplier generalizes this idea to the nonlinear setting. What is more, shadow prices
in the LP setting equalled the slack variable coefficients in the top row of the tableau, which
in turn corresponded to the decision variables in the LP's dual formulation. That Lagrange multipliers are somehow connected to dual decision variables in the LP setting becomes the focus of further investigation
in Exercise (4).

\section*{
Exercises Section \protect\ref{S:Lagrangian}}
\input{Exercises/Exercises_Lagrangian}	
\endinput








