Time-Varying Semidefinite Programs
Amir Ali Ahmadi (a_a_aprinceton.edu)
Abstract: We study time-varying semidefinite programs (TV-SDPs), which are semidefinite programs whose data (and solutions) are functions of time. Our focus is on the setting where the data varies polynomially with time. We show that under a strict feasibility assumption, restricting the solutions to also be polynomial functions of time does not change the optimal value of the TV-SDP. Moreover, by using a Positivstellensatz on univariate polynomial matrices, we show that the best polynomial solution of a given degree to a TV-SDP can be found by solving a semidefinite program of tractable size. We also provide a sequence of dual problems which can be cast as SDPs and that give upper bounds on the optimal value of a TV-SDP (in maximization form). We prove that under a boundedness assumption, this sequence of upper bounds converges to the optimal value of the TV-SDP. Under the same assumption, we also show that the optimal value of the TV-SDP is attained. We demonstrate the efficacy of our algorithms on a maximum-flow problem with time-varying edge capacities, a wireless coverage problem with time-varying coverage requirements, and on bi-objective semidefinite optimization where the goal is to approximate the Pareto curve in one shot.
Keywords: Semidefinite programming, time-varying convex optimization, univariate polynomial matrices, Positivstellensatze, continuous linear programs, bi-objective optimization
Category 1: Infinite Dimensional Optimization
Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )
Category 3: Applications -- Science and Engineering (Basic Sciences Applications )
Citation: Department of ORFE, Princeton University, August 2018.
Entry Submitted: 08/12/2018
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|