DOUBLE SMOOTHING TECHNIQUE FOR LARGE-SCALE LINEARLY CONSTRAINED CONVEX OPTIMIZATION

作者：Devolder Olivier^*; Glineur Francois; Nesterov Yurii

来源：SIAM Journal on Optimization, 2012, 22(2): 702-727.

DOI：10.1137/110826102

• convex optimization
• fast gradient methods
• infinite-dimensional
• Hilbert space
• complexity theory
• smoothing technique
• optimal control

In this paper, we propose an efficient approach for solving a class of large-scale convex optimization problems. The problem we consider is the minimization of a convex function over a simple (possibly infinite-dimensional) convex set, under the additional constraint Au is an element of T, where A is a linear operator and T is a convex set whose dimension is small compared to the dimension of the feasible region. In our approach, we dualize the linear constraints, solve the resulting dual problem with a purely dual gradient-type method and show how to reconstruct an approximate primal solution. Because the linear constraints have been dualized, the dual objective function typically becomes separable, and therefore easy to compute. In order to accelerate our scheme, we introduce a novel double smoothing technique that involves regularization of the dual problem to allow the use of a fast gradient method. As a result, we obtain a method with complexity O(1/epsilon ln 1/epsilon) gradient iterations, where epsilon is the desired accuracy for the primal-dual solution. Our approach covers, in particular, optimal control problems with a trajectory governed by a system of linear differential equations, where the additional constraints can, for example, force the trajectory to visit some convex sets at certain moments in time.

• 出版日期2012