Optimization Online


Convergence rates of moment-sum-of-squares hierarchies for optimal control problems

Milan Korda (korda.m***at***gmail.com)
Didier Henrion (henrion***at***laas.fr)
Colin N. Jones (colin.jones***at***epfl.ch)

Abstract: We study the convergence rate of moment-sum-of-squares hierarchies of semidefinite programs for optimal control problems with polynomial data. It is known that these hierarchies generate polynomial under-approximations to the value function of the optimal control problem and that these under-approximations converge in the $L^1$ norm to the value function as their degree $d$ tends to infinity. We show that the rate of this convergence is $O(1/\log\log\,d)$. We treat in detail the continuous-time infinite-horizon discounted problem and describe in brief how the same rate can be obtained for the finite-horizon continuous-time problem and for the discrete-time counterparts of both problems.

Keywords: optimal control, moment relaxations, polynomial sums of squares, semidefinite programming, approximation theory

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Applications -- Science and Engineering (Control Applications )

Category 3: Nonlinear Optimization (Systems governed by Differential Equations Optimization )


Download: [PDF]

Entry Submitted: 09/08/2016
Entry Accepted: 09/08/2016
Entry Last Modified: 09/08/2016

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