0
$\begingroup$

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?

$\endgroup$

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.