Welcome to our community

Be a part of something great, join today!

Optimization With Two Constraints

  • Thread starter
  • Admin
  • #1

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,689
Hi MHB,

I've come across this problem recently:

If a²+b²=2 and (c-3)²+(d-4)²=1, find the maximum value of ad-bc.

I haven't solved it and actually, I don't know of any algebraic method I could use to solve it and I am wondering if this problem is doable with the Lagrange Multiplier method. However, as some of you know, I am new to this method, and I don't know how to handle multiple constraints.

If you're interested in this problem and want to share with me your idea on how to crack it using a purely algebraic method that would be fine, but if you could help me solve it using Lagrange Multipliers, I would like that too.

Thanks!
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
We have the objective function:

\(\displaystyle f(a,b,c,d)=ad-bc\)

subject to the constraints:

\(\displaystyle g(a,b,c,d)=a^2+b^2-2=0\)

\(\displaystyle h(a,b,c,d)=(c-3)^2+(d-4)^2-1=0\)

So, what you want to do is write the system (involving the indicated partials):

\(\displaystyle f_a=\lambda g_a+\mu h_a\)

\(\displaystyle f_b=\lambda g_b+\mu h_b\)

\(\displaystyle f_c=\lambda g_c+\mu h_c\)

\(\displaystyle f_d=\lambda g_d+\mu h_d\)

What do you get?
 
  • Thread starter
  • Admin
  • #3

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,689
We have the objective function:

\(\displaystyle f(a,b,c,d)=ad-bc\)

subject to the constraints:

\(\displaystyle g(a,b,c,d)=a^2+b^2-2=0\)

\(\displaystyle h(a,b,c,d)=(c-3)^2+(d-4)^2-1=0\)

So, what you want to do is write the system (involving the indicated partials):

\(\displaystyle f_a=\lambda g_a+\mu h_a\)

\(\displaystyle f_b=\lambda g_b+\mu h_b\)

\(\displaystyle f_c=\lambda g_c+\mu h_c\)

\(\displaystyle f_d=\lambda g_d+\mu h_d\)

What do you get?
Hey MarkFL, thanks for the quick reply!:)

Oh...what you have suggested is by approaching it using the Lagrange Multipliers method...(Tmi):eek:

Okay...for those 4 equations in the system, I get:

\(\displaystyle d=\lambda (2a)\)

\(\displaystyle -c=\lambda (2b)\)

\(\displaystyle -b=\mu (2(c-3))\)

\(\displaystyle a=\mu (2(d-4))\)
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Your first two equations are correct, but the last two are not...do you see your error in taking the partials of $f$ with respect to $c$ and $d$?
 
  • Thread starter
  • Admin
  • #5

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,689
Your first two equations are correct, but the last two are not...do you see your error in taking the partials of $f$ with respect to $c$ and $d$?
Yes, I realized I made two errors and have them fixed right before you replied...:D
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Okay, looks good! :D

Now, what you want to do is try to find what this system implies regarding how the variables are related to get the critical point(s). I suggest solving the first two equations for $2\lambda$ and the last two equations for $2\mu$ and equate the results. What do you find?
 
  • Thread starter
  • Admin
  • #7

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,689
Okay, looks good! :D

Now, what you want to do is try to find what this system implies regarding how the variables are related to get the critical point(s). I suggest solving the first two equations for $2\lambda$ and the last two equations for $2\mu$ and equate the results. What do you find?
Oh okay...after equating the results, I get

$bd=-ac$ and $-bd+4b=ac-3a$

and this implies $b=-\dfrac{3a}{4}$.
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Okay good...can you think of a way to solve for $(a,b)$? Do you have any additional relationship between these variables that you can use?

Can you also find a relationship between $c$ and $d$?
 
  • Thread starter
  • Admin
  • #9

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,689
Okay good...can you think of a way to solve for $(a,b)$? Do you have any additional relationship between these variables that you can use?

Can you also find a relationship between $c$ and $d$?
Sure...

After doing some simple addition and subtraction steps, we arrived at:

$(a,b,c,d)=\dfrac{4\sqrt{2}}{5}, -\dfrac{3\sqrt{2}}{5}, \dfrac{18}{5}, \dfrac{24}{5}$

or

$(a,b,c,d)=-\dfrac{4\sqrt{2}}{5},\dfrac{3\sqrt{2}}{5}, \dfrac{12}{5}, \dfrac{16}{5}$
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Let me check your work...:D

You found from $\lambda$:

\(\displaystyle ac+bd=0\)

and from $\mu$:

\(\displaystyle 4b+3a=ac+bd\)

Hence, we know:

\(\displaystyle 4b+3a=0\implies b=-\frac{3}{4}a\)

Substituting for $b$ into the first constraint, we obtain:

