Lagrangian multipliers and duality

248 Views Asked by At

I am working on an constraint optimization problem with inequalities like the following:

Maximize $f(\mathbf{x}) = 1 - x_1^{2} - x_2^{2}$ by giving that $g(\mathbf{x}) = x_1 + x_2 >=1$.

The usual steps are to create the Lagranging $L(x, \lambda) = f(\mathbf{x}) + \lambda g(\mathbf{x})$ and write down the KKT conditions, stationary, primal, and dual feasibility as well as complementary slackness and solve. I am a bit confused since I can use the KKT conditions to calculate the derivatives over $x_1, x_2$ and also the complementary slackness and come up with values. So I do not need to calculate the dual in this case.

But when should I make use of the dual lagrangian and how can I do it in my case? Is it that I need to solve over $\partial L/ \partial \mathbf{x}$ and then replace over $\lambda$?

1

There are 1 best solutions below

20
On BEST ANSWER

First, your problem does not have any solution because taking one of the variable, e.g. $x_1$, to $-\infty$ we have $f \to -\infty$.

Second, KKT conditions are in general only necessary optimality conditions (e.g. if the problem is non-convex). This means: if $x^*$ is a solution then there exist dual variables $\lambda^*$ that, together with $x^*$, satisfy the KKT conditions, given that your problem satisfies some further assumption such as the Slater's qualification constraints. (Note also that in your case $x^*$ does not exist so the "if" does not happen.)

Finally, regarding your main concern:

I am a bit confused since I can use the KKT conditions to calculate the derivatives over $x_1,x_2,x_3$ and also the complementary slackness and come up with values. So I do not need to calculate the dual in this case. But when should I make use of the dual lagrangian and how can I do it in my case?

In short: If we can solve the KKT, why do we need the dual function at all? I'm supposing here that our problem is convex and satisfies the Slater's conditions.

The answer simply lies in the word "if". If we can solve the KKT, then that's great, we don't need to care about the dual function. In practice, however, the KKT system often cannot be solved easily/analytically. In this case, one can solve the dual problem numerically (if it's easier to solve than the primal) to obtain $\lambda^*$ and then recover the primal solution by solving $x^* = \arg\min_x L(x,\lambda^*)$. This is a typical routine in convex optimization, and it should be noted that there are also methods that numerically solve both the primal and dual problems at the same time, called primal-dual methods.

Let me know if you have further questions.

Update: Per OP's request, I show below how to apply the above routine to the following corrected (and convex) problem: $$\max_x 1 - x_1^2 - x_2^2 \quad \mbox{s.t. } x_1 + x_2 \ge 1.$$

There are a few steps.

  1. Re-write the problem into the canonical form for convex problems: $$\min_x f(x) \quad \mbox{s.t. } h(x) \le 0,$$ where $f(x) = x_1^2 + x_2^2 - 1$ and $h(x) = 1 - x_1 - x_2$ are both convex. Strong duality holds because the Slater's condition holds: $\exists x: h(x) < 0.$

  2. Find the dual function $g(\lambda) \triangleq \inf_x L(x,\lambda)$ where $L(x,\lambda)$ is the Lagrangian with $\lambda \ge 0$: $$L(x,\lambda) = f(x) + \lambda h(x) = x_1^2 + x_2^2 - 1 + \lambda(1 - x_1 - x_2).$$ To minimize $L(x,\lambda)$ with respect to $x$, it suffices to set the derivatives with respect to $x_1$ and $x_2$ to $0$, which gives $x_1=x_2=\frac{\lambda}{2}$. Therefore $$g(\lambda) = \inf_x L(x,\lambda) = L((\lambda/2, \lambda/2),\lambda) = -\frac{\lambda^2}{2} + \lambda - 1.$$ Thus, we have found the dual function.

  3. We maximize the dual function to find $\lambda^*$: $$\lambda^* = \arg\max_{\lambda \ge 0} g(\lambda).$$ You can take the derivative of $g(\lambda)$ and set it to $0$ to find $\lambda^*$, or just notice that $$g(\lambda) = -\frac{\lambda^2}{2} + \lambda - 1 = -\frac{1}{2}(\lambda - 1)^2 - \frac{1}{2} \le -\frac{1}{2},$$ and observe that the maximum value of $g(\lambda)$ is $-\frac{1}{2}$, attained at $\lambda^* = 1$.

  4. Finally, we recover the primal solution by solving $$x^* = \arg\min_x L(x,\lambda^*),$$ where $L(x,\lambda^*) = L(x,1) = x_1^2 + x_2^2 - x_1 - x_2$. Again, by setting the derivatives with respect to $x_1$ and $x_2$ to $0$, or by completing the squares, we easily obtain $x_1^* = x_2^* = \frac{1}{2}$.

Conclusion: the solution to our original problem is $x^* = (1/2, 1/2)$.