Nonlinearly Constrained Optimization

From NEOS

Jump to: navigation, search

The general constrained optimization problem is to minimize a nonlinear function subject to nonlinear constraints. Two equivalent formulations of this problem are useful for describing algorithms. They are

minimize f(x)
subject to ci(x) = 0 for i \in E
c_i(x) \geq 0 for i \in I

where each ci(x) is a mapping from Rn to R, and E and I are index sets for inequality and equality constraints, respectively; and

minimize f(x)
subject to c(x) = 0
l \leq x \leq u

where c(x) maps Rn to Rm, and the lower- and upper-bound vectors, l and u, may contain some infinite components.

The main techniques that have been proposed for solving constrained optimization problems are reduced-gradient methods, sequential linear and quadratic programming methods, and methods based on augmented Lagrangians and exact penalty functions. Fundamental to the understanding of these algorithms is the Lagrangian function, which for the first formulation is defined as

L(x,y) = f(x) + \sum_{i \in E \cup I} y_i c_i(x)

The Lagrangian is used to express first-order and second-order conditions for a local minimizer. We simplify matters by stating just first-order necessary and second-order sufficiency conditions without trying to make the weakest possible assumptions.

The first-order necessary conditions for the existence of a local minimizer x * of the constrained optimization problem require the existence of Lagrange multipliers y * , such that

\nabla L(x^*,y^*) = \nabla f(x^*) + \sum_{i \in A^*} y_i^* \nabla c_i(x^*) = 0

where

A * = A(x * ) = {i:ci(x * ) = 0}

is the active set at x * , and y_i^* \geq 0 if i \in I. This result requires a constraint qualification to ensure that the geometry of the feasible set is adequately captured by a linearization of the constraints about x * . A standard constraint qualification requires the constraint normals, \nabla c_i(x^*) for i \in A^*, to be linearly independent.

The second-order sufficiency condition requires that (x * ,y * ) satisfies the first-order condition and that the Hessian of the Lagrangian

\nabla^2_{xx} L(x^*,y^*) = \nabla^2 f(x^*) + \sum_{i \in A^*} y_i^* \nabla^2 c_i(x^*) = 0

satisfies the condition

s^T \nabla^2_{xx} L(x^*,y^*) s > 0

for all nonzero s in the set

\{ s | \nabla c_i(x^*)^T s = 0 \; \forall i \in I_+^* \cup E \quad {and} \quad \nabla c_i(x^*)^T s \geq 0 \; \forall i \in I_0^*\}

where

I_+^* = \{ i \in I \cap A : y_i^* > 0 \} and I_0^* = \{ i \in I \cap A : y_i^* = 0\}.

The previous condition guarantees that the optimization problem is well behaved near x * in particular, if the second-order sufficiency condition holds, then x * is a strict local minimizer of the first constrained problem. An important ingredient in the convergence analysis of a constrained algorithm is its behavior in the vicinity of a point (x * ,y * ) that satisfies the second-order sufficiency condition.

[edit]

Further Details

Retrieved from "http://wiki.mcs.anl.gov/NEOS/index.php/Nonlinearly_Constrained_Optimization"
Personal tools