著者

MATSUKAWA Yasuaki YOSHISE Akiko

出版者

University of Tsukuba. Graduate School of Systems and Information Engineering. Doctoral Program in Social Systems & Management

巻号頁・発行日

2011-11

---

We call a positive semidefinite matrix whose elements are nonnegative a doubly nonnegativematrix, and the set of those matrices the doubly nonnegative cone (DNN cone). The DNN coneis not symmetric but can be represented as the projection of a symmetric cone embedded in ahigher dimension. In [16], the authors demonstrated the efficiency of the DNN relaxation usingthe symmetric cone representation of the DNN cone. They showed that the DNN relaxation givessignificantly tight bounds for a class of quadratic assignment problems, but the computational timeis not affordable as long as we employ the symmetric cone representation. They then suggested aprimal barrier function approach for solving the DNN optimization problem directly, instead of usingthe symmetric cone representation. However, most of existing studies on the primal barrier functionapproach assume the availability of a feasible interior point. This fact means that those studies arenot inextricably tied to the practical usage. Motivated by these observations, we propose a primalbarrier function Phase I algorithm for solving conic optimization problems over the closed convexcone K having the following properties: (a) K is not necessarily symmetric, (b) a self-concordantfunction f is defined over intK, and (c) its dual cone K∗ is not explicit or is intractable, all of whichare observed when K is the DNN cone. We analyze the algorithm and provide a sufficient conditionfor finite termination.