Friday, 11:00 - 11:25 h, Room: H 0112

 

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

Coauthors: Maria Helena C. Jardim, Nelson Maculan

 

Abstract:
In this work, we present an efficient strongly polynomial algorithm for the projection of a point on the intersection of two hyperplanes and a box in I\!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. In addition, 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(n2 log n).

 

Talk 2 of the contributed session Fri.1.H 0112
"Complexity issues in optimization" [...]
Cluster 16
"Nonlinear programming" [...]

 

  payday advance . In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.