pymanopt.

core.

problem

Module containing pymanopt problem class. Use this to build a problem object to feed to one of the solvers.

class pymanopt.core.problem.Problem(manifold, cost, egrad=None, ehess=None, grad=None, hess=None, arg=None, precon=None, verbosity=2)

Bases: object

Problem class for setting up a problem to feed to one of the pymanopt solvers.

Attributes:
  • manifold

    Manifold to optimize over.

  • cost

    A callable which takes an element of manifold and returns a real number, or a symbolic Theano or TensorFlow expression. In case of a symbolic expression, the gradient (and if necessary the Hessian) are computed automatically if they are not explicitly given. We recommend you take this approach rather than calculating gradients and Hessians by hand.

  • grad

    grad(x) is the gradient of cost at x. This must take an element X of manifold and return an element of the tangent space to manifold at X. This is usually computed automatically and doesn’t need to be set by the user.

  • hess

    hess(x, a) is the directional derivative of grad at x, in direction a. It should return an element of the tangent space to manifold at x.

  • egrad

    The ‘Euclidean gradient’, egrad(x) should return the grad of cost in the usual sense, i.e. egrad(x) need not lie in the tangent space.

  • ehess

    The ‘Euclidean Hessian’, ehess(x, a) should return the directional derivative of egrad at x in direction a. This need not lie in the tangent space.

  • arg

    A symbolic (tensor) variable with respect to which you would like to optimize. Its type (together with the type of the cost argument) defines the autodiff backend used.

  • verbosity (2)

    Level of information printed by the solver while it operates, 0 is silent, 2 is most information.

__init__(manifold, cost, egrad=None, ehess=None, grad=None, hess=None, arg=None, precon=None, verbosity=2)
backend
cost
egrad
ehess
grad
hess

manifolds.

manifold (abc)

class pymanopt.manifolds.manifold.Manifold

Bases: object

Abstract base class setting out a template for manifold classes. If you would like to extend Pymanopt with a new manifold, then your manifold should inherit from this class.

Not all methods are required by all solvers. In particular, first order gradient based solvers such as pymanopt.solvers.steepest_descent and pymanopt.solvers.conjugate_gradient require egrad2rgrad() to be implemented but not ehess2rhess(). Second order solvers such as pymanopt.solvers.trust_regions will require ehess2rhess().

All of these methods correspond closely to methods in Manopt. See http://www.manopt.org/tutorial.html#manifolds for more details on manifolds in Manopt, which are effectively identical to those in Pymanopt (all of the methods in this class have equivalents in Manopt with the same name).

dim

Dimension of the manifold

dist(X, Y)

Geodesic distance on the manifold

egrad2rgrad(X, G)

A mapping from the Euclidean gradient G into the tangent space to the manifold at X.

ehess2rhess(X, Hess)

Convert Euclidean into Riemannian Hessian.

exp(X, U)

The exponential (in the sense of Lie group theory) of a tangent vector U at X.

inner(X, G, H)

Inner product (Riemannian metric) on the tangent space

log(X, Y)

The logarithm (in the sense of Lie group theory) of Y. This is the inverse of exp.

norm(X, G)

Compute the norm of a tangent vector G, which is tangent to the manifold at X.

pairmean(X, Y)

Computes the intrinsic mean of X and Y, that is, a point that lies mid-way between X and Y on the geodesic arc joining them.

proj(X, G)

Project into the tangent space. Usually the same as egrad2rgrad

rand()

A function which returns a random point on the manifold.

randvec(X)

Returns a random, unit norm vector in the tangent space at X.

retr(X, G)

A retraction mapping from the tangent space at X to the manifold. See Absil for definition of retraction.

transp(x1, x2, d)

Transports d, which is a tangent vector at x1, into the tangent space at x2.

typicaldist

Returns the “scale” of the manifold. This is used by the trust-regions solver, to determine default initial and maximal trust-region radii.

zerovec(X)

Returns the zero tangent vector at X.

euclidean

class pymanopt.manifolds.euclidean.Euclidean(*shape)

Bases: pymanopt.manifolds.manifold.Manifold

Euclidean manifold of shape n1 x n2 x ... x nk tensors. Useful for unconstrained optimization problems or for unconstrained hyperparameters, as part of a product manifold.

