$ \DeclareMathOperator{\arccosh}{arccosh} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator{\Exp}{Exp} \newcommand{\geo}[2]{\gamma_{\overset{\frown}{#1,#2}}} \newcommand{\geoS}{\gamma} \newcommand{\geoD}[2]{\gamma_} \newcommand{\geoL}[2]{\gamma(#2; #1)} \newcommand{\gradM}{\nabla_{\M}} \newcommand{\gradMComp}[1]{\nabla_{\M,#1}} \newcommand{\Grid}{\mathcal G} \DeclareMathOperator{\Log}{Log} \newcommand{\M}{\mathcal M} \newcommand{\N}{\mathcal N} \newcommand{\mat}[1]{\mathbf{#1}} \DeclareMathOperator{\prox}{prox} \newcommand{\PT}[3]{\mathrm{PT}_{#1\to#2}#3} \newcommand{\R}{\mathbb R} \newcommand{\SPD}[1]{\mathcal{P}(#1)} \DeclareMathOperator{\Tr}{Tr} \newcommand{\tT}{\mathrm{T}} \newcommand{\vect}[1]{\mathbf{#1}} $

The subgradient descent algorithm on a manifold

Based on a manifold , a starting point , and an element from the (sub)gradient (or descent) direction of a function this function performs a subgradient descent algorithm %}

with step sizes , where we keep track of the minimal value . If is not single valued, this algorithm assumes, that it is meant as a parallel subgradient algorithm with respect to the last dimension(s) of .

The implementation is based on the paper [1].

All functions involved are provided as anonymous functions: The subgradient subgradF is a function based on @(x), the step size is a function @(x,descentDir,iter,initial) based on the current iterate, descent direction , the iteration and an initial step size to start seaching with. This value is set to the last step size within the iterations. Finally the stoppingCriterion is a function based on @(x,xold,iter) that returns false as long as the algorithm should run, hence the algorithm stops if the stopping criterion is fulfilled for the first time.

Optional Parameters

Debug
If set to an anonymous functional depending on @(x,xold,iter) this is called in each cycle, for example to produce text output or save iteration data to a file.
Record
If set to a functional @(x,iter) returning a column vector, and calling the cyclicProximalPoint with a second return value, this function records these column vectors in a matrix returned in the second return value recData.

There are several (sub)gradients available.

Matlab Documentation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
% subGradientDescent(M,x,F,gradF,stepSizeRule,stoppingCriterion)
% compute a sub gradient descent on F using x as inital data and subgradF
% as the (sub)gradient. If F returns a number, the classical subgradient
% descent is performed; if it returs a vector or matrix; a parallel
% subgradient descent is computed, where the (last) data dimensions of x
% are handled in parallel.
%
%   Ferreira, O.P.; Oliverira, P.R.: Subgradient Algorithm on Riemannian
%       manifolds
%       Journal of Optimization Theory and Applications 97.1, 93-104, 1998.
%
% INPUT
%    M                : a manifold M
%    x                : initial data
%    F                : the function F for the different gradients in
%                       parallel or just a value for standard gradient
%                       descent
%    subgradF         : a function @(x) returning the gradient of F at x
%    stepSize         : a function @(x,eta,iter,initial) returning the
%                       stepsize at x with direction eta corresponding to
%                       a certain rule (e.g. Amijo) based on iterate point
%                       x, descent direction eta, iteration iter and
%                       initial stepsize initial.
%   stoppingCriterion : a function @(x,xold,iter) determining whether to
%                       stop or not
% OPTIONAL
%   Debug             : ([]) a function @ (x,xold,iter) producing debug
%                          output
%   Record            : (@(x,iter)) a function returning a column vector,
%                       if there's a second return value and this function
%                       is given, data is recorded in an array and returned
% ---
% MVIRT | R. Bergmann | 2018-03-15

See also

References

  1. Ferreira, O P and Oliveira, P R (1998). Subgradient algorithm on Riemannian manifolds. Journal of Optimization Theory and Applications. 97 93–104