6
$\begingroup$

I'm optimizing a family of objectives over $x_1,\ldots,x_n$ with a single constraint that $x$'s add up to $1$, and when using method of Lagrange multipliers, the single multiplier always ends up $0$ for members of this family... does this tell us anything interesting about these objectives?

Edit: the answer was -- it means the constraint it inactive, ie, removing the constraint doesn't change the answer of optimization problem

$\endgroup$
  • 2
    $\begingroup$ It seems that the constraints are always satisfied. Can you post the formulation of your problem? $\endgroup$ – Tom Stephens Aug 10 '10 at 2:46
  • $\begingroup$ One more thing... are you solving this numerically? Your algorithm may be choosing $q$'s satisfying the conservation constraint that $\sum q_i = 1$. $\endgroup$ – Tom Stephens Aug 10 '10 at 2:59
4
$\begingroup$

One of two things that I can think of are happening here. The global minimum (or max, whatever your goal is here) of your function may actually lie within the simplex defined by $\sum_{i=1}^{4} q_{i} = 1$. In this case your algorithm is finding the correct solution and the constraint is trivially satisfied. (Consider minimizing $x^2+y^2$ constrained to the line $x = 0$, so the Lagrange formulation is $L(x,y,\nu) = x^2 + y^2 + \nu x$. Solving $\nabla L=0$ demands that $\nu=0$. )

Alternatively, your algorithm could be sampling only points that already satisfy the constraint - so you are only checking those points (intentionally or otherwise). Then the algorithm is hopefully finding a local minimum (or max) along this constraint and your multiplier will always be zero.

I hope this helps you identify where a problem may be in your model - or clears up a conceptual issue and allows you to move forward with the solution you have. As far as interpreting the meaning of Lagrange multipliers, look here.

$\endgroup$
  • $\begingroup$ OK, good point, for that objective it seems the former holds -- maximum is inside the simplex. $\endgroup$ – Yaroslav Bulatov Aug 10 '10 at 4:48

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.