Consider the problem \begin{equation} \begin{aligned} \min_{x} \quad & f(x) + g(x), \\ \textrm{s.t.} \quad & x \in X \end{aligned} \tag{1} \end{equation} where $X \subset \mathbb R^n$ is a convex set, $f$ is convex and twice-differentiable over $X$, and $g$ is neither convex nor concave, but also twice-differentiable, over $X$. Is there a class of algorithms that aim to efficiently solve this kind of problem?

  • $\begingroup$ If g(x) is concave, that is a Difference of Convex (Functions) Programming problem, known as DC Programming, for which there are specialized algorithm for various subclasses. $\endgroup$ Sep 16, 2023 at 22:49
  • $\begingroup$ @MarkL.Stone Sorry, I should’ve been more precise in my question. What I meant is that $g$ is neither convex nor concave. I’ve edited my question accordingly. $\endgroup$
    – mhdadk
    Sep 17, 2023 at 0:04
  • 2
    $\begingroup$ I understood my comment as covering a special case of your then question, a special case for which there is a large body of work. I'm not sure that if g(x) is neither convex nor concave (i.e., is indefinite), that is really different than just the overall objective function being indefinite, for which there are various local and global non-convex optimization solvers. $\endgroup$ Sep 17, 2023 at 0:22
  • 2
    $\begingroup$ If you have the analytical form of the functions, you can first try a global solver. Otherwise or if its not successful, since its differentiable, you can try a local NLP solver. You'll get a locally optimal solution $\endgroup$
    – fontanf
    Sep 17, 2023 at 10:47
  • $\begingroup$ @MarkL.Stone thanks for the feedback. I suspected that this was the case, but I guess I was hoping I was wrong. $\endgroup$
    – mhdadk
    Sep 17, 2023 at 15:10


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.