KKT unconstrained optimization of duals

Question

I've been working through parts of "KKT Conditions, First-Order and Second-Order Optimization, and Distributed Optimization: Tutorial and Survey" and can't fully comprehend it. The problem is optimization with inequality constraints. In Section 4.7 (page 19) the tutorial says:

Recall the dual problem (50). The constraint in this problem is already satisfied by the dual feasibility in the KKT conditions. Hence, we can ignore the constraint of the dual problem (as it is automatically satisfied by dual feasibility)

I do not see how restricting domain and then optimizing can be equivalent to first optimizing and then restricting the domain.

The following section of the tutorial "4.8. Solving Optimization by Method of Lagrange Multipliers" builds on it and describes an algorithm to solve the problem. However, the algorithm never verifies that the duals λ, ν obtained are non-negative. I have tried to apply the algorithm step-by-step on a toy problem to illustrate the issue.

Let's say we want to: minimize $f(x) = x^2$ subject to $y(x) = x - 1 \leq 0$. I believe this problem is convex and satisfies Slater's condition.

1. "We write the Lagrangian" $L = f(x) + \lambda y(x) = x^2 + \lambda (x-1)$

2. "We consider the dual function defined in Eq. (44) and we solve it ... by taking the derivative of Lagrangian w.r.t. x and setting it to zero" $\frac{\partial{L}}{\partial{x}}=0 \implies x^{\dagger} = -\frac{\lambda}{2}$ "This gives us the dual function" $g(\lambda, \nu) = L(x^\dagger, \lambda, \nu) = -\frac{\lambda^2}{4}-\lambda$

3. "We consider the dual problem ... we solve this problem by taking the derivative of dual function w.r.t. λ and ν and setting them to zero" $-\frac{\lambda^*}{2} - 1 = 0 \implies \lambda^* = -2$ <- here is the issue

4. "We put the optimal dual variables $\lambda^∗$ and $\nu^*$ in Eq. (64) to find the optimal primal variable ... solve this problem by taking the derivative of Lagrangian at optimal dual variables w.r.t. x and setting it to zero" $x^* = -\frac{\lambda^*}{2} = 1$

This does not yield the expected $x^*=0$ and $\lambda^* = 0$. Could somebody please advise if I have missed the part of the algorithm and tutorials that deals with negative duals? I would really like to know what the authors meant.

Thank you!

Answer 1

This part of the paper is wrong. You have to use the dual feasibility in the dual problem (50). As you observed, the solution may change (and may become dual infeasible) if you drop the dual feasibility as in (69).