Solving Optimization Problems with Inequality Constraints

Similar to the solution of optimization problems with only equality constraints discussed previously, optimization problems with inequality constraints can also be solved using the Lagrange multiplier method. For a general form of the optimization problem:

minimizef(x)subject toh(x)=0g(x)≤0minimize\quad f(x)\\ subject\ to\quad h(x)=0\\ \quad\quad g(x)\le 0

where f:Rn→R,h:Rn→Rm,m≤n,g:Rn→Rpf: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 gj(x)≤0g_{j}(x)\le 0, if at x∗x^{*} we have gj(x∗)=0g_{j}(x^{*})=0, then the inequality constraint is called an active constraint at x∗x^{*}; if at x∗x^{*} we have gj(x∗)<0g_{j}(x^{*})<0, then the constraint is called an inactive constraint at x∗x^{*}. By convention, equality constraints hi(x)h_{i}(x) are always considered active constraints.

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

J(x∗)≜{j:gj(x∗)=0}J(x^{*})\triangleq \{j:g_{j}(x^{*})=0\}

If the vectors

∇hi(x∗),∇gj(x∗),1≤i≤m,j∈J(x∗)\nabla h_{i}(x^{*}),\nabla g_{j}(x^{*}),1\le i\le m,j\in J(x^{*})

are linearly independent, then x∗x^{*} is called a regular point.

The following introduces the first-order necessary condition that a point must satisfy to be a local minimum, known as the KKT conditions. KKT Conditions: Let f,h,g∈C1f,h,g\in C^{1}, and let x∗x^{*} be a regular point and a local minimum of the problem h(x)=0,g(x)≤0h(x)=0,g(x)\le 0. Then there must exist λ∗∈Rm\lambda^{*}\in R^{m} and μ∗∈Rp\mu^{*}\in R^{p} such that the following conditions hold:

μ∗≥0Df(x∗)+λ∗TDh(x∗)+μ∗TDg(x∗)=0Tμ∗Tg(x∗)=0h(x∗)=0g(x∗)≤0\mu^{*}\ge0\\ Df(x^{*})+\lambda^{*T}Dh(x^{*})+\mu^{*T}Dg(x^{*})=0^{T}\\ \mu^{*T}g(x^{*})=0\\ h(x^{*})=0\\ g(x^{*})\le0

When solving optimization problems with inequality constraints, one can search for points that satisfy the KKT conditions and consider these points as candidates for local minima.

Second-Order Sufficient and Necessary Conditions

Besides the first-order KKT conditions, there are second-order sufficient and necessary conditions for solving such problems.

Second-Order Necessary Condition: In the above problem, if x∗x^{*} is a local minimum and f,h,g∈C2f,h,g\in C^{2}, and assuming x∗x^{*} is a regular point, then there exist λ∗∈Rm\lambda^{*}\in R^{m} and μ∗∈Rp\mu^{*}\in R^{p} such that

  1. μ∗≥0,Df(x∗)+λ∗TDh(x∗)+μ∗TDg(x∗)=0T,μ∗Tg(x∗)=0\mu^{*}\ge 0,Df(x^{*})+\lambda^{*T}Dh(x^{*})+\mu^{*T}Dg(x^{*})=0^{T},\mu^{*T}g(x^{*})=0
  2. For all y∈T(x∗)y\in T(x^{*}), yTL(x∗,λ∗,μ∗)y≥0y^{T}L(x^{*},\lambda^{*},\mu^{*})y\ge0 holds

Second-Order Sufficient Condition: Assume f,h,g∈C2f,h,g\in C^{2}, x∗∈Rnx^{*}\in R^{n} is a feasible point, and there exist vectors λ∗∈Rm\lambda^{*}\in R^{m} and μ∗∈Rp\mu^{*}\in R^{p} such that

  1. μ∗≥0,Df(x∗)+λ∗TDh(x∗)+μ∗TDg(x∗)=0T,μ∗Tg(x∗)=0\mu^{*}\ge 0,Df(x^{*})+\lambda^{*T}Dh(x^{*})+\mu^{*T}Dg(x^{*})=0^{T},\mu^{*T}g(x^{*})=0
  2. For all y∈T~(x∗,μ∗),y≠0y\in \widetilde{T}(x^{*},\mu^{*}),y\neq0, yTL(x∗,λ∗,μ∗)y>0y^{T}L(x^{*},\lambda^{*},\mu^{*})y>0 holds

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

#Tech