How to determine if a function is convex or not ?
Hi all, 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 ? Thanks. Xiao Jianfeng
there are many ways to determine if a function is convex, but not a single best check for all circumstances. Perhaps the simplest approach is to verify that the Hessian matrix is positive semidefinite everywhere by construction, or to use composition rules: http://www.stanford.edu/~boyd/cvxbook/ If you want to use CVXOPT for a general convex problem you first have to make sure the problem is actually convex (of course), and then you have to provide functions for evaluating first and second order derivatives, which sounded problematic in your case. What about the general nonlinear programming package someone else suggested? That might work for you (provided you figure out how to evaluate derivatives, which can be cumbersome but should be possible nevertheless). On 6/18/07, fdu.xiaojf@gmail.com <fdu.xiaojf@gmail.com> wrote:
Hi all,
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 ?
Thanks.
Xiao Jianfeng
_______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 fdu.xiaojf@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-----
participants (3)
-
Dominique Orban -
fdu.xiaojf＠gmail.com -
Joachim Dahl