# gsubg

### From OpenOpt

**gsubg**

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

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