1
$\begingroup$

I am trying to implement Nesterov's first method to solve convex piece-wise linear optimization problem, from this website:

https://blogs.princeton.edu/imabandit/2013/04/01/acceleratedgradientdescent/

But then, such $\beta$ does not exist convex piece-wise linear function. So I am wondering what shall I put into $\beta$ for my implementations.

PS: LP is not feasible because there are $2^{80}$ such hyper planes.

$\endgroup$
  • $\begingroup$ Since your functional is not smooth, you simply cannot use this method. Either replace your function by a smoothed approximation, or use Nesterov's method for nonsmooth problems. $\endgroup$ – Christian Clason Mar 26 '15 at 1:39
  • $\begingroup$ what is Nesterov's method for non smooth problems? Thank you:D $\endgroup$ – user40780 Mar 26 '15 at 2:17
  • 1
    $\begingroup$ link.springer.com/article/10.1007/s10107-007-0149-x $\endgroup$ – Christian Clason Mar 26 '15 at 4:21
  • 1
    $\begingroup$ Your comment solves my problem:D You could post it and I accept it:D $\endgroup$ – user40780 Mar 26 '15 at 4:57
  • $\begingroup$ Is delayed column generation not an option? $\endgroup$ – Geoff Oxberry Mar 27 '15 at 12:13
6
$\begingroup$

A piecewise linear function is not differentiable (except in the trivial case), so as you noticed this method cannot be applied - the gradient does not exist, let alone its Lipschitz constant beta.

If you want to use a variant of Nesterov's accelerated algorithm, you have two options:

  1. You replace your function by a smooth approximation and apply an accelerated gradient descent; this is described in Nesterov's paper Smooth minimization of non-smooth functions, Mathematical Programming May 2005, Volume 103, Issue 1, pp 127-152, or

  2. you use his accelerated subgradient scheme for nonsmooth convex functions; this is described in his paper Primal-dual subgradient methods for convex problems, Mathematical Programming August 2009, Volume 120, Issue 1, pp 221-259.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.