My Math Forum  

Go Back   My Math Forum > College Math Forum > Calculus

Calculus Calculus Math Forum


Thanks Tree2Thanks
Reply
 
LinkBack Thread Tools Display Modes
September 6th, 2018, 05:13 PM   #11
SDK
Senior Member
 
Joined: Sep 2016
From: USA

Posts: 504
Thanks: 283

Math Focus: Dynamical systems, analytic function theory, numerics
I suspect the problem here is that if you do a google search for examples of Lagrangian optimization, you find only examples with 0-dimensional solution manifolds i.e. the number of variables matches the number of constraints.

However, this not what he is asking about I don't think. In general if you have $n$ variables and $m$ constraints containing $n + k$ variables, then you expect (for sufficient smoothness conditions) to have a $n + k - m$ dimensional manifold which satisfies the problem.

One of the best resources I know of for this case is the following book. Sadly I don't know of any free options. Hope it helps.

https://epubs.siam.org/doi/book/10.1137/1.9781611972573
SDK is online now  
 
September 7th, 2018, 07:59 AM   #12
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,192
Thanks: 489

Quote:
Originally Posted by zylo View Post
As far as I can determine, Lagranges equations only apply when the function to be maximized and the constraints contain the same variables.

For ex,
Maximize f(x,y,u,v) subject to g(x,y,u,v)=0 and h(x,y,u,v)=0

If you know otherwise, please demonstrate with OP example:
Maximize w=xy subject to x+y+z-M=0
The problem with the OP's example is that it has no local extrema as he has formulated it. There is no maximum and no minimum short of positive and negative infinity respectively. With the addition of some extra but reasonable constraints, the objective function will have extrema, but they will occur at the boundaries. As I know you know, extrema at boundaries do not necessarily have derivatives = 0. The only purpose of the Lagrangian process in that case will be to prove that there are no extrema except at boundaries (and here those boundaries were not even in the original example).

$z = x^2 + y^2.$

$\text {Find extrema of } z \text { subject to } x^2 + 4y^2 + w^2 = 26 \text { and } w \ge 1.$

$L = x^2 + y^2 - \lambda (26 - x^2 - 4y^2 - w^2) - \kappa (1 - w).$

$\dfrac{\delta L}{\delta x} = 0 \text { if } x = \lambda x.$

$\dfrac{\delta L}{\delta y} = 0 \text { if } y = 4 \lambda y.$

$\dfrac{\delta L}{\delta w} = 0 \text { if } 2w \lambda = -\ \kappa.$

$\dfrac{\delta L}{\delta \lambda} = 0 \text { if } x^2 + 4y^2 + w^2 = 26.$

$\dfrac{\delta L}{\delta \kappa} = 0 \text { if } w = 1.$

$x = \lambda x \implies x = 0 \text { or } \lambda = 1.$

$\text {CASE I: } x = 0.$

$x = 0, \ w = 1, \text { and } 26 = x^2 + 4y^2 + w^2 = 4y^2 + 1 \implies$

$y = \pm \dfrac{5}{2} \implies z = \dfrac{25}{4}.$

$\text {CASE II: } \lambda = 1.$

$\therefore y = 4 \lambda y \implies y = 4y \implies y = 0.$

$x^2 + 0^2 + 1^2 = 26 \implies x = \pm 5 \implies z = 25.$

$\therefore \text { constrained } z \text { has a minimum of } \dfrac{25}{4} \text { at } \left (0, \ \dfrac{5}{2} \right ) \text { and } \left (0,\ -\ \dfrac{5}{2} \right ).$

$\text {And constrained } z \text { has a maximum of } 25 \text { at } (5,\ 0) \text { and } (-\ 5,\ 0).$

This is such a simple example that it can be checked by common sense, but it shows how it can be done.

Admittedly, this process has all the difficulties associated with Lagrangians: it only works if all relevant functions are differentiable, irrelevant constraints result in an inconsistent system of equations, extrema may be at boundaries, the second derivative test may be a bear, etc. But none of this has anything to do with the number of independent variables in the constraints exceeding the number of independent variables in the objective function.
Thanks from zylo

Last edited by JeffM1; September 7th, 2018 at 08:08 AM.
JeffM1 is offline  
September 8th, 2018, 07:51 AM   #13
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 1,603
Thanks: 115

Quote:
Originally Posted by JeffM1 View Post

$z = x^2 + y^2.$

$\text {Find extrema of } z \text { subject to } x^2 + 4y^2 + w^2 = 26 \text { and } w \ge 1.$
......
This is such a simple example that it can be checked by common sense, but it shows how it can be done.
......
Check by common sense.

