A successive linear approximation algorithm for the global minimization of a concave quadratic program
- PDF / 642,403 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 40 Downloads / 175 Views
A successive linear approximation algorithm for the global minimization of a concave quadratic program Mohamed Telli1 · Mohand Bentobache1
· Abdelkader Mokhtari1
Received: 11 April 2019 / Revised: 7 August 2020 / Accepted: 27 August 2020 © SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional 2020
Abstract In this work, we propose an algorithm for finding an approximate global minimum of a concave quadratic function with a negative semi-definite matrix, subject to linear equality and inequality constraints, where the variables are bounded with finite or infinite bounds. The proposed algorithm starts with an initial extreme point, then it moves from the current extreme point to a new one with a better objective function value. The passage from one basic feasible solution to a new one is done by the construction of certain approximation sets and solving a sequence of linear programming problems. In order to compare our algorithm with the existing approaches, we have developed an implementation with MATLAB and conducted numerical experiments on numerous collections of test problems. The obtained numerical results show the accuracy and the efficiency of our approach. Keywords Concave quadratic programming · Global optimization · Linear programming · Approximation sets · Level curve · Numerical experiments Mathematics Subject Classification 90C20 · 90C26 · 90C59
1 Introduction The concave quadratic programming (QP) problem consists in minimizing a concave quadratic function over a certain convex set. This problem, which is a special case of the general nonconvex QP problem, is NP-hard (Pardalos and Rodgers 1990) and its minimum is achieved at an extreme point (Luenberger and Ye 2008). Concave quadratic programming
Communicated by Ernesto G. Birgin.
B
Mohand Bentobache [email protected] Mohamed Telli [email protected] Abdelkader Mokhtari [email protected]
1
Laboratory of Pure and Applied Mathematics, University Amar Telidji of Laghouat, BP 37G, Ghardaia Road, 03000 Laghouat, Algeria 0123456789().: V,-vol
123
272
Page 2 of 28
M. Telli et al.
has many important applications, and we can cite: credit scoring (Bugera et al. 2002; Baesens et al. 2003; Guillou 2013), minimization of the global energy of a complex physical system composed of magnetic moments in interaction (Bieche et al. 1980; An and Tao 1998), evaluation of medical diagnosis (Mangasarian et al. 1995; Fung 2003; Guillou 2013), optimization of electrical systems (Momoh et al. 1995), missile flight testing (Rusakov 2003), response surface analysis (Enkhbat and Bazarsad 2010), etc. In particular, if the domain of the concave QP problem is a compact polyhedron, then it has a finite number of extreme points which can be enumerated when the problem dimension is small. Otherwise, we must apply an iterative algorithm for finding an approximate global solution. Many algorithms have been developed for solving this problem, such as cutting plane methods and partition of feasible domain techniques (Tuy 1964) which do not ens
Data Loading...