Examples: Create a manifold of vectors of length n: manifold = Euclidean(n)

Create a manifold of m x n matrices: manifold = Euclidean(m, n)

__init__(*shape)
class pymanopt.manifolds.euclidean.Symmetric(n, k=1)

Bases: pymanopt.manifolds.euclidean.Euclidean

Manifold of n x n symmetric matrices, as a Riemannian submanifold of Euclidean space.

If k > 1 then this is an array of shape (k, n, n) (product manifold) containing k (n x n) matrices.

__init__(n, k=1)

grassmann

class pymanopt.manifolds.grassmann.Grassmann(height, width, k=1)

Bases: pymanopt.manifolds.manifold.Manifold

Factory class for the Grassmann manifold. This is the manifold of p- dimensional subspaces of n dimensional real vector space. Initiation requires the dimensions n, p to be specified. Optional argument k allows the user to optimize over the product of k Grassmanns.

Elements are represented as n x p matrices (if k == 1), and as k x n x p matrices if k > 1 (Note that this is different to manopt!).

__init__(height, width, k=1)

oblique

class pymanopt.manifolds.oblique.Oblique(m, n)

Bases: pymanopt.manifolds.manifold.Manifold

Manifold of matrices w/ unit-norm columns.

Oblique manifold: deals with matrices of size m-by-n such that each column has unit 2-norm, i.e., is a point on the unit sphere in R^m. The metric is such that the oblique manifold is a Riemannian submanifold of the space of m-by-n matrices with the usual trace inner product, i.e., the usual metric.

__init__(m, n)

product

class pymanopt.manifolds.product.Product(manifolds)

Bases: pymanopt.manifolds.manifold.Manifold

Product manifold, i.e. the cartesian product of multiple manifolds.

__init__(manifolds)

psd

class pymanopt.manifolds.psd.Elliptope(n, k)

Bases: pymanopt.manifolds.manifold.Manifold

Manifold of n-by-n psd matrices of rank k with unit diagonal elements.

A point X on the manifold is parameterized as YY^T where Y is a matrix of size nxk. As such, X is symmetric, positive semidefinite. We restrict to full-rank Y’s, such that X has rank exactly k. The point X is numerically represented by Y (this is more efficient than working with X, which may be big). Tangent vectors are represented as matrices of the same size as Y, call them Ydot, so that Xdot = Y Ydot’ + Ydot Y and diag(Xdot) == 0. The metric is the canonical Euclidean metric on Y.

The diagonal constraints on X (X(i, i) == 1 for all i) translate to unit-norm constraints on the rows of Y: norm(Y(i, :)) == 1 for all i. The set of such Y’s forms the oblique manifold. But because for any orthogonal Q of size k, it holds that (YQ)(YQ)’ = YY’, we “group” all matrices of the form YQ in an equivalence class. The set of equivalence classes is a Riemannian quotient manifold, implemented here.

Note that this geometry formally breaks down at rank-deficient Y’s. This does not appear to be a major issue in practice when optimization algorithms converge to rank-deficient Y’s, but convergence theorems no longer hold. As an alternative, you may use the oblique manifold (it has larger dimension, but does not break down at rank drop.)

The geometry is taken from the 2010 paper: M. Journee, P.-A. Absil, F. Bach and R. Sepulchre, “Low-Rank Optimization on the Cone of Positive Semidefinite Matrices”. Paper link: http://www.di.ens.fr/~fbach/journee2010_sdp.pdf

__init__(n, k)
class pymanopt.manifolds.psd.PSDFixedRank(n, k)

Bases: pymanopt.manifolds.manifold.Manifold

Manifold of n-by-n symmetric positive semidefinite matrices of rank k.

A point X on the manifold is parameterized as YY^T where Y is a matrix of size nxk. As such, X is symmetric, positive semidefinite. We restrict to full-rank Y’s, such that X has rank exactly k. The point X is numerically represented by Y (this is more efficient than working with X, which may be big). Tangent vectors are represented as matrices of the same size as Y, call them Ydot, so that Xdot = Y Ydot’ + Ydot Y. The metric is the canonical Euclidean metric on Y.

Since for any orthogonal Q of size k, it holds that (YQ)(YQ)’ = YY’, we “group” all matrices of the form YQ in an equivalence class. The set of equivalence classes is a Riemannian quotient manifold, implemented here.

