Optimization Online


A Double Smoothing Technique for Constrained Convex Optimization Problems and Applications to Optimal Control

Olivier Devolder (Olivier.Devolder***at***uclouvain.be)
François Glineur (Francois.Glineur***at***uclouvain.be)
Yurii Nesterov (Yurii.Nesterov***at***uclouvain.be)

Abstract: In this paper, we propose an efficient approach for solving a class of convex optimization problems in Hilbert spaces. Our feasible region is a (possibly infinite-dimensional) simple convex set, i.e. we assume that projections on this set are computationally easy to compute. The problem we consider is the minimization of a convex function over this region under the additional constraint $Au \in T$, where $A$ is a linear operator and $T$ is a (finite-dimensional) convex set whose dimension is small as 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 method and show how to reconstruct an approximate primal solution. 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 \over \epsilon} \ln {1 \over \epsilon})$ gradient iterations, where $\epsilon$ is the desired accuracy for the primal-dual solution. Our approach covers, in particular, optimal control problems with 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 of time.

Keywords: convex optimization, fast gradient methods, complexity theory, smoothing technique, optimal control

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 3: Infinite Dimensional Optimization

Citation: CORE Discussion paper 2010/34 (updated version), Center for Operations Research and Econometrics (CORE), Universite catholique de Louvain (UCL), Belgium. Modified version accepted for publication in SIAM Journal of Optimization under the title: 'DOUBLE SMOOTHING TECHNIQUE FOR LARGE-SCALE LINEARLY CONSTRAINED CONVEX OPTIMIZATION'

Download: [PDF]

Entry Submitted: 01/25/2011
Entry Accepted: 01/25/2011
Entry Last Modified: 07/04/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society