Time-Varying Semidefinite Programs

Amir Ali Ahmadi () and Bachir El Khadir ()
Additional contact information
Amir Ali Ahmadi: Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544
Bachir El Khadir: Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544

Mathematics of Operations Research, 2021, vol. 46, issue 3, 1054-1080

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.

Keywords: Primary: 90C22; 90C23; Primary: Mathematics; programming/nonlinear/convex; programming/nonlinear/theory; semidefinite programming; time-varying convex optimization; univariate polynomial matrices; Positivstellensatz; continuous linear programs; biobjective optimization (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1117 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:3:p:1054-1080

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().