Notice that this manifold is not complete: if optimization leads Y to be rank-deficient, the geometry will break down. Hence, this geometry should only be used if it is expected that the points of interest will have rank exactly k. Reduce k if that is not the case.

An alternative, complete, geometry for positive semidefinite matrices of rank k is described in Bonnabel and Sepulchre 2009, “Riemannian Metric and Geometric Mean for Positive Semidefinite Matrices of Fixed Rank”, SIAM Journal on Matrix Analysis and Applications.

The geometry implemented here is the simplest case of the 2010 paper: M. Journee, P.-A. Absil, F. Bach and R. Sepulchre, “Low-Rank Optimization on the Cone of Positive Semidefinite Matrices”. Paper link: http://www.di.ens.fr/~fbach/journee2010_sdp.pdf

__init__(n, k)
class pymanopt.manifolds.psd.PSDFixedRankComplex(*args, **kwargs)

Bases: pymanopt.manifolds.psd.PSDFixedRank

Manifold of n x n complex Hermitian pos. semidefinite matrices of rank k.

Manifold of n-by-n complex Hermitian positive semidefinite matrices of fixed rank k. This follows the quotient geometry described in Sarod Yatawatta’s 2013 paper: “Radio interferometric calibration using a Riemannian manifold”, ICASSP.

Paper link: http://dx.doi.org/10.1109/ICASSP.2013.6638382.

A point X on the manifold M is parameterized as YY^*, where Y is a complex matrix of size nxk. For any point Y on the manifold M, given any kxk complex unitary matrix U, we say Y*U is equivalent to Y, i.e., YY^* does not change. Therefore, M is the set of equivalence classes and is a Riemannian quotient manifold C^{nk}/SU(k). The metric is the usual real-trace inner product, that is, it is the usual metric for the complex plane identified with R^2.

Notice that this manifold is not complete: if optimization leads Y to be rank-deficient, the geometry will break down. Hence, this geometry should only be used if it is expected that the points of interest will have rank exactly k. Reduce k if that is not the case.

__init__(*args, **kwargs)
class pymanopt.manifolds.psd.PositiveDefinite(n, k=1)

Bases: pymanopt.manifolds.manifold.Manifold

Manifold of (n x n)^k positive definite matrices, based on the geometry discussed in Chapter 6 of Positive Definite Matrices (Bhatia 2007). Some of the implementation is based on sympositivedefinitefactory.m from the Manopt MATLAB package. Also see “Conic geometric optimisation on the manifold of positive definite matrices” (Sra & Hosseini 2013) for more details.

__init__(n, k=1)
pairmean(X, Y)

Computes the intrinsic mean of X and Y, that is, a point that lies mid-way between X and Y on the geodesic arc joining them.

sphere

class pymanopt.manifolds.sphere.Sphere(*shape)

Bases: pymanopt.manifolds.manifold.Manifold

Manifold of shape n1 x n2 x ... x nk tensors with unit 2-norm. The metric is such that the sphere is a Riemannian submanifold of Euclidean space. This implementation is based on spherefactory.m from the Manopt MATLAB package.

Examples: The ‘usual’ sphere S^2, the set of points lying on the surface of a ball in 3D space: sphere = Sphere(3)

__init__(*shape)

stiefel

class pymanopt.manifolds.stiefel.Stiefel(height, width, k=1)

Bases: pymanopt.manifolds.manifold.Manifold

Factory class for the Stiefel manifold. Initiation requires the dimensions n, p to be specified. Optional argument k allows the user to optimize over the product of k Stiefels.

Elements are represented as n x p matrices (if k == 1), and as k x n x p matrices if k > 1 (Note that this is different to manopt!).

__init__(height, width, k=1)

solvers.

solver (abc)

class pymanopt.solvers.solver.Solver(maxtime=1000, maxiter=1000, mingradnorm=1e-06, minstepsize=1e-10, maxcostevals=5000, logverbosity=0)

Bases: object

Abstract base class setting out template for solver classes.

