Mailman 3 January 2011 - SciPy-Dev

SLSQP Constrained Optimizer Status
by Rob Falck 25 Nov '13

25 Nov '13

I'm currently implementing the Sequential Least Squares Quadratic Programming (SLSQP) optimizer, by Dieter Kraft, for use in Scipy. The Fortran code being wrapped with F2PY is here: http://www.netlib.org/toms/733 (its use within Scipy has been cleared) SLSQP provides for bounds on the independent variables, as well as equality and inequality constraint functions, which is a capability that doesn't exist in scipy.optimize. Currently the code works, although the constraint normals are being generated by approximation. I'm working on a way to pass these in. I think the most elegant way will be a single function that returns the matrix of constraint normals. For a demonstration of what the code can do, here is an optimization of f(x,y) = 2xy + 2x - x**2 - 2y**2 Example 14.2 in Chapra & Canale gives the maximum as x=2.0, y=1.0. The unbounded optimization tests find this solution. As expected, its faster when derivatives are provided rather than approximated. Unbounded optimization. Derivatives approximated. Elapsed time: 1.45792961121 ms Results [[1.9999999515712266, 0.99999996181577444], -1.9999999999999984, 4, 0, 'Optimization terminated successfully.'] Unbounded optimization. Derivatives provided. Elapsed time: 1.03211402893 ms Results [[1.9999999515712266, 0.99999996181577444], -1.9999999999999984, 4, 0, 'Optimization terminated successfully.'] The following example uses an equality constraint to find the optimal when x=y. Bound optimization. Derivatives approximated. Elapsed time: 1.384973526 ms Results [[0.99999996845920858, 0.99999996845920858], -0.99999999999999889, 4, 0, 'Optimization terminated successfully.'] I've tried to conform to the syntax used by the other optimizers in scipy.optimize. The function definition and doc string are below. If anyone is interested in testing it out, let me know. def fmin_slsqp( func, x0 , eqcons=[], f_eqcons=None, ieqcons=[], f_ieqcons=None, bounds = [], fprime = None, fprime_cons=None,args = (), iter = 100, acc = 1.0E-6, iprint = 1, full_output = 0, epsilon = _epsilon ): """ Minimize a function using Sequential Least SQuares Programming Description: Python interface function for the SLSQP Optimization subroutine originally implemented by Dieter Kraft. Inputs: func - Objective function (in the form func(x, *args)) x0 - Initial guess for the independent variable(s). eqcons - A list of functions of length n such that eqcons[j](x0,*args) == 0.0 in a successfully optimized problem f_eqcons - A function of the form f_eqcons(x, *args) that returns an array in which each element must equal 0.0 in a successfully optimized problem. If f_eqcons is specified, eqcons is ignored. ieqcons - A list of functions of length n such that ieqcons[j](x0,*args) >= 0.0 in a successfully optimized problem f_ieqcons - A function of the form f_ieqcons(x0, *args) that returns an array in which each element must be greater or equal to 0.0 in a successfully optimized problem. If f_ieqcons is specified, ieqcons is ignored. bounds - A list of tuples specifying the lower and upper bound for each independent variable [ (xl0, xu0), (xl1, xu1), ...] fprime - A function that evaluates the partial derivatives of func fprime_cons - A function of the form f(x, *args) that returns the m by n array of constraint normals. If not provided, the normals will be approximated. Equality constraint normals precede inequality constraint normals. args - A sequence of additional arguments passed to func and fprime iter - The maximum number of iterations (int) acc - Requested accuracy (float) iprint - The verbosity of fmin_slsqp. iprint <= 0 : Silent operation iprint == 1 : Print summary upon completion (default) iprint >= 2 : Print status of each iterate and summary full_output - If 0, return only the minimizer of func (default). Otherwise, output final objective function and summary information. epsilon - The step size for finite-difference derivative estimates. Outputs: ( x, { fx, gnorm, its, imode, smode }) x - The final minimizer of func. fx - The final value of the objective function. its - The number of iterations. imode - The exit mode from the optimizer, as an integer. smode - A string describing the exit mode from the optimizer. Exit modes are defined as follows: -1 : Gradient evaluation required (g & a) 0 : Optimization terminated successfully. 1 : Function evaluation required (f & c) 2 : Number of equality constraints larger than number of independent variables 3 : More than 3*n iterations in LSQ subproblem 4 : Inequality constraints incompatible 5 : Singular matrix E in LSQ subproblem 6 : Singular matrix C in LSQ subproblem 7 : Rank-deficient equality constraint subproblem HFTI 8 : Positive directional derivative for linesearch 9 : Iteration limit exceeded -- - Rob Falck

4 16

request of a FGMRES krylov solver
by Thélesphonse Bigorneault 18 Feb '11

18 Feb '11

I would like to have a FGMRES Krylov solver in scipy. FGMRES is a variant of the GMRES method with right preconditioning that enables the use of a different preconditioner at each step of the Arnoldi process. A possibility could be to "borrow" the fgmres function from pyamg (which as a compatible license) http://code.google.com/p/pyamg/source/browse/trunk/pyamg/krylov/_fgmres.py Including this code into scipy should be straightforward. Télesphore Bigorneault

3 3

Starting a scikit for NUFFT
by David Kremer 05 Feb '11

05 Feb '11

Hello, I would like to start a scikit on nufft. I already gather some materials to start my work. Source code here : http://www.cims.nyu.edu/cmcl/nufft/nufft.html References here : [DR] Fast Fourier transforms for nonequispaced data, A. Dutt and V. Rokhlin, SIAM J. Sci. Comput. 14, 1368-1383, 1993. [GL] Accelerating the Nonuniform Fast Fourier Transform, L. Greengard and J.-Y. Lee, SIAM Review 46, 443-454 (2004). I'm not an expert on it. Actually, I do need to perform a nufft, but I would appreciate any comment on the way it should be implemented. Please, provide me with good information on the better way to build a scikit. Thank you very much. David Kremer

3 5

ANN: SciPy 0.9.0 release candidate 2
by Ralf Gommers 03 Feb '11

03 Feb '11

Hi, I am pleased to announce the availability of the second release candidate of SciPy 0.9.0. This will be the first SciPy release to include support for Python 3 (all modules except scipy.weave), as well as for Python 2.7. Due to the Sourceforge outage I am not able to put binaries on the normal download site right now, that will probably only happen in a week or so. If you want to try the RC now please build from svn, and report any issues. Changes since release candidate 1: - fixes for build problems with MSVC + MKL (#1210, #1376) - fix pilutil test to work with numpy master branch - fix constants.codata to be backwards-compatible Enjoy, Ralf

5 18

legendre regression
by Yaroslav Halchenko 01 Feb '11

01 Feb '11

Switching to scipy (0.8.0) + numpy (1.5.1) from scipy (0.7.2) + numpy (1.4.1) reveals regression: *(Pdb) print legendre(1)(N.array([-0.999999999999 , -0.6, -0.2, 0.2, 0.6, 1. ])) [-1. -0.6 -0.2 0.2 0.6 1. ] *(Pdb) print legendre(1)(N.array([-1 , -0.6, -0.2, 0.2, 0.6, 1. ])) [ inf -0.6 -0.2 0.2 0.6 1. ] while before it was giving correct boundary value (-1). Could anyone please check if it is still present in current HEAD? imho worth a bugreport (haven't ran into similar one upon query but decided to check -- may be it was resolved already). -- =------------------------------------------------------------------= Keep in touch www.onerussian.com Yaroslav Halchenko www.ohloh.net/accounts/yarikoptic

4 6

git-friendly cythonize script + Tempita templating
by Dag Sverre Seljebotn 01 Feb '11

01 Feb '11

It's getting close to the finish of my Fwrap work on SciPy. I'll get something to the list on that soon. Meanwhile here's a small start re: Cython vs. SciPy: cythonize.py ------------- I've been working with a lot of Cython files. Since Cython isn't (currently at least) invoked by the build system and is not a build-time dependency, I created a development-time utility script to scan for Cython files and invoke Cython in a way that is fast and hopefully safe with git (I had a Makefile, but that didn't work well with switching git branch). https://github.com/dagss/scipy-refactor/blob/cythonize/cythonize.py (Ignore the "-refactor", it is based off scipy/master). It: - First, checks if there's been any changes since the last time it was regenerated by you (checked by sha1 hash against a local "cythonize.dat") - Then, checks with git to see if the .c has been committed in a child commit to the .pyx (it is assumed you use git) - Finally, resort to invoking Cython. I'm sure it needs some polish/Python 3 support etc. (but keep in mind that it is a development time script only). Also, it won't currently strip comments like, e.g., generate_qhull.py did. Feedback welcome. Tempita --------- I needed a template language, and since Robert Kern recommended Tempita, I went with that for wrappers I made with Fwrap: http://pythonpaste.org/tempita/ cythonize.py above will interpret ".pyx.in" as being Tempita-templated Cython source code. Later (too late) I discovered that Mako was already in use in SciPy in interpolate/interpnd.pyx. In the "cythonize" branch linked to above I've converted it to use Tempita instead, in case you agree with that. The advantage with Tempita is that it fits in a single ~1000-line Python file, so that it should be convenient to bundle it with the build system on a later date. Dag Sverre

2 2

ANN: SciPy 0.9.0 release candidate 1
by Ralf Gommers 29 Jan '11

29 Jan '11

Hi, I am pleased to announce the availability of the first release candidate of SciPy 0.9.0. This will be the first SciPy release to include support for Python 3 (all modules except scipy.weave), as well as for Python 2.7. Please try this release candidate and report any problems on the scipy-dev mailing list. Binaries, sources and release notes can be found at http://sourceforge.net/projects/scipy/files/scipy/0.9.0rc1/. Note that some OS X binaries are not uploaded yet, they should follow in the next few days. Enjoy, Ralf

2 3

Lomb-Scargle periodogram
by Pim Schellart 28 Jan '11

28 Jan '11

Dear SciPy developers, I have recently submitted code to calculate the Lomb-Scargle periodogram (see ticket http://projects.scipy.org/scipy/ticket/1352 for more information). After some iterations of review, recoding, adding documentation and adding unit tests the code (according to Ralf Gommers) is ready to go in. Ralf has nicely integrated the code into SciPy trunk in his git branch (https://github.com/rgommers/scipy/tree/lomb-scargle) and you may pull from there. Now the time has come to discuss where to put it and Ralf has suggested to have this discussion here: "I've played with your code a bit, changed a few things, and added it to scipy.signal in a github branch: https://github.com/rgommers/scipy/tree/lomb-scargle. I think it looks good, whether it really should go into signal should be discussed on the mailing list (but seemed like the logical place for it). ... The best name for the module I could think of was spectral_analysis, maybe there's a better one? It allows to add similar methods later. " I would like to suggest the module name "lssa" for "Least-squares spectral analysis". So the full path would be scipy.signal.lssa. This has several advantages. 1. It is a short name without underscores (personal preference) 2. It is a category name that can comprise several similar algorithms as desired. 3. It is immediately obvious from this name that this is different than FFT and therefore people will not be confused looking for FFT functions in this sub-module. 4. The name corresponds to the Wikipedia entry for this category of algorithms :) (but on a serious note this may help for people that want to find more information, or for people browsing wikipedia that are looking for an implementation). Please let me know what you think. Kind regards, Pim Schellart

1 0

Re: [SciPy-Dev] Another Bug in KDTree
by Charles R. Schmidt 28 Jan '11

28 Jan '11

Thanks for confirming. I created a ticket, http://projects.scipy.org/scipy/ticket/1373 - Charlie. > From: Ralf Gommers <ralf.gommers(a)googlemail.com> > Subject: Re: [SciPy-Dev] Another Bug in KDTree > To: SciPy Developers List <scipy-dev(a)scipy.org> > Message-ID: > <AANLkTin+VsAH0u8eGdOStZavM+=cqP5BJkP9kz9Yy+vQ(a)mail.gmail.com> > Content-Type: text/plain; charset="iso-8859-1" > > On Wed, Jan 26, 2011 at 12:32 AM, Charles R. Schmidt <schmidtc(a)gmail.com>wrote: > >> Has anyone been able to verify this bug? or know if it's already >> documented somewhere? >> > > Same output on my system, looks like a bug. I don't think it's documented > anywhere, could you open a ticket for it? > > Thanks, > Ralf > >

1 0

Another Bug in KDTree
by Charles R. Schmidt 27 Jan '11

27 Jan '11

There appears to be a bug in KDTree.query_ball_point, when using integer points neighbor points that lie on the radius are not always returned. Eg, with a 4x4 grid >>> import scipy.spatial >>> points = [(0, 0), (0, 1), (0, 2), (0, 3), \ ... (1, 0), (1, 1), (1, 2), (1, 3), \ ... (2, 0), (2, 1), (2, 2), (2, 3), \ ... (3, 0), (3, 1), (3, 2), (3, 3)] >>> kd=scipy.spatial.KDTree(points) >>> kd.query_ball_point((2,0),1) [8, 9, 12] >>> points = [(0.0, 0.0), (0.0, 1.0), (0.0, 2.0), (0.0, 3.0), \ ... (1.0, 0.0), (1.0, 1.0), (1.0, 2.0), (1.0, 3.0), \ ... (2.0, 0.0), (2.0, 1.0), (2.0, 2.0), (2.0, 3.0), \ ... (3.0, 0.0), (3.0, 1.0), (3.0, 2.0), (3.0, 3.0)] >>> kd=scipy.spatial.KDTree(points) >>> kd.query_ball_point((2,0),1) [4, 8, 9, 12]

2 2