For an optimization problem $$ \max f(x)\\\ s.t. g(x)\le 0 $$ The Lagrangian is $$ \mathcal L(x, \lambda)=f(x)-\lambda g(x) $$ Dual gradient descent solves it by (according to Page 43 of this lecture, I modify the process for solving a maximization problem here)
- We first find the an optimal value of $x$ that maximizes $\mathcal L(x,\lambda)$, i.e., solving $x^*\leftarrow\arg\max_x\mathcal L (x,\lambda)$
- Then we apply gradient descent on $\lambda$: $\lambda \leftarrow \lambda - \alpha \nabla_\lambda \mathcal L(x^*,\lambda)$
- Repeat the above process until convergence
The method of Lagrangian multipliers solves it by directly computing the gradients of both $x$ and $\lambda$ and setting them to zero.
It seems to me that the only difference between these two algorithms is that one repeatedly performs gradient descent on $\lambda$, and the other computes $\lambda$ directly by setting $\nabla_\lambda\mathcal L(x,\lambda)$ to zero. Am I right? If that's the only difference, when should we prefer one over the other?