A semismooth Newton based dual proximal point algorithm for maximum eigenvalue problem

Yong-Jin Liu () and Jing Yu ()
Additional contact information
Yong-Jin Liu: Fuzhou University
Jing Yu: Fuzhou University

Computational Optimization and Applications, 2023, vol. 85, issue 2, No 7, 547-582

Abstract: Abstract The maximum eigenvalue problem is to minimize the maximum eigenvalue function over an affine subspace in a symmetric matrix space, which has many applications in structural engineering, such as combinatorial optimization, control theory and structural design. Based on classical analysis of proximal point (Ppa) algorithm and semismooth analysis of nonseparable spectral operator, we propose an efficient semismooth Newton based dual proximal point (Ssndppa) algorithm to solve the maximum eigenvalue problem, in which an inexact semismooth Newton (Ssn) algorithm is applied to solve inner subproblem of the dual proximal point (d-Ppa) algorithm. Global convergence and locally asymptotically superlinear convergence of the d-Ppa algorithm are established under very mild conditions, and fast superlinear or even quadratic convergence of the Ssn algorithm is obtained when the primal constraint nondegeneracy condition holds for the inner subproblem. Computational costs of the Ssn algorithm for solving the inner subproblem can be reduced by fully exploiting low-rank or high-rank property of a matrix. Numerical experiments on max-cut problems and randomly generated maximum eigenvalue optimization problems demonstrate that the Ssndppa algorithm substantially outperforms the Sdpnal+ solver and several state-of-the-art first-order algorithms.

Keywords: Maximum eigenvalue problem; Proximal point algorithm; Semismooth Newton algorithm; Density matrix; Quadratic growth condition; 90C06; 90C25; 90C90 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-023-00467-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:85:y:2023:i:2:d:10.1007_s10589-023-00467-2

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-023-00467-2

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().