x^2=26-4y^2-w^2
z=26-3y^2-w^2
dz=-6ydy-2wdw

dz=0 for arbitrary dy and dw (condition for an extreme) if y=0 and w=0, in which case x^2=26 and

z=26 is an extreme at x^2=26, y=0, w=0

--------------------------------------------------------------------------
I came across last post after doing the following:

Nice simple illustration of OP.
w=x^2 with constraint x^2+y^2+z^2-k=0.

Without constraint:
dw=2xdx is zero for arbitrary dx (condition for extreme) if x=0. w has a min value of 0.

With constraint, two methods:

I) Solve constraint for x and put it into object function:
w=k-y^2-z^2
Now y and z are the independent variables and
dw=-2ydy-2zdz=0 for arbitrary dy and dz if y=0 and z=0. Then x^2=k and
w=k at the extreme

II) Take differentials first:
dw=2xdx
2xdx+2ydy+2zdz=0
dw=2x(-ydy-zdx)/2x=0
dw=ydy+zdz=0 for arbitrary dy and dz if y=0 and z=0. Then x^2=k and
w=k at the extreme

Method II) saves the trouble of solving constraint for x, which in general might not be that easy.
Lagrange multiplier doesn't work here because object equation and constraint equations don't have same number of variables. You need to know why Lagrange multipiers work.

EDIT: I thanked JeffM1 for a nice example of why Lagrange multipliers doesn't work if number of variables in object function and constraints are different.

Last edited by zylo; September 8th, 2018 at 08:11 AM.
zylo is offline  
September 10th, 2018, 10:27 AM   #14
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,192
Thanks: 489

Quote:
Originally Posted by zylo View Post
EDIT: I thanked JeffM1 for a nice example of why Lagrange multipliers doesn't work if number of variables in object function and constraints are different.
But my example showed that Lagrangian multipliers DO work in that situation.

Quote:
Check by common sense.

x^2=26-4y^2-w^2
z=26-3y^2-w^2
dz=-6ydy-2wdw

dz=0 for arbitrary dy and dw (condition for an extreme) if y=0 and w=0, in which case x^2=26 and

z=26 is an extreme at x^2=26, y=0, w=0
Yes, but the example had a constraint that $w \ge 1.$ So what is the relevance of saying that z = 26 when that requires violating the constraint. Your answer is incorrect. I like being thanked as much as anyone else, but it is best when it is not for the wrong thing.

Quote:
Nice simple illustration of OP.
w=x^2 with constraint x^2+y^2+z^2-k=0....

Lagrange multiplier doesn't work here because object equation and constraint equations don't have same number of variables. You need to know why Lagrange multipiers work.
Lagrangian multipliers work just fine here.

$L = x^2 - \lambda (x^2 + y^2 + z^2 - k = 0)$

Optimize L.

$\dfrac{\delta L}{\delta x} = 0 \text { if } 2x = 2 \lambda x.$

Two cases: $\lambda = 1 \text { or } \lambda = 1.$

$\dfrac{\delta L}{\delta y} = 0 \text { if } 2y \lambda = 0.$

$\dfrac{\delta L}{\delta z} = 0 \text { if } 2z \lambda = 0.$

$\dfrac{\delta L}{\delta \lambda} = 0 \text { if } x^2 + y^2 + z^2 - k = 0.$

$\text {Case I: } \lambda = 1 \implies y = 0 = z \implies x^2 - k = 0 \implies x = \pm \sqrt{k} \text { and } w = k.$

Two points of maximization under the constraint.

$\text {Case II: } \lambda = 0 \implies 2x = 2 * 0 * x = 0 \implies x = 0 \implies w = 0.$

One point of minimization under the constraint.

{QUOTE]Without constraint:
dw=2xdx is zero for arbitrary dx (condition for extreme) if x=0. w has a min value of 0.

With constraint, two methods:

I) Solve constraint for x and put it into object function:
w=k-y^2-z^2
Now y and z are the independent variables and
dw=-2ydy-2zdz=0 for arbitrary dy and dz if y=0 and z=0. Then x^2=k and
w=k at the extreme[/QUOTE]
Yes this method sometimes works if the constraint can be restated in a closed form. I never said that Lagrangian multipliers are required to solve all problems in constrained minimization. But it is false that they cannot be applied if the number of independent variables in the constraints exceeds the number of independent variables in the objective function.
JeffM1 is offline  
September 10th, 2018, 01:05 PM   #15
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 1,603
Thanks: 115

"Maximize" (really find critical points) f(x,y) subject to constraint g(x,y,z) =0

