Algorithms

Solver

oars.oars.solve(n, data, resolvents, W=None, Z=None, parallel=False, **kwargs)[source]

Solve the problem with a given W and Z matrix

Parameters:

  • n (int) – the number of nodes

  • data (list) – list containing the problem data for each resolvent

  • resolvents (list) – list of uninitialized resolvent classes

  • W (ndarray) – W matrix (optional, default is fully connected)

  • Z (ndarray) – Z matrix (optional, default is fully connected)

  • parallel (bool) – whether to run the algorithm in parallel

  • kwargs –

    additional keyword arguments for the algorithm

    • itrs (int): the number of iterations

    • gamma (float): the consensus parameter

    • alpha (float): the resolvent scaling parameter

    • verbose (bool): whether to print verbose output

Returns:

x, results (ndarray, list) – tuple with the solution and a list of dictionaries with the results for each resolvent

Examples

>>> from oars.utils.proxs import quadprox
>>> from oars import solve
>>> from oars.matrices import getFull
>>> import numpy as np
>>> vals = np.array([0, 1, 3, 40])
>>> n = len(vals)
>>> proxs = [quadprox]*n
>>> Z, W = getFull(n)
>>> x, results = solve(n, vals, proxs, W, Z, itrs=1000, vartol=1e-6, gamma=1.0)
Converged in objective value, iteration 13
>>> x
10.999999999990674
>>> results
[{'x': 10.999999999906539, 'v': 22.00000000003744}, {'x': 11.000000000103075, 'v': 13.66666666663539}, {'x': 10.999999999962412, 'v': 4.333333333327117}, {'x': 10.999999999990674, 'v': -40.0}]

MT Solve

oars.oars.solveMT(n, data, resolvents, **kwargs)[source]

Solve the problem with the Malitsky-Tam W and Z matrices

Parameters:

  • n (int) – the number of nodes

  • data (list) – list of dictionaries containing the problem data

  • resolvents (list) – list of uninitialized resolvent classes

  • kwargs –

    additional keyword arguments for the algorithm

    • itrs (int): the number of iterations

    • gamma (float): the consensus parameter

    • alpha (float): the resolvent scaling parameter

    • verbose (bool): whether to print verbose output

Returns:

x, results (ndarray, list) – tuple with the solution and a list of dictionaries with the results for each resolvent

Examples

>>> from oars.utils.proxs import quadprox
>>> from oars import solveMT
>>> import numpy as np
>>> vals = np.array([0, 1, 3, 40])
>>> n = len(vals)
>>> proxs = [quadprox]*n
>>> x, results = solveMT(n, vals, proxs, itrs=1000, vartol=1e-6, gamma=1.0)
Converged in objective value, iteration 69
>>> x
10.999999857565648
>>> results
[{'x': 10.999999565156383, 'v': 21.99999932717702}, {'x': 10.999999762020636, 'v': 9.99999996819179}, {'x': 10.99999996819179, 'v': 8.00000013489378}, {'x': 11.000000134893778, 'v': -39.999999430262605}]

Serial Algorithm

oars.algorithms.serial.serialAlgorithm(n, data, resolvents, W, Z, warmstartprimal=None, warmstartdual=None, itrs=1001, gamma=0.9, alpha=1.0, vartol=None, objtol=None, objective=None, checkperiod=10, verbose=False, debug=False)[source]

Run the frugal resolvent splitting algorithm defined by Z and W in serial

Parameters:

  • n (int) – the number of resolvents

  • data (list) – list containing the problem data for each resolvent

  • resolvents (list) – list of \(n\) resolvent classes

  • W (ndarray) – size (n, n) ndarray for the \(W\) matrix

  • Z (ndarray) – size (n, n) ndarray for the \(Z\) matrix

  • warmstartprimal (ndarray, optional) – resolvent.shape ndarray for \(x\) in v^0

  • warmstartdual (list, optional) – is a list of n ndarrays for \(u\) which sums to 0 in v^0

  • itrs (int, optional) – the number of iterations

  • gamma (float, optional) – parameter in \(v^{k+1} = v^k - \gamma W x^k\)

  • alpha (float, optional) – the resolvent step size in \(x^{k+1} = J_{\alpha F^i}(y^k)\)

  • vartol (float, optional) – is the variable tolerance

  • objtol (float, optional) – is the objective tolerance

  • objective (function, optional) – the objective function

  • checkperiod (int, optional) – the period to check for convergence

  • verbose (bool, optional) – True for verbose output

Returns:

  • x (ndarray) – the solution

  • results (list) – list of dictionaries with the results for each resolvent

Examples

>>> from oars.utils.proxs import quadprox
>>> from oars.algorithms import serialAlgorithm
>>> from oars.matrices import getFull
>>> import numpy as np
>>> vals = np.array([0, 1, 3, 40])
>>> n = len(vals)
>>> proxs = [quadprox]*n
>>> Z, W = getFull(n)
>>> x, results = serialAlgorithm(n, vals, proxs, W, Z, itrs=1000, vartol=1e-6, gamma=1.0)
Converged in objective value, iteration 13
>>> x
10.999999999990674
>>> results
[{'x': 10.999999999906539, 'v': 22.00000000003744}, {'x': 11.000000000103075, 'v': 13.66666666663539}, {'x': 10.999999999962412, 'v': 4.333333333327117}, {'x': 10.999999999990674, 'v': -40.0}]

