Learn more about Optimization Toolbox

First-Order Optimality Measure

First-order optimality is a measure of how close a point x is to optimal. It is used in all smooth solvers, constrained and unconstrained, though it has different meanings depending on the problem and solver. For more information about first-order optimality, see Nocedal and Wright [31].

The tolerance TolFun relates to the first-order optimality measure. If the optimality measure is less than TolFun, the solver iterations will end.

Unconstrained Optimality

For a smooth unconstrained problem,

the optimality measure is the infinity-norm (i.e., maximum absolute value) of ∇f(x):

This measure of optimality is based on the familiar condition for a smooth function to achieve a minimum: its gradient must be zero. For unconstrained problems, when the first-order optimality measure is nearly zero, the objective function has gradient nearly zero, so the objective function could be nearly minimized. If the first-order optimality measure is not small, the objective function is not minimized.

Back to Top

Constrained Optimality—Theory

The theory behind the definition of first-order optimality measure for constrained problems. The definition as used in Optimization Toolbox functions is in Constrained Optimality in Solver Form.

For a smooth constrained problem let g and h be vector functions representing all inequality and equality constraints respectively (i.e., bound, linear, and nonlinear constraints):

The meaning of first-order optimality in this case is more involved than for unconstrained problems. The definition is based on the Karush-Kuhn-Tucker (KKT) conditions. The KKT conditions are analogous to the condition that the gradient must be zero at a minimum, modified to take constraints into account. The difference is that the KKT conditions hold for constrained problems.

The KKT conditions are given via an auxiliary Lagrangian function

(3-1)

The vector λ, which is the concatenation of λ_g and λ_h, is called the Lagrange multiplier vector. Its length is the total number of constraints.

The KKT conditions are:

(3-2)

(3-3)

(3-4)

The three expressions in Equation 3-4 are not used in the calculation of optimality measure.

The optimality measure associated with Equation 3-2 is

(3-5)

The optimality measure associated with Equation 3-3 is

(3-6)

where the infinity norm (maximum) is used for the vector .

The combined optimality measure is the maximum of the values calculated in Equation 3-5 and Equation 3-6. In solvers that accept nonlinear constraint functions, constraint violations g(x) > 0 or |h(x)| > 0 are measured and reported as tolerance violations; see Tolerances and Stopping Criteria.

Back to Top

Constrained Optimality in Solver Form

The first-order optimality measure used by toolbox solvers is expressed as follows for constraints given separately by bounds, linear functions, and nonlinear functions. The measure is the maximum of the following two norms, which correspond to Equation 3-5 and Equation 3-6:

(3-7)

(3-8)

where the infinity norm (maximum) is used for the vector in Equation 3-7 and in Equation 3-8. The subscripts on the Lagrange multipliers correspond to solver Lagrange multiplier structures; see Lagrange Multiplier Structures. The summations in Equation 3-7 range over all constraints. If a bound is ±Inf, that term is not considered constrained, so is not part of the summation.

For some large-scale problems with only linear equalities, the first-order optimality measure is the infinity norm of the projected gradient (i.e., the gradient projected onto the nullspace of Aeq).

Back to Top

Iterations and Function Counts

Displaying Iterative Output

© 1984-2009- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS