On minimization of a quadratic function with one negative eigenvalue
- PDF / 273,071 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 85 Downloads / 233 Views
On minimization of a quadratic function with one negative eigenvalue Ilya Minarchenko1
· Oleg Khamisov1
Received: 21 February 2020 / Accepted: 6 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract It is well known that a quadratic programming minimization problem with one negative eigenvalue is NP-hard. However, in practice one may expect such problems being not so difficult to solve. We suggest to make a single partition of the feasible set in a concave variable only so that a convex approximation of the objective function upon every partition set has an acceptable error. Minimizing convex approximations on partition sets provides an approximate solution of the nonconvex quadratic program that we consider. These minimization problems are to be solved concurrently by parallel computing. An estimation of the number of partition sets is given. The study presents a computational comparison with a standard branch-and-bound procedure. Keywords Quadratic programming · Global optimization · Branch-and-bound method · Parallel computing
1 Introduction Quadratic nonconvex programming has a wide range of applications and is an intensively studied field of global optimization. The number of publications devoted to this topic is quite impressive, see, for example, [1–3] and references therein. The main issue of the paper is connected to the result published in [4]. Namely, nonconvex quadratic programming problem with one negative eigenvalue in the objective is NP-hard. Properties of a quadratic function with one negative eigenvalue and the
This study was funded by Russian Foundation for Basic Research according to the research Project No. 18-07-01432.
B
Oleg Khamisov [email protected] Ilya Minarchenko [email protected]
1
Melentiev Energy Systems Institute of Siberian Branch of the Russian Academy of Sciences, Lermontov st. 130, Irkutsk, Russia 664033
123
I. Minarchenko, O. Khamisov
corresponding theoretical results can be found in [5,6]. We get interested in how difficult on average the problem of global minimization of quadratic objective is with exactly one negative eigenvalue. We assume that the eigenvalues and eigenvectors of the matrix in the minimized function are known. Testing the problem from [4] showed that NP-hardness follows from exponential growth of the size of the feasible set. If the size is bounded then the problem can be solved in a reasonable time. The paper investigates this topic in details.
2 Problem formulation We consider a quadratic programming problem f (x) = x T Qx + x T c → min , x
x ∈ X = {x ∈ R | Ax ≤ b} , n
(1) (2)
where Q is an indefinite n × n matrix with exactly one negative eigenvalue, A is an m × n matrix. The feasible set X is assumed to be nonempty and bounded. Here x T denotes the transpose of vector x. Let us represent the matrix Q such that Q = W ΛW T ,
Λ = diag{λ1 , λ2 , . . . , λn } ,
(3)
where λ1 , λ2 , . . . , λn are the eigenvalues of the matrix Q rearranged by increasing order, i.e. λ1 ≤ . . . ≤ λn , λ1 < 0, λi ≥ 0, i = 2, . . .
Data Loading...
