Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I read in a textbook a passing comment that Lagrange multipliers are not applicable if there are points of non-differentiability in the constraints (even if the constraints are continuous). For example, in the following problem:

$\min_{\boldsymbol x} \boldsymbol{a} \cdot \boldsymbol{x}$

s.t. $\max(x_1, x_2) = x_3$

for vectors $\boldsymbol a \in \mathbb{R}^3$ and $\boldsymbol x \in \mathbb{R}^3$.

Why can't I use Lagrange multipliers here? If I push through the standard steps of constructing the Lagrangian, differentiating w.r.t. to variables and Lagrange multipliers, setting the partial derivatives to 0, and solving (assuming I'm able to), what goes wrong? Is there some related but alternative method that I can use?

Thanks in advance.

Edit: I'm ok finding any critical point. I'm looking for issues beyond the standard one that just because you find a point with gradient = 0 doesn't mean you've found the optimum.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

What goes wrong is that the minimum might happen to be at a point where a derivative might not exist. Try e.g. minimize $y$ subject to $g(x,y) = y - |x| = 0$. The minimum is at $(0,0)$, where $\frac{\partial g}{\partial x}$ does not exist.

share|improve this answer
    
I see, thanks. Does it work to generalize the derivative to subderivative, then try to solve the equations so that 0 is in the subdifferential? In this case, when x=0, the subdifferential of g w.r.t. x is the interval from negative lambda to lambda, so 0 is in the subdifferential. Is there a reason why that wouldn't work? –  dan_x Aug 15 '11 at 23:36
    
I decided to accept this answer and post the question asked in the above comment as a separate follow-up. Thanks for the help! math.stackexchange.com/questions/57859/… –  dan_x Aug 16 '11 at 16:15

In the last quarter-century, the subject of nonsmooth optimization has become an area of very active research. The pioneering book is Frank (Francis) Clarke's book Optimization and Nonsmooth Analysis. Clarke gave the entire subject its name. Another major figure is Rockafellar.

As your comment notes, a key tool is the subgradient. But that comment indicates some acquaintance with the subject, which likely makes this answer superfluous.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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