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)

  1. 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)$
  2. Then we apply gradient descent on $\lambda$: $\lambda \leftarrow \lambda - \alpha \nabla_\lambda \mathcal L(x^*,\lambda)$
  3. 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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.