\section{Nonlinear Programming: An Overview}\label{S:NLP_Overview}
\setcounter{progress_ck_counter}{0}

\noi The world we live in is ``nonlinear'' in that mathematical relationships between
quantities are rarely described by simple linear functions. As a result, nonlinear programming is
an essential tool for solving problems from a variety of disciplines. The goal of subsequent chapters is to become acquainted with several such problems and to develop an understanding of fundamental mathematical tools used to address them.

\subsection{The General Nonlinear Programming Model}

\noi A nonlinear program, or NLP, is a
generalization of the LP in which the objective function is permitted to be nonlinear and constraints
are permitted to take the form of nonlinear inequalities. Specifically, an NLP can be expressed as follows:\index{nonlinear programming problem!general form}
\begin{align}\label{E:overview_NLP_general_NLP_form}
 \mbox{minimize } f(x_1, x_2, \ldots, x_n)   \\
	\mbox{ subject to}& \notag \\
	g_1(x_1, x_2, \ldots, x_n) &\leq 0 \notag\\
	g_2(x_1, x_2, \ldots, x_n) &\leq 0  \notag\\
	\vdots \phantom{g_2(x_1, x_2)} \vdots & \notag \\
	g_m(x_1, x_2, \ldots, x_n) &\leq 0.  \notag
	\end{align}	

\newpar
Unless stated otherwise, we will incorporate any sign restrictions into the constraints. Of course NLPs whose goal involves maximization and/or whose constraints include equations as opposed to inequalities, can easily be converted to the form of (\ref{E:overview_NLP_general_NLP_form}) through simple algebraic manipulations. Finally, an NLP having no constraints is said to be \emph{unconstrained}.

\subsection{Plotting Feasible Regions and Solving NLPs with Maple}

\noi Feasible regions for NLPs are a bit more complicated to graph with Maple than are those for LPs, due
the fact Maple's \mf{inequal} command only plots feasible regions corresponding to lists of
linear inequalities. However, with a bit of creativity, we can work around this obstacle.

\newpar
To illustrate this idea, we consider the simple two-variable NLP given by
 \begin{align}\label{E:NLPintro_two_variable_example}
 \mbox{maximize} f(x_1,x_2) &=x_1x_2   \\
	\mbox{ subject to} \notag\\
	x_1^2+x_2^2 &\leq 1 \notag\\
	x_1 &\geq 0.  \notag
	\end{align}
\noi
Using the notation of (\ref{E:overview_NLP_general_NLP_form}) for the constraints, we note that (\ref{E:NLPintro_two_variable_example}) is
equivalent to

\begin{align}\label{E:overview_NLP_two_variable_model}
 \mbox{maximize} f(x_1, x_2) &=x_1x_2  \\
	\mbox{ subject to} \notag\\
	 x_1^2+x_2^2 -1 &\leq 0\notag\\
	-x_1 &\leq 0.  \notag
	\end{align}	

\noi The first constraint is nonlinear, so Maple's \mf{inequal} command cannot be used to plot the feasible region. Instead, we combine \mf{piecewise}\index{Maple!\mf{piecewise}} and \mf{implicitplot}\index{Maple!\mf{implicitplot}} as
follows:\index{nonlinear programming problem!plotting feasible regions with Maple}