Parallel Algorithm

oars.algorithms.parallel.parallelAlgorithm(n, data, resolvents, W, Z, warmstartprimal=None, warmstartdual=None, itrs=1001, gamma=0.9, alpha=1.0, vartol=None, checkperiod=1, verbose=False)[source]

Run the frugal resolvent splitting algorithm for W and Z matrices in parallel

Parameters:

  • n (int) – the number of resolvents

  • data (list) – list containing the problem data for each resolvent

  • resolvents (list) – list of \(n\) resolvent functions

  • W (ndarray) – size (n, n) ndarray for the \(W\) matrix

  • Z (ndarray) – size (n, n) ndarray for the \(Z\) matrix

  • warmstartprimal (ndarray, optional) – resolvent.shape ndarray for \(x\) in v^0

  • warmstartdual (list, optional) – is a list of n ndarrays for \(u\) which sums to 0 in v^0

  • itrs (int, optional) – the number of iterations

  • gamma (float, optional) – parameter in \(v^{k+1} = v^k - \gamma W x^k\)

  • alpha (float, optional) – the resolvent step size in \(x^{k+1} = J_{\alpha F^i}(y^k)\)

  • vartol (float, optional) – is the variable tolerance

  • earlyterm (int, optional) – the number of variables that must agree to terminate early and solve explicitly for the remaining variables

  • detectcycle (int, optional) – the number of iterations to check for cycling

  • verbose (bool, optional) – True for verbose output

Returns:

  • xbar (ndarray) – the solution

  • results (list) – list of dictionaries with the results for each node

Distributed Algorithm

oars.algorithms.distributed.distributedAlgorithm(n, data, resolvents, W, Z, warmstartprimal=None, warmstartdual=None, itrs=1001, gamma=0.9, alpha=1.0, vartol=None, verbose=False)[source]

Distributed algorithm for frugal resolvent splitting

Parameters:

  • n (int) – the number of resolvents

  • resolvents (list) – list of resolvent classes

  • W (ndarray) – size (n, n) ndarray for the W matrix

  • Z (ndarray) – size (n, n) ndarray for the Z matrix

  • data (list) – list containing the problem data for each resolvent

  • warmstartprimal (ndarray, optional) – resolvent.shape ndarray for x in v^0

  • warmstartdual (list, optional) – is a list of n ndarrays for u which sums to 0 in v^0

  • itrs (int, optional) – the number of iterations

  • gamma (float, optional) – step size for the consensus step

  • alpha (float, optional) – the resolvent step size

  • vartol (float, optional) – is the variable tolerance

  • objtol (float, optional) – is the objective tolerance

  • earlyterm (int, optional) – the number of iterations to run before checking for termination

  • detectcycle (int, optional) – the number of iterations to check for a cycle

  • objective (function, optional) – the objective function

  • verbose (bool, optional) – True for verbose output

Returns:

  • x (ndarray) – the solution

  • results (list) – list of dictionaries with the results for each resolvent

Distributed Block Algorithm

oars.algorithms.distributed_block.distributed_block_solve(n, data, resolvents, warmstartprimal, warmstartdual=None, w_own=0, w_other=None, itrs=1001, gamma=0.9, alpha=1.0, vartol=1e-08, logging=False, verbose=False)[source]

Solve the 2-Block resolvent splitting algorithm in parallel using MPI

Parameters:

  • n (int) – Number of resolvents

  • data (list) – List of data for each resolvent

  • resolvents (list) – List of resolvents

  • warmstartprimal (ndarray) – Warm start for the primal variables

  • warmstartdual (ndarray) – Warm start for the dual variables

  • w_own (float) – Weight for the own block

  • w_other (float) – Weight for the other block

  • itrs (int) – Number of iterations

  • gamma (float) – Step size

  • alpha (float) – Proximal parameter

  • vartol (float) – Tolerance for convergence

  • verbose (bool) – Print verbose output

Returns:

  • x_bar (ndarray) – The average of the primal variables

  • results (list) – List of dictionaries with the results for each resolvent

Examples

>>> mpiexec -n 1 python distributed_block_example.py
2024-08-27 11:39:50.517313 Worker 1 started
2024-08-27 11:39:50.517313 Worker 0 started
2024-08-27 11:39:50.517313 Iteration 0 time 0.0 Delta v 45.304966615151585 Sum diff 16.93553955443995 Sum zero diff 21.500000000000004
Converged at iteration 10 Delta v 4.530496464705242e-09 Sum diff 1.693553905459803e-09 Sum zero diff 2.1499886315723415e-09
2024-08-27 11:39:50.532951 Worker 0 finished, time 0.01563882827758789
10.999999999462496
[[{'first_x': 10.999999998899996, 'second_x': 10.999999999074998, 'first_v0': 21.999999999779995, 'second_v0': -2.999999999970001}], [{'first_x': 10.999999998949997, 'second_x': 11.000000000924997, 'first_v0': 20.999999999789992, 'second_v0': -39.9999999996}]]