时间：9月26日15:00-16:00
地点：zoom会议号：820 2553 6460；登录码：2023
内容：Quadratically-constrained quadratic programming (QCQP) is an optimization problem that has many practical applications, for example, network localization problems, max-cut problems, and polynomial optimization problems. Since QCQP is NP-hard, semidefinite programming (SDP) relaxation is often employed to obtain a good approximate solution, and many researchers have discussed the condition for the SDP relaxation to give an exact optimal solution of the original QCQP.
In this talk, we discuss such a condition using a graph structure generated from input matrices in QCQP. In particular, when the structure is represented by a bipartite graph and all the edges in the graph are nonnegative, the SDP relaxation is exact. This condition includes existing known conditions. This talk starts from a basic derivation of the SDP relaxation, then introduces existing conditions briefly, and discuss our new condition. This talk is based on Azuma, Kim, Fukuda, Yamashita: Exact SDP relaxations for quadratic programs with bipartite graph structures, Journal of Global Optimization, Vol. 86, pp. 671-691 (2023).
主讲人简介：Makoto Yamashita received a master degree in 2001 and a doctoral degree in 2004 at Tokyo Institute of Technology. He was a research associate at Kanawaga University and an assistant professor at Tokyo Institute of Technology. After working as an associate professor,he is a professor at the Department of Mathematical and Computing Science, Tokyo Institute of Technology. His research interests include numerical methods and applications of conic optimization, for example, an SDP solver SDPA.