__init__(maxtime=1000, maxiter=1000, mingradnorm=1e-06, minstepsize=1e-10, maxcostevals=5000, logverbosity=0)
Variable attributes (defaults in brackets):
  • maxtime (1000)

    Max time (in seconds) to run.

  • maxiter (1000)

    Max number of iterations to run.

  • mingradnorm (1e-6)

    Terminate if the norm of the gradient is below this.

  • minstepsize (1e-10)

    Terminate if linesearch returns a vector whose norm is below this.

  • maxcostevals (5000)

    Maximum number of allowed cost evaluations

  • logverbosity (0)

    Level of information logged by the solver while it operates, 0 is silent, 2 ist most information.

solve(problem, x=None)

Solve the given pymanopt.core.problem.Problem (starting from a random initial guess if the optional argument x is not provided).

conjugate_gradient

class pymanopt.solvers.conjugate_gradient.ConjugateGradient(beta_type=2, orth_value=inf, linesearch=None, *args, **kwargs)

Bases: pymanopt.solvers.solver.Solver

Module containing conjugate gradient algorithm based on conjugategradient.m from the manopt MATLAB package.

__init__(beta_type=2, orth_value=inf, linesearch=None, *args, **kwargs)

Instantiate gradient solver class. Variable attributes (defaults in brackets):

  • beta_type (BetaTypes.HestenesStiefel)

    Conjugate gradient beta rule used to construct the new search direction

  • orth_value (numpy.inf)

    Parameter for Powell’s restart strategy. An infinite value disables this strategy. See in code formula for the specific criterion used.

  • linesearch (LineSearchAdaptive)

    The linesearch method to used.

solve(problem, x=None, reuselinesearch=False)

Perform optimization using nonlinear conjugate gradient method with linesearch. This method first computes the gradient of obj w.r.t. arg, and then optimizes by moving in a direction that is conjugate to all previous search directions. Arguments:

  • problem

    Pymanopt problem setup using the Problem class, this must have a .manifold attribute specifying the manifold to optimize over, as well as a cost and enough information to compute the gradient of that cost.

  • x=None

    Optional parameter. Starting point on the manifold. If none then a starting point will be randomly generated.

  • reuselinesearch=False

    Whether to reuse the previous linesearch object. Allows to use information from a previous solve run.

Returns:
  • x

    Local minimum of obj, or if algorithm terminated before convergence x will be the point at which it terminated.

linesearch

class pymanopt.solvers.linesearch.LineSearchAdaptive(contraction_factor=0.5, suff_decr=0.5, maxiter=10, initial_stepsize=1)

Bases: object

Adaptive line-search

__init__(contraction_factor=0.5, suff_decr=0.5, maxiter=10, initial_stepsize=1)
search(objective, man, x, d, f0, df0)
class pymanopt.solvers.linesearch.LineSearchBackTracking(contraction_factor=0.5, optimism=2, suff_decr=0.0001, maxiter=25, initial_stepsize=1)

Bases: object

Back-tracking line-search based on linesearch.m in the manopt MATLAB package.

__init__(contraction_factor=0.5, optimism=2, suff_decr=0.0001, maxiter=25, initial_stepsize=1)
search(objective, manifold, x, d, f0, df0)

Function to perform backtracking line-search. Arguments:

  • objective

    objective function to optimise

  • manifold

    manifold to optimise over

  • x

    starting point on the manifold

  • d

    tangent vector at x (descent direction)

  • df0

    directional derivative at x along d

Returns:
  • stepsize

    norm of the vector retracted to reach newx from x

  • newx

    next iterate suggested by the line-search

nelder_mead

class pymanopt.solvers.nelder_mead.NelderMead(maxcostevals=None, maxiter=None, reflection=1, expansion=2, contraction=0.5, *args, **kwargs)

Bases: pymanopt.solvers.solver.Solver

Nelder-Mead minimization alglorithm for derivative-free minimization based on neldermead.m and centroid.m from the manopt MATLAB package.

__init__(maxcostevals=None, maxiter=None, reflection=1, expansion=2, contraction=0.5, *args, **kwargs)

Instantiate Nelder-Mead method solver class. Variable attributes (defaults in brackets):

  • maxcostevals (max(5000, 2 * dim))

    Maximum number of allowed cost evaluations

  • maxiter (max(500, 4 * dim))

    Maximum number of allowed iterations

  • reflection (1)

    Determines how far to reflect away from the worst vertex; stretched (reflection > 1), compressed (0 < reflection < 1), or exact (reflection = 1)

  • expansion (2)

    Factor by which to expand the reflected simplex

  • contraction (0.5)

    Factor by which to contract the reflected simplex

