From OpenOpt

Jump to: navigation, search

gsubg is a free solver (license: BSD) for large-scale convex NLP/NSP based on Nikolay Zhurbenko generalized epsilon-subgradient method (see his recent publications for more details), written by Dmitrey. It is capable of getting solution with required fTol: | f - f* | < fTol, provided roundoff errors in its engine and involved QP subsolver are insufficient, QP subsolver yields accurate enough results and no other stop criteria triggers.

Currently the solver requires CVXOPT to be installed; it CVXOPT GPL license is inappropriate for you, you could use other QP solver (via changing gsubg parameter "qpsolver" to something different, e.g. "qlcp" or "nlp:scipy_lbfgsb"), however, it can essentially decrease performance for some difficult cases. Also, you could use cplex if you have the one installed (use parameter qpsolver='cplex')

gsubg still requires lots of improvements, especially for constraints (especially for nonlinear equalities), but some people had informed that for some their (mostly large-scale) problems they found it more useful than other solvers, like in the example below, thus you may be interested in it right now as well.

A couple of examples

We are sorry about benching with the puny solvers from scipy.optimize written by "Numerical recipes" or kind of; we would gladly compare it with large-scale nonsmooth solvers, but AFAIK currently there are no other ones in SciPy yet (large-scale ones that are capable of using derivatives), and the situation will be hardly changed in nearest future (I wonder how small and insufficient progress has been done with the module during last 4 years since I observe it, and most of changes were initialized and done by 3rd party contributors, not scipy core team; I hope situation with other scipy modules is better). Thus we decided to bench it with IPOPT 3.8 (with MUMPS). As for algencan, it cannot handle nonsmooth problems and also stops too far from optimum.

Let's consider the nonsmooth problem
\mathbf{ f1(y) = \sum_{i=1}^{N} i (y_i + 10\ sin\ i)^2 / (10^4 N)}

\mathbf{ f2(x) = \sum_{i=1}^{K-1} 2^i |x_i -100 x_\mathbf{i+1}| / K^5 }
Minimize f = f1 + f2 from start point x[i] = cos(i), y[i] = cos(i).
Optimal objective function value is zero. One could add |x_0| to have exact minimum in x = 0, experiment shows it doesn't essentially change convergence to optimal value for the solvers involved.

Of course, we could use OpenOpt pure Python language funcs, but here let's use FuncDesigner (for to omit writing derivatives)

FuncDesigner code:

from numpy import arange, array
from numpy.linalg import norm
from openopt import NSP, oosolver
from FuncDesigner import *
K = 20
N = 5000
x, y = oovars('x', 'y')
a = 10*sin(arange(1, N+1))
b = arange(1, N+1)
f1 = sum((y+a)**2 * b) / (10**4 *N) 
f2 = sum(abs(x[1:K]-100*x[0:K-1]) * array(2)**arange(K-1))/K**5
startPoint = {x:cos(arange(K)), y:cos(arange(N))}
f = f1 + f2 
print('start point: f1 = %e   f2 = %e' % (f1(startPoint), f2(startPoint)))
solvers = ['ipopt', 'gsubg', 'scipy_cg']
for i, solver in enumerate(solvers):
    p = NSP(f, startPoint, maxIter = 300, maxFunEvals=1e7)
    p.fEnough = 1.0e-1 # obj func value 0.1 will be enough for us
    p.fTol = 0.5e-1 # user-required tolerance for objective function, is used in gsubg (default 15*p.ftol, default ftol = 10^-6)
    r = p.minimize(solver, iprint=10, plot = 1)
    print('end point: f1 = %e   f2 = %e' % (f1(r.xf), f2(r.xf)))

The output for current OOSuite subversion rev. 787:

start point: f1 = 1.473508e+01   f2 = 9.667442e+00

