Home Install Documentation Problems Tree Applications Forum

Increase your income
via IT outsourcing!
Ukrainian HI-TECH Initiative Ukrainian HI-TECH Initiative

gsubg

From OpenOpt

Jump to: navigation, search
gsubg

Preface

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 with some changes 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')

We haven't implemented some essential gsubg ideas yet, 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.


Parameters

(since v. 0.42)

NameDefault valueDescription
maxVectors 100 gsubg will store at most maxVectors vectors (2*maxVectors for constrained problems), each one of size nVariables (unknouns), for its inner purposes. Most of medium-scaled solvers, such as ralg or amsg2p, store matrix of size nVariables * nVariables instead.
maxShoots 15 used as one of stop criteria. You can get r.istop value 17 ("Max linesearch directions number has been exceeded, probably solution has been obtained"; then, if guaranteed accuracy is highly required, you could try increasing this parameter to bigger value to achieve r.istop = 16 (optimal solution wrt required fTol has been obtained)
sigma 0.001 the less the value is, the faster solver will work (however, usually difference is insufficient); however, it increases chances that QP solver for QP subproblem will fail.
fTol (prob parameter) None required accuracy: abs(f - f*) < fTol
qpsolver'cvxopt_qp' solver for QP subproblem. You could try using converter, e.g. "nlp:scipy_lbfgsb", but usually QP solvers work essentially better.


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 "http://openopt.org/gsubg"
Personal tools
Latest OOSuite 0.53

from 2014-03-15