A set of first-order methods for solving

when

• f(x) is convex, but not necessarily differentiable
• the set is convex

The package is pip-installable:

>>> pip install nsopy

Optional: tests are in ./nsopy/tests/ and can be run with the py.test test runner.

We want to minimize a non-differentiable function obtained by taking the max over a set of functions. The feasible set considered is the set of non-negative real numbers, i.e., for which the projection operation is straightforward.

It is straightforward to see that the optimum is at x* = 2.25; we can solve this optimization problem numerically as follows:

import numpy as np

def oracle(x_k):
    # evaluation of the f_i components at x_k
    fi_x_k = [-2*x_k + 2,  -1.0/3*x_k + 1,  x_k - 2]

    f_x_k = max(fi_x_k)  # function value at x_k

    diff_fi = [-2, -1.0/3.0, 1]  # gradients of the components
    max_i = fi_x_k.index(f_x_k)
    # subgradient at x_k is the gradient of the active function component; cast as (1x1 dimensional) np.array
    diff_f_xk = np.array([diff_fi[max_i], ])  

    return 0, f_x_k, diff_f_xk

def projection_function(x_k):
    if x_k is 0:
        return np.array([0,])
    else:
        return np.maximum(x_k, 0)

Instantiation of method and logger, solve and print

from nsopy.methods.subgradient import SubgradientMethod
from nsopy.loggers import GenericMethodLogger

method = SubgradientMethod(oracle, projection_function, stepsize_0=0.1, stepsize_rule='constant', sense='min')
logger = GenericMethodLogger(method)

for iteration in range(200):
    method.step()

Result:

>>> print(logger.x_k_iterates[-5:])

[2.1999999999999904, 2.216666666666657, 2.2333333333333236, 2.2499999999999902, 2.266666666666657]

• Standard Subgradient Method

SubgradientMethod(oracle, projection_function, dimension=0, stepsize_0=1.0, stepsize_rule='1/k', sense='min')

Stepsize rules valiable: stepsize_rule: ['constant', '1/k', '1/sqrt(k)']

• Quasi-Monotone Methods

Implementation of double simple averaging, and triple averaging methods from Nesterov's paper on quasi-monotone methods.

SGMDoubleSimpleAveraging(oracle, projection_function, dimension=0, gamma=1.0, sense='min')
SGMTripleAveraging(oracle, projection_function, dimension=0, variant=1, gamma=1.0, sense='min'):

Variants of SGMTripleAveraging available: variant: [1, 2]

• Universal Gradient Methods

Implementation of Nesterov's universal gradient methods, primal, dual and fast versions.

UniversalPGM(oracle, projection_function, dimension=0, epsilon=1.0, averaging=False, sense='min')
UniversalDGM(oracle, projection_function, dimension=0, epsilon=1.0, averaging=False, sense='min'):        
UniversalFGM(oracle, projection_function, dimension=0, epsilon=1.0, averaging=False, sense='min'):

• Cutting Planes Method

Warning: this method requires gurobipy; if you are an academic, you can get a free license here.

CuttingPlanesMethod(oracle, projection_function, dimension=0, epsilon=0.01, search_box_min=-10, search_box_max=10, sense='min')

The parameter epsilon is the absolute required suboptimality level |f_k - f*| used as a stopping criterion. Note that a search box needs to be specified.

• Bundle Method

Warning: this method requires gurobipy; if you are an academic, you can get a free license here.

Implementation of a basic variant of the bundle method.

BundleMethod(oracle, projection_function, dimension=0, epsilon=0.01, mu=0.5, sense='min'):

• Methods have to either be instantiated with the appropriate dimension argument, or implement a special case for 0. The basic usage example above illustrates an oracle implementing such a special case. For this example, alternatively one could have instantiated the solution method with dimension = 1.

• The first-order oracle must also provide a projection function; here is a list of cases for which the projection operation is computationally inexpensive.

• Currently, all methods are implemented in Python. Numerical performance is not optimized, but they may be still useful for quick comparisons or for applications in which the main computational burden is in evaluating the first order oracle.

• See analytical example for a more challenging optimization model.

• How to get approximate solutions to structured MILPs using Lagrangian duality.

We can also use these methods to decompose stochastic multistage mixed integer programs (preview), which in turn allows the computation of approximate solutions to these models on distributed environments (e.g., on cloud infrastructure).

Contributions and pull requests are very much welcome. The TODO contains a number of tasks whose completion would be helpful.

@article{Vujanic2018,
	title={Dual Decomposition of Stochastic Integer Programs: New Results and Experimental Comparison of Solution Methods},
	author={Vujanic, Robin and Esfahani, Peyman Mohajerin},
	journal={TO BE COMPLETED},
	volume={TO BE COMPLETED},
	number={TO BE COMPLETED},
	pages={TO BE COMPLETED},
	year={2018},
	publisher={TO BE COMPLETED}
}