Toolboxes

NonSmoothSolvers.jl

We consider the problem

\min_{x\in \mathbb{R}^n} F(x),

where $F:\mathbb{R}^n \to \mathbb{R}$ is nonsmooth: at point $x$ , one can compute $F(x)$ and $v\in\partial F(x)$ .

$\triangleright$ NonSmoothSolvers.jl implements the following algorithms:

the superlinear $\mathcal{VU}$ bundle algorithm^[1]
nonsmooth BFGS^[2]
gradient sampling^[3]

$\triangleright$ NonSmoothProblems.jl implements some classical problems:

the maximum of smooth functions: $F(x) = \max(f_1(x), \cdots, f_m(x))$ ,
the maximum eigenvalue problem $F(x) = \lambda_{\max} (A(x))$ , where $A(x)$ is a symmetric real matrix, that depends smoothly on $x$ .

RandomizedProgressiveHedging.jl

RandomizedProgressiveHedging.jl: a julia package for solving multistage stochastic problems by randomized versions of the progressive hedging algorithm.

QuadProgSimplex.jl

QuadProgSimplex.jl: an active set algorithm to minimize certain quadratic functions on the simplex, in arbitrary precision.^[4]^[5]

\min_{x\in\mathbb{R}^m} \frac{1}{2}\|Ax\|^2 + \langle p, x\rangle \quad \text{ s.t. } \quad x \ge 0, \; \sum_i x_i = 1.

QuadProgSpectraplex.jl

QuadProgSpectraplex.jl: an active set algorithm to minimize smooth functions on the spectraplex, in arbitrary precision.

\min_{Z\in\mathbb{R}^{m\times m}} f(x) \quad \text{ s.t. } \quad Z = Z^\top,\; Z \succeq 0, \; \mathrm{tr}(Z) = 1.

Implements the algorithm proposed in: B, Iutzeler, Malick (2022) Newton Acceleration on Manifolds Identified by Proximal Gradient Methods, Mathematical Programming.

Paper code

Additive nonsmooth minimization

\min_{x\in\mathbb{R}^n} f(x) + g(x),

where $f$ is smooth and $g$ is nonsmooth but "prox-easy".

CompositeProblems.jl – additive learning problems (lasso, logistic $\ell_1$ ).
StructuredProximalOperators.jl – some proximal operators and structure manifolds.
StructuredSolvers.jl – proximal gradient variants and its Riemannian acceleration.

$\triangleright$ B, Iutzeler, Malick (2022) Newton Acceleration on Manifolds Identified by Proximal Gradient Methods, Mathematical Programming.

Composite nonsmooth minimization

\min_{x\in\mathbb{R}^n} g \circ c(x),

where $c$ is a smooth map and $g$ is nonsmooth but "prox-easy".

LocalCompositeNewton.jl – algorithm and numerical experiments of the paper.

$\triangleright$ B, Iutzeler, Malick (2022) Harnessing Structure in Composite Nonsmooth Minimization.

Other projects and dependencies

Optimization Plots

PlotsOptim.jl provides convenience helpers to build PGF/Tikz plots from julia. Tailored for suboptimality type curves, or 2d plots of iterates.

Side projects

ConjugateGradient.jl: pure julia implementation of the Conjugate Gradient algorithm, with detection of quasi-negative curvature directions.
EigenDerivatives.jl: implementation of first and second-order derivatives of eigenvalues of parametrized matrices, handling points where some eigenvalues coalesce. Works for any representation of reals (e.g. julia's Float64, BigFloat types).

Old projects

SDCO.jl: implementation of a self-dual conic interior point supporting real and complex variables.

References:

[1]	Mifflin, Sagastizábal (2005) A VU-algorithm for Convex Minimization, Mathematical Programming.

[2]	Lewis, Overton (2013) Nonsmooth Optimization via Quasi-Newton Methods, Mathematical Programming.

[3]	Burke, Curtis, Lewis, Overton, Simões (2018) Gradient Sampling Methods for Nonsmooth Optimization, Numerical Nonsmooth Optimization.

[4]	Kiwiel (1986) A Method for Solving Certain Quadratic Programming Problems Arising in Nonsmooth Optimization, IMA Journal of Numerical Analysis.

[5]	Wolfe (1976) Finding the Nearest Point in A Polytope, Mathematical Programming.