# minimization of a cost function with lagrange method

• October 1st 2012, 11:51 AM
justinen
minimization of a cost function with lagrange method
Hi everyone!

I'm new here, I found this forum as I was looking for a clue in solving this minimization exercise with 2 constraints:

min 0,2*x1+0,2*x2+0,6*x3
x1, x2, x3

s.t. 0,2*+√x1+0,2*√x2+0,6*√x3 - 8 >= 12

s.t. 0,2*+√x1+0,2*√x2+0,6*√x3 - 8 >= 0,7*√x1+0,2*√x2+0,1*√x3

• October 1st 2012, 12:39 PM
johnsomeone
Re: minimization of a cost function with lagrange method

Minimize $0.2x_1 + 0.2x_2 + 0.6x_3$

subject to $0.2\sqrt{x_1}+ 0.2\sqrt{x_2} + 0.6\sqrt{x_3- 8} \ge 12$

and $0.2\sqrt{x_1}+ 0.2\sqrt{x_2} + 0.6\sqrt{x_3- 8} \ge 0.7\sqrt{x_1}+ 0.2\sqrt{x_2} + 0.1\sqrt{x_3}$.
• October 1st 2012, 12:44 PM
justinen
Re: minimization of a cost function with lagrange method
There are actually two mistakes,sorry:

1) the first term is 0,2x1 (not 0,2x-1)
2) in the constraints (-8) is outside the square root

Thank you!
• October 1st 2012, 12:45 PM
justinen
Re: minimization of a cost function with lagrange method
The first point doesn't hold anymore!
• October 1st 2012, 12:52 PM
johnsomeone
Re: minimization of a cost function with lagrange method
Gotcha. So it's this:

Minimize $0.2x_1 + 0.2x_2 + 0.6x_3$

subject to $0.2\sqrt{x_1}+ 0.2\sqrt{x_2} + 0.6\sqrt{x_3} - 8 \ge 12$

and $0.2\sqrt{x_1}+ 0.2\sqrt{x_2} + 0.6\sqrt{x_3} - 8 \ge 0.7\sqrt{x_1}+ 0.2\sqrt{x_2} + 0.1\sqrt{x_3}$.
• October 1st 2012, 12:53 PM
justinen
Re: minimization of a cost function with lagrange method
Yep!
• October 1st 2012, 01:12 PM
johnsomeone
Re: minimization of a cost function with lagrange method
See Karush–Kuhn–Tucker conditions: Karush

It looks exactly like it's set up and solved exactly like Lagrange Mulitpliers, except for the added conditions "Dual feasibility" and "Complementary slackness" to account for having an inequality in the constraint, rather than an equality.

I can't recall ever having done a problem like this, but it looks straightforward (if I trust wikipedia when it comes to math...)
• October 1st 2012, 01:23 PM
justinen
Re: minimization of a cost function with lagrange method
I feel extremely stupid but I can't solve the exercise :( I have never seen a double costraint and an inequality in the constraint plus I haven't been practicing maths for a few years and I realize I forgot everything :S
• October 1st 2012, 01:35 PM
johnsomeone
Re: minimization of a cost function with lagrange method
I think I'd reformulate it as:

Minimize $0.2a_1^2 + 0.2a_2^2 + 0.6a_3^2$

subject to $0.2a_1+ 0.2a_2 + 0.6a_3 - 8 \ge 12$

and $0.2a_1+ 0.2a_2 + 0.6a_3 - 8 \ge 0.7a_1+ 0.2a_2 + 0.1a_3$

and $a_1, a_2, a_3 \ge 0$.

Now the domain is defined by a bunch of planes, which are easier to handle.

Never having used that KKT method, I'd probably approach it this way:

1) Find the function's stationary points, using no contraints, and then see if any are inside that domain. (In this case, it's obvious that only the origin will show up, and it's outside the domain.)

2) Consider the geometric meaning of -gradient of f as the direction of steepest descent, and then follow that from the interior of the domain, to it's boundary planes, to their boundary lines (intersection of those planes), and then to a boundary vertex (assuming you don't hit a 0 along the way).

However, this isn't exactly Lagrange's method, which was what the problem requested. So for that, see the link I gave before.
• October 1st 2012, 01:38 PM
johnsomeone
Re: minimization of a cost function with lagrange method
The double constraints are fairly easy. If you can do lagrange with one constraint, you can do it with two. It's the inequalities that give it a different flavor than the usual Lagrange problem.
• October 1st 2012, 01:38 PM
justinen
Re: minimization of a cost function with lagrange method
Thank u anyways, I think I'll follow your method first and then retry with the Lagrangian, I am stuck and need to find a way out for the moment!
• October 1st 2012, 02:18 PM
MaxJasper
Re: minimization of a cost function with lagrange method
Min(0.2 x1 + 0.2 x2 + 0.6 x3)=0.95335 for
x1=0.044196
x2=2.0721
x3=0.8835

but not absolutely sure!
• October 1st 2012, 02:46 PM
johnsomeone
Re: minimization of a cost function with lagrange method
To clarify, any time you have a non-zero component of -grad f, you have a direction you can move and make f smaller. It's easy to see that in the interior, you keep move back toward the boundary planes. On one of the boundary planes, if -grad f is parallel to the normal to plane, you've "lost your component of -grad f" , and so might have a minimum there. Those points are easy enough to solve for, and then check to see if they're in the domain. Other than such points, by following -grad f along a plane, you'll eventually hit a line. If the line is given by P0+tP1, you'll have "lost your component of -grad f" where <P1, grad f> = 0. Again, those points are easy to find and check if they're in the domain. Barring those points, following a line eventually takes you to a vertex in the domain's boundary - and there you now just have to check if it's a min.

Check:
1) Where "lost your component of -grad f" in space - in one of the interior points. Solve grad f = 0. (Obviously only happens at origin, so none for this problem - the origin is outside of the domain.)

2) Where "lost your component of -grad f" on one of those 5 planes. Solve where grad f is parallel to the normal to plane. Collect only those points that are actually in this domain. (Remember to include the plane a1=0 (normal is the unit vector in the a1 direction), the plane a2=0, and the plane a3=0.)

3) Where "lost your component of -grad f" on one of the lines that's an intersection of two of those 5 planes. Solve <P1, grad f> = 0, where the line is given by P0+tP1. Collect only those points that are actually in this domain. (Remember things like the plane a1=0 intersect the plane a2=0 is the line (0, 0, t) = (0, 0, 0) + (0, 0, 1)t. And like the line where the plane a2=0 intersects the plane a1+a2+3a3=100, which is (100-3t, 0, t) = (100, 0, 0) + (-3, 0, 1)t.)

4) Where you hit a vertex, collect it. Collect all the verticies of this domain. (In theory, you could examine the grad f and decide the vertex is even a possible minimum I suppose - but that would be more work than just plugging the vertex into f to see if it's a global minimum.)

Then examine the value of f on each of those collected points to determine its global minimum.

By the way, this reasoning us very similar to the reasoning that makes the Lagrange Multipliers method work.