Author(s)： Mirai Tanaka, Kazuhide Nakata and Hayato Waki

J. Math-for-Ind. 5A (2013) 41-50.

• File： JMI2013A-6.pdf (138KB)

Abstract
Doubly nonnegative (DNN) optimization is one of the most important topics in convex optimization. Some approaches which use DNN optimization are effective for some NP-hard optimization problems, e.g., the maximum stable set problem and the quadratic assignment problem (QAP). However, the obtained DNN optimization problems often become highly degenerate. This implies that it is numerically difficult to find accurate optimal values and solutions of such problems even by the state-of-the-art computational technology. We propose a numerical reduction method for such DNN optimization problems, which uses a simple idea based on facial reduction algorithms. We improve the numerical tractability of the DNN optimization problems by our proposed method. We present the improvement by presenting the preliminary numerical experiments for QAP.

Keyword(s).　 doubly nonnegative optimization, semidefinite optimization, facial reduction algorithm