\(\displaystyle a^2+\left(-\frac{3}{4}a \right)^2=2\)

\(\displaystyle \frac{25}{16}a^2=2\)

\(\displaystyle a=\pm\frac{4}{5}\sqrt{2}\implies b=\mp\frac{3}{5}\sqrt{2}\)

Case 1: \(\displaystyle (a,b)=\left(\frac{4}{5}\sqrt{2},-\frac{3}{5}\sqrt{2} \right)\)

\(\displaystyle \left(\frac{4}{5}\sqrt{2} \right)c-\left(\frac{3}{5}\sqrt{2} \right)d=0\)

\(\displaystyle d=\frac{4}{3}c\)

Substituting into the second constraint, we obtain:

\(\displaystyle (c-3)^2+\left(\frac{4}{3}c-4 \right)=1\)

\(\displaystyle c^2-6c+9+\frac{16}{9}c^2-\frac{32}{3}c+16=1\)

\(\displaystyle \frac{25}{9}c^2-\frac{50}{3}c+24=0\)

\(\displaystyle 25c^2-150c+216=0\)

\(\displaystyle (5c-18)(5c-12)=0\)

\(\displaystyle c=\frac{12}{5},\,\frac{18}{5}\)

Hence:

\(\displaystyle d=\frac{16}{5},\,\frac{24}{5}\)

Thus, from this first case, we have the critical points:

\(\displaystyle (a,b,c,d)=\left(\frac{4}{5}\sqrt{2},-\frac{3}{5}\sqrt{2},\frac{12}{5},\frac{16}{5} \right),\,\left(\frac{4}{5}\sqrt{2},-\frac{3}{5}\sqrt{2},\frac{18}{5},\frac{24}{5} \right)\)

Case 2: \(\displaystyle (a,b)=\left(-\frac{4}{5}\sqrt{2},\frac{3}{5}\sqrt{2} \right)\)

\(\displaystyle \left(-\frac{4}{5}\sqrt{2} \right)c+\left(\frac{3}{5}\sqrt{2} \right)d=0\)

\(\displaystyle d=\frac{4}{3}c\)

And so the second constraint gives the same values we found from the first case:

\(\displaystyle c=\frac{12}{5},\,\frac{18}{5}\)

Hence:

\(\displaystyle d=\frac{16}{5},\,\frac{24}{5}\)

Thus, from this second case, we have the critical points:

\(\displaystyle (a,b,c,d)=\left(-\frac{4}{5}\sqrt{2},\frac{3}{5}\sqrt{2},\frac{12}{5},\frac{16}{5} \right),\,\left(-\frac{4}{5}\sqrt{2},\frac{3}{5}\sqrt{2},\frac{18}{5},\frac{24}{5} \right)\)

So, we have a total of four critical points to check, and the one that gives the largest value for the objective function will maximize it.

What do you find is the value of the objective function for the four critical points?
 

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,689
Let me check your work...:D
Hey, I'm so so sorry, Mark!

I should have included all of my steps in my previous post so that you wouldn't have to work it out and typed everything in LaTeX for me...please forgive me
and I will not repeat this again, I promise!


\(\displaystyle (a,b,c,d)=\left(\frac{4}{5}\sqrt{2},-\frac{3}{5}\sqrt{2},\frac{12}{5},\frac{16}{5} \right),\,\left(\frac{4}{5}\sqrt{2},-\frac{3}{5}\sqrt{2},\frac{18}{5},\frac{24}{5} \right),\left(-\frac{4}{5}\sqrt{2},\frac{3}{5}\sqrt{2},\frac{12}{5},\frac{16}{5} \right),\,\left(-\frac{4}{5}\sqrt{2},+\frac{3}{5}\sqrt{2},\frac{18}{5},\frac{24}{5} \right)\)

So, we have a total of four critical points to check, and the one that gives the largest value for the objective function will maximize it.

What do you find is the value of the objective function for the four critical points?
Ops...there are a total of four critical points to check instead of two...:eek:

\(\displaystyle f\left(\frac{4}{5}\sqrt{2},-\frac{3}{5}\sqrt{2},\frac{12}{5},\frac{16}{5} \right)=\left(\frac{4}{5}\sqrt{2} \right) \left( \frac{16}{5} \right)-\left(-\frac{3}{5}\sqrt{2} \right) \left( \frac{12}{5} \right)=4\sqrt{2}\)

\(\displaystyle f\left(\frac{4}{5}\sqrt{2},-\frac{3}{5}\sqrt{2},\frac{18}{5},\frac{24}{5} \right)=\left(\frac{4}{5}\sqrt{2} \right) \left( \frac{24}{5} \right)-\left(-\frac{3}{5}\sqrt{2} \right) \left( \frac{18}{5} \right)=6\sqrt{2}\)

