\section{Differentiability and a Necessary First-Order Condition}\label{S:diff_Gradient}
\setcounter{progress_ck_counter}{0}

\noi We begin our study of nonlinear programming by focusing on unconstrained NLPs.
If $S \subseteq \R^n$ and the objective function $\ds f:S \to \R$, then the general form
of such a problem is given by
\begin{equation}\label{E:diff_Gradient_general_NLP}
\mbox{minimize (or maximize) } f(\vecx) \mbox{, where }\vecx \in S.
\end{equation}

\noi We shall later discover that constrained NLPs are solved using a method that involves
cleverly converting them to an unconstrained problem
of the form (\ref{E:diff_Gradient_general_NLP}). For unconstrained NLPs,
our investigation follows a line of reasoning similar to that from
a single-variable calculus course. In this section we derive necessary conditions for a feasible point
to be an optimal solution. This step will be the easy part. The more challenging task,
which is addressed in Sections \ref{S:convexity_FOC}
and \ref{S:optimality_sufficient_SOC}, is to establish sufficient conditions.

\subsection{Differentiability}

\noi Deriving necessary conditions begins with stating a clear definition
of differentiability. Throughout subsequent discussions, we let $\ds \|\vecx \|$ denote the usual Euclidean vector norm in $\R^n$.

\begin{definition}\label{Th:diff_Gradient_diff_def}\index{gradient}
Suppose that $\ds S \subseteq \R^n$ and that $\ds f:S \to \R$. We say that the function $f$
is \emph{differentiable}\index{differentiable} at $\vecx_0$ in $S$ if and only if there exists a vector depending
upon $f$ and $\vecx_0$ ,
called \emph{the gradient of $f$ at $\vecx_0$}, written $\ds \nabla f(\vecx_0)$, and a
scalar function
$R(\vecx_0;\vecx)$ dependent upon $\vecx_0$ and defined for all $\vecx$ in $S$, such that
\begin{equation}\label{E:diff_Gradient_diff_def}
f(\vecx )= f(\vecx_0 )+ \nabla f(\vecx_0)^t ( \vecx-\vecx_0 )+ \|\vecx -\vecx_0\|R(\vecx_0;\vecx) ,
\end{equation}
for all $\vecx$ in $S$ and $\ds \lim_{\vecx \to \vecx_0} R(\vecx_0;\vecx)=0$.
\end{definition}

\newpar
Here are some important facts to keep in mind regarding this definition.
\be
\item
Since $\ds \nabla f(\vecx_0)$ is a column vector, its transpose is a row vector in $\R^n$.
Thus, $\ds \nabla f(x_0)^t ( \vecx-\vecx_0 )$ is a scalar, as are the remaining
three terms in (\ref{E:diff_Gradient_diff_def}).
\item Equation (\ref{E:diff_Gradient_diff_def}), due to the presence of the limit, implicitly assumes
that $f$ is defined at inputs sufficiently close to
$\vecx_0$. Consequently, there
must exist a small neighborhood, or open disk, about $\vecx_0$ that is contained in $S$. A set $S \subseteq \R^n$ in which
every point has an open disk about it contained in $S$, is said to be
\emph{open}\index{open set}.
\item If the last term is discarded from (\ref{E:diff_Gradient_diff_def}), we
obtain the function
\begin{equation}\label{E:diff_Gradient_tangent_plane}
T(\vecx)= f(\vecx_0 )+ \nabla f(\vecx_0)^t ( \vecx-\vecx_0 ),
\end{equation}
the linearization\index{linearization}, or linear approximation of $f$, based at $\vecx_0$, which is analogous to the tangent line formula
from calculus.
Thus, \newline
$\ds \|\vecx -\vecx_0\|R(\vecx_0;\vecx)$ is
an error term in this approximation, and
the condition that $\ds \lim_{\vecx \to \vecx_0} R(\vecx_0;\vecx)=0$ indicates
how quickly this error term decays to zero as $\ds \vecx \to \vecx_0$.
\ee

\newpar
An elementary fact, whose proof we omit, is that the
components of the gradient consist of the first-order partial derivatives
of $f$. That is,
\begin{equation}\label{E:diff_Gradient_grad_partials}
\nabla f(\vecx)= \begin{bmatrix} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_2}
\\ \vdots \\ \frac{\partial f}{\partial x_n} \end{bmatrix},
\end{equation}
where $\ds \vecx=\begin{bmatrix}  x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}$. This result is easily proven
using (\ref{E:diff_Gradient_diff_def}). If each partial derivative,
$\ds \frac{\partial f}{\partial x_i}$, where $1 \leq i \leq n$, is continuous on $S$, we
say that $\nabla f(\vecx)$ is \emph{continuously differentiable}\index{continuously differentiable}
on $S$.