\begin{maplelist}
\item \mf{restart:with(plots):}
\item \mf{g1:=(x1,x2)->x1\^{}2 + x2\^{}2-1; \# Enter first constraint function.}
\mo{g_1:=(x_1,x_2) \rightarrow x_1^2+x_2^2-1}
\item \mf{g2:=(x1,x2)->-x1; \# Enter second constraint function.}
\mo{g_2:=(x_1,x_2) \rightarrow -x_1}
\item \mf{ F:=piecewise(g1(x1,x2)<=0 and g2(x1,x2)<=0,1);
\newline \# Define a two-variable function that equals 1 precisely
\newline if its input is feasible for the NLP.}
\mo{ F:=(x_1,x_2) \rightarrow piecewise(g_1(x_1,x_2) \leq 0 \mbox{ and } g_2(x_1,x_2) \leq 0, 1)}
\item \mf{FeasibleRegion:=implicitplot(F(x1,x2)=1,x1=0..1,x2=-1..1,color=grey, grid=[200,200]):
\newline \# Create feasible region plot using implicitplot command.
\newline \# The horizontal and vertical viewing windows are
\newline \# divided into 200 grid points.}
\item \mf{display(FeasibleRegion);}
\end{maplelist}

\noi
The result of the \mf{display} command is shown in Figure \ref{Fi:f07x01x01}.

\begin{figure}[h]
\centering
\psfrag{x1axislabel}[Bc][Bc]{$x_1$}
\psfrag{x2axislabel}[Bc][Bc]{$x_2$}
\includegraphics[width=.7\linewidth]{images/f07x01x01.eps}
\caption{Feasible region for NLP (\ref{E:NLPintro_two_variable_example}).}\label{Fi:f07x01x01}
\end{figure}

\newpar
As was the case in the linear programming setting, contours are useful for estimating the solution of an NLP. In Maple, they can be generated and then
superimposed on the feasible region by combining the \mf{contourplot} and \mf{display}
commands as was done in Section \ref{S:LP_Graphical}. Unfortunately, Maple does not label contours. This fact, along with the nonlinearity of the objective and constraints, can make estimating the solution
of an NLP using its contour diagram extremely difficult.

\newpar One means of gaining a better sense of how the objective function changes within the feasible region is to add within the \mf{implicitplot} command the options
\mf{filled = true, coloring = [white, black]}. Doing so has the effect
 of shading between contours in such a way that smallest function values correspond to white regions, largest values correspond to black, and intermediate values to
varying shades of grey. Maple syntax that achieves this outcome is given as follows:

\begin{maplelist}
\item \mf{f:=(x1,x2) -> x1*x2;}
\mo{ f:=(x_1,x_2) \rightarrow x_1x_2}
\item \mf{ObjectiveContours:=contourplot(f(x1,x2),x1=0..1,x2=-1..1,filled = true, coloring = [white, black]): \# Create contour plot.}
\item \mf{display(\{FeasibleRegion,ObjectiveContours\});
\newline \# Superimpose contours on previously-constructed feasible region.}
\end{maplelist}

\newpar
The result in this case produces the graph in Figure \ref{Fi:f07x01x02}.
It suggests that the solution of (\ref{E:overview_NLP_two_variable_model}) occurs at the point on the unit circle corresponding
to $\frac{\pi}{4}$, which is of course $(x_1,x_2)=\left(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}} \right)$.

\begin{figure}[h]
\centering
\psfrag{x1axislabel}[Bc][Bc]{$x_1$}
\psfrag{x2axislabel}[Bc][Bc]{$x_2$}
\includegraphics[width=.7\linewidth]{images/f07x01x02.eps}
\caption{Feasible region and contour shading for NLP (\ref{E:NLPintro_two_variable_example}).}\label{Fi:f07x01x02}
\end{figure}

\newpar
Maple's \mf{NLPSolve}\index{Maple!\mf{NLPSolve}} command, located in the \mf{Optimization} package, functions almost exactly as its linear programming counterpart, \mf{LPSolve}. To
solve NLP (\ref{E:overview_NLP_two_variable_model}), we merely enter the following:

\begin{maplelist}
\item \mf{restart: with(Optimization):}
\item \mf{f:=(x1,x2)->x1*x2;}
\mo{f:=(x_1,x_2) \rightarrow x_1x_2}
\item \mf{g1:=(x1,x2)->x1\^{}2 + x2\^{}2-1;}
\mo{g_1:=(x_1,x_2) \rightarrow x_1^2+x_2^2-1}
\item \mf{g2:=(x1,x2)->-x1;}
\mo{g_2:=(x_1,x_2) \rightarrow -x_1}
\item \mf{NLPSolve(f(x1,x2),[g1(x1,x2)<=0,g2(x1,x2)<=0],'maximize');}
\mo{.500000000001127654, [x_1 = .707106781187344936, x_2 = .707106781187344936]}
\end{maplelist}

\noi
Thus NLP (\ref{E:overview_NLP_two_variable_model}) has a solution of
$(x_1,x_2) \approx (.7071,.7071)$, with corresponding objective value of $.5$. In subsequent sections
will develop develop algebraic techniques that
prove this solution equals
$(x_1,x_2)=\left(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}} \right)$.

\subsection{A Prototype NLP Example}\label{SS:ConProNLP}

\noi In Part \ref{P:Linear_Programming}, the \LPC model served to illustrate a variety
of important linear programming principles. As two-variable models are convenient for
visualizing important concepts in general, we focus in Part \ref{P:Nonlinear_Programming} on a simple two-variable NLP.

\newpar
\CMC\index{ConPro Manufacturing Company} is a small business that produces large concrete pipes. The
company seeks to maximize its profit subject to certain constraints. Assume pipe production is a function of material and labor and that the number of units of each of these quantities is
denoted by $x_1$ and $x_2$,
respectively. The company has determined that production, measured in units of pipe, is given by the product power function

\begin{equation}\label{E:overview_NLP_prod_fcn}
P(x_1, x_2) = x_1^{\frac{1}{2}}x_2^{\frac{1}{3}}.
\end{equation}

\noi
The function $P$ is known as a \emph{Cobb-Douglas Production Function}\index{Cobb-Douglas Production Function}, whose
general form is given by $\ds P(x_1, x_2) = x_1^{\alpha}x_2^{\beta}$, where $\alpha, \beta >0$.

\newpar
Each unit of produced pipe generates \$1400 of revenue but costs \$350 in materials and \$200 in labor to
produce. The company has \$40,000 of available funds to spend, and the ratio of labor units to material
units must be at least one-third in order to ensure adequate labor to produce pipe from acquired materials.
Assume \CM sells all the pipe that it produces.

\newpar
\CM's profit as a function of material and labor is given by revenue, less material and
labor cost:
\begin{align}\label{E:obj_fcn_overview_NLP}
f(x_1, x_2) &= 1400P(x_1,x_2)-350x_1-200x_2 \\
             &= 1400 x_1^{\frac{1}{2}}x_2^{\frac{1}{3}} -350x_1-200x_2. \notag
\end{align}

\noi
Funding limits imply that $\ds 350x_1+200x_2  \leq 40000  $, and the requirement
of adequate labor to ensure pipe production of acquired materials  forces $\ds x_1 \leq 3x_2$.
Assuming positive decision variable
values capable of taking on non-integer values, we obtain NLP (\ref{E:ConProNLP_overview_NLP}):\index{Conpro problem}

\begin{align}\label{E:ConProNLP_overview_NLP}
 \mbox{maximize} f(x_1,x_2 )&= 1400 x_1^{\frac{1}{2}}x_2^{\frac{1}{3}} -350x_1-200x_2 \\
	\mbox{ subject to} & \notag\\
	350x_1+200x_2  &\leq 40000 \notag\\
	x_1-3x_2 &\leq 0  \notag\\
	x_1,x_2 &> 0.  \notag
	\end{align}	
\noi
Note that this NLP includes sign restrictions on its decision variables. By our convention, these restrictions contribute two constraints, $-x_1 \leq 0$ and $-x_2 \leq 0$, so that the NLP has four constraints total.

\newpar
In subsequent chapters, we learn how nonlinear programming tools can be used to address a variety of questions. Among these are the following:
\be
\item How closely does $P$ portray the actual production values?
\item In the absence of any constraints, what combination of material units and labor units
maximizes profit? Is this combination necessarily unique?
\item If constraints are incorporated into the model, what new combination maximizes profit? Again,
is this combination unique?
\item If exact answers to the previous two questions are unattainable using algebraic means, do numeric methods exist that achieve
approximate results?
\ee

\newpar
Answers to these questions incorporate a variety of mathematical tools, most notably those from
linear algebra and multivariate calculus.


\begin{progress_ck}
Consider the \CM NLP, (\ref{E:ConProNLP_overview_NLP}).
\be
\item Graph the feasible region for this NLP.
\item Using Maple if necessary, create a contour diagram of the objective function and estimate the NLP's solution.
\item Solve the NLP using Maple's \mf{NLPSolve} command. Is the solution
at a corner point of the feasible region as was always the case in the linear programming
setting?
\ee
\end{progress_ck}

\section*{
Exercises Section \protect\ref{S:NLP_Overview}}
\input{Exercises/Exercises_NLP_Overview}	

\endinput 