No. 980

Title:

An extension of the standard polynomial-time primal-dual path-following algorithm to the weighted determinant maximization problem with semidefinite constraints

Author(s):

Tsuchiya, Takashi (The Institute of Statistical Mathematics);
Xia, Yu (The Institute of Statistical Mathematics)

Key words:

determinant maximization problem; logarithmic determinant function; semidefinite programming; primal-dual interior-point algorithm

Abstract:

    The problem of maximizing the sum of linear functional and several weighted logarithmic determinant (logdet) functions under semidefinite constraints is a generalization of the semidefinite programming (SDP) and has a number of applications in statistics and datamining, and other areas of informatics and mathematical sciences. In this paper, we extend the framework of standard primal-dual path-following algorithms for SDP to this problem. Employing this framework, we show that the long-step path-following algorithm analogous to the one in SDP has ${\cal O}(N\log(1/\varepsilon)+N)$ iteration-complexity to reduce the duality gap by a factor of $\varepsilon$, where $N = \sum N_i$, where $N_i$ is the size of the $i$-th positive semidefinite matrix block which is assumed to be an $N_i\times N_i$ matrix.