Which algorithms are suitable for solving problems of the form $$ \min_x \lbrace f(x) \; | \; Ax \leq b \rbrace $$ with nonconvex, differentiable obfective $f$. Unfortunately, $f$ cannot be assumed to be differentiable twice. I am also interested in the case where $f$ has Lipschitz continuous gradients.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
First things first: Be aware that global minima may be out of reach.
Here are two possibilities that come to mind:
If you have differentiability, you may use projected gradient descent: Start with an initial guess $x_0$ that fulfills $Ax_0\leq b$, do a gradient descent step for $f$ and project the result back to the constraint set $Ax\leq b$ and iterate. You may need to control the stepsize to ensure descent and convergence.
Another approach (which gives a descent method in all cases) it what has been called "$\eta$-trick" (see here). The idea is to write the non-convex function as a minimum of a family of quadratic functions of the form $\tfrac{x^2}{2\eta} + h(\eta)$ i.e. $f(x) = \inf_{\eta>0} \tfrac{x^2}{2\eta} + h(\eta)$. If you find some $h$ which does that you can minimize with the respect to $x$ and $\eta$ alternatingly in a simple way…
