TY - JOUR
T1 - Time-varying semidefinite programs
AU - Ahmadi, Amir Ali
AU - El Khadir, Bachir
N1 - Funding Information:
Funding: This work was partially supported by the Defense Advanced Research Projects Agency’s DARPA Young Faculty Award, a Multidisciplinary University Research Initiative award of the Air Force Office of Scientific Research, the CAREER Award of the National Science Foundation, the Google Faculty Award, the Innovation Award of the School of Engineering and Applied Sciences at Princeton University, and the Sloan Fellowship.
Publisher Copyright:
© 2021 INFORMS
PY - 2021/8
Y1 - 2021/8
N2 - 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.
AB - 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.
KW - Biobjective optimization
KW - Continuous linear programs
KW - Positivstellensatz
KW - Semidefinite programming
KW - Time-varying convex optimization
KW - Univariate polynomial matrices
UR - http://www.scopus.com/inward/record.url?scp=85106176279&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85106176279&partnerID=8YFLogxK
U2 - 10.1287/MOOR.2020.1117
DO - 10.1287/MOOR.2020.1117
M3 - Article
AN - SCOPUS:85106176279
SN - 0364-765X
VL - 46
SP - 1054
EP - 1080
JO - Mathematics of Operations Research
JF - Mathematics of Operations Research
IS - 3
ER -