I) x,y independent.
Maximize f(x,y) and plug results into g(x,y,z)=0 to determine z.
$\displaystyle df=f_{x}dx+f_{y}dy=o \rightarrow f_{x}=f_{y}=0
$

II) x,z independent

a) Solve g(x,y,z) for y=y(x,z) and substitute into f(x,y) to get F(x,z). Maximize F(x,z) to find x,z and plug into g(x,y,z)=0 to find y.

b) Use differentials.
$\displaystyle df=f_{x}dx+f_{y}dy=o$
$\displaystyle g_{x}dx+g_{y}dy+g_{z}dz=0
$
Solve the latter for dy and plug into former and then equate coefficients of dx and dz to zero to find x,z. Then plug into g(x,y,z) to find y.

Example 1: f(x,y)=xy, g(x,y,z)=x+y+z-M=0, x,z independent.
Method IIa:
y=M-x-z, xy=x(M-x-z), df=Mdx-2xdx-zdx-xdz=0
(M-2x-z)dx-xdz=0 $\displaystyle \rightarrow$ x=0, z=M, y=0

Method IIb:
df=ydx+xdy=0
dx+dy+dz=0, dy=-dx-dz, ydx+x(-dx-dz)=0, (y-x)dx-xdz=0, $\displaystyle \rightarrow$ x=0, y=0, z=M
Neither result makes much sense but illustrates the procedure.

Example 2

$\displaystyle f(x,y)=x^{2}+y^{2}$,
$\displaystyle g(x,y,z)=x^{2}+4y^{2}+w^{2}-26$, x,z independent
Method IIb
df=2xdx+2ydy=0
2xdx+8ydy+2wdw=0
$\displaystyle dy=\frac{-x}{4y}dx-\frac{w}{4y}dw$, then
df=(3/2)xdx-1/2wdw=0, \rightarrow x=0, w=0, y^{2}=26/4

y and w independent $\displaystyle \rightarrow$ y=0, w=0, x$\displaystyle ^{2}$=26

==========================================

Lagranges Multiplier

Max f(x,y) subject to g(x,y)=0

$\displaystyle df=f_{x}dx+f_{y}dy=0$
$\displaystyle \lambda g_{x}dx+\lambda g_{y}dy=0$
$\displaystyle (f_{x}-\lambda g_{x})dx+(f_{y}-\lambda g_{y})dy=0$
So instead of solving for dy in terms of dx, if
$\displaystyle f_{y}-\lambda g_{y}=0$ and dx arbitrary,
$\displaystyle f_{x}-\lambda g_{x}=0 $is condition for extremum.
This gives with g(x,y)=0 three conditions for x,y,z.

Now try the same method with:
Maximize" f(x,y) subject to constraint g(x,y,z) =0
$\displaystyle df=f_{x}dx+f_{y}dy=0$
$\displaystyle \lambda g_{x}dx+\lambda g_{y}dy+\lambda g_{z}dz=0$
$\displaystyle (f_{x}-\lambda g_{x})dx+(f_{y}-\lambda g_{y})dy-\lambda g_{x}dz=0$
Let x and w be independent. Then eliminate dy by
$\displaystyle (f_{y}-\lambda g_{y})$
Then dx and dw independent require
$\displaystyle f_{x}-\lambda g_{x}=0$ and $\displaystyle g_{z}=0$
These three conditions with g(x,y,z)=0 give four equations in the four unknowns x,y,z,$\displaystyle \lambda$

It works with Example 2

Using f(x,y)-$\displaystyle \lambda$g(x,y,z) and taking partial derivatives is a meaningless extension of Lagranges multiplier unless you can justify it. To do that you have to understand the rationale behind Lagranges multiplier.
zylo is offline  
September 10th, 2018, 06:47 PM   #16
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,192
Thanks: 489

Quote:
Originally Posted by zylo View Post
"Maximize" (really find critical points) f(x,y) subject to constraint g(x,y,z) =0

I) x,y independent.
Maximize f(x,y) and plug results into g(x,y,z)=0 to determine z.
Which only works if the maximizing values for x and y permit a solution for z in g(x,y,z) = 0. That is the problem with reasoning from examples. But the solution set of x,y pairs for solving g(x,y,z) = 0 may not intersect with the solution set of x,y pairs for optimizing f(x,y) at all. That is the rationale for using the Lagrangian process.
JeffM1 is offline  
September 11th, 2018, 09:33 AM   #17
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 1,603
Thanks: 115

JeffM1. I acknowledge your method was correct, but i had to know why. So I figured out the rationale behind Lagranges multipliers here:

Lagrange Multiplier with more constraint variables

I posted it separately because I could never find a derivation. All that I could find was a rule and examples, to the point that I wonder if most authors understand it.

