Constrained optimization

Sequential quadratic programming computes steps from a quadratic model of the optimization Lagrangian with linearized constraints. Its constrained Newton system couples a primal step and multiplier estimates. A line search or trust region then controls the use of that local model.

Roger Fletcher's method uses an L1 exact penalty on linearized constraints and a bounded trust region. It therefore admits a model minimizer even when hard linearized constraints are inconsistent or the quadratic model is indefinite.^[ref]

An L1 penalty can enforce a constraint exactly at a finite weight, rather than only in an infinite-weight limit. For a convex equality-constrained problem with an optimal multiplier $y_{\ast }$ and optimization Lagrangian $f-y^{T}c$, the lower bound $f(x)-y_{\ast }^{T}c(x)\ge f(x_{\ast })$ givesThus $\rho >\Vert y_{\ast }{\Vert }_{\infty }$ makes every penalty minimizer feasible and optimal. Local versions require appropriate regularity and second-order assumptions. The nonsquared norm is essential to this finite-threshold property; a quadratic penalty method usually approaches feasibility only as its weight diverges.

The critical cone consists of linearized feasible directions along which the objective function has zero first-order change. For constraints $c_i\ge 0$, its directions satisfy $D{c}_{i}d\ge 0$ at active constraints and $\nabla f^{T}d=0$; equality constraints impose zero linearized residual. Under the usual regularity conditions, second-order Karush-Kuhn-Tucker conditions test the optimization Lagrangian Hessian matrix on this cone. Positive active multipliers force their corresponding directional residuals to vanish.

Suppose $0<\Vert a\Vert <R$ in a Euclidean space. Among points outside or on the radius-$R$ ball centred at zero, the unique closest point to $a$ is $x_{\ast }=Ra/\Vert a\Vert$. Its squared distance is $(R-\Vert a\Vert {)}^2$.

Indeed, the reverse triangle inequality gives $\Vert x-a\Vert \ge \Vert x\Vert -\Vert a\Vert \ge R-\Vert a\Vert$. Equality requires $\Vert x\Vert =R$ and $x$ pointing in the same direction as $a$, giving the stated unique point. If $a=0$, every point on the sphere is a minimizer. If $\Vert a\Vert \ge R$, the point $a$ itself is feasible and the minimum distance is zero.

The exterior is not a convex set, so a direct geometric argument is useful: it certifies the global answer without treating every candidate satisfying the Karush-Kuhn-Tucker conditions as a minimum.

Represent feasible variables using unconstrained coordinates. For example, $x=a+e^y$ enforces $x>a$, while $x=a+y^2$ includes $x=a$ but introduces a stationary point at $y=0$. A transformation can change conditioning and does not remove a nonconvex objective's multiple extrema.

An optimization constraint restricts the feasible points in constrained optimization, for example by an equality $g(x)=0$ or an inequality $h(x)\le 0$. Extrema are considered on the resulting feasible set rather than on the whole domain of the objective.

For a constraint written $g_i(x)\ge 0$, its violation is the nonnegative number $v_i(x)=\max \{-g_i(x),0\}$. It vanishes precisely when the constraint holds. An equality $h_j(x)=0$ has violation $|h_j(x)|$. A norm of all these violations measures total infeasibility; its numerical magnitude depends on the scaling of the constraint functions.