Title: Support solving method for box-constrained indefinite quadratic minimisation problems

Authors: Amar Andjouh; Mohand Ouamer Bibi

Addresses: Research Unit LaMOS, Department of Operations Research, Faculty of the Exact Sciences, University of Bejaia, 06000, Bejaia, Algeria ' Research Unit LaMOS, Department of Operations Research, Faculty of the Exact Sciences, University of Bejaia, 06000, Bejaia, Algeria

Abstract: This paper provides a new support solving method (SSM) of global optimisation for the box-constrained non-convex quadratic minimisation problem, in particular with one negative eigenvalue. We investigate the support of the objective function and exploit properties of the indefinite associated matrix for establishing global optimality criterion (necessary and sufficient conditions). Furthermore, using these conditions and computational techniques of abstract convexity, we suggest an SSM that can effectively solve an indefinite quadratic minimisation problem, providing thus a global minimiser. We present numerical examples and generate some test problems with known global minimiser, solving them by the proposed SSM. Finally, we provide the comparative effectiveness of the SSM with active set method (ASM) and interior point method (IPM) implemented under MATLAB optimisation toolbox.

Keywords: global optimisation; non-convex quadratic minimisation; sufficient global optimality condition; support feasible pair; SFP; support solving method; SSM.

DOI: 10.1504/IJMMNO.2022.126556

International Journal of Mathematical Modelling and Numerical Optimisation, 2022 Vol.12 No.4, pp.390 - 415

Received: 20 Aug 2021
Accepted: 21 Feb 2022
Published online: 28 Oct 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article