0
$\begingroup$

The lecturer taught this method in my Optimization and Control Theory Class and I wasn't quite there when he named it. Could you help me out?

He gave the following example of the method in class:

Example: Solve $$ \text{max} [ f(x) = x_1 (30 - x_1) + x_2 (50 -2x_2) - 3x_1 - 5x_2 - 10x_3]$$ Subject to the constraints: $$ x_1 + x_2 \le x_3 \text{and } x_3 \le 17.25 $$

Solution: Begin by converting constraints to form:

$$g_1(\bar x) = x_1 + x_2 - x_3 \le 0$$ $$g_2(\bar x) = x_3 - 17.25 \le 0$$ Then: $$ L(\bar x, \bar \lambda) = f(\bar x) \pm \left( \lambda_1 g_1(\bar x) + ... + \lambda_m g_m(\bar x) \right) $$

And then he proceeded as follows:

$$\begin{align} D_{\bar x} L: & \frac{\partial L}{\partial x_1} = 30 - 2x_1 - 3 - \lambda_1 = 0 \\ & \frac{\partial L}{\partial x_2} = 50 - 4x_2 - 5 - \lambda_1 = 0\\ & \frac{\partial L}{\partial x_3} = -10 + \lambda_1 - \lambda_2 = 0 \\ \end{align}$$

A system of equations is found and solved with further constraints: $\lambda_1 \ge 0$ and $\lambda_2 \ge 0$:

$$\lambda_1(x_1 + x_2 + x_3) = 0$$ $$\lambda_2 (x_3 - 17.25) = 0$$

(Through trial and error it is found that $\lambda_1 > 0 $ and $ \lambda_2 = 0$ is the best condition to solve this system)

Ultimately we get the solution: $$ x_1 = 8.5$$ $$ x_2 = 8.75$$ $$ x_3 = 17.25$$

And the equation is solved.

-- So I want to read more background on this method. I'd like to know what its called. I notice the 'L' as the name of the function. Could it be Lagrange? Or something of the sort?

$\endgroup$
1
$\begingroup$

Yes, $L$ is called the Lagrangian. In calculus, if you want to minimize $f$, you write down the optimality condition $\nabla f(x) = 0$ and solve for $x$. But what if you want to minimize $f$ subject to certain constraints? In this situation too you can write down the optimality conditions (now called KKT conditions) and solve for $x$.

Multivariable calculus books often discuss Lagrange multipliers, but they may only consider equality constraints. One reference for the case where we have inequality constraints also is the book Nocedal and Wright. For the case where our optimization problem is convex, Boyd and Vandenberghe is a great book that's free online.

$\endgroup$
  • $\begingroup$ Oh, thank you so much! Will check out those books ASAP. And I had been having trouble finding a textbook that applied to the material. Thank you again $\endgroup$ – Siyanda Aug 31 '13 at 11:54
  • $\begingroup$ Also, can I use this method to solve problems that involve constraints with non-linear variables? $\endgroup$ – Siyanda Aug 31 '13 at 11:55
  • $\begingroup$ Yes, the method applies to nonlinear optimization problems. This wikipedia article is probably a good place to start reading. $\endgroup$ – littleO Aug 31 '13 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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