Search

In recent years, the proximal gradient method and its variants have been generalized to Riemannian manifolds for solving optimization problems with an additively separable structure, i.e., f+h, where f is continuously differentiable, and h may be nonsmooth but convex with computationally reasonable proximal mapping. In this paper, we generalize the proximal Newton method to embedded submanifolds for solving the type of problem with h(x) = µ||x||1. The generalization relies on the Weingarten and semismooth analysis. It is shown that the Riemannian proximal Newton method has a local superlinear convergence rate under certain reasonable assumptions. Moreover, a hybrid version is given by concatenating a Riemannian proximal gradient method and the Riemannian proximal Newton method. It is shown that if the switch parameter is chosen appropriately, then the hybrid method converges globally and also has a local superlinear convergence rate. Numerical experiments on random and synthetic data are used to demonstrate the performance of the proposed methods. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing a differentiate function with locally Lipschitz continuous gradient on the real determinantal variety and present a first-order algorithm designed to find a stationary point of that problem. This algorithm applies steps of a retraction-free descent method proposed by Schneider and Uschmajew [SIAM J. Optirn., 25 (2015), pp. 622-646], while taking the numerical rank into account to attempt rank reductions. We prove that this algorithm produces a sequence of iterates whose accumulation points are stationary and therefore does not follow the so-called apocalypses described by Levin, Kileel, and Boumal [Math. Program., 199 (2023), pp. 831-864], Moreover, the rank reduction mechanism of this algorithm requires at most one rank reduction attempt per iteration, in contrast with the one of the P2GDR algorithm introduced by Olikier, Gallivan, and Absil [An Apocalypse-Free First-Order Low-Rank Optimization Algorithm, Technical report UCL-INMA-2022.01, https://arxiv.org/abs/2201.03962, 2022], which can require a number of rank reduction attempts equal to the rank of the iterate in the worst-case scenario. [ABSTRACT FROM AUTHOR]

We address the problem of computing the smallest symplectic eigenvalues and the corresponding eigenvectors of symmetric positive-definite matrices in the sense of Williamson's theorem. It is formulated as minimizing a trace cost function over the symplectic Stiefel manifold. We first investigate various theoretical aspects of this optimization problem such as characterizing the sets of critical points, saddle points, and global minimizers as well as proving that nonglobal local minimizers do not exist. Based on our recent results on constructing Riemannian structures on the symplectic Stiefel manifold and the associated optimization algorithms, we then propose a numerical procedure for computing symplectic eigenpairs in the framework of Riemannian optimization. Moreover, a connection of the sought solution with the eigenvalues of a special class of Hamiltonian matrices is discussed. Numerical examples are presented. [ABSTRACT FROM AUTHOR]

The symplectic Stiefel manifold, denoted by Sp(2p, 2n), is the set of linear symplectic maps between the standard symplectic spaces ℝ2p and ℝ2n. When p = n, it reduces to the wellknown set of 2n \times 2n symplectic matrices. Optimization problems on Sp(2p, 2n) find applications in various areas, such as optics, quantum physics, numerical linear algebra, and model order reduction of dynamical systems. The purpose of this paper is to propose and analyze gradient-descent methods on Sp(2p, 2n), where the notion of gradient stems from a Riemannian metric. We consider a novel Riemannian metric on Sp(2p, 2n) akin to the canonical metric of the (standard) Stiefel manifold. In order to perform a feasible step along the antigradient, we develop two types of search strategies: one is based on quasi-geodesic curves and the other one on the symplectic Cayley transform. The resulting optimization algorithms are proved to converge globally to critical points of the objective function. Numerical experiments illustrate the efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

This paper explores the well-known identification of the manifold of rank p positivesemidefinite matrices of size n with the quotient of the set of full-rank n-by-p matrices by the orthogonal group in dimension p. The induced metric corresponds to the Wasserstein metric between centered degenerate Gaussian distributions and is a generalization of the Bures--Wasserstein metric on the manifold of positive-definite matrices. We compute the Riemannian logarithm and show that the local injectivity radius at any matrix C is the square root of the pth largest eigenvalue of C. As a result, the global injectivity radius on this manifold is zero. Finally, this paper also contains a detailed description of this geometry, recovering previously known expressions by applying the standard machinery of Riemannian submersions. [ABSTRACT FROM AUTHOR]

In this paper, a Riemannian BFGS method for minimizing a smooth function on a Riemannian manifold is defined, based on a Riemannian generalization of a cautious update and a weak line search condition. It is proven that the Riemannian BFGS method converges (i) globally to stationary points without assuming the objective function to be convex and (ii) superlinearly to a nondegenerate minimizer. Using the weak line search condition removes the need for information from differentiated retraction. The joint matrix diagonalization problem is chosen to demonstrate the performance of the algorithms with various parameters, line search conditions, and pairs of retraction and vector transport. A preliminary version can be found in [Numerical Mathematics and Advanced Applications: ENUMATH 2015, Lect. Notes Comput. Sci. Eng. 112, Springer, New York, 2016, pp. 627{634]. [ABSTRACT FROM AUTHOR]

We generalize the notion of Bézier surfaces and surface splines to Riemannian manifolds. To this end we put forward and compare three possible alternative definitions of Bézier surfaces. We furthermore investigate how to achieve C0- and C¹-continuity of Bézier surface splines. Unlike in Euclidean space and for one-dimensional Bézier splines on manifolds, C¹-continuity cannot be ensured by simple conditions on the Bézier control points: it requires an adaptation of the Bézier spline evaluation scheme. Finally, we propose an algorithm to optimize the Bézier control points given a set of points to be interpolated by a Bézier surface spline. We show computational examples on the sphere, the special orthogonal group, and two Riemannian shape spaces. [ABSTRACT FROM AUTHOR]

Low-rank matrix completion is the problem where one tries to recover a low-rank matrix from noisy observations of a subset of its entries. In this paper, we propose RMC, a new method to deal with the problem of robust low-rank matrix completion, i.e., matrix completion where a fraction of the observed entries are corrupted by non-Gaussian noise, typically outliers. The method relies on the idea of smoothing the l1 norm and using Riemannian optimization to deal with the low-rank constraint. We first state the algorithm as the successive minimization of smooth approximations of the l1 norm, and we analyze its convergence by showing the strict decrease of the objective function. We then perform numerical experiments on synthetic data and demonstrate the effectiveness on the proposed method on the Net ix dataset. [ABSTRACT FROM AUTHOR]

The problem discussed in this paper is the symmetric best low multilinear rank approximation of third-order symmetric tensors. We propose an algorithm based on Jacobi rotations, for which symmetry is preserved at each iteration. Two numerical examples are provided indicating the need for such algorithms. An important part of the paper consists of proving that our algorithm converges to stationary points of the objective function. This can be considered an advantage of the proposed algorithm over existing symmetry-preserving algorithms in the literature. [ABSTRACT FROM AUTHOR]

This paper deals with constructing retractions, a key step when applying optimization algorithms on matrix manifolds. For submanifolds of Euclidean spaces, we show that the operation consisting of taking a tangent step in the embedding Euclidean space followed by a projection onto the submanifold is a retraction. We also show that the operation remains a retraction if the projection is generalized to a projection-like procedure that consists of coming back to the submanifold along "admissible" directions, and we give a sufficient condition on the admissible directions for the generated retraction to be second order. This theory offers a framework in which previously proposed retractions can be analyzed, as well as a toolbox for constructing new ones. Illustrations are given for projection-like procedures on some specific manifolds for which we have an explicit, easy-to-compute expression. [ABSTRACT FROM AUTHOR]

Higher-order tensors are used in many application fields, such as statistics, signal processing, and scientific computing. Efficient and reliable algorithms for manipulating these multi-way arrays are thus required. In this paper, we focus on the best rank-(R1, R2, R3) approximation of third-order tensors. We propose a new iterative algorithm based on the trust-region scheme. The tensor approximation problem is expressed as a minimization of a cost function on a product of three Grassmann manifolds. We apply the Riemannian trust-region scheme, using the truncated conjugate-gradient method for solving the trust-region subproblem. Making use of second order information of the cost function, superlinear convergence is achieved. If the stopping criterion of the subproblem is chosen adequately, the local convergence rate is quadratic. We compare this new method with the well-known higher-order orthogonal iteration method and discuss the advantages over Newton-type methods. [ABSTRACT FROM AUTHOR]

In numerical optimization, line-search and trust-region methods are two important classes of descent schemes, with well-understood global convergence properties. We say that these methods are "accelerated" when the conventional iterate is replaced by any point that produces at least as much of a decrease in the cost function as a fixed fraction of the decrease produced by the conventional iterate. A detailed convergence analysis reveals that global convergence properties of line-search and trust-region methods still hold when the methods are accelerated. The analysis is performed in the general context of optimization on manifolds, of which optimization in Rn is a particular case. This general convergence analysis sheds new light on the behavior of several existing algorithms. [ABSTRACT FROM AUTHOR]

Consider solving a linear program in standard form where the constraint matrix A is m x n, with n ≫ m ≫ 1. Such problems arise, for example, as the result of finely discretizing a semi-infinite program. The cost per iteration of typical primal-dual interior-point methods on such problems is O(m²n). We propose to reduce that cost by replacing the normal equation matrix, AD²AT, where D is a diagonal matrix, with a "reduced" version (of same dimension), AQDQ²AQT, where Q is an index set including the indices of M most nearly active (or most violated) dual constraints at the current iterate, with M ≥ m a prescribed integer. This can result in a speedup of close to n/¦Q¦ at each iteration. Promising numerical results are reported for constraint-reduced versions of a dual-feasible affine-scaling algorithm and of Mehrotra's predictor-corrector method [S. Mehrotra, SIAM J. Optim., 2 (1992), pp. 575-601]. In particular, while it could be expected that neglecting a large portion of the constraints, especially at early iterations, may result in a significant deterioration of the search direction, it appears that the total number of iterations typically remains essentially constant as the size of the reduced constraint set is decreased down to some threshold. In some cases this threshold is a small fraction of the total set. In the case of the affine-scaling algorithm, global convergence and local quadratic convergence are proved. [ABSTRACT FROM AUTHOR]

In the early eighties Lojasiewicz [in Seminari di Geometria 1982-1983, Università di Bologna, Istituto di Geometria, Dipartimento di Matematica, 1984, pp. 115--117] proved that a bounded solution of a gradient flow for an analytic cost function converges to a well-defined limit point. In this paper, we show that the iterates of numerical descent algorithms, for an analytic cost function, share this convergence property if they satisfy certain natural descent conditions. The results obtained are applicable to a broad class of optimization schemes and strengthen classical "weak convergence" results for descent methods to "strong limit-point convergence" for a large class of cost functions of practical interest. The result does not require that the cost has isolated critical points and requires no assumptions on the convexity of the cost nor any nondegeneracy conditions on the Hessian of the cost at critical points. [ABSTRACT FROM AUTHOR]

We propose a Newton-like iteration that evolves on the set of fixed dimensional subspaces of Rn and converges locally cubically to the invariant subspaces of a symmetric matrix. This iteration is compared in terms of numerical cost and global behavior with three other methods that display the same property of cubic convergence. Moreover, we consider heuristics that greatly improve the global behavior of the iterations. [ABSTRACT FROM AUTHOR]