Mangasarian-Fromovitz constraint qualification

The Mangasarian-Fromovitz constraint qualification or MFCQ for short is an important prerequisite that the necessary optimality criteria apply in non-linear optimization . The MFCQ is a condition on the regularity of a permissible point. If the MFCQ is fulfilled at one point and if this point is a local minimum , then the Karush-Kuhn-Tucker conditions are also fulfilled at this point. If the MFCQ applies, it is easy to check whether a given point is an optimum or not. ${\displaystyle {\tilde {x}}}$

It is named after Olvi Mangasarian and Stanley Fromovitz.

definition

There is an optimization problem in the form

${\displaystyle \min _{x\in X}f(x)}$

in which

${\displaystyle X=\{x\in \mathbb {R} ^{n}\,|\,g_{i}(x)\leq 0,h_{j}(x)=0\}}$

and all functions should be continuously differentiable . Then a feasible point of the restricted optimization problem satisfies the MFCQ if the following two conditions are met: ${\displaystyle {\tilde {x}}\in X}$

1. The gradients of the equation constraints are linearly independent at the point . ${\displaystyle h_{j}(x)}$ ${\displaystyle {\tilde {x}}}$
2. There is a vector such that and if is. ${\displaystyle d\in \mathbb {R} ^{n}}$ ${\displaystyle \nabla h_{j}({\tilde {x}})^{T}d=0}$ ${\displaystyle \nabla g_{i}({\tilde {x}})^{T}d<0}$ ${\displaystyle g_{i}({\tilde {x}})=0}$

example

MFCQ

Let us consider the equation restriction and the inequality restriction . The set described by these restrictions is the edge of the unit circle, restricted to the lower half of the coordinate system. We examine the point for the MFCQ's applicability. The gradients of the restriction functions are and the inequality is in active. ${\displaystyle h(x)=x_{1}^{2}+x_{2}^{2}-1=0}$ ${\displaystyle g(x)=x_{2}\leq 0}$ ${\displaystyle {\tilde {x}}=(1,0)}$ ${\displaystyle \nabla g({\tilde {x}})=(0,1)\,,\,\nabla h({\tilde {x}})=(2,0)}$ ${\displaystyle {\tilde {x}}}$

Since there is only one equation constraint, the linear independence follows directly. Furthermore, each vector of the form is orthogonal to the gradient of the equation constraint. Is also so is . For example, the vector would meet all the required conditions that apply to the MFCQ. ${\displaystyle (0,t)}$ ${\displaystyle t<0}$ ${\displaystyle \nabla g_{i}({\tilde {x}})^{T}(0,t)<0}$ ${\displaystyle d=(0,-1)}$

Abadie CQ without MFCQ

Let us consider the functions and the restriction set described by them ${\displaystyle g_{1}(x)=-x_{1}\,,\,g_{2}(x)=-x_{1}^{2}-x_{2}\,,\,g_{3}=-x_{1}^{2}+x_{2}}$

${\displaystyle X=\{x\in \mathbb {R} ^{2}\,|\,g_{i}(x)\leq 0,\,i=1,2,3\}}$.

This amount is the area that is enclosed between a positive and a negative parabola, restricted to the right side of the coordinate system. We now examine the set for the MFCQ and the Abadie CQ in point . ${\displaystyle X}$ ${\displaystyle {\tilde {x}}=(0,0)}$

All inequalities are active at this point and the gradients of the inequality inequalities are . The MFCQ cannot be fulfilled, otherwise and would have to apply. The CQ Abadie, however, is fulfilled because both the tangent and the linearized tangent to the beam with match. ${\displaystyle \nabla g_{1}({\tilde {x}})=(-1,0)^{T}\,,\,\nabla g_{2}({\tilde {x}})=(0,-1)^{T}\,,\,\nabla g_{3}({\tilde {x}})=(0,1)^{T}}$ ${\displaystyle d_{2}>0}$ ${\displaystyle d_{2}<0}$ ${\displaystyle (0,\lambda )}$ ${\displaystyle \lambda \geq 0}$

Comparison with other constraint qualifications

Among the other constraint qualifications, the MFCQ is a compromise between generality and ease of use. It is harder to use, but more general than the LICQ and easier to use than the Abadie CQ , but not as general. The implications apply between these constraint qualifications

${\displaystyle {\text{LICQ}}\implies {\text{MFCQ}}\implies {\text{Abadie CQ}}}$.

But the inversions do not apply.

literature

• C. Geiger, C. Kanzow: Theory and numerics of restricted optimization tasks . Springer, 2002. ISBN 3-540-42790-2 . http://books.google.de/books?id=spmzFyso_b8C

Individual evidence

1. ↑ Mangasarian, Fromovitz, The Fritz John necessary optimality conditions in the presence of equality and inequality constraints. J. Math. Anal. Appl., Vol. 17, 1967, pp. 37-47