\(\displaystyle f\left(-\frac{4}{5}\sqrt{2},\frac{3}{5}\sqrt{2},\frac{12}{5},\frac{16}{5} \right)=\left(-\frac{4}{5}\sqrt{2} \right) \left( \frac{16}{5} \right)-\left(\frac{3}{5}\sqrt{2} \right) \left( \frac{12}{5} \right)=-4\sqrt{2}\)

\(\displaystyle f\left(-\frac{4}{5}\sqrt{2},-\frac{3}{5}\sqrt{2},\frac{18}{5},\frac{24}{5} \right)=\left(-\frac{4}{5}\sqrt{2} \right) \left( \frac{24}{5} \right)-\left(\frac{3}{5}\sqrt{2} \right) \left( \frac{18}{5} \right)=-6\sqrt{2}\)

So the maximum value of $ad-bc=6\sqrt{2}$.
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Hey, I'm so so sorry, Mark!

I should have included all of my steps in my previous post so that you wouldn't have to work it out and typed everything in LaTeX for me...please forgive me
and I will not repeat this again, I promise!
Hey, no worries! (Hug)

Ops...there are a total of four critical points to check instead of two...:eek:

\(\displaystyle f\left(\frac{4}{5}\sqrt{2},-\frac{3}{5}\sqrt{2},\frac{12}{5},\frac{16}{5} \right)=\left(\frac{4}{5}\sqrt{2} \right) \left( \frac{16}{5} \right)-\left(-\frac{3}{5}\sqrt{2} \right) \left( \frac{12}{5} \right)=4\sqrt{2}\)

\(\displaystyle f\left(\frac{4}{5}\sqrt{2},-\frac{3}{5}\sqrt{2},\frac{18}{5},\frac{24}{5} \right)=\left(\frac{4}{5}\sqrt{2} \right) \left( \frac{24}{5} \right)-\left(-\frac{3}{5}\sqrt{2} \right) \left( \frac{18}{5} \right)=6\sqrt{2}\)

\(\displaystyle f\left(-\frac{4}{5}\sqrt{2},\frac{3}{5}\sqrt{2},\frac{12}{5},\frac{16}{5} \right)=\left(-\frac{4}{5}\sqrt{2} \right) \left( \frac{16}{5} \right)-\left(\frac{3}{5}\sqrt{2} \right) \left( \frac{12}{5} \right)=-4\sqrt{2}\)

\(\displaystyle f\left(-\frac{4}{5}\sqrt{2},-\frac{3}{5}\sqrt{2},\frac{18}{5},\frac{24}{5} \right)=\left(-\frac{4}{5}\sqrt{2} \right) \left( \frac{24}{5} \right)-\left(\frac{3}{5}\sqrt{2} \right) \left( \frac{18}{5} \right)=-6\sqrt{2}\)

So the maximum value of $ad-bc=6\sqrt{2}$.
Looks good! (Yes)

Would you know what to do for a problem with 3 or more constraints? (Thinking)
 

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,689
Hey, no worries! (Hug)
Thank you for forgiving me...:eek:(Inlove) and also thank you for guiding me through the problem!


Looks good! (Yes)

Would you know what to do for a problem with 3 or more constraints? (Thinking)
I honestly think I can, but my preference is to try my very best to solve any optimization problems algebraically first, and if I failed, then and only then I would consider the LM method!:p

I think it's best to tell what I've attempted so that if anyone happens to know of a way to crack it without the use of LM method, they can show me their method.:)

My Attempt (by algebraic approach):


I first let $a, b$ to represent $x_1$ and $y_1$ respectively and then I let $d$ and $c$ to become $x_2$ and $y_2$ and I then plot them separately on the same Cartesian diagram and I get
optimization problem.JPG

But the question asked us to maximize the expression $ad-bc$, which is equivalent to $x_1(x_2)-y_1(y_2)$, and I just don't see there is any significant meaning to the expression $x_1(x_2)-y_1(y_2)$ and up to this point, I know I am headed in the wrong direction. I still believe this problem is doable with the algebraic method, just that I don't see it...
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
For each constraint, we need a multiplier, traditionally (or at least the way I was taught) we use $\lambda$ for the first, and $\mu$ for the second. I think what I would do for more than two constraints, is to simply subscript $\lambda$, so I don't have to keep choosing Greek letters. :D
 

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,689
For each constraint, we need a multiplier, traditionally (or at least the way I was taught) we use $\lambda$ for the first, and $\mu$ for the second. I think what I would do for more than two constraints, is to simply subscript $\lambda$, so I don't have to keep choosing Greek letters. :D
I see...hey, I'm not afraid...because if I ever encounter any math optimization problems which I couldn't solve, I have MHB or you to help me out!:)