[SciPy-user] lagrange multipliers in python

Dominique Orban dominique.orban@gmail....
Fri Jun 15 10:54:54 CDT 2007


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


More information about the SciPy-user mailing list