Unconstrained Proximal Operator: the Optimal Parameter for the Douglas-Rachford Type Primal-Dual Methods
share
In this work, we propose an alternative parametrized form of the proximal operator, of which the parameter no longer needs to be positive. That is, the parameter can be a non-zero scalar, a full-rank square matrix, or, more generally, a bijective bounded linear operator. We demonstrate that the positivity requirement is essentially due to a quadratic form. We prove several key characterizations for the new form in a generic way (with an operator parameter). We establish the optimal choice of parameter for the Douglas-Rachford type methods by solving a simple unconstrained optimization problem. The optimality is in the sense that a non-ergodic worst-case convergence rate bound is minimized. We provide closed-form optimal choices for scalar and orthogonal matrix parameters under zero initialization. Additionally, a simple self-contained proof of a sharp linear convergence rate for a (1/L)-cocoercive fixed-point sequence with L∈(0,1) is provided (as a preliminary result). To our knowledge, an operator parameter is new. To show its practical use, we design a dedicated parameter for the 2-by-2 block-structured semidefinite program (SDP). Such a structured SDP is strongly related to the quadratically constrained quadratic program (QCQP), and we therefore expect the proposed parameter to be of great potential use. At last, two well-known applications are investigated. Numerical results show that the theoretical optimal parameters are close to the practical optimums, except they are not a priori knowledge. We then demonstrate that, by exploiting problem model structures, the theoretical optimums can be well approximated. Such approximations turn out to work very well, and in some cases almost reach the underlying limits.
READ FULL TEXT