Search

This paper develops an adaptive Proximal Alternating Direction Method of Multipliers (P-ADMM) for solving linearly-constrained, weakly convex, composite optimization problems. This method is adaptive to all problem parameters, including smoothness and weak convexity constants. It is assumed that the smooth component of the objective is weakly convex and possibly nonseparable, while the non-smooth component is convex and block-separable. The proposed method is tolerant to the inexact solution of its block proximal subproblem so it does not require that the non-smooth component has easily computable block proximal maps. Each iteration of our adaptive P-ADMM consists of two steps: (1) the sequential solution of each block proximal subproblem, and (2) adaptive tests to decide whether to perform a full Lagrange multiplier and/or penalty parameter update(s). Without any rank assumptions on the constraint matrices, it is shown that the adaptive P-ADMM obtains an approximate first-order stationary point of the constrained problem in a number of iterations that matches the state-of-the-art complexity for the class of P-ADMMs. The two proof-of-concept numerical experiments that conclude the paper suggest our adaptive P-ADMM enjoys significant computational benefits.

A quasi-Newton method with cubic regularization is designed for solving Riemannian unconstrained nonconvex optimization problems. The proposed algorithm is fully adaptive with at most ${\cal O} (\epsilon_g^{-3/2})$ iterations to achieve a gradient smaller than $\epsilon_g$ for given $\epsilon_g$, and at most $\mathcal O(\max\{ \epsilon_g^{-\frac{3}{2}}, \epsilon_H^{-3} \})$ iterations to reach a second-order stationary point respectively. Notably, the proposed algorithm remains applicable even in cases of the gradient and Hessian of the objective function unknown. Numerical experiments are performed with gradient and Hessian being approximated by forward finite-differences to illustrate the theoretical results and numerical comparison.