2
$\begingroup$

If we have a function $f:\Bbb {R}^n\to \Bbb R$ that we want to maximize subject to the constraint $x\in \mathcal D$, where $\mathcal D=\{x\in \mathbb R ^n :g_i(x)\leq 0, \text { for } i= 1,...,k \}$.

The constraint qualification in lagrangian optimization states that the rank of the Jacobian of the vector of constraints $g(x)=(g_1(x),g_2(x),...g_k(x))^T$ must be equal to the number of constraints $k$. That is, $\text{rank } Dg(x)=k$ must hold.

This condition can also be satisfied if $k\geq n$, i.e. when there are more constraints than variables. However, my intuition tells me that if there are more constraints in $g$ (or even an equal amount of constraints) than variables in $x$, we should not necessarily expect to find a lagrange multiplier $\lambda$ that would allow us to say that at a local optimum $x^*$, the lagrange theorem can be used.

My argument is as follows: Suppose we have 2 constraints in $g$, such that they only intersect at one point. i.e. there is only one point in the constraint set $\mathcal D$. Obviously, we can trivially state what the global optimum is, so Lagrangian analysis is redundant, but let's nevertheless see if lagrange's conditions apply.

It seems to me that most of the time, the conditions will not apply. They would only apply, when by pure coincidence, the gradient of $f$ coincides with the gradients of $g$. So it seems to me that Lagrange's theorem doesn't apply, yet my textbook (which seems fairly rigorous) says it does.

$\endgroup$

1 Answer 1

1
$\begingroup$

My conjecture was wrong. Here is a proof.

If we have a point $x^*$ that is the unique point in $\mathcal D$. The matrix $A=Dg$ is an $k\times n$ matrix, which means that $A^T$ is a linear mapping from $\mathbb R^k \to \mathbb R^n$, and if the constraint qualification is met, it has full rank, and therefore if we also assume $k\geq n$, it is an injective map. We can therefore for any $d\in \mathbb R^n$ find a $\lambda \in \mathbb R^k$, such that $\lambda ^T A=(A^T\lambda )^T=d^T$. Hence, we can find a $\lambda$ such that $Df(x^*)=\lambda^T Dg(x^*)$.

Note that I haven't used the fact that $x^*$ is an optimum. In other words, if the amount of constraints is equal or larger to the amount of variables, then for every point in $\mathbb R^n$ a vector of lagrange multipliers can be found.

(Someone should check this proof).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.