How to formulate and solve a Lagrange dual problem?

223 Views Asked by At

I want to consider this simple convex problem: $$\min f(x) = {x_1 + x_2} {\ {\ }}$$ $$s.t.{\ {\ }} -x_1 +x_2^2\leq 0$$ $$ x \in X = \mathbb{R}^2 $$

Finding the lagrangian, in my case $$L(x,\lambda) = x_1 + x_2 -\lambda(-x_1 + x_2^2)$$

Obtaining the first derivative: $$\frac{\partial L(x_1,\lambda)}{\partial x} = 1 +\lambda$$ $$\frac{\partial L(x_2,\lambda)}{\partial x} = 1 -2\lambda x_2$$

From here, I obtain an expresssion of x in terms of the lagrange multiplier, $\lambda$: ${\ } x_2=\dfrac{1}{2\lambda}$

So now I can substitute this value in the lagrangian obtaining an expression just in terms of the Lagrange multiplier:

$$L(\lambda) = 1 +\lambda -\dfrac{\lambda+1}{2}-\lambda(\dfrac{\lambda+1}{2}-3)$$ $$L(\lambda) = 1 +\lambda + \dfrac{1}{2\lambda} -\lambda(1 -\lambda) + \dfrac{1}{4\lambda^2})$$

From here, I am not really sure how to manage the constraints for $\lambda$ and solve the dual problem.

1

There are 1 best solutions below

0
On BEST ANSWER

Basically you are trying to minimize $f(x,y) = x+y$ subject to $x \ge y^2$ over $(x,y) \in \mathbb{R}^2$.

It's easy to see $f$ has no extrema, so the only solutions will come from the boundary. Hence we must minimize subject to $x = y^2$.

Basic Approach

Because of the constraint, we can write $$ f(x,y) = x + y = y^2 + y $$ which is a parabola opening up, hence the minimum point is achieved at $y = -1/2$, and $x= y^2 = 1/4$.

Lagrange Multipliers

We have $f(x,y) = x+y$ and $g(x,y) = x - y^2$ so $$ \begin{pmatrix} 0 \\ 0 \end{pmatrix} = \vec{\nabla} f + \lambda \vec{\nabla} g = \begin{pmatrix} 1 + \lambda \\ 1 - 2\lambda y \end{pmatrix} $$ The first equation implies $\lambda = -1$, so the second reads $$ 0 = 1 - 2(-1)y \iff y = -1/2 $$ Now plug into the constraint to compute $x$.