After going through all that, i believe the better approach to OP type problem is to work with the differentials, as I outlined earlier. At least then you can see what's going on and think about it rather than using blind formalism for a case it wasn't derived for without a clue as to what's happening.
Even better is simply solving constraint equation, plugging into object equation, and finding extrema. Outlined in latter part of my post#13.

My thanks now are without reservations.
Thanks from JeffM1
zylo is offline  
September 11th, 2018, 12:44 PM   #18
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,192
Thanks: 489

@ Zylo

I apologize most sincerely if I sounded a bit testy at times. Most of that was caused by the fact that I had already answered a very similar question by the same OP at another site. And that other question made clear that he was thinking in terms of theoretical economics so the OP did not give the context of the problem here. In theoretical economics, LaGrangian multipliers are standard technique for at least two important reasons.

The first is that although some constraints, such as non-negativity constraints, are fully specified, other constraints and the objective function itself are almost always only partially specified, and so the system cannot actually be solved numerically without additional information. What is being sought are certain general attributes of the maximum or minimum achievable under a general class of constraints. (As Samuelson said, theoretical economics is a qualitative calculus.) Furthermore, some of the constraints may not be relevant. Indeed you frequently have constraints such as x must be non-negative but cannot exceed some positive function. Obviously, x cannot be both zero and positive:the constraints are literally contradictory. One may be binding and the other "slack," or both may be "slack." You can determine which constraints are "slack" from the sign of the Lagrangian multiplier.

The second reason is that for binding constraints

"The Lagrange Multiplier λ gives the ... [incremental] increase in the objective
function from a unit relaxation of the constraint."

You were correctly thinking about the numeric solution of fully specified problems (where LaGrangians may well be unnecessary) whereas I was thinking about the highly abstract problems of theoretical economics, where information about the multipliers may be the second most important result of the analysis.

Had the OP shared the context of his concern, this might have been a less lengthy thread.

Thank you for your kind words.
JeffM1 is offline  
September 15th, 2018, 11:36 AM   #19
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 1,603
Thanks: 115

An interestig example illustrating JeffM1's use of Lagrange multiplier for Subject is:
Opt w=xy with
$\displaystyle x^{2}+y^{2}+z^{2}-k^{2}$=0
$\displaystyle L(x,y,z,\lambda)=xy-\lambda (x^{2}+y^{2}+z^{2}-k^{2})$
$\displaystyle \frac{\partial L }{\partial x}, \frac{\partial L }{\partial y},\frac{\partial L }{\partial z},\frac{\partial L }{\partial \lambda}$ all set equal to zero gives:
$\displaystyle y-2\lambda x=0$
$\displaystyle x-2\lambda y=0$
$\displaystyle -2 \lambda z=0$
$\displaystyle x^{2}+y^{2}+z^{2}-k^{2}=0 \rightarrow$
$\displaystyle z=0, x=\pm y, x^{2}=y^{2}$
$\displaystyle w=xy=x^{2}=k^{2}/2$

If you let x,y be independent. $\displaystyle dw=xdy+ydx =0 \rightarrow x=0, y=0, z^{2}=k^{2}$. This case is missed by Lagrange Multiplier.

Same problem using differentials:
Opt w=xy with
$\displaystyle x^{2}+y^{2}+z^{2}-k^{2}=0
$
dw=xdy+ydx
2xdx+2ydy+2zdz=0
Assume y and z are independent, solve for dx and substitute:
$\displaystyle (x-\frac{y^{2}}{x})dy-\frac{yz}{x}dz=0$, and set coefficients of dy and dz equal to 0 since they are now independent.
$\displaystyle x^{2}=y^{2}=k^{2}/2$
w=xy=k^{2}/2

For an overview of optimization see:
https://en.wikipedia.org/wiki/Mathematical_optimization
But this isn't necessary for OP, which is strictly a multi-variable extremum problem with extra variables in the constraint.
zylo is offline  
Reply

  My Math Forum > College Math Forum > Calculus

Tags
constraint, function, objective, optimization, variables



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
statics class, ended up with 2 equations and 2 variables, rules to isolate variables fixxit Algebra 4 September 10th, 2014 12:29 PM
Quadratic Optimization in multiple variables (closed form) variatnik Abstract Algebra 1 August 11th, 2012 10:56 PM
Function of Several Variables emath Math Books 5 July 27th, 2012 01:51 PM
Optimization of a Matrix with one constraint. shack Linear Algebra 3 December 17th, 2007 02:11 PM
Function of Several Variables emath Calculus 0 December 31st, 1969 04:00 PM





Copyright © 2018 My Math Forum. All rights reserved.