Cargando…

An accelerating algorithm for globally solving nonconvex quadratic programming

To globally solve a nonconvex quadratic programming problem, this paper presents an accelerating linearizing algorithm based on the framework of the branch-and-bound method. By utilizing a new linear relaxation approach, the initial quadratic programming problem is reduced to a sequence of linear re...

Descripción completa

Detalles Bibliográficos
Autores principales: Ge, Li, Liu, Sanyang
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer International Publishing 2018
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6061662/
https://www.ncbi.nlm.nih.gov/pubmed/30137906
http://dx.doi.org/10.1186/s13660-018-1764-1
_version_ 1783342268919316480
author Ge, Li
Liu, Sanyang
author_facet Ge, Li
Liu, Sanyang
author_sort Ge, Li
collection PubMed
description To globally solve a nonconvex quadratic programming problem, this paper presents an accelerating linearizing algorithm based on the framework of the branch-and-bound method. By utilizing a new linear relaxation approach, the initial quadratic programming problem is reduced to a sequence of linear relaxation programming problems, which is used to obtain a lower bound of the optimal value of this problem. Then, by using the deleting operation of the investigated regions, we can improve the convergent speed of the proposed algorithm. The proposed algorithm is proved to be convergent, and some experiments are reported to show higher feasibility and efficiency of the proposed algorithm.
format Online
Article
Text
id pubmed-6061662
institution National Center for Biotechnology Information
language English
publishDate 2018
publisher Springer International Publishing
record_format MEDLINE/PubMed
spelling pubmed-60616622018-08-09 An accelerating algorithm for globally solving nonconvex quadratic programming Ge, Li Liu, Sanyang J Inequal Appl Research To globally solve a nonconvex quadratic programming problem, this paper presents an accelerating linearizing algorithm based on the framework of the branch-and-bound method. By utilizing a new linear relaxation approach, the initial quadratic programming problem is reduced to a sequence of linear relaxation programming problems, which is used to obtain a lower bound of the optimal value of this problem. Then, by using the deleting operation of the investigated regions, we can improve the convergent speed of the proposed algorithm. The proposed algorithm is proved to be convergent, and some experiments are reported to show higher feasibility and efficiency of the proposed algorithm. Springer International Publishing 2018-07-16 2018 /pmc/articles/PMC6061662/ /pubmed/30137906 http://dx.doi.org/10.1186/s13660-018-1764-1 Text en © The Author(s) 2018 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
spellingShingle Research
Ge, Li
Liu, Sanyang
An accelerating algorithm for globally solving nonconvex quadratic programming
title An accelerating algorithm for globally solving nonconvex quadratic programming
title_full An accelerating algorithm for globally solving nonconvex quadratic programming
title_fullStr An accelerating algorithm for globally solving nonconvex quadratic programming
title_full_unstemmed An accelerating algorithm for globally solving nonconvex quadratic programming
title_short An accelerating algorithm for globally solving nonconvex quadratic programming
title_sort accelerating algorithm for globally solving nonconvex quadratic programming
topic Research
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6061662/
https://www.ncbi.nlm.nih.gov/pubmed/30137906
http://dx.doi.org/10.1186/s13660-018-1764-1
work_keys_str_mv AT geli anacceleratingalgorithmforgloballysolvingnonconvexquadraticprogramming
AT liusanyang anacceleratingalgorithmforgloballysolvingnonconvexquadraticprogramming
AT geli acceleratingalgorithmforgloballysolvingnonconvexquadraticprogramming
AT liusanyang acceleratingalgorithmforgloballysolvingnonconvexquadraticprogramming