# beta in Nesterov's first method for piece wise linear convex optimization problem

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.

• 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. – Christian Clason Mar 26 '15 at 1:39
• what is Nesterov's method for non smooth problems? Thank you:D – user40780 Mar 26 '15 at 2:17
• link.springer.com/article/10.1007/s10107-007-0149-x – Christian Clason Mar 26 '15 at 4:21
• Your comment solves my problem:D You could post it and I accept it:D – user40780 Mar 26 '15 at 4:57
• Is delayed column generation not an option? – Geoff Oxberry Mar 27 '15 at 12:13

## 1 Answer

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.