solver: ipopt   problem: ns5020    type: NSP   goal: minimum
 iter    objFunVal   
    0  2.440e+01 
   10  1.542e+01 
   20  1.506e+01 
   30  1.506e+01 
   40  1.506e+01 
   50  1.506e+01 
   60  1.483e+01 
   70  1.481e+01 
   80  1.479e+01 
   90  1.475e+01 
  100  1.475e+01 
  110  1.474e+01 
  120  1.474e+01 
  130  1.474e+01 
  140  1.474e+01 
  150  1.474e+01 
  160  1.474e+01 
  170  1.474e+01 
  180  1.474e+01 
  190  1.474e+01 
  200  1.474e+01 
  210  1.474e+01 
  220  1.474e+01 
  230  9.329e+02 
  240  7.194e+01 
  250  1.398e+01 
  260  7.203e+03 
  270  1.100e+01 
  280  1.062e+01 
  290  1.060e+01 
  300  1.059e+01 
  301  1.059e+01 
istop: -7 (Max Iter has been reached)
Solver:   Time Elapsed = 39.18  CPU Time Elapsed = 36.83
Plotting: Time Elapsed = 32.05  CPU Time Elapsed = 26.11
objFunValue: 10.59303
end point: f1 = 7.010367e+00   f2 = 3.582663e+00

solver: gsubg   problem: ns5020    type: NSP   goal: minimum
 iter    objFunVal   
    0  2.440e+01 
   10  1.479e+01 
   20  9.155e+00 
   30  1.340e+00 
   40  6.095e-01 
   50  2.684e-01 
   60  2.597e-01 
   70  1.857e-01 
   80  1.425e-01 
   84  7.524e-02 
istop: 10 (fEnough has been reached)
Solver:   Time Elapsed = 24.89  CPU Time Elapsed = 24.37
Plotting: Time Elapsed = 15.92  CPU Time Elapsed = 15.37
objFunValue: 0.075239494
end point: f1 = 5.942323e-02   f2 = 1.581627e-02

solver: scipy_cg   problem: ns5020    type: NSP   goal: minimum
 iter    objFunVal   
    0  2.440e+01 
    3  1.768e+01 
istop: 1000 (|| F[k] - F[k-1] || < ftol)
Solver:   Time Elapsed = 1.04   CPU Time Elapsed = 1.04
Plotting: Time Elapsed = 1.56   CPU Time Elapsed = 1.48
objFunValue: 17.678681
end point: f1 = 1.473477e+01   f2 = 2.943912e+00

Let's solve the exampe with N = 150000, K = 25:

start point: f1 = 4.418662e+02   f2 = 1.132957e+02
solver: gsubg   problem: ns150025    type: NSP   goal: minimum
 iter    objFunVal   
    0  5.552e+02 
   10  4.419e+02 
   20  3.877e+02 
   30  1.709e+02 
   40  1.687e+02 
   50  1.679e+02 
   60  1.305e+02 
   70  7.615e+01 
   80  6.796e+01 
   90  6.649e+01 
  100  5.130e+01 
  110  4.738e+01 
  120  4.015e+01 
  130  2.179e+01 
  140  2.119e+01 
  150  2.114e+01 
  160  1.164e+01 
  170  4.463e+00 
Terminated (singular KKT matrix).
  180  4.428e+00 
  190  3.786e+00 
  200  3.763e+00 
  210  3.221e+00 
Terminated (singular KKT matrix).
Terminated (singular KKT matrix).
Terminated (singular KKT matrix).
Terminated (singular KKT matrix).
Terminated (singular KKT matrix).
Terminated (singular KKT matrix).
  220  2.760e+00 
Terminated (singular KKT matrix).
Terminated (singular KKT matrix).
  230  2.692e+00 
Terminated (singular KKT matrix).
Terminated (singular KKT matrix).
Terminated (singular KKT matrix).
Terminated (singular KKT matrix).
Terminated (singular KKT matrix).
Terminated (singular KKT matrix).
  240  1.657e+00 
  250  1.589e+00 
  260  1.359e+00 
  270  9.121e-01 
  280  8.681e-01 
  290  5.340e-01 
  300  5.241e-01 
istop: -7 (Max Iter has been reached)
Solver:   Time Elapsed = 2408.66        CPU Time Elapsed = 2375.79
objFunValue: 0.52409368
end point: f1 = 3.812894e-01   f2 = 1.428043e-01
Retrieved from ""
Personal tools
    Latest OOSuite 0.38

    from 2012-03-15

    Next release: