Proximal methods for constrained optimization
Project description
Proximal Minimization
The methods in this package provide solvers for constrained optimization problems. All of them use proximal operators to deal with nonsmooth penalty functions.
The algorithms:
 Proximal Gradient Method (PGM): forwardbackward splitting with a single smooth function with a Lipschitzcontinuous gradient and a single (nonsmooth) penalty function. Includes multiblock optimization and Nesterov acceleration.
 Adam and derivatives (AdamX, AMSGrad, PAdam): forwardbackward splitting with adaptive gradient steps for single and multiblock optimization.
 Alternating Direction Method of Multipliers (ADMM): RachfordDouglas splitting for two potentially nonsmooth functions. We use its linearized form to solve for additional linear mappings in the penalty functions.
 Simultaneous Direction Method of Multipliers (SDMM): Extension of linearized ADMM for several penalty functions.
 BlockSimultaneous Direction Method of Multipliers (bSDMM): Extension of SDMM to work with objective functions that are convex in several arguments. It's a proximal version of Block coordinate descent methods.
Twoblock PGM or bSDMM is used as backend solvers for Nonnegative Matrix Factorization (NMF). As the algorithms allow any proxable function as constraint on each of the matrix factors, we prefer the term Constrained Matrix Factorization.
Details can be found in the paper "BlockSimultaneous Direction Method of Multipliers  A proximal primaldual splitting algorithm for nonconvex problems with multiple constraints" by Fred Moolekamp and Peter Melchior.
We ask that any published work that utilizes this package cites:
@ARTICLE{proxmin,
author="{Moolekamp}, Fred and {Melchior}, Peter",
title="Blocksimultaneous direction method of multipliers: a proximal primaldual splitting algorithm for nonconvex problems with multiple constraints",
journal="Optimization and Engineering",
year="2018",
month="Dec",
volume=19,
issue=4,
pages={871885},
doi="10.1007/s110810189380y",
url="https://doi.org/10.1007/s110810189380y"
archivePrefix="arXiv",
eprint={1708.09066},
primaryClass="math.OC"
}
Also, let us know (e.g. @peter_melchior), we're curious.
Installation and Dependencies
pip install proxmin
For the latest development version, clone this repository and execute python setup.py install
.
The code works on python>2.7 and requires numpy and scipy. It is fully compatible with gradient computation by autograd
.
Approach
The gradientbased methods PGM and Adam expect two callback function: one to compute the gradients, the other to compute step sizes. In the former case, the step sizes are bound between 0 and 2/L, where L is the Lipschitz constant of the gradient.
The penalty functions are given as proximal mappings: X < prox(X, step)
.
Many proximal operators can be constructed analytically, see e.g. Parikh & Boyd (2014). We provide a number of common ones in proxmin.operators
. An important class of constraints are indicator functions of convex sets, for which the proximal operator, given some point X, returns the closest point to X in the Euclidean norm that is in the set.
Example: find the minimum of a shifted parabola on the unit circle in 2D
import numpy as np import proxmin dX = np.array([1.,0.5]) radius = 1 def f(X): """Shifted parabola""" return np.sum((X  dX)**2, axis=1) def grad_f(X): return 2*(X  dX) def step_f(X, it=0): L = 2. # Lipschitz constant of grad f return 1 / L def prox_circle(X, step): """Projection onto circle""" center = np.array([0,0]) dX = X  center # exclude everything other than perimeter of circle phi = np.arctan2(dX[1], dX[0]) return center + radius*np.array([np.cos(phi), np.sin(phi)]) X = np.array([1.,1.]) # or whereever converged, grad, step = proxmin.pgm(X, grad_f, step_f, prox=prox_circle)
Since the objective function is smooth and there is only one constraint, one can simply perform a sequence of forwardbackward steps: a step in gradient direction, followed by a projection onto the constraint subset. That is, in essence, the proximal gradient method.
If both functions are not smooth, one can use ADMM. It therefore operates on two proxed functions. Unlike PGM, feasibility is only achieved at the end of the optimization and only within some error tolerance.
Continuing the example above, the smooth function gets turned into a proxed function by performing the gradient step internally and returning the updated position:
def prox_gradf(X, step): """Proximal gradient step""" return Xstep*grad_f(X) converged = proxmin.admm(X, prox_gradf, step_f, prox_g=prox_circle, e_rel=1e3, e_abs=1e3)
Constrained matrix factorization (CMF)
Matrix factorization seeks to approximate a target matrix Y
as a product of np.dot(A,S)
. If those constraints are only nonnegativity, the method is known as NMF.
We have extended the capabilities by allowing for an arbitrary number of constraints to be enforced on either matrix factor:
# PGM approach for each factor prox_A = ... # a single constraint on A, solved by projection prox_S = ... # a single constraint on S, solved by projection A0, S0 = ... # initialization proxmin.nmf.nmf(Y, A0, S0, prox_A=prox_A, prox_S=prox_S) # same with AdaProxAMSGrad proxmin.nmf.nmf(Y, A0, S0, prox_A=prox_A, prox_S=prox_S, algorithm=proxmin.algorithms.adaprox, scheme="amsgrad") # for multiple constraints, solved by ADMMstyle split proxs_g = [[...], # list of proxs for A [...]] # list of proxs for S A, S = proxmin.nmf.nmf(Y, A0, S0, algorithm=proxmin.algorithms.bsdmm, proxs_g=proxs_g) # or a combination A, S = proxmin.nmf.nmf(Y, A0, S0, algorithm=proxmin.algorithms.bsdmm, prox_A=prox_A, prox_S=prox_S, proxs_g=proxs_g)
Project details
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Filename, size  File type  Python version  Upload date  Hashes 

Filename, size proxmin0.6.10py2.py3noneany.whl (18.2 kB)  File type Wheel  Python version py2.py3  Upload date  Hashes View 
Filename, size proxmin0.6.10.tar.gz (18.4 kB)  File type Source  Python version None  Upload date  Hashes View 
Hashes for proxmin0.6.10py2.py3noneany.whl
Algorithm  Hash digest  

SHA256  d9f510a73943f94a87f1ed06c79cd22f24f6290780f1e35b024990f3ec8c059f 

MD5  0bd55054828952a965df6465acfcb01d 

BLAKE2256  55803b2198e9120b537532a4c12374857d3e6765960f50813c7ecb15545bf705 