Solve the Lagrangian dual problem associated to $\max_{x_1,x_2\ge0}(3x_1+4x_2)$ such that $x_1^2+x_2^2\le25$

Question

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?

Answer 1

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}$...

Answer 2

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.