[01976] Tightness conditions of SDP relaxation for QCQPs with bipartite graph structure
Format : Talk at Waseda University
Author(s) :
Godai Azuma (Tokyo Institute of Technology)
Mituhiro Fukuda (Federal University of ABC)
Sunyoung Kim (Ewha Womans University)
Makoto Yamashita (Tokyo Institute of Technology)
Abstract : We discuss a tightness condition of SDP, semidefinite programming, relaxation for QCQPs, quadratically-constrained quadratic programming problems, with bipartite graph structure, and this result generalizes that a condition that the SDP relaxation is tight for QCQPs with diagonal matrices due to Burer and Ye, and a condition based the signs of the elements in input data matrices analyzed by Sojoudi and Lavaei. Our condition to check the tightness of SDP relaxation demands to solve SDP systems, but it requires weaker assumptions than Sojoudi and Lavaei. Our approach also gives another proof for the tightness of SDP relaxations for QCQPs with off-diagonal nonpositive elements by converting such QCQPs into QCQPs with bipartite graph structure.
[02464] Equivalent Sufficient Conditions for Exact SDP Relaxation and the Saddle Point of Lagrangian Function of QCQP
Format : Talk at Waseda University
Author(s) :
Sunyoung Kim (Ewha W. University)
Masakazu Kojima (Chuo University)
Abstract : We study global optimality conditions for general quadratically constrained quadratic program $(\rm QCQP)$. For NP-hard nonconvex QCQP, there has been a great interest in the class of QCQPs whose global optimality can be obtained via convex relaxations. The exactness of optimal solutions of QCQP can determined by several methods: First, the optimal solution $X \in S_+^n$ of the semidefinite $(\rm SDP)$ relaxation of nonconvex QCQP is exact if its rank is 1 or the rank of dual optimal solution of the SDP relaxation is n-1 under strong duality. Second, the global optimality of solutions of QCQP can be also determined by the saddle point of the Lagrangian function of QCQP. Third, second-order sufficient condition for the global optimality can also be used. We examine the relationship among the three conditions and prove their equivalence. A QCQP instance is provided to illustrate the equivalent conditions.
[02214] Approximation Hierarchies for Copositive Cone over Symmetric Cone
Format : Talk at Waseda University
Author(s) :
Mitsuhiro Nishijima (Tokyo Institute of Technology)
Kazuhide Nakata (Tokyo Institute of Technology)
Abstract : We first provide an inner-approximation hierarchy described by a sum-of-squares constraint for the copositive cone over a general symmetric cone. We second provide inner- and outer-approximation hierarchies described by semidefinite but not by sum-of-squares constraints for the copositive cone over the direct product of a nonnegative orthant and a second-order cone. We also compare them with existing hierarchies. Numerical experiments show that, by combining them, we can solve copositive programming problems more accurately and efficiently.
[02008] An inexact projected gradient method with rounding and lifting for rank-one semidefinite relaxation of polynomial optimization
Format : Talk at Waseda University
Author(s) :
Kim-Chuan Toh (National University of Singapore)
Heng Yang (Harvard University)
Ling Liang (National University of Singapore)
Luca Carlone (MIT)
Abstract :
We consider solving high-order semidefinite programming (SDP) relaxations
of polynomial optimization problems (POPs) that often admit
degenerate rank-one optimal solutions. We propose
a new algorithmic framework that uses an inexact projected gradient method for solving the SDP, together with acceleration by
taking long, but safeguarded, rank-one steps generated by fast local solver for the underlying POP. Our framework achieves state-of-the-art efficiency, scalability, and robustness in solving degenerate rank-one SDPs to high accuracy, even with millions of equality constraints.
