Scholarlink

<p>This paper presents an efficient algorithm for solving log-determinant semidefinite programming problems characterized by chordal sparsity. By employing chordal decomposition and maximum-determinant positive definite matrix completion, we reformulate the original optimization problem into an equivalent form that replaces the large-scale decision matrix with a set of smaller, computationally tractable submatrices. Although this reformulation may lead to a nonconvex objective in the reduced variables, we address this challenge by developing a tailored difference-of-convex algorithm. We rigorously prove that the sequence generated by our algorithm converges globally to the optimal solution at a linear rate under the Łojasiewicz inequality. Numerical experiments demonstrate the effectiveness and efficiency of our approach; notably, our method achieves optimality in only 4.29&#xa0;s on a test instance compared to 616&#xa0;s required by the benchmark method.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A difference-of-convex approach for log-determinant semidefinite programming with chordal sparsity

  • 期刊论文

  • 发表日期：

    2026年3月24日

查看全文
  • Ryoga Masaki,
  • Xiangyu Yang,
  • Makoto Yamashita

摘要

This paper presents an efficient algorithm for solving log-determinant semidefinite programming problems characterized by chordal sparsity. By employing chordal decomposition and maximum-determinant positive definite matrix completion, we reformulate the original optimization problem into an equivalent form that replaces the large-scale decision matrix with a set of smaller, computationally tractable submatrices. Although this reformulation may lead to a nonconvex objective in the reduced variables, we address this challenge by developing a tailored difference-of-convex algorithm. We rigorously prove that the sequence generated by our algorithm converges globally to the optimal solution at a linear rate under the Łojasiewicz inequality. Numerical experiments demonstrate the effectiveness and efficiency of our approach; notably, our method achieves optimality in only 4.29 s on a test instance compared to 616 s required by the benchmark method.