Lagrange Multipler KKT condition

Question

I am looking at SVM, and reviewing Lagrange multiplier. Let's say with the constraint function $$g(x,y) = x^2 + y^2 -1 > 0, $$ I am maximizing $$f(x,y) = x + y -1 .$$ Intuitively, since the constraint function does not provide a finite constrained region, there is no solution, and $f(x,y)$ can infinitely increase.

However, if I just plainly proceed with Lagrange multiplier calculation, $$L(x,\lambda) = (x + y -1) +\lambda(x^2 + y^2 -1)$$ I get the solution: $$y,x = -\sqrt{2}/2, \lambda = 1/\sqrt{2}$$ And this still satisfies KKT conditions although the solution is wrong. $$g(x) => 0 , \lambda => 0, \lambda g(x) = 0.$$

I expected that I would have some result that conflicted KKT conditions, but nothing was violated.

Does this mean that Lagrange multiplier under KKT conditions can produce a solution that cannot be solved, without giving any indication of intractability?

If functions are complicated, what's the systematic way to confirm that the optimization with inequality constraint functions is solvable using Lagrange multiplier?

Answer 1

A key concept with optimization in general and the KKT conditions in particular is distinguishing:

• necessary conditions for an optimum
• sufficient conditions for an optimum

In its most basic form, the KKT conditions are necessary conditions for an optimum. If an optimum exists and certain regularity conditions are satisfied, the optimum must satisfy the KKT conditions.

Consider an even simpler case:

\begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{maximize (over $x$)} & x^2 \\ \end{array} \end{equation}

The KKT condition is $2x = 0$. Every optimum satisfies these conditions, but there is no optimum!

For the KKT conditions to be sufficient conditions, more is required! For example, if the optimization problem is convex and Slater's condition is satisfied, then the KKT conditions are also sufficient conditions for an optimum (and every point that satisfies the KKT conditions is an optimum).

For example, \begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{minimize (over $x$)} & x^2 \\ \end{array} \end{equation}

is a convex, unconstrained problem hence the KKT conditions are sufficient conditions hence the condition $2x = 0$ implies $x=0$ is a solution.

Answering your direct question:

If functions are complicated, what's the systematic way to confirm that the optimization with inequality constraint functions is solvable using Lagrange multiplier?

Unfortunately, there's a bit of nuance to the answer here. There are many different conditions for the optimization problem that imply that the KKT conditions are either necessary or sufficient for an optimum.

One of the most useful categories of problems where the KKT conditions are sufficient conditions for an optimum are when the optimization problem is convex and Slater's condition holds. Checkout Stanford Prof. Boyd's course on convex optimization, but the basic idea is that a convex optimization problem can be written as:

\begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{minimize (over $\mathbf{x}$)} & f(\mathbf{x}) \\ \mbox{subject to} & \forall_j g_j(\mathbf{x}) \leq 0 \\ & A\mathbf{x} = \mathbf{b} \end{array} \end{equation}

where $\mathbf{x}$ is a vector, objective function $f$ is convex in $\mathbf{x}$, constraints $g_j$ are convex in $\mathbf{x}$, and equality constraints are affine. Slater's condition is that there exists a point in relative interior of the feasible set (eg. you don't have constraints like $x^2 \leq 0$ which are only satisfied by a single point).

In the case of a convex problem where Slater's condition is satisfied, the optimal pair $(\mathbf{x}, \boldsymbol{\lambda})$ is a saddle point of the Lagrangian.

Another useful regularity condition for the KKT conditions to be necessary is the LICQ constraint qualification. The KKT Wikipedia page has a whole list of possible regularity conditions. The mathematics of optimization is a big, broad topic! Anyway, this will hopefully get you going in the right direction! As you're going along, be sure to distinguish:

• Conditions on your optimization problem that imply the KKT conditions are necessary for an optimum.
• Conditions on your optimization problem that imply the KKT conditions are sufficient for an optimum.