Mathematics desk
< April 7	<< Mar \| April \| May >>	April 9 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 8

Lagrange Multipliers with Inequality Constraints

Is that true that the point $(x,\lambda ,\mu )$ maximizes the Lagrangian: $L(x,\lambda ,\mu )=f(x)+\sum _{i}{\lambda _{i}x_{i}}+\sum _{i}{\mu _{i}(1-x_{i})}$ iff the point $x$ maximizes the convex function $f$ subject to the constraints $\forall i\ 0\leq x_{i}\leq 1$ ? עברית (talk) 14:52, 8 April 2017 (UTC)[reply]

The optimum is never at a maximum of the Lagrangian. Instead, for a problem with equality constraints, the optimum is a saddle point. The saddle point property remains true in your problem if the inequality constraints are non-binding, and if your constraints are binding the optimum is still not at a maximum of the Lagrangian. So your question needs to be "Is it true that a point satisfies the Kuhn-Tucker conditions iff...?" I'll think about your question when I get a chance, but in the meantime you could check to see if your answer is in Kuhn-Tucker conditions. Loraof (talk) 15:49, 8 April 2017 (UTC)[reply]

In your particular problem, with convex f and with each constraint involving only one x, it seems like any point satisfying the Kuhn-Tucker conditions will have every x equal to 0 or 1, and moving any x from there into the interior would lower f; so the Kuhn-Tucker conditions must be not only necessary but also sufficient for a local optimum. Loraof (talk) 19:02, 8 April 2017 (UTC)[reply]

I don't get your saddle point argument, Loraof. Normally, one would expect that the optimum of the constrained problem is precisely the optimum of the Lagrangian with equality conditions: in other words, the precise utlility of the Lagrange multipliers is that the optimum of the Lagrangian equates precisely the optimum of

f\left(\bullet \right)

in the constrained set.

In general, for a maximization problem, notice that the second-order condition needed for the equivalence demands that f be quasiconcave. Thus, replacing convex with quasiconcave you get the wording of Kuhn-Tucker theorem. If the function is not quasiconcave, then, you may well miss the optimum and get instead local minimizers.

In your case, if the function is convex, as Loraof points out, K-T conditions may give you the maximizers on the edges of the unit hypercube. Pallida Mors 21:20, 8 April 2017 (UTC)[reply]

For the ~~unconstrained~~ inequality-constrained problem, the Lagrangian optimum is a saddle point as per Chiang, Fundamental Methods of Mathematical Economics, 3rd edition, p. 742: At the constrained maximum of f, the Lagrangian is maximized in every x direction but is minimized in every Lagrange multiplier direction. If a problem has inequality constraints, then as you say it is equivalent to a problem with some of the constraints rewritten as equality constraints (and some constraints non-binding and hence ignored in this equivalent problem). So in that equivalent problem there's a saddle point. Loraof (talk) 21:47, 8 April 2017 (UTC)[reply]

That is indeed interesting, since at the optimum moving the multiplier has no effect on the value of the Lagrangian (its effect on the Lagrangian is the product

\lambda _{i}\cdot g_{i}\left(\mathbf {x} \right)

), which is null as

g_{i}\left(\mathbf {x} \right)

is satisfied. The corresponding pages are missing from my digital 3rd edition, and I can't find the text in the 4th edition... I hope my library has an unabridged 3rd edition. I'll find out on monday.. Pallida Mors 23:00, 8 April 2017 (UTC)[reply]

Yes, the effect of the Lagrange multiplier on the Lagrangian expression is zero, because the Lagrangian expression is minimized with respect to the Lagrange multiplier (so we have a valley bottom, with zero slope, in the direction of the Lagrange multiplier). Loraof (talk) 01:16, 9 April 2017 (UTC)[reply]
Actually the page in Chiang about the saddle point was in the context of the inequality-constrained problem, though I think the saddle point feature also applies to equality constraints. While the page numbers may not line up between the 3rd and 4th editions, maybe the chapter headings and section and sub-section headings do agree: chapter "Nonlinear programming", section "Kuhn-Tucker sufficiency theorem: Concave programming", sub-section "Saddle point". Loraof (talk) 02:05, 9 April 2017 (UTC)[reply]
Regarding the saddle point in the case of equality constraints, see Lagrange multiplier#Example 4: Numerical optimization. Loraof (talk) 02:22, 9 April 2017 (UTC)[reply]