9
$\begingroup$

I want to minimize a complicated objective function, and I'm not sure if it is convex. Is there a nice algorithm that attempts to prove that it is not convex? Of course the algorithm could fail to prove this, in which case I would not know if it is convex or not, and this is OK; I just want to try to rule out convexity before I spend a lot of time trying to analytically determine whether the objective function is convex, for example by trying to rewrite the problem in a standard form known to be convex. One quick test would be to try to minimize from various starting points and if multiple local minima are found in this manner then it is not convex. But I was wondering if there is a better algorithm that was designed with this goal in mind.

$\endgroup$
  • $\begingroup$ Is the objective function smooth? Is it one-dimensional? Is the 2nd-derivative (or Hessian) expensive to evaluate? If possible I'd like to see the formula, or at least have a better notion of why it is "complicated". $\endgroup$ – hardmath Aug 20 '12 at 13:46
10
$\begingroup$

A function that is convex needs to satisfy $f(\alpha x + (1-\alpha)y) \le \alpha f(x) + (1-\alpha)f(y)$ for all $\alpha\in(0,1)$ and $x,y$ in the domain of definition. You could simply try to verify this formula for a large number of pairs $x,y$ and a couple of values $\alpha$, e.g. $\alpha=\{1/4,1/2,3/4\}$.

$\endgroup$
6
$\begingroup$

For a number of practically useful convexity/nonconvexity verification tests, see (self-disclaimer, I am the third author on this paper):

R. Fourer, C. Maheshwari, A. Neumaier, D. Orban, and H. Schichl, Convexity and Concavity Detection in Computational Graphs. Tree Walks for Convexity Assessment, INFORMS J. Computing 22 (2010), 26-43.

Note that there are many functions that are convex in the domain of interest but acannot easily be ''disciplined'', i.e., written in one of the forms required by structured convex solvers such as CVX.

$\endgroup$
  • $\begingroup$ Is this an evolution of DrAmpl, Arnold? $\endgroup$ – Michael Grant Dec 5 '14 at 3:43
  • 1
    $\begingroup$ @MichaelGrant: Yes, it is the official publication of the Dr. AMPL material. $\endgroup$ – Arnold Neumaier Dec 6 '14 at 12:59
2
$\begingroup$

A function can be non-convex without having multiple minima. There are a variety of optimization methods that apply (linear or nonlinear) conjugate gradient iterations, truncated when a negative operator norm is computed. The negative value indicates a direction of negative curvature (which cannot happen for convex functionals). If negative curvature is rarely encountered, these methods converge in a small number of optimization iterations. (If a quality preconditioner is available, the inner steps should also converge quickly.)

$\endgroup$
  • 2
    $\begingroup$ Just to clarify, what Jed is referring to when he says "is negative" is that the matrix of second derivatives of the function has negative eigenvalues. $\endgroup$ – Wolfgang Bangerth Aug 19 '12 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.