[SciPy-user] How to determine if a function is convex or not ?

[Dominique Orban]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

fdu.xiaojf at gmail.com wrote:

> CVXOPT(http://abel.ee.ucla.edu/cvxopt) can handle both equality and
> inequality constraints, but it can only deal with convex functions.
> 
> So I want to know how to determine if a function is convex or not. Are
> there some rules for this? Or I have to calculate the derivatives ?

If you know that your function is twice differentiable, a necessary and
sufficient condition for it to be convex *at one given x* is for its Hessian
matrix (the matrix of second derivatives) to be positive semi-definite *at that
x*. This means all the eigenvalues must be >= 0.

Unfortunately, this process is undecidable. Algorithms that compute the
eigenvalues are of numerical nature and therefore, suffer from finite precision
errors. If you were told that your smallest eigenvalue were -1.0e-15, you
wouldn't be able to tell whether your matrix is indeed positive semi-definite
and roundoff errors caused the smallest eigenvalue to be evaluated to a very
small negative number, or whether your matrix is indefinite and really has a
negative eigenvalue.

Assessing convexity is difficult. I wrote a piece of software for functions
modeled as part of an optimization problem in the AMPL (www.ampl.com) modeling
language (again, but it is a standard in this field). The code is called DrAMPL
and there is a website: www.gerad.ca/~orban/drampl. Let me know and I can send
you the software. It isn't (yet) interface to Python, though, but it would let
you assess the convexity of your problem.

Dominique
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGdrAo2vhdTNgbn8wRAu7zAKDPb6RO9WlZRpZnNumyOYAJLl8rHQCgo+o1
qLLM+0m6D3XmvuU/wB7ZEnw=
=tC31
-----END PGP SIGNATURE-----