Abstract
The paper is devoted to adaptive first-order primal–dual methods for relatively smooth optimization problems subject to inequality constraints and their applications to low-rank matrix recovering problems. It is shown that, for a class of relatively smooth low-rank matrix recovering problems, the triangle scaling property with the scaling factor \(\gamma = 2\) can be applied, which opens the possibility of applying accelerated methods and Frank–Wolfe-type methods and results on their computational guarantees to such problems. An adaptive version of the similar triangle method is proposed for smooth problems with respect to the Bregman divergence with the triangle scaling property with the scaling factor \(\gamma = 2\) . An unaccelerated and an accelerated primal–dual adaptive methods with an inexact oracle are also proposed for relatively smooth problems. The accelerated primal–dual method is an analog of the similar triangle method and uses the triangle scaling property of the Bregman divergence with the scaling factor \(\gamma = 2\) . The key feature of the methods studied in this paper is their ability to use inexact information at iterations and take into account the inexactness of the solution to auxiliary subproblems at iterations of the methods. This is natural because such subproblems are complicated due to the use of the Bregman divergence instead of the squared Euclidean norm. In particular, this led to a version of the Frank–Wolfe method for the selected class of relatively smooth problems. For all proposed methods, theoretical results on the quality of the solution are obtained.
