Hi all, Sorry for the cross-posting. I'm trying to find the minimum of a multivariate function F(x1, x2, ..., xn) subject to multiple constraints G1(x1, x2, ..., xn) = 0, G2(...) = 0, ..., Gm(...) = 0. The conventional way is to construct a dummy function Q, $$Q(X, \Lambda) = F(X) + \lambda_1 G1(X) + \lambda_2 G2(X) + ... + \lambda_m Gm(X)$$ and then calculate the value of X and \Lambda when the gradient of function Q equals 0. I think this is a routine work, so I want to know if there are available functions in python(mainly scipy) to do this? Or maybe there is already a better way in python? I have googled but haven't found helpful pages. Thanks a lot. Xiao Jianfeng
afaik scipy hasn't NLP solvers with equality constraints, as well as CVXOPT. I had seen somewhere a Python package (seems like binding to c-code) where rSQP had been implemented, it allows to have nonlin equality constraints. Try web search "python rsqp optimization solver" or "python sqp optimization solver" for example visit http://trilinos.sandia.gov/packages/moocho/ and python binding to the latter http://trilinos.sandia.gov/packages/pytrilinos/ However, I didn't use the ones. Another one approach is use penalty coefficients (instead of Lagrange multipliers) with Naum Z. Shor r-alg implemented in scikits.openopt ralg solver (it doesn't contain c- or f-code, BSD lic.). It can handle gradient/subgradient provided by user and plot graphics output for NLP UC ralg solver. Currently it's unconstrained, but it allows to handle very huge penalties rather well. svn co http://svn.scipy.org/svn/scikits/trunk/openopt openopt sudo python setup.py install from scikits.openopt import NLP help(NLP) however, it doesn't produce pyc-files in the site-packages directory while installation, you'd better to do it by hands now. this is very preliminary version, only some months has been spent. WBR, D. fdu.xiaojf@gmail.com wrote:
Hi all,
Sorry for the cross-posting.
I'm trying to find the minimum of a multivariate function F(x1, x2, ..., xn) subject to multiple constraints G1(x1, x2, ..., xn) = 0, G2(...) = 0, ..., Gm(...) = 0.
The conventional way is to construct a dummy function Q,
$$Q(X, \Lambda) = F(X) + \lambda_1 G1(X) + \lambda_2 G2(X) + ... + \lambda_m Gm(X)$$
and then calculate the value of X and \Lambda when the gradient of function Q equals 0.
I think this is a routine work, so I want to know if there are available functions in python(mainly scipy) to do this? Or maybe there is already a better way in python?
I have googled but haven't found helpful pages.
Thanks a lot.
Xiao Jianfeng _______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
Hi dmitrey: dmitrey wrote:
afaik scipy hasn't NLP solvers with equality constraints, as well as CVXOPT. I had seen somewhere a Python package (seems like binding to c-code) where rSQP had been implemented, it allows to have nonlin equality constraints. Try web search "python rsqp optimization solver" or "python sqp optimization solver"
The equailty constraints in my problem are linear equations. Does this make things easier?
for example visit http://trilinos.sandia.gov/packages/moocho/ and python binding to the latter http://trilinos.sandia.gov/packages/pytrilinos/
However, I didn't use the ones. Another one approach is use penalty coefficients (instead of Lagrange multipliers) with Naum Z. Shor r-alg implemented in scikits.openopt ralg solver (it doesn't contain c- or f-code, BSD lic.). It can handle gradient/subgradient provided by user and plot graphics output for NLP UC ralg solver. Currently it's unconstrained, but it allows to handle very huge penalties rather well.
svn co http://svn.scipy.org/svn/scikits/trunk/openopt openopt sudo python setup.py install
from scikits.openopt import NLP help(NLP)
however, it doesn't produce pyc-files in the site-packages directory while
installation, you'd better to do it by hands now.
this is very preliminary version, only some months has been spent.
WBR, D.
Thanks a lot! Regards, Xiao Jianfeng
fdu.xiaojf@gmail.com wrote:
Hi dmitrey:
dmitrey wrote:
afaik scipy hasn't NLP solvers with equality constraints, as well as CVXOPT. I had seen somewhere a Python package (seems like binding to c-code) where rSQP had been implemented, it allows to have nonlin equality constraints. Try web search "python rsqp optimization solver" or "python sqp optimization solver"
The equailty constraints in my problem are linear equations. Does this make things easier?
afaik no, at least for those free Python solvers that I knew Maybe some weeks later free (BSD) NLP linearization-based Python solver will be available in openopt module, that will be capable of handling both equality & inequality NL constraints. HTH, D.
for example visit http://trilinos.sandia.gov/packages/moocho/ and python binding to the latter http://trilinos.sandia.gov/packages/pytrilinos/
However, I didn't use the ones. Another one approach is use penalty coefficients (instead of Lagrange multipliers) with Naum Z. Shor r-alg implemented in scikits.openopt ralg solver (it doesn't contain c- or f-code, BSD lic.). It can handle gradient/subgradient provided by user and plot graphics output for NLP UC ralg solver. Currently it's unconstrained, but it allows to handle very huge penalties rather well.
svn co http://svn.scipy.org/svn/scikits/trunk/openopt openopt sudo python setup.py install
from scikits.openopt import NLP help(NLP)
however, it doesn't produce pyc-files in the site-packages directory while
installation, you'd better to do it by hands now.
this is very preliminary version, only some months has been spent.
WBR, D.
Thanks a lot!
Regards,
Xiao Jianfeng _______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
What kind of function are you minimizing? CVXOPT handles convex functions with convex inequality constraints and linear equality constraints. If your function is non-convex, couldn't you eliminate your linear equality constraints and try Newton's method for the unconstrained problem?
Joachim Dahl wrote:
What kind of function are you minimizing?
CVXOPT handles convex functions with convex inequality constraints and linear equality constraints.
If your function is non-convex, couldn't you eliminate your linear equality constraints and try Newton's method for the unconstrained problem?
Can you give me some hints on how to eliminate the linear equality constraints ? How to judge if a function is non-convex? The expression of my function is too complex to calculate the derivative. Thanks. Xiao Jianfeng
If your function is too complicated to evaluate derivatives, chances are that it's not convex. But you're still going to need the first and second order derivatives for Newton's method... If you want to solve min. f(x) s.t. A*x = b you could first find a feasible point x0 satisfying A*x0 = b (e.g., the least-norm solution to A*x = b) and parametrize all feasible points as z = x0+ B*y where B spans the nullspace of A, i.e., A*B = 0. Now you have an unconstrained problem min. f( x0 + B*y ) over the new variable y. On 6/15/07, fdu.xiaojf@gmail.com <fdu.xiaojf@gmail.com> wrote:
What kind of function are you minimizing?
CVXOPT handles convex functions with convex inequality constraints and linear equality constraints.
If your function is non-convex, couldn't you eliminate your linear equality constraints and try Newton's method for the unconstrained
Joachim Dahl wrote: problem?
Can you give me some hints on how to eliminate the linear equality constraints ?
How to judge if a function is non-convex? The expression of my function is too complex to calculate the derivative.
Thanks.
Xiao Jianfeng
_______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
Hi Joachim, Joachim Dahl wrote:
If your function is too complicated to evaluate derivatives, chances are that it's not convex. But you're still going to need the first and second order derivatives for Newton's method...
If you want to solve
min. f(x) s.t. A*x = b
you could first find a feasible point x0 satisfying A*x0 = b (e.g., the least-norm solution to A*x = b) and parametrize all feasible points as
z = x0+ B*y
where B spans the nullspace of A, i.e., A*B = 0. Now you have an unconstrained problem
min. f( x0 + B*y )
over the new variable y.
I still don't quite understand how to liminate linear equality constraints. Could you please point me to some web resources that describe this method in detail? Or what key words I should use if I want to google on the web? Thanks. Xiao Jianfeng
Since your problem includes inequality constraints, the simple method I suggested doesn't apply; it only works for problems involving only linear equality constraints. To use the method, you need to identify the nullspace of your constraint matrix, e.g., using a singular value decomposition. On 6/17/07, fdu.xiaojf@gmail.com <fdu.xiaojf@gmail.com> wrote:
Hi Joachim,
Joachim Dahl wrote:
If your function is too complicated to evaluate derivatives, chances are that it's not convex. But you're still going to need the first and second order derivatives for Newton's method...
If you want to solve
min. f(x) s.t. A*x = b
you could first find a feasible point x0 satisfying A*x0 = b (e.g., the least-norm solution to A*x = b) and parametrize all feasible points as
z = x0+ B*y
where B spans the nullspace of A, i.e., A*B = 0. Now you have an unconstrained problem
min. f( x0 + B*y )
over the new variable y.
I still don't quite understand how to liminate linear equality constraints. Could you please point me to some web resources that describe this method in detail? Or what key words I should use if I want to google on the web?
Thanks.
Xiao Jianfeng _______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
On Sun, 17 Jun 2007, "fdu.xiaojf@gmail.com" apparently wrote:
I still don't quite understand how to liminate linear equality constraints. Could you please point me to some web resources that describe this method in detail? Or what key words I should use if I want to google on the web?
Perhaps an example would be useful. Example: solve the bivariate constrained minimization problem min x1**2 + x2**2 subject to: 2 x1 + 3 x2 = 5 Reparametrize constraint: Particular Soln: (1,1) General soln: x = (1,1) + (1,-2/3)y So solve the unconstrained univariate problem: min (1+y)**2 + (1-2y/3)**2 -> y = -3/13 -> x = (1,1) + (1,-2/3)(-3/13) = (10/13,15/13) hth, Alan Isaac
Hello Xiao, fdu.xiaojf@gmail.com wrote:
Hi all,
Sorry for the cross-posting.
I'm trying to find the minimum of a multivariate function F(x1, x2, ..., xn) subject to multiple constraints G1(x1, x2, ..., xn) = 0, G2(...) = 0, ..., Gm(...) = 0.
The conventional way is to construct a dummy function Q,
$$Q(X, \Lambda) = F(X) + \lambda_1 G1(X) + \lambda_2 G2(X) + ... + \lambda_m Gm(X)$$
and then calculate the value of X and \Lambda when the gradient of function Q equals 0.
I think this is a routine work, so I want to know if there are available functions in python(mainly scipy) to do this? Or maybe there is already a better way in python?
I have googled but haven't found helpful pages.
Thanks a lot.
Xiao Jianfeng
I am working on a Python package for nonlinear optimization called NLPy: http://nlpy.sf.net NLPy doesn't feature an SQP method just yet. There is however a full-fledged method for problems with nonlinear constraints (equalities or inequalities) in the works. At this point, since I understand from another post that your equality constraints are in fact linear, you should be able to solve your problem in NLPy with minimal programming, but somehow, the environment will need the first and second derivatives of your objective function. There are basically two ways to achieve that: 1) the hard way: write Python functions to implement those derivatives, 2) the back way: model your problem using a modeling language such as AMPL (www.ampl.org), which will compute the derivatives for you using automatic differentiation. NLPy has hooks to AMPL to make things work seamlessly and transparently. However, AMPL is commerical software. There exists a size-limited "student version" that comes free of charge, though, and that will serve your purposes well if your problem isn't too large. If you can compute first, but not second derivatives, there is possibility of approximating those using a limited-memory BFGS matrix. NLPy features a L-BFGS implementation in pure Python, save for the linesearch, which is in Fortran. Eliminating the linear constraints, as somebody suggested, is referred to as a "nullspace method" in optimization lingo. It entices computing a basis for the nullspace of your constraints, which can sometimes be just as time consuming as performing the minimization on the constrained problem. What is the size of your problem (how many constraints and variables)? I can help you offline with setting up your problem for use with NLPy. I hope this help, Dominique
On 6/16/07, Dominique Orban <dominique.orban@gmail.com> wrote:
Hello Xiao,
If you can compute first, but not second derivatives, there is possibility of approximating those using a limited-memory BFGS matrix. NLPy features a L-BFGS implementation in pure Python, save for the linesearch, which is in Fortran.
scipy.optimize also has an L-BFGS implementation -- in pure C I believe. Is there something yours offers that scipy's doesn't? (like constraints?) --bb
Bill Baxter wrote:
On 6/16/07, Dominique Orban <dominique.orban@gmail.com> wrote:
Hello Xiao,
If you can compute first, but not second derivatives, there is possibility of approximating those using a limited-memory BFGS matrix. NLPy features a L-BFGS implementation in pure Python, save for the linesearch, which is in Fortran.
scipy.optimize also has an L-BFGS implementation -- in pure C I believe. Is there something yours offers that scipy's doesn't? (like constraints?)
L-BFGS has been generalized to bound constraints only (resulting in the code L-BFGS-B), but the implementation is very different from that of L-BFGS. NLPy only contains L-BFGS for now and the implementation is standard. Since it is all in Python it is easy to read and modify (e.g, implement different iteration-dependent scalings.) I am not sure which one is interfaced in SciPy. Dominique
On 6/16/07, Dominique Orban <dominique.orban@gmail.com> wrote:
Bill Baxter wrote:
On 6/16/07, Dominique Orban <dominique.orban@gmail.com> wrote:
scipy.optimize also has an L-BFGS implementation -- in pure C I believe. Is there something yours offers that scipy's doesn't? (like constraints?)
L-BFGS has been generalized to bound constraints only (resulting in the code L-BFGS-B), but the implementation is very different from that of L-BFGS. NLPy only contains L-BFGS for now and the implementation is standard. Since it is all in Python it is easy to read and modify (e.g, implement different iteration-dependent scalings.) I am not sure which one is interfaced in SciPy.
Yes, it's L-BFGS-B in Scipy, actually. I was referring to constraints other than simple bounds. --bb
Bill Baxter wrote:
On 6/16/07, Dominique Orban <dominique.orban@gmail.com> wrote:
Bill Baxter wrote:
On 6/16/07, Dominique Orban <dominique.orban@gmail.com> wrote:
scipy.optimize also has an L-BFGS implementation -- in pure C I believe. Is there something yours offers that scipy's doesn't? (like constraints?)
L-BFGS has been generalized to bound constraints only (resulting in the code L-BFGS-B), but the implementation is very different from that of L-BFGS. NLPy only contains L-BFGS for now and the implementation is standard. Since it is all in Python it is easy to read and modify (e.g, implement different iteration-dependent scalings.) I am not sure which one is interfaced in SciPy.
Yes, it's L-BFGS-B in Scipy, actually. I was referring to constraints other than simple bounds.
Thanks, I will look into Scipy's interface. One of the ideas behind NLPy is that only fundamental building blocks for optimization are interfaces to state-of-the-art code in C or Fortran (e.g., some factorization routines, complex linesearches, ...) while I try to keep the algorithms themselves in Python. I haven't gotten around to implementing L-BFGS-B yet. There are also other ways to solve bound-constrained problems and still use an L-BFGS approx to the second derivatives. Dominique
Hi all, So much thanks for so many kind people. fdu.xiaojf@gmail.com wrote:
Hi all,
Sorry for the cross-posting.
I'm trying to find the minimum of a multivariate function F(x1, x2, ..., xn) subject to multiple constraints G1(x1, x2, ..., xn) = 0, G2(...) = 0, ..., Gm(...) = 0.
I'm sorry that I haven't fully stated my question correctly. There are still inequality constraints for my problem. All the variables(x1, x2, ..., xn) should be equal or bigger than 0.
The conventional way is to construct a dummy function Q,
$$Q(X, \Lambda) = F(X) + \lambda_1 G1(X) + \lambda_2 G2(X) + ... + \lambda_m Gm(X)$$
and then calculate the value of X and \Lambda when the gradient of function Q equals 0.
I think this is a routine work, so I want to know if there are available functions in python(mainly scipy) to do this? Or maybe there is already a better way in python?
I have googled but haven't found helpful pages.
Thanks a lot.
Xiao Jianfeng
Regards, Xiao Jianfeng
Hi all, First, I have to say thanks to so many kind people. fdu.xiaojf@gmail.com wrote:
Hi all,
So much thanks for so many kind people.
fdu.xiaojf@gmail.com wrote:
Hi all,
Sorry for the cross-posting.
I'm trying to find the minimum of a multivariate function F(x1, x2, ..., xn) subject to multiple constraints G1(x1, x2, ..., xn) = 0, G2(...) = 0, ..., Gm(...) = 0.
I'm sorry that I haven't fully stated my question correctly. There are still inequality constraints for my problem. All the variables(x1, x2, ..., xn) should be equal or bigger than 0.
The conventional way is to construct a dummy function Q,
$$Q(X, \Lambda) = F(X) + \lambda_1 G1(X) + \lambda_2 G2(X) + ... + \lambda_m Gm(X)$$
and then calculate the value of X and \Lambda when the gradient of function Q equals 0.
I think this is a routine work, so I want to know if there are available functions in python(mainly scipy) to do this? Or maybe there is already a better way in python?
I have googled but haven't found helpful pages.
Thanks a lot.
My last email was composed in a hurry, so let me describe my problem in detail to make it clear. I have to minimize a multivariate function F(x1, x2, ..., xn) subject to multiple inequality constraints and equality constraints. The number of variables(x1, x2, ..., xn) is 10 ~ 20, the number of inequality constraints is the same with the number of variables( all variables should be no less than 0). The number of equality constraints is less than 8(mainly 4 or 5), and the equality constraints are linear. My function is too complicated to get the expression of derivate easily, so according to Joachim Dahl(dahl.joachim@gmail.com)'s post, it is probably non-convex. But I think it's possible to calculate the first derivate numerically. I have tried scipy.optimize.fmin_l_bfgs_b(), which can handle bound constraints but seems cannot handle equality constraints. Mr. Markus Amann has kindly sent me a script written by him, which can handle equality constraints and is easy to use. The method used by Markus involves the calculation of Jacobian, which I don't understand.(Sorry for my ignorance in this filed. My major is chemistry, and I'm trying to learn some knowledge about numerical optimization.) However, it seems that the script cannot handle inequality constraints. (sorry if I was wrong). I hope my bad English have described my problem clearly. Any help will be greatly appreciated. Best regards, Xiao Jianfeng
Hi all, fdu.xiaojf@gmail.com wrote:
My last email was composed in a hurry, so let me describe my problem in detail to make it clear.
I have to minimize a multivariate function F(x1, x2, ..., xn) subject to multiple inequality constraints and equality constraints.
The number of variables(x1, x2, ..., xn) is 10 ~ 20, the number of inequality constraints is the same with the number of variables( all variables should be no less than 0). The number of equality constraints is less than 8(mainly 4 or 5), and the equality constraints are linear.
My function is too complicated to get the expression of derivate easily, so according to Joachim Dahl(dahl.joachim@gmail.com)'s post, it is probably non-convex. But I think it's possible to calculate the first derivate numerically.
I have tried scipy.optimize.fmin_l_bfgs_b(), which can handle bound constraints but seems cannot handle equality constraints.
Mr. Markus Amann has kindly sent me a script written by him, which can handle equality constraints and is easy to use. The method used by Markus involves the calculation of Jacobian, which I don't understand.(Sorry for my ignorance in this filed. My major is chemistry, and I'm trying to learn some knowledge about numerical optimization.) However, it seems that the script cannot handle inequality constraints. (sorry if I was wrong).
I hope my bad English have described my problem clearly.
Any help will be greatly appreciated.
Best regards,
Xiao Jianfeng
I have found COBYLA(http://www.jeannot.org/~js/code/index.en.html#COBYLA), and it has a Python interface, which make it very easy to use. It seems that COBYLA is capable to handle both equality and inequality constraints together. Here is an example of COBYLA(it actually example.py shiped with COBYLA): ##--------------------begin of example.py------------------ #!/usr/bin/env python # Python COBYLA example # @(#) $Jeannot: example.py,v 1.2 2004/04/13 16:35:11 js Exp $ import cobyla # A function to minimize # Must return a tuple with the function value and the value of the constraints # or None to abort the minimization def function(x): f = x[0]**2+abs(x[1])**3 # Two constraints to represent the equality constraint x**2+y**2 == 25 con = [0]*2 con[0] = x[0]**2 + x[1]**2 - 25 # x**2+y**2 >= 25 con[1] = - con[0] # x**2+y**2 <= 25 return f, con # Optimizer call rc, nf, x = cobyla.minimize(function, [-7, 3], low = [-10, 1], up = [3, 10]) print "After", nf, "function evaluations, COBYLA returned:", cobyla.RCSTRINGS[rc] print "x =", x print "f =", function(x)[0] print "con = ", function(x)[1] print "exact value = [-4.898979456, 1]" ##--------------------end of example.py------------------ Would somebody who is familiar with COBYLA tell me that is COBYLA suitable for my problem? Thanks. Xiao Jianfeng
fdu.xiaojf@gmail.com wrote:
Hi all,
fdu.xiaojf@gmail.com wrote:
My last email was composed in a hurry, so let me describe my problem in detail to make it clear.
I have to minimize a multivariate function F(x1, x2, ..., xn) subject to multiple inequality constraints and equality constraints.
The number of variables(x1, x2, ..., xn) is 10 ~ 20, the number of inequality constraints is the same with the number of variables( all variables should be no less than 0). The number of equality constraints is less than 8(mainly 4 or 5), and the equality constraints are linear.
My function is too complicated to get the expression of derivate easily, so according to Joachim Dahl(dahl.joachim@gmail.com)'s post, it is probably non-convex. But I think it's possible to calculate the first derivate numerically.
I have tried scipy.optimize.fmin_l_bfgs_b(), which can handle bound constraints but seems cannot handle equality constraints.
Mr. Markus Amann has kindly sent me a script written by him, which can handle equality constraints and is easy to use. The method used by Markus involves the calculation of Jacobian, which I don't understand.(Sorry for my ignorance in this filed. My major is chemistry, and I'm trying to learn some knowledge about numerical optimization.) However, it seems that the script cannot handle inequality constraints. (sorry if I was wrong).
I hope my bad English have described my problem clearly.
Any help will be greatly appreciated.
Best regards,
Xiao Jianfeng
I have found COBYLA(http://www.jeannot.org/~js/code/index.en.html#COBYLA), and it has a Python interface, which make it very easy to use.
You seem not to be aware that cobyla is part of scipy: scipy.optimize.fmin_cobyla Christian
Christian K wrote:
I have found COBYLA(http://www.jeannot.org/~js/code/index.en.html#COBYLA), and it has a Python interface, which make it very easy to use.
You seem not to be aware that cobyla is part of scipy: scipy.optimize.fmin_cobyla
Christian
Oh, my God! I have studied fmin_l_bfgs_b, fmin_tnc, and fmin_cobyla before, but I don't quit understand the "cons" parameter for fmin_cobyla after I have found COBYLA and have seen the example shipped with it. It seems that the interface of fmin_cobyla is a little different with that is provided with COBYLA. Anyway, it doesn't matter and I think fmin_cobyla is what I want. Thanks :-) Xiao Jianfeng
fdu.xiaojf@gmail.com wrote:
Christian K wrote:
I have found COBYLA(http://www.jeannot.org/~js/code/index.en.html#COBYLA), and it has a Python interface, which make it very easy to use.
You seem not to be aware that cobyla is part of scipy: scipy.optimize.fmin_cobyla
Christian
Oh, my God!
I have studied fmin_l_bfgs_b, fmin_tnc, and fmin_cobyla before, but I don't quit understand the "cons" parameter for fmin_cobyla after I have found COBYLA and have seen the example shipped with it.
I used fmin_cobyla once to find the envelope to some noisy signal. Thus I had as many inequality constraints as data points. See the attached file. This is not what you want of course, but it gives you an idea of how to use cobyla. Christian
participants (7)
-
Alan G Isaac -
Bill Baxter -
Christian K -
dmitrey -
Dominique Orban -
fdu.xiaojf＠gmail.com -
Joachim Dahl