A two-phase sequential algorithm for global optimization of the standard quadratic programming problem - Centre de Mathématiques Appliquées Access content directly
Preprints, Working Papers, ... Year : 2024

A two-phase sequential algorithm for global optimization of the standard quadratic programming problem

Joaquim Júdice
  • Function : Author
Valentina Sessa
  • Function : Author
  • PersonId : 1378670
Masao Fukushima
  • Function : Author

Abstract

We introduce a new sequential algorithm for the Standard Quadratic Programming Problem (StQP), which exploits a formulation of StQP as a Linear Program with Linear Complementarity Constraints (LPLCC). The algorithm is finite and guarantees at least in theory a δ-approximate global minimum for an arbitrary small δ, which is a global minimum in practice. The sequential algorithm has two phases. In Phase 1, Stationary Points (SP) with strictly decreasing objective function values are computed. Phase 2 is designed for giving a certificate of global optimality for the last SP computed in Phase 1. Two different Nonlinear Programming Formulations for LPLCC are proposed for each one of these phases, which are solved by efficient enumerative algorithms. New procedures for computing a lower bound for StQP are also proposed, which are easy to implement and give tight bounds in general. Computational experiments with a number of test problems from known sources indicate that the two-phase sequential algorithm is, in general, efficient in practice. Furthermore, the algorithm seems to be an efficient way to study the copositivity of a matrix by exploiting an StQP with this matrix.
Fichier principal
Vignette du fichier
StQP_paper_VS.pdf (605.14 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-04560413 , version 1 (26-04-2024)

Identifiers

  • HAL Id : hal-04560413 , version 1

Cite

Joaquim Júdice, Valentina Sessa, Masao Fukushima. A two-phase sequential algorithm for global optimization of the standard quadratic programming problem. 2024. ⟨hal-04560413⟩
26 View
11 Download

Share

Gmail Mastodon Facebook X LinkedIn More