An efficient algorithm for the projection of a point on the intersection of two hyperplanes and a box in $$\mathbb {R}^n$$
Tóm tắt
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
$$\mathbb {R}^n$$
. 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(n^2 \log n)$$
.
Tài liệu tham khảo
Athans M, Falb PL (1966) Optimal control. McGraw-Hill, New York
Ben-Tal A, Nemirovski A (2001) Lectures on modern convex optimization: analysis, algorithms, and engineering applications. MPS-SIAM series on optimization. SIAM, Philadelphia
Brucker P (1984) An \({O} (n)\) algorithm for quadratic knapsack problems. Oper Res Lett 3(3):163–166
Byrd RH, Peihuang L, Nocedal J, Zhu C (1995) A limited memory algorithm for bound constrained optimization. SIAM J Sci Comput 16(5):1190–1208
Kiwiel KC (2008) Breakpoint searching algorithms for the continuous quadratic knapsack problem. Math Programm 112:473–491
Koza JR (1992) Genetic programming. MIT Press, Cambridge
Lin C-J, Moré JJ (1998) Newton’s method for large bound-constrained optimization problems. SIAM J Optim 9:1100–1127
Maculan N, Minoux M, Plateau G (1997) A \(\mathit{O}(n)\) algorithm for projecting a vector on the intersection of a hyperplane and \({\mathbb{R}}^n_+\). RAIRO Oper Res 3(1):7–16
Maculan N, Santiago CP, Macambira EM, Jardim MHC (2003) An \(\mathit{O}(n)\) algorithm for projecting a vector on the intersection of a hyperplane and a box in \({\mathbb{R}}^n\). J Optim Theory Appl 117(3):553–574
Maculan Nelson, de Paula Geraldo Galdino (1989) A linear-time median-finding algorithm for projecting a vector on the simplex of \(\mathbb{R}^n\). Oper Res Lett 8(4):219–222
Michelot Christian (1986) A finite algorithm for finding the projection of a point onto the canonical simplex of \(\mathbb{R}^n\). J Optim Theory Appl 50(1):195–200
Morales José Luis, Nocedal Jorge (2011) Remark on algorithm 778: L-bfgs-b: Fortran subroutines for large-scale bound constrained optimization. ACM Trans Math Softw 38(1):7:1–7:4
Pardalos Panos M, Kovoor Naina (1990) An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds. Math Programm 46(1):321–328
Wright Stephen J (1987) Primal–dual interior point methods. SIAM, philadelphia