linear independence constraint qualification: what to do when they don't hold?

Question

I want to solve a general nonlinear constrained optimization problem $$\min_q\ f(q)\quad \textrm{s.t.}\quad g_i(q) = 0,\ h_j(q) \geq 0.$$ The problem is that while the equality constraints $g_i(q)$ are individually smooth and have non-vanishing gradients at feasible points, the gradients are not linearly independent. If they were algebraically dependent I could simply remove the redundant constraints, but unfortunately the rank of $\nabla g$ is not constant over the feasible set.

What is the standard approach to solving such problems? Are there higher-order analogues of the KKT conditions that can be used instead, and are there standard solvers that are based on them?

Answer 1

The best reference I've seen on establishing relationships between constraint qualifications is Constraint Qualification for Nonlinear Programming.

Since the function $g$ is nonlinear, your problem is likely nonconvex, so the Slater condition will be inapplicable to your problem, but any other constraint qualification should work, as long as you can show it holds.

The canonical reference for constraint qualification seems to be A Review of Constraint Qualification in Finite-Dimensional Spaces (paywalled by SIAM), even though the reference is old.

There are ways to deduce optimality without constraint qualifications for convex programs (see Characterization of optimality in convex programming without a constraint qualification, paywalled by Springer). The abstract of this article (also paywalled by Springer) may be what you're looking for.

The trouble with generalizing constraint qualifications is that the weaker they get, the harder they are to verify. One of the weakest constraint qualifications is the Abadie Constraint Qualification, but it's very difficult to use in practice. It's considerably easier to verify a condition like the linearly independent constraint qualification or the constant rank constraint qualification.

Answer 2

The LICQ is only one condition that ensures solvability of the problem. However, there are weaker conditions that you can find in the literature. They guarantee that a unique solution exists, but typically you do not get unique Lagrange multipliers in these cases.