In this section, we consider optimization problems in standard forms
\[\begin{aligned} &\min\nolimits_x&& f_0(x) \\ &\subjectto&& \{f_i(x)\le 0\}_{i=1}^m, \\ &&& \{h_i(x)=0\}_{i=1}^p. \end{aligned}\]Fritz John proved that any (local) minimum is characterized by a generalized optimality system
\[\newcommand{\abs}[1]{\left|#1\right|} \begin{aligned}\textstyle 0 = \lambda_0\partial f_0(x) + \sum_{i=1}^m \lambda_i \partial f_i(x) + \sum_{i=1}^p \nu_i\partial h_i(x),\\ \{f_i(x)\le 0\}_{i=1}^m, \{h_i(x)=0\}_{i=1}^p,\\ \lambda\succeq 0, \\ \{\lambda_if_i(x)=0\}_{i=1}^m \end{aligned} \tag{FJ}\](see Ch 2.3 in Borwein & Lewis for a slick proof of (FJ) in the inequality constrained case). The \(\lambda_i\)’s (including \(\lambda_0\)s) are called generalized Lagrange multipliers. Note that the set of generalized Lagrange multipliers is a cone; i.e. if \(\lambda\in\reals^{m+1}\) is a generalized Lagrange multiplier, then so is \(\alpha\lambda\) for any \(\alpha\ge 0\). If \(\lambda_0\) is nonzero, then it is possible to remove this extra degree of freedom in the generalized Lagrange multipliers by dividing (FJ) thru by \(\lambda_0\):
\[\begin{aligned}\textstyle 0 = \partial f_0(x) + \frac{1}{\lambda_0}\sum_{i=1}^m\lambda_i\partial f_i(x) + \frac{1}{\lambda_0}\sum_{i=1}^p\nu_i\partial h_i(x),\\ \{f_i(x)\le 0\}_{i=1}^m, \{h_i(x)=0\}_{i=1}^p,\\\textstyle \frac{1}{\lambda_0}\lambda_{1:m}\succeq 0,\\\textstyle \{\frac{\lambda_i}{\lambda_0}f_i(x)=0\}_{i=1}^m. \end{aligned} \tag{KKT}\]The normalized generalized Lagrange multipliers \(\frac{\lambda_i}{\lambda_0}\) are simply called Lagrange multipliers. Although there are always generalized Lagrange multipliers that satisfy (FJ), there may not be Lagrange multipliers that satisfy (KKT). A simple example is the optimization problem
\[\begin{aligned} &\min\nolimits_x&& x \\ &\subjectto&& x^2\le 0 \end{aligned}.\]To guarantee the existence of Lagrange multipliers, we impose restrictions on the optimization problem to rule out generalized Lagrange multipliers with \(\lambda_0 = 0\). Such restrictions are called constraint qualifications.
A prominent example is the Mangasarian-Fromovitz constraint qualification (MFCQ):
\[\begin{aligned} \{\nabla h_i(x)\}_{i=1}^p\text{ are linearly independent;}\\ \text{there is }h\in\reals^n\text{ such that } \left\{\begin{aligned} \{h^\top\nabla h_i(x)=0\}_{i=1}^p \\ \{h^\top\nabla f_i(x)<0\}_{i\in\cA(x)} \end{aligned}\right\}, \end{aligned} \tag{MFCQ}\]where \(\cA(x)\) is the set of (indicies of) active inequality constraints at \(x\):
\[\cA(x)\triangleq\{i\in[m]\mid f_i(x)=0\}.\]To see why the MFCQ rules out generalized Lagrange multipliers with \(\lambda_0 = 0\), consider the inequality constrained case (i.e. there are no \(h_i\)’s). In this case, (FJ) with \(\lambda_0 = 0\) implies
\[\begin{aligned}\textstyle 0 = \sum_{i\in\cA(x)}\lambda_i\partial f_i(x),\\ \{\lambda_i\ge 0\}_{i\in\cA(x)}, \end{aligned}\]i.e. the nullspace of (the matrix whose columns are) \(\{\partial f_i(x)\}_{i\in\cA(x)}\) intersects non-trivially with the non-negative orthant. To rule out this case, it is enough to assume that the nullspace and \(\reals_+^{\abs{\cA}}\setminus\{0\}\) are disjoint. Under this assumption, the separating hyperplane theorem implies that there is \(h\in\reals^n\) such that \(h^\top y > 0\) for all \(y\in\reals_+^{\mid\cA\mid}\setminus\{0\}\) and \(h^\top z\le 0\) for all \(z\) in the nullspace. The first condition implies \(h\) is in the positive orthant, and the second condition is equivalent to \(h^\top z=0\) for all \(z\) in the nullspace, which implies \(h\) is in the row space. In other words, the row space intersects with the positive orthant. Equivalently, there is \(h\in\reals^n\) such that \(\{h^\top\nabla f_i(x) > 0\}_{i\in\cA(x)}\). This is exactly the MFCQ for inequality constrained problems!
In this section, we consider optimization problems with abstract constraints
\[\begin{aligned} &\min\nolimits_x&& f_0(x) \\ &\subjectto&& G(x)\in\cK \end{aligned}\]where \(\cK\) is a closed convex set. As we shall see, the story here is similar to the story for optimization problems in standard form.
The generalized optimality system for this problem is
\[\begin{aligned} 0 = \lambda_0\partial f_0(x) + \partial G(x)^\top\lambda,\\ G(x)\in\cK,\\ \lambda\in N_{\cK}(G(x)),\lambda_0\ge 0. \end{aligned}\]If \(\cK\) is a closed convex cone, then \(N_{\cK}(y) = \cK^\circ\cap\{y\}^\perp\) for any \(y\in\cK\). Thus \(\lambda\in N_{\cK}(G(x))\) is equivalent to \(\lambda\in\cL^\circ\) and \(\langle\lambda,G(x)\rangle = 0\).
To rule out generalized Lagrange multipliers with \(\lambda_0 = 0\), we assume that the nullspace of \(\partial G(x)\) and \(N_{\cK}(G(x))\setminus\{0\}\) are disjoint; i.e. there is no \(\lambda\) such that
\[\begin{aligned} 0 = \partial F(x)^\top\lambda, \\ \lambda\in N_{\cK}(G(x))\setminus\{0\}. \end{aligned}\]The separating hyperplane theorem implies that there is \(h\in\reals^n\) such that \(h^\top y > 0\) for all \(y\in N_{\cK}(G(x))\setminus\{0\}\) and \(h^\top z\le 0\) for all \(z\) in the nullspace. The first condition implies \(h\) is in the interior of the negative polar of the normal cone of \(\cK\) at \(G(x)\); i.e. \(h\) is in the interior of the negative tangent cone to \(\cK\) at \(G(x)\) (the polar of the normal cone is the tangent cone). The second condition is equivalent to \(h^\top z=0\) for all \(z\) in the nullspace of \(\partial G(x)^\top\); i.e. \(h\) is in the column space of \(\partial G(x)\). In other words, the separating hyperplane theorem implies the column space of \(\partial G(x)\) intersects with the interior of the negative tangent cone to \(\cK\) at \(G(x)\). This is often stated as
\[\def\col{\mathrm{col}} \def\cone{\mathrm{cone}} \begin{aligned} 0 &\in\col(\partial G(x)) - \intr(\cone(\cK - G(x))) \\ &= \intr(\col(\partial G(x)) - \cone(\cK - G(x))). \end{aligned}\]Since both the column space of \(\partial G(x)\) and the tangent cone to \(\cK\) at \(G(x)\) are closed under positive scaling, we can without loss of generality require the common point in the column space of \(\partial G(x)\) and the interior of the tangent cone to \(\cK\) at \(G(x)\) to be in the interior of \(\cK - G(x)\). This leads to Robinson’s constraint qualification (RCQ):
\[\def\col{\mathrm{col}} \def\cone{\mathrm{cone}} 0\in\intr(\col(\partial G(x)) - (\cK - G(x))) = \intr(G(x) + \col(\partial G(x)) - \cK). \tag{RCQ}\]Posted on August 27, 2024 from Ann Arbor, MI.