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.
beta in Nesterov's first method for piece wise linear convex optimization problem
convex optimization
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: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 ProgrammingMay 2005, Volume 103, Issue 1, pp 127-152, oryou use his accelerated subgradient scheme for nonsmooth convex functions; this is described in his paper Primal-dual subgradient methods for convex problems, Mathematical ProgrammingAugust 2009, Volume 120, Issue 1, pp 221-259.