3
$\begingroup$

Consider the (non-linear) optimization problem ($P$)

$$max \quad3x_1 + 4x_2$$

$$s.t. \quad x_1^2 + x_2^2 \leq 25$$

$$ \quad x_1,x_2 \geq 0$$

Solve the Lagrangian dual problem.


I don't have a clue how the dual problem is even obtained since the constraint is nonlinear. Could anyone please help me?

$\endgroup$
  • $\begingroup$ Here is a tip. Grab the old school grid paper and draw the circle with Center in Origin, radius 5. Your last constraint tells us that we are either in the first or third quadrant. Since you MAX expression has positive coefficient, we need to be in the first quadrant. Find the tangent to the circle having the same slope as the 3x+4y=C That point of tangency should do it in my view. That calculation isn't too hard $\endgroup$ – imranfat May 20 '13 at 13:54
  • $\begingroup$ @imranfat I think you misunderstood my question. I know how to solve this problem, however, I need to find a solution to the dual problem that corresponds to this problem. $\endgroup$ – dreamer May 20 '13 at 13:56
4
$\begingroup$

gt6989b's work isn't correct. The dual problem involves minimizing over the Lagrange multipliers, not maximizing over $x$. Furthermore, to contruct the Lagrangian dual problem, you need Lagrange multipliers not just for the quadratic constraint but also for the two nonnegativity constraints.

Note that most texts that talk about convex duality assume the primal problem is a minimization. So the derivations below are the negatives of what you'd do if you constructed the Lagrangian from the equivalent minimization problem (with the negative objective $-3x_1-4x_2$).

The Lagrangian is $$L(x_1,x_2,\lambda_1,\lambda_2,\lambda_3) = 3x_1+4x_2+\lambda_1(25-x_1^2-x_2^2)+\lambda_2x_1+\lambda_3x_2.$$ The Lagrange multipliers $\lambda_1$, $\lambda_2$, and $\lambda_3$ are all nonnegative. The dual function is $$g(\lambda_1,\lambda_2,\lambda_3) = \max_{x_1,x_2} 3x_1+4x_2+\lambda_1(25-x_1^2-x_2^2)+\lambda_2x_1+\lambda_3x_2$$ and the dual problem is $$\begin{array}{ll} \text{minimize} & g(\lambda_1,\lambda_2,\lambda_3) \\ \text{subject to} & \lambda_1,\lambda_2,\lambda_3 \geq 0 \end{array}$$ To complete the construction of the dual problem, you'll want to eliminate $x_1$ and $x_2$ from the dual function $g(\cdot)$ using simple calculus. This will give you an expression for $g$ that is independent of $x_1$ and $x_2$. There might be a couple of division by zero issues there you'll want to be careful with.

Alternatively, instead of constructing the full dual problem, you can determine the correct values of $\lambda_1$, $\lambda_2$, and $\lambda_3$ from complementary slackness conditions. This requires solving for the optimal values of $x_1$ and $x_2$, and examining which constraints are active at the solution.

$\endgroup$
  • 1
    $\begingroup$ @MichaelCGrant Thanks a lot for your help! I am still not sure though how I should go about constructing the dual problem any further. How should I proceed to obtain a function that is easily minimizable? Furthermore, could you please give me some intuitive reason for this specific approach? Why do you minimize the maximum of the original Lagrangian? Thanks a lot! $\endgroup$ – dreamer May 20 '13 at 15:40
  • 1
    $\begingroup$ I gave you the function $g$. It's an unconstrained maximization over $x_1$ and $x_2$, so like I said, simple calculus will get you there if you're careful. As for intuition, that's opening a rather large can of worms :P I suggest you return to your instructors for help with that. A discussion of "shadow prices" may provide intuition on dual variables. The dual of maximization problem is a minimization, and vice versa. $\endgroup$ – Michael Grant May 20 '13 at 16:03
  • $\begingroup$ @MichaelCGrant I found the values of $x_1$ and $x_2$ for the maximum of your $L$ function, namely $x_1=3,x_2=4$. Now should I plug these values in to find the g function and then minimize this function with respect to the lambda's? So is the g function defined as 25 + 3$\lambda_2$ + 4$\lambda_3$? $\endgroup$ – dreamer May 20 '13 at 19:29
  • 1
    $\begingroup$ That can't be correct. The maximum values of $x_1$ and $x_2$ should be functions of the $\lambda_i$ values. $\endgroup$ – Michael Grant May 20 '13 at 19:30
  • $\begingroup$ @MichaelCGrant Sorry to ask, but would you mind showing me how it is done? I've been desperately trying to find a solution for quite long now but I just can't seem to work it out. I'd be very grateful :). $\endgroup$ – dreamer May 20 '13 at 19:31
1
$\begingroup$

Here is a first couple of steps. See http://en.wikipedia.org/wiki/Duality_(optimization) for more details on Lagrangian duals.

To convert the original problem into a minimization problem, we minimize $-3x_1-4x_2$. Your Lagrangian is $$ \Lambda(x_1, x_2, \lambda) = -3x_1 - 4x_2 + \lambda (x_1^2 + x_2^2-25). $$ The dual problem is to maximimze $\Lambda(x_1, x_2, \lambda)$ over the region $x_1,x_2 \geq 0$.

Your problem is convex, so the min should occur where $\nabla \Lambda = \vec{0}$...

$\endgroup$
  • $\begingroup$ I've seen the same approach when the constraint function is presented with equality instead of inequality like in this particular case. Does having equality in the constraint change the way we solve this problem? Thanks! $\endgroup$ – e2l3n Mar 8 '15 at 19:20
  • 1
    $\begingroup$ @e2l3n I don't think so, but it's been a while since i looked at these $\endgroup$ – gt6989b Mar 9 '15 at 23:49

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.