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...
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
Elsevier
2019
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/7ca5eb28b4ea49798f4faa85d1541965 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | 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). |
|---|