Search

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 ∈ 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, mid 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/ε ln 1/ε) gradient iterations, where ε 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. [ABSTRACT FROM AUTHOR]