Solving Optimization Problems with Inequality Constraints

Basic Concepts

Similar to the equality-constrained optimization problems discussed earlier, optimization problems with inequality constraints can also be solved using the method of Lagrange multipliers. For the general form of an optimization problem:

where $f:R^{n}\to R,h:R^{n}\to R^{m},m\le n,g:R^{n}\to R^{p}$. We introduce the following two definitions:

Definition 1: For an inequality constraint $g_{j}(x)\le 0$, if $g_{j}(x^{*})=0$ at $x^{*}$, then this inequality constraint is said to be active at $x^{*}$; if $g_{j}(x^{*})<0$ at $x^{*}$, then this constraint is said to be inactive at $x^{*}$. By convention, equality constraints $h_{i}(x)$ are always treated as active.

Definition 2: Let $x^{*}$ satisfy $h(x^{*})=0,g(x^{*})\le 0$, and let $J(x^{*})$ be the index set of active inequality constraints:

If the vectors

are linearly independent, then $x^{*}$ is said to be a regular point.

KKT Conditions

We now introduce the first-order necessary conditions that a point must satisfy to be a local minimizer, namely the KKT conditions. KKT conditions: Let $f,h,g\in C^{1}$, and let $x^{*}$ be a regular point and a local minimizer of the problem $h(x)=0,g(x)\le 0$. Then there must exist $\lambda^{*}\in R^{m}$ and $\mu^{*}\in R^{p}$ such that the following conditions hold:

Thus, when solving an inequality-constrained optimization problem, we can search for points satisfying the KKT conditions and treat these points as candidates for the minimizer.

Second-Order Necessary and Sufficient Conditions

In addition to the first-order KKT conditions, there are also second-order necessary and sufficient conditions for solving problems of this kind.

Second-order necessary conditions: In the problem above, suppose $x^{*}$ is a minimizer and $f,h,g\in C^{2}$. Assume $x^{*}$ is a regular point. Then there exist $\lambda^{*}\in R^{m}$ and $\mu^{*}\in R^{p}$ such that

1. $\mu^{*}\ge 0,Df(x^{*})+\lambda^{*T}Dh(x^{*})+\mu^{*T}Dg(x^{*})=0^{T},\mu^{*T}g(x^{*})=0$
2. for all $y\in T(x^{*})$, $y^{T}L(x^{*},\lambda^{*},\mu^{*})y\ge0$ holds

Second-order sufficient conditions: Assume $f,h,g\in C^{2}$, that $x^{*}\in R^{n}$ is a feasible point, and that there exist vectors $\lambda^{*}\in R^{m}$ and $\mu^{*}\in R^{p}$ such that

1. $\mu^{*}\ge 0,Df(x^{*})+\lambda^{*T}Dh(x^{*})+\mu^{*T}Dg(x^{*})=0^{T},\mu^{*T}g(x^{*})=0$
2. for all $y\in \widetilde{T}(x^{*},\mu^{*}),y\neq0$, $y^{T}L(x^{*},\lambda^{*},\mu^{*})y>0$ holds

Then $x^{*}$ is a strict local minimizer of the optimization problem $h(x)=0,g(x)\le 0$.