TY - JOUR
T1 - Optimization over structured subsets of positive semidefinite matrices via column generation
AU - Ahmadi, Amir Ali
AU - Dash, Sanjeeb
AU - Hall, Georgina
N1 - Funding Information:
Amir Ali Ahmadi and Georgina Hall are partially supported by the Young Investigator Award of the Air Force Office of Scientific Research (grant #10006257) and the CAREER Award of the National Science Foundation (grant #10008461).
Publisher Copyright:
© 2016 Elsevier B.V.
PY - 2017/5/1
Y1 - 2017/5/1
N2 - We develop algorithms to construct inner approximations of the cone of positive semidefinite matrices via linear programming and second order cone programming. Starting with an initial linear algebraic approximation suggested recently by Ahmadi and Majumdar, we describe an iterative process through which our approximation is improved at every step. This is done using ideas from column generation in large-scale linear programming. We then apply these techniques to approximate the sum of squares cone in a nonconvex polynomial optimization setting, and the copositive cone for a discrete optimization problem.
AB - We develop algorithms to construct inner approximations of the cone of positive semidefinite matrices via linear programming and second order cone programming. Starting with an initial linear algebraic approximation suggested recently by Ahmadi and Majumdar, we describe an iterative process through which our approximation is improved at every step. This is done using ideas from column generation in large-scale linear programming. We then apply these techniques to approximate the sum of squares cone in a nonconvex polynomial optimization setting, and the copositive cone for a discrete optimization problem.
KW - Copositive programming
KW - Linear programming
KW - Polynomial optimization
KW - Second order cone programming
KW - Semidefinite programming
UR - http://www.scopus.com/inward/record.url?scp=85008191203&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85008191203&partnerID=8YFLogxK
U2 - 10.1016/j.disopt.2016.04.004
DO - 10.1016/j.disopt.2016.04.004
M3 - Article
AN - SCOPUS:85008191203
SN - 1572-5286
VL - 24
SP - 129
EP - 151
JO - Discrete Optimization
JF - Discrete Optimization
ER -