# gsubg

### From OpenOpt

**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)

Name | Default value | Description |

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

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