The Unconstrained Nonlinear Programming Solver: Conditions of Optimality :: SAS/OR(R) 9.2 User's Guide: Mathematical Programming

The Unconstrained Nonlinear Programming Solver

Conditions of Optimality

Before beginning the discussion, we present the following notation for easy reference:

: dimension of , i.e., the number of decision variables
: iterate, i.e., the vector of decision variables
: objective function
$\nabla\!f(x)$: gradient of the objective function
$\nabla^2\!f(x)$: Hessian matrix of the objective function

Denote the feasible region as $\cal{f}$ . In unconstrained problems, any point $x \in \mathbb{r}^n$ is a feasible point. Therefore, the set $\cal{f}$ is the entire $\mathbb{r}^n$ space.

A point is a local solution of the problem if there exists a neighborhood ${\cal n}$ of such that

$f(x)\ge f(x^*)\;\;{\rm forall} x\in{\cal n}\cap{\cal{f}}$

Further, a point

is a strict local solution if strict inequality holds in the preceding case, i.e.,

$f(x) \gt f(x^*)\;\;{\rm forall} x\in{\cal n}\cap{\cal{f}}$

A point $x^* \in \mathbb{r}^n$ is a global solution of the problem if no point in $\cal{f}$ has a smaller function value than

), i.e.,

$f(x)\ge f(x^*)\;\;{\rm forall} x\in{\cal{f}}$

All the algorithms in the NLPU solver find a local minimum of an optimization problem.

Unconstrained Optimization

The following conditions hold for unconstrained optimization problems:

First-order necessary conditions: If is a local solution and is continuously differentiable in some neighborhood of , then
$\nabla\!f(x^*) = 0$
Second-order necessary conditions: If is a local solution and is twice continuously differentiable in some neighborhood of , then $\nabla^2\!f(x^*)$ is positive semidefinite.
Second-order sufficient conditions: If is twice continuously differentiable in some neighborhood of , and $\nabla\!f(x^*) = 0$ and $\nabla^2\!f(x^*)$ is positive definite, then is a strict local solution.

Top of Page