GillesBareilles/ConvexHullProjection.jl

Project on structured sets, with active face identification and quadratic convergence.

ConvexHullProjections.jl

Minimize smooth functions on structured sets iteratively using arbitrary precision, the iterates eventually identify the active faces of the set and converge quadratically.

Supported sets:

• the simplex;
• the spectraplex, e.g. the simplex for symmetric matrices.

The implemented algorithm is described in the preprint Newton acceleration on manifolds identified by proximal-gradient methods, G. Bareilles, F. Iutzeler, J. Malick available on arXiv.

Note that this a rather experimental code, don’t hesitate to get in touch!

Example

Projecting zero on the convex hull of vectors

Three points in $\mathbb R^2$. The result is given as the coefficients of the linear combination of the vectors. The identification property is evidenced by the exact zeros in the combination coefficients, and the SimplexFace object.

**Example**: Float64

julia> using ConvexHullProjection

julia> set = SimplexShadow{Float64}([
           1 1 2
           1 2 1
       ])
SimplexShadow{Float64}([1.0 1.0 2.0; 1.0 2.0 1.0])

julia> res, manifold = optimize(set, zeros(3))
([1.0, 0.0, 0.0], SimplexFace(Bool[1, 0, 0]))

**Example**: BigFloat

julia> set = SimplexShadow{BigFloat}([
           2 1 2
           2 2 1
       ])
SimplexShadow{BigFloat}(BigFloat[2.0 1.0 2.0; 2.0 2.0 1.0])

julia> res, structure = optimize(set, zeros(BigFloat, 3))
(BigFloat[0.0, 0.50, 0.50], SimplexFace(Bool[0, 1, 1]))

Projecting zero on a spectraplex shadow

We compute here the projection of zero on the image of the spectraplex by a linear map, aka a shadow of the spectraplex. The algorithm returns the point of the spectraplex which image by the linear mapping has minimal norm. This point may lie at a kink of the spectraplex, that is it may not have full rank : the rank identified by the algorithm is encoded in the SymmPosSemidefFixedRankUnitTrace object.

julia> using ConvexHullProjection, LinearAlgebra, Random

julia> n, m = 12, 5;

julia> Random.seed!(1643);

julia> set = SpectraplexShadow([Symmetric(rand(m, m)) for i in 1:n], m);

julia> Z, manifold = optimize(set, zeros(m, m));

julia> manifold
SymmPosSemidefFixedRankUnitTrace{5, 3}()