1

Take the following optimization problem:

$$\max_{x\in X}f(x) \text{ s.t. } g(x)\geq 0, h(x)=0$$ for $X$ an open subset of $\mathbb R^n, f:X\to \mathbb R, g:X\to \mathbb R^k,h:X\to\mathbb R^m$.

The linearly independent constraint qualification (LICQ) is said to hold at a point when the gradients of all the binding constraint functions at the point are linearly independent. My understanding is LICQ guarantees the Karush Kuhn Tucker (KKT) conditions are met at a maximizer. I see why we focus on binding constraints; by complementary slackness, those that don't bind are annihilated by a zero multiplier in the KKT conditions. For simplicity, take the case of two constraints ($k=m=1$), and let's assume both bind. Then the KKT conditions are

$$\nabla f(x)+\lambda \nabla g(x)+\mu \nabla h(x)=0,g(x)=h(x)=0,\lambda\geq 0,\mu\geq 0.$$

Writing the first equation in matrix form gives

$$\left[\begin{array}{cc} \nabla g(x) & \nabla h(x)\end{array}\right]\left[\begin{array}{c} \lambda\\ \mu \end{array}\right]=-\nabla f(x)$$

but how does linearly independent $\nabla g(x),\nabla h(x)$ guarantee KKT conditions are met at a maximizer?

Golden_Ratio
  • 12,326
  • 3
  • 12
  • 33
  • What do you mean by "solvable"? There's a theorem that if the $x^*$ is a local maximizer and the LICQ is satisfied then the KKT conditions are satisfied. You can find a proof of that theorem in the book Numerical Optimization by Nocedal and Wright for example. This doesn't mean that, in practice, you will be able to actually compute a solution to the KKT conditions (at least, not without using a sophisticated numerical algorithm). – littleO Aug 25 '22 at 05:47
  • Related thread: [How to prove Lagrange multiplier theorem in a rigorous but intuitive way](https://math.stackexchange.com/questions/1760709/how-to-prove-lagrange-multiplier-theorem-in-a-rigorous-but-intuitive-way/1760741#1760741). – littleO Aug 25 '22 at 05:49
  • @littleO that's correct, I have edited my question. I was looking for a simple linear algebra argument to explain the intuition for this result. – Golden_Ratio Aug 25 '22 at 06:16
  • @littleO My thinking was that if CQ fails, the KKT conditions may not have a solution in the first place (putting aside the question of whether the solution is a maximizer). – Golden_Ratio Aug 25 '22 at 06:23
  • The thread I linked to contains my attempt to explain the intution for this result using a linear algebra argument. – littleO Aug 25 '22 at 07:11
  • Well, shall I give a "10 lines proof"? Because I am willing to mark this question as duplicate. By the way, are you happy with littleO comments? – R. W. Prado Sep 02 '22 at 04:55
  • 1
    @R.W.Prado yes littleO's comments are helpful. I think Nocedal and Wright should essentially suffice. I was mainly looking for an intuitive way to illustrate CQ's role for instructing an audience at an undergrad level. – Golden_Ratio Sep 03 '22 at 05:11
  • Does this answer your question? [How to prove Lagrange multiplier theorem in a rigorous but intuitive way?](https://math.stackexchange.com/questions/1760709/how-to-prove-lagrange-multiplier-theorem-in-a-rigorous-but-intuitive-way) – R. W. Prado Sep 03 '22 at 06:28

0 Answers0