A sequential partial linearization algorithm for the symmetric eigenvalue complementarity problem
- PDF / 1,697,171 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 94 Downloads / 181 Views
A sequential partial linearization algorithm for the symmetric eigenvalue complementarity problem Masao Fukushima1 · Joaquim Júdice2 · Welington de Oliveira3 · Valentina Sessa3 Received: 21 April 2020 / Accepted: 2 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper, we introduce a Sequential Partial Linearization (SPL) algorithm for finding a solution of the symmetric Eigenvalue Complementarity Problem (EiCP). The algorithm can also be used for the computation of a stationary point of a standard fractional quadratic program. A first version of the SPL algorithm employs a line search technique and possesses global convergence to a solution of the EiCP under a simple condition related to the minimum eigenvalue of one of the matrices of the problem. Furthermore, it is shown that this condition is verified for a simpler version of the SPL algorithm that does not require a line search technique. The main computational effort of the SPL algorithm is the solution of a strictly convex standard quadratic problem, which is efficiently solved by a finitely convergent block principal pivoting algorithm. Numerical results of the solution of test problems from different sources indicate that the SPL algorithm is in general efficient for the solution of the symmetric EiCP in terms of the number of iterations, accuracy of the solution and total computational effort. Keywords Complementarity problems · Eigenvalue problems · Fractional quadratic programming · Quadratic programming
The research of J. Júdice is funded by FCT/MCTES through national funds and when applicable cofunded EU funds under the project UIDB/EEA/50008/2020. W. de Oliveira acknowledges financial support from the Gaspard-Monge program for Optimization and Operations Research (PGMO) Project “Models for planning energy investment under uncertainty”. * Valentina Sessa [email protected] 1
Faculty of Science and Technology, Nanzan University, Nagoya, Japan
2
Instituto de Telecomunicações, Universidade de Coimbra, Coimbra, Portugal
3
MINES ParisTech, PSL Research University, CMA Centre de Mathématiques Appliquées, CS 10207 ‑ 1, rue Claude Daunesse, 06904 Sophia Antipolis Cedex, France
13
Vol.:(0123456789)
M. Fukushima et al.
Mathematics Subject Classification MSC 90C26 · MSC 90C32 · MSC 90C33 · MSC 90C30 · MSC 93B60
1 Introduction The Eigenvalue Complementarity Problem (EiCP) consists of finding 𝜆 ∈ ℝ and x ∈ ℝn ⧵ {0} such that:
w = Ax − 𝜆Bx
(1a)
x ≥0, w ≥ 0
(1b)
xT w = 0,
(1c)
where A and B are given matrices of order n and B is positive definite (PD). The real number 𝜆 is called a complementary eigenvalue and x is the complementary eigenvector associated with 𝜆 . We denote by EiCP(A, B) an EiCP with matrices A and B. An EiCP is symmetric if both the matrices in its definition are symmetric (B is SPD). In order to guarantee that a solution of the problem (1) is nonzero, it is sufficient to add the constraint
eT x = 1,
(1d)
where e ∈ ℝn is a vector of ones [14]. Since B is a PD
Data Loading...