solve(problem, x=None)

Perform optimization using a Nelder-Mead minimization algorithm. Arguments:

  • problem

    Pymanopt problem setup using the Problem class, this must have a .manifold attribute specifying the manifold to optimize over, as well as a cost and enough information to compute the gradient of that cost.

  • x=None

    Optional parameter. Initial population of elements on the manifold. If None then an initial population will be randomly generated

Returns:
  • x

    Local minimum of obj, or if algorithm terminated before convergence x will be the point at which it terminated

pymanopt.solvers.nelder_mead.compute_centroid(man, x)

Compute the centroid as Karcher mean of points x belonging to the manifold man.

particle_swarm

class pymanopt.solvers.particle_swarm.ParticleSwarm(maxcostevals=None, maxiter=None, populationsize=None, nostalgia=1.4, social=1.4, *args, **kwargs)

Bases: pymanopt.solvers.solver.Solver

Particle swarm optimization method based on pso.m from the manopt MATLAB package.

__init__(maxcostevals=None, maxiter=None, populationsize=None, nostalgia=1.4, social=1.4, *args, **kwargs)

Instantiate Particle Swarm Optimization (PSO) solver class. Variable attributes (defaults in brackets):

  • maxcostevals (max(5000, 2 * dim))

    Maximum number of allowed cost evaluations

  • maxiter (max(500, 4 * dim))

    Maximum number of allowed iterations

  • populationsize (min(40, 10 * dim))

    Size of the considered swarm population

  • nostalgia (1.4)

    Quantifies performance relative to past performances

  • social (1.4)

    Quantifies performance relative to neighbors

solve(problem, x=None)

Perform optimization using the particle swarm optimization algorithm. Arguments:

  • problem

    Pymanopt problem setup using the Problem class, this must have a .manifold attribute specifying the manifold to optimize over, as well as a cost (specified using a theano graph or as a python function).

  • x=None

    Optional parameter. Initial population of elements on the manifold. If None then an initial population will be randomly generated

Returns:
  • x

    Local minimum of obj, or if algorithm terminated before convergence x will be the point at which it terminated

steepest_descent

class pymanopt.solvers.steepest_descent.SteepestDescent(linesearch=<pymanopt.solvers.linesearch.LineSearchBackTracking object>, *args, **kwargs)

Bases: pymanopt.solvers.solver.Solver

Steepest descent (gradient descent) algorithm based on steepestdescent.m from the manopt MATLAB package.

__init__(linesearch=<pymanopt.solvers.linesearch.LineSearchBackTracking object>, *args, **kwargs)
solve(problem, x=None, reuselinesearch=False)

Perform optimization using gradient descent with linesearch. This method first computes the gradient (derivative) of obj w.r.t. arg, and then optimizes by moving in the direction of steepest descent (which is the opposite direction to the gradient). Arguments:

  • problem

    Pymanopt problem setup using the Problem class, this must have a .manifold attribute specifying the manifold to optimize over, as well as a cost and enough information to compute the gradient of that cost.

  • x=None

    Optional parameter. Starting point on the manifold. If none then a starting point will be randomly generated.

  • reuselinesearch=False

    Whether to reuse the previous linesearch object. Allows to use information from a previous solve run.

Returns:
  • x

    Local minimum of obj, or if algorithm terminated before convergence x will be the point at which it terminated.

trust_regions

class pymanopt.solvers.trust_regions.TrustRegions(miniter=3, kappa=0.1, theta=1.0, rho_prime=0.1, use_rand=False, rho_regularization=1000.0, *args, **kwargs)

Bases: pymanopt.solvers.solver.Solver

EXCEEDED_TR = 1
MAX_INNER_ITER = 4
MODEL_INCREASED = 5
NEGATIVE_CURVATURE = 0
REACHED_TARGET_LINEAR = 2
REACHED_TARGET_SUPERLINEAR = 3
TCG_STOP_REASONS = {0: 'negative curvature', 1: 'exceeded trust region', 2: 'reached target residual-kappa (linear)', 3: 'reached target residual-theta (superlinear)', 4: 'maximum inner iterations', 5: 'model increased'}
__init__(miniter=3, kappa=0.1, theta=1.0, rho_prime=0.1, use_rand=False, rho_regularization=1000.0, *args, **kwargs)

