Mituhiro Fukuda For nonconvex quadratically constrained quadratic programs (QCQPs), we first show that, under certain feasibility conditions, the standard semidefinite (SDP) relaxation is exact for QCQPs with bipartite graph structures. The exact optimal solutions are obtained by examining the dual SDP relaxation and the rank of the optimal solution of this dual SDP relaxation under strong duality. … Read more
Difference of Convex (DC) optimization problems have objective functions that are differences between two convex functions. Representative ways of solving these problems are the proximal DC algorithms, which require that the convex part of the objective function have L-smoothness. In this article, we propose the Bregman Proximal DC Algorithm (BPDCA) for solving large-scale DC optimization … Read more
We study the exactness of the semidefinite programming (SDP) relaxation of quadratically constrained quadratic programs (QCQPs). With the aggregate sparsity matrix from the data matrices of a QCQP with $n$ variables, the rank and positive semidefiniteness of the matrix are examined. We prove that if the rank of the aggregate sparsity matrix is not less … Read more
In the development of first-order methods for smooth (resp., composite) convex optimization problems minimizing smooth functions, the gradient (resp., gradient mapping) norm is a fundamental optimality measure for which a regularization technique of first-order methods is known to be nearly optimal. In this paper, we report an adaptive regularization approach attaining this iteration complexity without … Read more
We extend the result on the spectral projected gradient method by Birgin et al in 2000 to a log-determinant semidefinite problem (SDP) with linear constraints and propose a spectral projected gradient method for the dual problem. Our method is based on alternate projections on the intersection of two convex sets, which first projects onto the … Read more
We propose a new family of subgradient- and gradient-based methods which converges with optimal complexity for convex optimization problems whose feasible region is simple enough. This includes cases where the objective function is non-smooth, smooth, have composite/saddle structure, or are given by an inexact oracle model. We unified the way of constructing the subproblems which … Read more
SemiDefinite Programming (SDP) problem is one of the most central problems in mathematical programming. SDP provides a practical computation framework for many research fields. Some applications, however, require solving large-scale SDPs whose size exceeds the capacity of a single processor in terms of computational time and available memory. SDPARA (SemiDefinite Programming Algorithm paRAllel version) developed … Read more
The SDPA (SemiDefinite Programming Algorithm) Project launched in 1995 has been known to provide high-performance packages for solving large-scale Semidefinite Programs (SDPs). SDPA Ver. 6 solves efficiently large-scale dense SDPs, however, it required much computation time compared with other software packages, especially when the Schur complement matrix is sparse. SDPA Ver. 7 is now completely … Read more
The Semidefinite Program (SDP) is a fundamental problem in mathematical programming. It covers a wide range of applications, such as combinatorial optimization, control theory, polynomial optimization, and quantum chemistry. Solving extremely large-scale SDPs which could not be solved before is a significant work to open up a new vista of future applications of SDPs. Our … Read more
Employing the variational approach having the two-body reduced density matrix (RDM) as variables to compute the ground state energies of atomic-molecular systems has been a long time dream in electronic structure theory in chemical physics/physical chemistry. Realization of the RDM approach has benefited greatly from recent developments in semidefinite programming (SDP). We present the actual … Read more