\newpar
In Maple, the \mf{Gradient}\index{Maple!\mf{Gradient}} command, located in the \mf{VectorCalculus}
package provides a means for computing the gradient. Its general form is given by  \mf{Gradient(\ma{expression,variable list})}. Here, \ma{variable list} indicates the variables with respect to which the gradient of \ma{expression} is computed. The output of the command
is an expression given in terms of unit vectors corresponding to each variable. Each unit
vector takes the form $\vece_{variable}$. A simple example of the
command's usage is as follows:

\begin{maplelist}
\item \mf{with(VectorCalculus):}
\item \mf{Gradient(x1\^{}2 +x1*x2\^{}3,[x1,x2]);}
\mo{(2x_1+x_2^3)\bar{e}_{x1} + 3x_1x_2^2\bar{e}_{x2} }
\end{maplelist}

\noi
If $f$ is a function, the \mf{unapply} command can be used to define the corresponding
gradient function. For example,
if $f(x_1,x_2)= x_1^2+x_2^2$, its gradient function is constructed using the following syntax. Here
we name this function \mf{Delf}.

\begin{maplelist}
\item \mf{with(VectorCalculus):}
\item \mf{f:=(x1,x2)->x1\^{}2+x2\^{}2;}
\mo{f:=(x_1,x_2) \rightarrow x_1^2+x_2^2}
\item \mf{Delf:=unapply(Gradient(f(x1,x2),[x1,x2]),[x1,x2]):}
\item \mf{Delf(x1,x2);}
\mo{2x_1\vece_{x_1} + 2x_2\vece_{x_2}}
\end{maplelist}

\newpar
Using Definition (\ref{Th:diff_Gradient_diff_def}) to establish a function
is differentiable at an input, $\vecx_0$, can be somewhat tedious due to the fact we
must show $\ds \lim_{\vecx \to \vecx_0} R(\vecx_0;\vecx)=0$. The following Waypoint
illustrates one means of accomplishing this.

\begin{progress_ck}
Consider the function $\ds f(x_1,x_2)=x_1x_2^2-2x_1^2+3x_2$ along with
$\ds \vecx_0=\begin{bmatrix} 2 \\ 1 \end{bmatrix}$.
\be
\item Calculate the linear approximation
\begin{equation*}
T(\vecx)= f(\vecx_0 )+ \nabla f(\vecx_0)^t ( \vecx-\vecx_0 ),
\end{equation*}
where $\ds \vecx=\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$. Use your
result to determine an explicit representation, in terms of $x_1$ and $x_2$,
for the remainder term, $\ds R(\vecx_0;\vecx)$.
\item Now express $\ds R(\vecx_0;\vecx)$ in polar form as a function of $r>0$ and
$\theta$, where $x_1=2+r\cos(\theta)$ and $x_2=1+r\sin(\theta)$. Show that
$\ds \left| R(\vecx_0;\vecx)\right| \leq C\cdot r$, where $C$ is a constant. Since
$r=\|\vecx-\vecx_0 \|$, this
inequality proves that $\ds \lim_{\vecx \to \vecx_0} R(\vecx_0;\vecx)=0$.
\ee
\end{progress_ck}

\subsection{Necessary Conditions for Local Maxima or Minima}

\noi In the linear setting, we saw that for any LP, one of four possible outcomes
must occur: the LP has a unique solution, has infinitely many solutions, is infeasible, or
is unbounded. For the general unconstrained NLP (\ref{E:diff_Gradient_general_NLP}), other cases
are possible, e.g., exactly two solutions. For this reason, we must exercise great care when defining
the concept of maximum and minimum objective value in the nonlinear setting.
\begin{definition}\label{Th:diff_Gradient_extrema_def}
Suppose $S\subseteq \R^n$ and $\ds f: S \to \R$.
We say that $\vecx_0$ is a \emph{local minimum}\index{minimum!local} of $f$ if there is a sufficiently small
$\epsilon>0$ such that
\begin{equation*}
f(\vecx_0) \leq f(\vecx) \mbox{ for all $\vecx$ in $S$ satisfying } \|\vecx-\vecx_0\| < \epsilon.
\end{equation*}
If in fact $\ds f(\vecx_0) \leq f(\vecx)$ for all $\vecx$ in $S$, we say that $\vecx=\vecx_0$
is a \emph{global minimum} of $f$ on $S$.\index{minimum!global}
\end{definition}

\noi
Naturally, if the inequalities are reversed, ``minimum'' is replaced by ``maximum.'' The term \emph{strict}
is also frequently added to describe situations when inequalities are strict. For example, to say that
$\vecx=\vecx_0$ is a \emph{strict global minimum}\index{minimum!strict local}
means $\ds f(\vecx_0) < f(\vecx)$ for all $\vecx$ in $S$ with $\vecx \ne \vecx_0$. \emph{Local optimal solution}
refers to either a local minimum or maximum when the context of the appropriate term is clear.
\emph{Global optimal solution} is defined similarly.

