Hello all. I am a relatively new user of python and scipy and I have been trying out scipy's optimization facilities. I am using scipy version 0.6.0, as distributed with Ubuntu 8.04. My exploration has centered around the minimization of x*x*y, subject to the equality constraint 2*x*x+y*y=3. In my experience, this problem is solved by introducing a Lagrange multiplier and minimizing the Lagrangian: L = x*x*y - lambda * ( 2*x*x+y*y-3 ) I have had no problem finding the desired solution via Newton-Raphson using the function and its first and second derivatives: import scipy.optimize as opt import numpy import numpy.linalg as l def f(r): x,y,lam=r return x*x*y -lam*(2*x*x+y*y-3) def g(r): x,y,lam=r return numpy.array([2*x*y-4*lam*x, x*x-2*lam*y, -(2*x*x+y*y-3)]) def h(r): x,y,lam=r return numpy.mat([[2.*y-4.*lam, 2.*x, -4.*x],[2.*x,-2.*lam,-2.*y],[-4.*x,-2.*y,0.]]) def NR(f, g, h, x0, tol=1e-5, maxit=100): "Find a local extremum of f (a root of g) using Newton-Raphson" x1 = numpy.asarray(x0) f1 = f(x1) for i in range(0,maxit): dx = l.solve(h(x1),g(x1)) ldx = numpy.sqrt(numpy.dot(dx,dx)) x2 = x1-dx f2 = f(x2) if(ldx < tol): # x is close enough df = numpy.abs(f1-f2) if(df < tol): # f is close enough return x2, f2, df, ldx, i x1=x2 f1=f2 return x2, f2, df, ldx, i print NR(f,g,h,[-2.,2.,3.],tol=1e-10) My Newton-Raphson iteration converges in 5 iterations, but I have had no success using any of the functions in scipy.optimize, for example: print opt.fmin_bfgs(f=f, x0=[-2.,2.,3.], fprime=g) print opt.fmin_ncg(f=f, x0=[-2.,2.,3.], fprime=g, fhess=h) neither of which converges. I am beginning to suspect some fundamental misunderstanding on my part. Could someone throw me a bone? Best regards Gísli
On Fri, 21 Nov 2008 12:10:41 +0000 "Gísli Óttarsson" <gislio@gmail.com> wrote:
Hello all.
I am a relatively new user of python and scipy and I have been trying out scipy's optimization facilities. I am using scipy version 0.6.0, as distributed with Ubuntu 8.04.
My exploration has centered around the minimization of x*x*y, subject to the equality constraint 2*x*x+y*y=3. In my experience, this problem is solved by introducing a Lagrange multiplier and minimizing the Lagrangian:
L = x*x*y - lambda * ( 2*x*x+y*y-3 )
I have had no problem finding the desired solution via Newton-Raphson using the function and its first and second derivatives:
import scipy.optimize as opt import numpy import numpy.linalg as l
def f(r): x,y,lam=r return x*x*y -lam*(2*x*x+y*y-3)
def g(r): x,y,lam=r return numpy.array([2*x*y-4*lam*x, x*x-2*lam*y, -(2*x*x+y*y-3)])
def h(r): x,y,lam=r return numpy.mat([[2.*y-4.*lam, 2.*x, -4.*x],[2.*x,-2.*lam,-2.*y],[-4.*x,-2.*y,0.]])
def NR(f, g, h, x0, tol=1e-5, maxit=100): "Find a local extremum of f (a root of g) using Newton-Raphson" x1 = numpy.asarray(x0) f1 = f(x1) for i in range(0,maxit): dx = l.solve(h(x1),g(x1)) ldx = numpy.sqrt(numpy.dot(dx,dx)) x2 = x1-dx f2 = f(x2) if(ldx < tol): # x is close enough df = numpy.abs(f1-f2) if(df < tol): # f is close enough return x2, f2, df, ldx, i x1=x2 f1=f2 return x2, f2, df, ldx, i
print NR(f,g,h,[-2.,2.,3.],tol=1e-10)
My Newton-Raphson iteration converges in 5 iterations, but I have had no success using any of the functions in scipy.optimize, for example:
print opt.fmin_bfgs(f=f, x0=[-2.,2.,3.], fprime=g) print opt.fmin_ncg(f=f, x0=[-2.,2.,3.], fprime=g, fhess=h)
neither of which converges.
I am beginning to suspect some fundamental misunderstanding on my part. Could someone throw me a bone?
Best regards
Gísli _______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
Please find enclosed an untested implementation using openopt. Cheers, Nils
Thanks Nils. I will install and investigate openopt. This looks like a very exciting development. Others: I would still like to understand why I am not being successful with scipy.optimize. Was I wrong to think that NCG could handle my constraint, even when I am providing the Hessian matrix? Thanks Gísli On Fri, Nov 21, 2008 at 1:16 PM, Nils Wagner <nwagner@iam.uni-stuttgart.de>wrote:
On Fri, 21 Nov 2008 12:10:41 +0000 "Gísli Óttarsson" <gislio@gmail.com> wrote:
Hello all.
I am a relatively new user of python and scipy and I have been trying out scipy's optimization facilities. I am using scipy version 0.6.0, as distributed with Ubuntu 8.04.
My exploration has centered around the minimization of x*x*y, subject to the equality constraint 2*x*x+y*y=3. In my experience, this problem is solved by introducing a Lagrange multiplier and minimizing the Lagrangian:
L = x*x*y - lambda * ( 2*x*x+y*y-3 )
I have had no problem finding the desired solution via Newton-Raphson using the function and its first and second derivatives:
import scipy.optimize as opt import numpy import numpy.linalg as l
def f(r): x,y,lam=r return x*x*y -lam*(2*x*x+y*y-3)
def g(r): x,y,lam=r return numpy.array([2*x*y-4*lam*x, x*x-2*lam*y, -(2*x*x+y*y-3)])
def h(r): x,y,lam=r return numpy.mat([[2.*y-4.*lam, 2.*x, -4.*x],[2.*x,-2.*lam,-2.*y],[-4.*x,-2.*y,0.]])
def NR(f, g, h, x0, tol=1e-5, maxit=100): "Find a local extremum of f (a root of g) using Newton-Raphson" x1 = numpy.asarray(x0) f1 = f(x1) for i in range(0,maxit): dx = l.solve(h(x1),g(x1)) ldx = numpy.sqrt(numpy.dot(dx,dx)) x2 = x1-dx f2 = f(x2) if(ldx < tol): # x is close enough df = numpy.abs(f1-f2) if(df < tol): # f is close enough return x2, f2, df, ldx, i x1=x2 f1=f2 return x2, f2, df, ldx, i
print NR(f,g,h,[-2.,2.,3.],tol=1e-10)
My Newton-Raphson iteration converges in 5 iterations, but I have had no success using any of the functions in scipy.optimize, for example:
print opt.fmin_bfgs(f=f, x0=[-2.,2.,3.], fprime=g) print opt.fmin_ncg(f=f, x0=[-2.,2.,3.], fprime=g, fhess=h)
neither of which converges.
I am beginning to suspect some fundamental misunderstanding on my part. Could someone throw me a bone?
Best regards
Gísli _______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
Please find enclosed an untested implementation using openopt.
Cheers, Nils
_______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
Both fmin_bfgs and fmin_ncg expect objective function to be convex, while y*x^2 is not. I have no time & willing to dig more deeply for the solvers involved, problem and code mentione. D. Gísli Óttarsson wrote:
Thanks Nils. I will install and investigate openopt. This looks like a very exciting development.
Others: I would still like to understand why I am not being successful with scipy.optimize. Was I wrong to think that NCG could handle my constraint, even when I am providing the Hessian matrix?
Thanks
Gísli
On Fri, Nov 21, 2008 at 1:16 PM, Nils Wagner <nwagner@iam.uni-stuttgart.de <mailto:nwagner@iam.uni-stuttgart.de>> wrote:
On Fri, 21 Nov 2008 12:10:41 +0000 "Gísli Óttarsson" <gislio@gmail.com <mailto:gislio@gmail.com>> wrote:
Hello all.
I am a relatively new user of python and scipy and I have been trying out scipy's optimization facilities. I am using scipy version 0.6.0, as distributed with Ubuntu 8.04.
My exploration has centered around the minimization of x*x*y, subject to the equality constraint 2*x*x+y*y=3. In my experience, this problem is solved by introducing a Lagrange multiplier and minimizing the Lagrangian:
L = x*x*y - lambda * ( 2*x*x+y*y-3 )
I have had no problem finding the desired solution via Newton-Raphson using the function and its first and second derivatives:
import scipy.optimize as opt import numpy import numpy.linalg as l
def f(r): x,y,lam=r return x*x*y -lam*(2*x*x+y*y-3)
def g(r): x,y,lam=r return numpy.array([2*x*y-4*lam*x, x*x-2*lam*y, -(2*x*x+y*y-3)])
def h(r): x,y,lam=r return numpy.mat([[2.*y-4.*lam, 2.*x, -4.*x],[2.*x,-2.*lam,-2.*y],[-4.*x,-2.*y,0.]])
def NR(f, g, h, x0, tol=1e-5, maxit=100): "Find a local extremum of f (a root of g) using Newton-Raphson" x1 = numpy.asarray(x0) f1 = f(x1) for i in range(0,maxit): dx = l.solve(h(x1),g(x1)) ldx = numpy.sqrt(numpy.dot(dx,dx)) x2 = x1-dx f2 = f(x2) if(ldx < tol): # x is close enough df = numpy.abs(f1-f2) if(df < tol): # f is close enough return x2, f2, df, ldx, i x1=x2 f1=f2 return x2, f2, df, ldx, i
print NR(f,g,h,[-2.,2.,3.],tol=1e-10)
My Newton-Raphson iteration converges in 5 iterations, but I have had no success using any of the functions in scipy.optimize, for example:
print opt.fmin_bfgs(f=f, x0=[-2.,2.,3.], fprime=g) print opt.fmin_ncg(f=f, x0=[-2.,2.,3.], fprime=g, fhess=h)
neither of which converges.
I am beginning to suspect some fundamental misunderstanding on my part. Could someone throw me a bone?
Best regards
Gísli _______________________________________________ SciPy-user mailing list SciPy-user@scipy.org <mailto:SciPy-user@scipy.org> http://projects.scipy.org/mailman/listinfo/scipy-user
Please find enclosed an untested implementation using openopt.
Cheers, Nils
_______________________________________________ SciPy-user mailing list SciPy-user@scipy.org <mailto:SciPy-user@scipy.org> http://projects.scipy.org/mailman/listinfo/scipy-user
------------------------------------------------------------------------
_______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
Nuff said. Thanks for setting me straight. Gísli On Fri, Nov 21, 2008 at 2:19 PM, dmitrey <dmitrey.kroshko@scipy.org> wrote:
Both fmin_bfgs and fmin_ncg expect objective function to be convex, while y*x^2 is not. I have no time & willing to dig more deeply for the solvers involved, problem and code mentione. D.
Gísli Óttarsson wrote:
Thanks Nils. I will install and investigate openopt. This looks like a very exciting development.
Others: I would still like to understand why I am not being successful with scipy.optimize. Was I wrong to think that NCG could handle my constraint, even when I am providing the Hessian matrix?
Thanks
Gísli
On Fri, Nov 21, 2008 at 1:16 PM, Nils Wagner <nwagner@iam.uni-stuttgart.de <mailto:nwagner@iam.uni-stuttgart.de>> wrote:
On Fri, 21 Nov 2008 12:10:41 +0000 "Gísli Óttarsson" <gislio@gmail.com <mailto:gislio@gmail.com>>
wrote:
Hello all.
I am a relatively new user of python and scipy and I have been trying out scipy's optimization facilities. I am using scipy version 0.6.0, as distributed with Ubuntu 8.04.
My exploration has centered around the minimization of x*x*y, subject to the equality constraint 2*x*x+y*y=3. In my experience, this problem is solved by introducing a Lagrange multiplier and minimizing the Lagrangian:
L = x*x*y - lambda * ( 2*x*x+y*y-3 )
I have had no problem finding the desired solution via Newton-Raphson using the function and its first and second derivatives:
import scipy.optimize as opt import numpy import numpy.linalg as l
def f(r): x,y,lam=r return x*x*y -lam*(2*x*x+y*y-3)
def g(r): x,y,lam=r return numpy.array([2*x*y-4*lam*x, x*x-2*lam*y,
-(2*x*x+y*y-3)])
def h(r): x,y,lam=r return numpy.mat([[2.*y-4.*lam, 2.*x, -4.*x],[2.*x,-2.*lam,-2.*y],[-4.*x,-2.*y,0.]])
def NR(f, g, h, x0, tol=1e-5, maxit=100): "Find a local extremum of f (a root of g) using Newton-Raphson" x1 = numpy.asarray(x0) f1 = f(x1) for i in range(0,maxit): dx = l.solve(h(x1),g(x1)) ldx = numpy.sqrt(numpy.dot(dx,dx)) x2 = x1-dx f2 = f(x2) if(ldx < tol): # x is close enough df = numpy.abs(f1-f2) if(df < tol): # f is close enough return x2, f2, df, ldx, i x1=x2 f1=f2 return x2, f2, df, ldx, i
print NR(f,g,h,[-2.,2.,3.],tol=1e-10)
My Newton-Raphson iteration converges in 5 iterations, but I have had no success using any of the functions in scipy.optimize, for example:
print opt.fmin_bfgs(f=f, x0=[-2.,2.,3.], fprime=g) print opt.fmin_ncg(f=f, x0=[-2.,2.,3.], fprime=g, fhess=h)
neither of which converges.
I am beginning to suspect some fundamental misunderstanding on my part. Could someone throw me a bone?
Best regards
Gísli _______________________________________________ SciPy-user mailing list SciPy-user@scipy.org <mailto:SciPy-user@scipy.org> http://projects.scipy.org/mailman/listinfo/scipy-user
Please find enclosed an untested implementation using openopt.
Cheers, Nils
_______________________________________________ SciPy-user mailing list SciPy-user@scipy.org <mailto:SciPy-user@scipy.org> http://projects.scipy.org/mailman/listinfo/scipy-user
------------------------------------------------------------------------
_______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
_______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
If I understand what you sent, you are trying to turn a constrained minimization into an unconstrained minimization by introducing a Lagrange multiplier. This does not work: the first order conditions associated with L characterize a saddle. However in your case you can simply solve 2*x*x+y*y=3 for y (only the bottom half of the ellipse is relevant) and substitute this into x*x*y to get an unconstrained optimization problem in x. Naturally it will not have a unique solution, since x occurs only as x*x. However the resulting function is convex local to the minima, so you should then be able to use scipy.optimize. Cheers, Alan Isaac
participants (4)
-
Alan G Isaac -
dmitrey -
Gísli Óttarsson -
Nils Wagner