1
$\begingroup$

Consider the a convex optimization problem to minimize $f(x)$ subject to the constraint $g(x)\leq0$. Based on the lecture notes Link,Pg 23 , the Lagrange can be expressed as $$L(x,\lambda) = f(x) + \lambda g(x)$$ Suppose $x(\lambda)$ is the minimizer for $\min_x L(x,\lambda)$ ($x(\lambda)$ denotes $x$ in terms of $\lambda$ and this expression is generally obtained by KKT conditions), then the subgradient method to update dual variable $\lambda$ and find optimal dual variable $\lambda^*$ is given by

  • Initialize $\lambda(0)$
  • for $i$
  • $x(i) = x(\lambda(i))$
  • $\lambda(i+1) = [\lambda(i) + \alpha_i g(x(i))]_+$
  • end $i$

where $\alpha_i$ is the step size and $[\cdot]_+=max(\cdot,0)$.

My question is in some cases, it is hard or impossible to find $x(\lambda)$, i.e., no analytical expression for $x(\lambda)$ (This happens a lot when you have multiple nonlinear constraints). In these cases, how does subgradient method work to find the optimal dual $\lambda^*$. If subgradient method fails, any other efficient method to find $\lambda^*$. Any suggestion or reference is appreciated.

$\endgroup$
  • $\begingroup$ What's your optimization problem? You could just use a primal-dual method that solves the primal and dual problems simultaneously. $\endgroup$ – littleO Dec 23 '16 at 1:32
  • 1
    $\begingroup$ My student just wrote a paper on this problem that may be of interest here, it has faster convergence than standard primal-dual subgradient: ee.usc.edu/stochastic-nets/docs/primaldual-convex-cdc2016.pdf $\endgroup$ – Michael Dec 23 '16 at 2:24
  • 1
    $\begingroup$ @Michael that looks very interesting. Seems to be inspired by the concepts of accelerated gradients (Nesterov)? $\endgroup$ – Michael Grant Dec 23 '16 at 3:25
  • 2
    $\begingroup$ @MichaelGrant Like Nesterov, our algorithm uses decisions at time $t-1$. However, this seems to be a coincidence and we do not know if there is a deeper relationship. It was inspired by Lyapunov drift, where a pesky $g(x(t))^2$ term slows convergence. We could remove this term by doing a minimization of the form $min_{x \in \mathcal{X}}[f(x) + \lambda g(x) + a g(x(t))^2]$ every step, but $g(x(t))$ is usually a sum of terms and squaring it would make these terms appear nonseparably. So we approximated it by $g(x(t))g(x(t-1))$, then we compensate for the error using a prox term. $\endgroup$ – Michael Dec 23 '16 at 14:47
  • 1
    $\begingroup$ Maybe one possibility if there is no analytical formula for $x(\lambda)$ when using the dual subgradient method would be to solve for $x(\lambda)$ using Newton's method. Newton's method might converge very quickly because you have a good first guess from the previous iteration. (But, I would be inclined to just not use the dual subgradient method.) $\endgroup$ – littleO Dec 24 '16 at 4:21

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.