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 '18 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 '18 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 '18 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 '18 at 18:48

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.