Time-varying semidefinite programs

Amir Ali Ahmadi, Bachir El Khadir

Research output: Contribution to journalArticlepeer-review

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 vary 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 (positive locus theorem) 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 that 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 biobjective semidefinite optimization where the goal is to approximate the Pareto curve in one shot.

Original languageEnglish (US)
Pages (from-to)1054-1080
Number of pages27
JournalMathematics of Operations Research
Volume46
Issue number3
DOIs
StatePublished - Aug 2021

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • Biobjective optimization
  • Continuous linear programs
  • Positivstellensatz
  • Semidefinite programming
  • Time-varying convex optimization
  • Univariate polynomial matrices

Fingerprint

Dive into the research topics of 'Time-varying semidefinite programs'. Together they form a unique fingerprint.

Cite this