Dual Gradient Descent

Tags	Constrained

This is how you can turn a constrained optimization problem into an unconstrained.

Let’s say you wanted to do

\max_x f(x) \\ \text{s.t.} ~g(x) \geq 0

You can set up the lagrangian:

\mathcal{L}(x,\lambda) = f(x) - \lambda g(x)

Now, we propose that we can yield a constrained solution with the following objective:

\max_x \min_{\lambda \geq 0} [f(x) -\lambda g(x)]

Why? Well, let’s set up two scenarios

Scenario 1: $g(x) \geq 0$ . In this case, when we run the inner optimization, the best value we can get is using $\lambda = 0$ . Then, the outer optimization is the unchanged $\max f(x)$ .

Scenario 2: $g(x) < 0$ . In this case, the inner optimization will diverge, as the minimum is achieved when $\lambda = \infty$ , and there’s no way to recover in the outer loop.

Therefore, we see that using this objective, the only viable solution will follow the constraint

Implementation

In practice, we just alternate a gradient WRT $\lambda$ and the policy.