The Unconstrained Nonlinear Programming Solver |
Conditions of Optimality
Before beginning the discussion, we present the following notation for easy reference:
![n](images/nlpu_nlpueq24.gif)
- dimension of
, i.e., the number of decision variables
![x](images/nlpu_nlpueq25.gif)
- iterate, i.e., the vector of
decision variables
![f(x)](images/nlpu_nlpueq26.gif)
- objective function
![\nabla\!f(x)](images/nlpu_nlpueq27.gif)
- gradient of the objective function
![\nabla^2\!f(x)](images/nlpu_nlpueq28.gif)
- Hessian matrix of the objective function
Denote the feasible region as
![\cal{f}](images/nlpu_nlpueq29.gif)
. In unconstrained problems, any point
![x \in \mathbb{r}^n](images/nlpu_nlpueq2.gif)
is a feasible point. Therefore, the set
![\cal{f}](images/nlpu_nlpueq29.gif)
is the entire
![\mathbb{r}^n](images/nlpu_nlpueq5.gif)
space.
A point
is a local solution of the problem if there exists a
neighborhood
of
such that
![f(x)\ge f(x^*)\;\;{\rm forall} x\in{\cal n}\cap{\cal{f}}](images/nlpu_nlpueq32.gif)
Further, a point
![x^*](images/nlpu_nlpueq30.gif)
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}}](images/nlpu_nlpueq33.gif)
A point
![x^* \in \mathbb{r}^n](images/nlpu_nlpueq34.gif)
is a global solution of the problem if no point in
![\cal{f}](images/nlpu_nlpueq29.gif)
has a smaller function value than
![f(x^*](images/nlpu_nlpueq35.gif)
), i.e.,
![f(x)\ge f(x^*)\;\;{\rm forall} x\in{\cal{f}}](images/nlpu_nlpueq36.gif)
All the algorithms in the NLPU solver find a local minimum of an optimization problem.
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](images/nlpu_nlpueq37.gif)
- Second-order necessary conditions: If
is a local solution and
is twice continuously differentiable in some neighborhood of
, then
is positive semidefinite.
- Second-order sufficient conditions: If
is twice continuously differentiable in some neighborhood of
, and
and
is positive definite, then
is a
strict local solution.
Copyright © 2008 by SAS Institute Inc., Cary, NC, USA. All rights reserved.