\newpar
A function can have many local maxima and/or minima, and many inputs can share the distinction of being
the global maximum (or minimum).

\newpar
When $n=1$, the gradient is nothing more than the derivative of a function of one variable. Recall
that in the single-variable setting, the first step towards maximizing or minimizing a differentiable
function involves determining roots of the derivative, which we denote as the \emph{critical points}\index{critical point}.
The same principle, as formally stated by Theorem \ref{Th:diff_Gradient_necessary_conditions}, applies to the general unconstrained NLP.

\begin{theorem}\label{Th:diff_Gradient_necessary_conditions}
Suppose $\ds S \subseteq \R^n$ is an open set and that $\ds f:S \to \R$ is differentiable at
$\vecx_0$. If $f$ has a local minimum
or maximum at $\vecx_0$, then $\ds \nabla f(\vecx_0)=\zerovec$.
\end{theorem}
\begin{proof}
The proof involves little more than applying the single-variable result to each component of $\vecx_0$. Without
loss of generality, assume $f$ has a local minimum at $\vecx_0$. Fix an arbitrary $j$, where
$1 \leq j \leq n$ and write
$\ds \vecx_0=\begin{bmatrix} x_{0,1} \\ x_{0,2}
\\ \vdots \\ x_{0,j} \\ \vdots \\x_{0,n}\end{bmatrix}$.
Define $\ds f_j$ to be the ``cross-section'' obtained by fixing all but
the $j$th component of $f$. In other words,
\begin{equation*}
f_j(x)=f\left( \begin{bmatrix} x_{0,1} \\ \vdots \\ x_{0,j-1} \\ x \\ x_{0,j+1}
\\ \vdots \\ x_{0,n}\end{bmatrix} \right).
\end{equation*}
Observe that
\begin{equation}\label{E:differentiability_gradient_singlevariable_identity}
f_j'(x_{0,j})= \left[ \nabla f(\vecx_0) \right]_j,
\end{equation}
the $j$th component of $\nabla f(\vecx_0)$.

\newpar
Since $f$ has a local minimum at $\vecx_0$, the function
$f_j$ has a local minimum at $x=x_{0,j}$, and therefore $\ds f_j'(x_{0,j})=0$
by the single-variable result. Because $j$ was arbitrary, $\ds \left[ \nabla f(\vecx_0) \right]_j=0$ for all $1 \leq j \leq n$, implying
$\ds \nabla f(\vecx_0)=\zerovec$.
\end{proof}

\newpar
In future discussions, if $\ds S \subseteq \R^n$ is open and $\ds f:S \to \R$, we will
say $\vecx_0$ in $\R^n$ is a \emph{critical point} of $f$ if $\ds \nabla f(\vecx_0)$
is zero of undefined. Of course, if $f$ is differentiable on $S$ and $\vecx_0$ is a critical point of $f$, then $\ds \nabla f(\vecx_0)=\zerovec$.

\newpar In the single-variable setting, a critical point need not
be a local minimum or maximum. The same can be said of the unconstrained NLP
 insofar as Theorem \ref{Th:diff_Gradient_necessary_conditions} merely provides a
\emph{necessary first-order condition}, stated in terms of the gradient. If
 $\ds \nabla f(\vecx_0) \ne \zerovec$, then $\vecx_0$ can be neither a local minimum nor a local maximum. In subsequent sections we establish \emph{sufficient conditions}, which are analogous to the first- and second-derivative tests from the single-variable setting and which are adequate to guarantee  $\vecx_0$ is a local minimum or maximum.

\begin{progress_ck}
Suppose $\ds f(x_1,x_2)=x_1^3-3x_1x_2^2$. A
surface plot of this function, which is sometimes called a ``monkey saddle,''
is shown in
Figure \ref{Fi:diff_Gradient_grad_monkey_saddle_figures}.
\be
\item Show that $\vecx_0=\zerovec$ is the only critical point of $f$.
\item Explain why this critical point is neither a local maximum nor a local minimum.
\ee
\end{progress_ck}
\newpage
\begin{figure}[h]
\centering
\psfrag{x1_axis_label}[Bc][Bc]{$x_1$}
\psfrag{x2_axis_label}[Bc][Bc]{$x_2$}
\includegraphics[width=.7\linewidth]{images/f07x02x01.eps}
\caption{Surface plot of $\ds f(x_1,x_2)=x_1^3-3x_1x_2^2$.}\label{Fi:diff_Gradient_grad_monkey_saddle_figures}
\end{figure}

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

\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_diff_gradient}

\endinput 