Trust regions algorithm based on trustregions.m from the Manopt MATLAB package.

Also included is the Truncated (Steihaug-Toint) Conjugate-Gradient algorithm, based on tCG.m from the Manopt MATLAB package.

solve(problem, x=None, mininner=1, maxinner=None, Delta_bar=None, Delta0=None)

tools.

autodiff

class pymanopt.tools.autodiff.TheanoBackend

Bases: pymanopt.tools.autodiff._backend.Backend

compile_function(objective, argument)

Wrapper for the theano.function(). Compiles a theano graph into a python function.

compute_gradient(objective, argument)

Wrapper for theano.tensor.grad(). Computes the gradient of ‘objective’ with respect to ‘argument’ and returns compiled version.

compute_hessian(objective, argument)

Computes the directional derivative of the gradient (which is equal to the Hessian multiplied by direction).

is_available()
is_compatible(objective, argument)
class pymanopt.tools.autodiff.AutogradBackend

Bases: pymanopt.tools.autodiff._backend.Backend

compute_gradient(objective, argument)

Compute the gradient of ‘objective’ with respect to the first argument and return as a function.

compute_hessian(objective, argument)
is_available()
is_compatible(objective, argument)
class pymanopt.tools.autodiff.TensorflowBackend

Bases: pymanopt.tools.autodiff._backend.Backend

__init__()
compile_function(objective, argument)
compute_gradient(objective, argument)

Compute the gradient of ‘objective’ and return as a function.

compute_hessian(objective, argument)
is_available()
is_compatible(objective, argument)

multi

Operations on multiple matrices.

pymanopt.tools.multi.multiexp(A, sym=False)
pymanopt.tools.multi.multieye(k, n)
pymanopt.tools.multi.multilog(A, pos_def=False)
pymanopt.tools.multi.multiprod(A, B)

Inspired by MATLAB multiprod function by Paolo de Leva. A and B are assumed to be arrays containing M matrices, that is, A and B have dimensions A: (M, N, P), B:(M, P, Q). multiprod multiplies each matrix in A with the corresponding matrix in B, using matrix multiplication. so multiprod(A, B) has dimensions (M, N, Q).

pymanopt.tools.multi.multisym(A)
pymanopt.tools.multi.multitransp(A)

Inspired by MATLAB multitransp function by Paolo de Leva. A is assumed to be an array containing M matrices, each of which has dimension N x P. That is, A is an M x N x P array. Multitransp then returns an array containing the M matrix transposes of the matrices in A, each of which will be P x N.

testing

Module containing tools for testing correctness in Pymanopt. Note, these currently require autograd.

Note: the methods for generating rgrad, egrad2rgrad, ehess and ehess2rhess will only be correct if the manifold is a submanifold of Euclidean space, that is if the projection is an orthogonal projection onto the tangent space.

pymanopt.tools.testing.egrad2rgrad(proj)

Generates an egrad2rgrad function.

pymanopt.tools.testing.ehess2rhess(proj)

Generates an ehess2rhess function for a manifold which is a sub-manifold of Euclidean space. ehess2rhess(proj)(x, egrad, ehess, u) converts the Euclidean hessian ehess at the point x to a Riemannian hessian. That is the directional derivatative of the gradient in the direction u. proj must be defined using autograd.numpy. This will not be an efficient implementation because of missing support for efficient jacobian-vector products in autograd.

pymanopt.tools.testing.rgrad(cost, proj)

Generates the Riemannain gradient of cost. Cost must be defined using autograd.numpy.

pymanopt.tools.testing.rhess(cost, proj)

Generates the Riemannian hessian of the cost. Specifically, rhess(cost, proj)(x, u) is the directional derivatative of cost at point X on the manifold, in direction u. cost and proj must be defined using autograd.numpy. See http://sites.uclouvain.be/absil/2013-01/Weingarten_07PA_techrep.pdf for some discussion. proj and cost must be defined using autograd. Currently this is correct but not efficient, because of the jacobian- vector product. Hopefully this can be fixed in future.