I am working on convex approximations for non-convex optimization problems. For a non-convex constraint $g(x) \leq 0$ with Lipschitz continuous gradient i.e. ($\lvert|\nabla g (x_{1})-\nabla g(x_{2})\rvert|\leq L \lvert| x_{1}-x_{2}\rvert|$), a quadratic upper bound is given by $g(y)+\nabla g(y)(x-y)+\frac{L}{2}\lvert|{x-y}\rvert|^2$.

Is there a way to estimate the value of this Lipschitz constant?

  • $\begingroup$ Is $g$ differentiable? If so, can you obtain a bound on the Hessian of $g$? $\endgroup$
    – copper.hat
    Mar 27, 2018 at 3:58
  • $\begingroup$ In most scenarios, you'll be find with a local approximation, which can be gotten by line search... $\endgroup$
    – dohmatob
    Mar 27, 2018 at 9:54
  • $\begingroup$ @copper.hat Yes g is differentiable. From the Lipschitz condition, I can find that $\lvert| \nabla^{2} g(x) \rvert|_{F} \leq L$, i.e., an upper bound on the Frobenius norm of hessian of g, but that will only provide a lower bound on L. $\endgroup$
    – jjgarrison
    Mar 27, 2018 at 18:02
  • $\begingroup$ @dohmatob Do you mean a local Lipschitz constant? Can you provide some reference for the method you mentioned? Thanks! $\endgroup$
    – jjgarrison
    Mar 27, 2018 at 18:48


You must log in to answer this question.