6
$\begingroup$

I have more or less understood the underlying theory of the Lagrange multiplier method (by using the Implicit Function Theorem). Now, I try to extend this understanding to the general case, where we have more than one constraint. For example we try to maximize/minimize $f(x)$ subject to $g(x)=0$ and $h(x)=0$. As far as I can see, what we should do in this case is simply to build the Lagrange function $$L(x,\alpha,\beta) = f(x) + \alpha g(x) + \beta h(x) $$ and then try to maximize/minimize this function, with respect to constraints $g(x)=0$ and $h(x)=0$.

To justify this form of the Lagrange function $L(x,\alpha,\beta)$, I thought the following: Assume that we have a point $x'$ which satisfies $g(x')=0$ and $h(x')=0$. If this point is an extreme point on both constraints $g(x)$ and $h(x)$, then it is $$\nabla f(x') = \lambda_1 \nabla g(x')$$ $$\nabla f(x') = \lambda_2 \nabla h(x')$$. We can unify these in a single equation as: $$\nabla f(x') -\dfrac{\lambda_1}{2}\nabla g(x') - \dfrac{\lambda_2}{2}\nabla h(x') = \nabla f(x') + \alpha \nabla g(x') + \beta \nabla h(x')= 0$$

This partially justifies $L(x,\alpha,\beta) = f(x) + \alpha g(x) + \beta h(x)$ for me: Calculate $\nabla_{x}L(x,\alpha,\beta)$, set it equal to zero and solve it; by using $g(x)=0$ and $h(x)=0$ as well.

But what disturbs me is that we could not able to find an analytic solution to this most of the time. I have prepared a rough sketch to show it:

enter image description here

Here, the constrained extreme points for both $g(x)=0$ and $h(x)=0$ are distinct ($x'$ and $x''$). The only points which satisfy both constraints at the same time are $A$ and $B$. And they are not the extreme points of the both constraint surfaces, it is $\nabla f(A) \neq \alpha \nabla g(A)$ for any $\alpha$ for example. So, my question is, what good is the Lagrangian function $L(x,\alpha,\beta) = f(x) + \alpha g(x) + \beta h(x)$ in such a case? It does not provide an analytic solution for such cases, then what is the point of the Lagrange function and the coefficients $\alpha$ and $\beta$ now? Does this form constitute a good structure for numerical optimization algorithms or what? I am confused about that.

Thanks in advance.

$\endgroup$
  • $\begingroup$ Having two constraints $h(x)=0$ and $g(x)=0$ is equivalent to having a constraint $h^2(x)+g^2(x)=0$, so you can fall back to a case where you have only one constraint. $\endgroup$ – TZakrevskiy Nov 17 '14 at 23:05
  • 1
    $\begingroup$ Does having that provide us an analytic solution then? And what about the form $L(x,\alpha,\beta)=f(x)+\alpha g(x) + \beta h(x)$? $\endgroup$ – Ufuk Can Bicici Nov 17 '14 at 23:12
1
$\begingroup$

The sentence "If this point is an extreme point on both constraints $g(x)$ and $h(x)$, then it is $$\nabla f(x') = \lambda_1 \nabla g(x'),\qquad\nabla f(x') = \lambda_2 \nabla h(x')\ {\rm "}$$ is wrong. You only can say that $$\nabla f(x') = \lambda_1 \nabla g(x')+\lambda_2 \nabla h(x')\ .$$

$\endgroup$
  • $\begingroup$ Yes, I saw this too; I was wrong at that time. The gradient $\nabla f$ must be linearly dependent to $\nabla g$ and $\nabla h$. $\endgroup$ – Ufuk Can Bicici Jul 19 '17 at 12:27
0
$\begingroup$

It is perfectly valid to use the Lagrange multiplier approach for systems of equations (and inequalities) as constraints in optimization.

In your picture, you have two variables and two equations. Here, the feasible set may consist of isolated points, which is kind of a degenerate situation, as each isolated point is a local minimum.

Substituting equality constraints $h_1(x)=0$ $\dots$ $h_n(x)=0$ into $$ \tilde h(x):=\sum_{i=1}^nh_i(x)^2 =0 $$ is usually not advised, as the gradient of $\tilde h$ at a feasible point is always zero, and constraint qualifications are not satisfied, which means the Lagrangian approach will not work.

$\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.