A dual spectral projected gradient method for log-determinant semidefinite problems

DOI10.1007/S10589-020-00166-2zbMATH Open1433.90104arXiv1812.00523OpenAlexW2999732672WikidataQ126319000 ScholiaQ126319000MaRDI QIDQ1986103FDOQ1986103

Authors: Takashi Nakagaki, Mituhiro Fukuda, Sunyoung Kim, Makoto Yamashita 

Publication date: 7 April 2020

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Abstract: 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 box constraints and then onto a set defined by a linear matrix inequality. By exploiting structures of the two projections, we show the same convergence properties can be obtained for the proposed method as Birgin's method where the exact orthogonal projection onto the intersection of two convex sets is performed. Using the convergence properties, we prove that the proposed algorithm attains the optimal value or terminates in a finite number of iterations. The efficiency of the proposed method is illustrated with the numerical results on randomly generated synthetic/deterministic data and gene expression data, in comparison with other methods including the inexact primal-dual path-following interior-point method, the adaptive spectral projected gradient method, and the adaptive Nesterov's smooth method. For the gene expression data, our results are compared with the quadratic approximation for sparse inverse covariance estimation method. We show that our method outperforms the other methods in obtaining a better optimal value fast.

Full work available at URL: https://arxiv.org/abs/1812.00523

Recommendations

• On how to solve large-scale log-determinant optimization problems
• An inexact dual logarithmic barrier method for solving sparse semidefinite programs
• Solving log-determinant optimization problems by a Newton-CG primal proximal point algorithm
• An interior point sequential quadratic programming-type method for log-determinant semi-infinite programs
• Inexact spectral projected gradient methods on convex sets

zbMATH Keywords

computational efficiencydual problemdual spectral projected gradient methodslog-determinant semidefinite programs with linear constraintstheoretical convergence results

Mathematics Subject Classification ID

Quadratic programming (90C20) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22) Methods of reduced gradient type (90C52)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Nonmonotone Spectral Projected Gradient Methods on Convex Sets
• Two-Point Step Size Gradient Methods
• First-Order Methods for Sparse Covariance Selection
• Solving log-determinant optimization problems by a Newton-CG primal proximal point algorithm
• An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming
• A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
• Alternating direction method for covariance selection models
• An inexact interior point method for \(L_{1}\)-regularized sparse covariance selection
• A New Active Set Algorithm for Box Constrained Optimization
• Convex analysis and nonlinear optimization. Theory and examples.
• A proximal point algorithm for log-determinant optimization with group Lasso regularization
• On how to solve large-scale log-determinant optimization problems
• Adaptive First-Order Methods for General Sparse Inverse Covariance Selection
• Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
• A nonmonotone spectral projected gradient method for large-scale topology optimization problems
• An efficient algorithm for sparse inverse covariance matrix estimation based on dual formulation
• QUIC: quadratic approximation for sparse inverse covariance estimation
• A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications

Cited In (2)

• Solving log-determinant optimization problems by a Newton-CG primal proximal point algorithm
• On how to solve large-scale log-determinant optimization problems

Uses Software

• QUIC

This page was built for publication: A dual spectral projected gradient method for log-determinant semidefinite problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1986103)