An efficient algorithm for the projection of a point on the intersection of two hyperplanes and a box in Rn

In this work, Rn we present an efficient strongly polynomial algorithm for the projection of a point on the intersection of two hyperplanes and a box in Rn. Interior point methods are the most efficient algorithm in the literature to solve this problem. While efficient in practice, the complexity of...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	CláudioP. Santiago, Sérgio Assunção Monteiro, Helder Inácio, Nelson Maculan, MariaHelena Jardim
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2019
Materias:	90-08 Computational methods Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/7ca5eb28b4ea49798f4faa85d1541965
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:7ca5eb28b4ea49798f4faa85d1541965
record_format	dspace
spelling	oai:doaj.org-article:7ca5eb28b4ea49798f4faa85d15419652021-12-02T05:01:11ZAn efficient algorithm for the projection of a point on the intersection of two hyperplanes and a box in Rn2192-440610.1007/s13675-018-0105-yhttps://doaj.org/article/7ca5eb28b4ea49798f4faa85d15419652019-06-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621001155https://doaj.org/toc/2192-4406In this work, Rn we present an efficient strongly polynomial algorithm for the projection of a point on the intersection of two hyperplanes and a box in Rn. Interior point methods are the most efficient algorithm in the literature to solve this problem. While efficient in practice, the complexity of interior-point methods is bounded by a polynomial in the dimension of the problem and in the accuracy of the solution. Moreover, their efficiency is highly dependent on a series of parameters depending on the specific method chosen (especially for nonlinear problems), such as step size, barrier parameter, accuracy, among others. We propose a new method based on the KKT optimality conditions. In this method, we write the problem as a function of the Lagrangian multipliers of the hyperplanes and seek to find the pair of multipliers that corresponds to the optimal solution. We prove that the algorithm has complexity O(n2logn).CláudioP. SantiagoSérgio Assunção MonteiroHelder InácioNelson MaculanMariaHelena JardimElsevierarticle90-08 Computational methodsApplied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 7, Iss 2, Pp 177-207 (2019)
institution	DOAJ
collection	DOAJ
language	EN
topic	90-08 Computational methods Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90-08 Computational methods Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 CláudioP. Santiago Sérgio Assunção Monteiro Helder Inácio Nelson Maculan MariaHelena Jardim An efficient algorithm for the projection of a point on the intersection of two hyperplanes and a box in Rn
description	In this work, Rn we present an efficient strongly polynomial algorithm for the projection of a point on the intersection of two hyperplanes and a box in Rn. Interior point methods are the most efficient algorithm in the literature to solve this problem. While efficient in practice, the complexity of interior-point methods is bounded by a polynomial in the dimension of the problem and in the accuracy of the solution. Moreover, their efficiency is highly dependent on a series of parameters depending on the specific method chosen (especially for nonlinear problems), such as step size, barrier parameter, accuracy, among others. We propose a new method based on the KKT optimality conditions. In this method, we write the problem as a function of the Lagrangian multipliers of the hyperplanes and seek to find the pair of multipliers that corresponds to the optimal solution. We prove that the algorithm has complexity O(n2logn).
format	article
author	CláudioP. Santiago Sérgio Assunção Monteiro Helder Inácio Nelson Maculan MariaHelena Jardim
author_facet	CláudioP. Santiago Sérgio Assunção Monteiro Helder Inácio Nelson Maculan MariaHelena Jardim
author_sort	CláudioP. Santiago
title	An efficient algorithm for the projection of a point on the intersection of two hyperplanes and a box in Rn
title_short	An efficient algorithm for the projection of a point on the intersection of two hyperplanes and a box in Rn
title_full	An efficient algorithm for the projection of a point on the intersection of two hyperplanes and a box in Rn
title_fullStr	An efficient algorithm for the projection of a point on the intersection of two hyperplanes and a box in Rn
title_full_unstemmed	An efficient algorithm for the projection of a point on the intersection of two hyperplanes and a box in Rn
title_sort	efficient algorithm for the projection of a point on the intersection of two hyperplanes and a box in rn
publisher	Elsevier
publishDate	2019
url	https://doaj.org/article/7ca5eb28b4ea49798f4faa85d1541965
work_keys_str_mv	AT claudiopsantiago anefficientalgorithmfortheprojectionofapointontheintersectionoftwohyperplanesandaboxinrn AT sergioassuncaomonteiro anefficientalgorithmfortheprojectionofapointontheintersectionoftwohyperplanesandaboxinrn AT helderinacio anefficientalgorithmfortheprojectionofapointontheintersectionoftwohyperplanesandaboxinrn AT nelsonmaculan anefficientalgorithmfortheprojectionofapointontheintersectionoftwohyperplanesandaboxinrn AT mariahelenajardim anefficientalgorithmfortheprojectionofapointontheintersectionoftwohyperplanesandaboxinrn AT claudiopsantiago efficientalgorithmfortheprojectionofapointontheintersectionoftwohyperplanesandaboxinrn AT sergioassuncaomonteiro efficientalgorithmfortheprojectionofapointontheintersectionoftwohyperplanesandaboxinrn AT helderinacio efficientalgorithmfortheprojectionofapointontheintersectionoftwohyperplanesandaboxinrn AT nelsonmaculan efficientalgorithmfortheprojectionofapointontheintersectionoftwohyperplanesandaboxinrn AT mariahelenajardim efficientalgorithmfortheprojectionofapointontheintersectionoftwohyperplanesandaboxinrn
_version_	1718400837976326144

An efficient algorithm for the projection of a point on the intersection of two hyperplanes and a box in Rn

Ejemplares similares