Projection onto a polyhedron that exploits sparsity. An algorithm is developed for projecting a point onto a polyhedron. The algorithm solves a dual version of the projection problem and then uses the relationship between the primal and dual to recover the projection. The techniques in the paper exploit sparsity. Sparse reconstruction by separable approximation (SpaRSA) is used to approximately identify active constraints in the polyhedron, and the dual active set algorithm (DASA) is used to compute a high precision solution. A linear convergence result is established for SpaRSA that does not require the strong concavity of the dual to the projection problem, and an earlier R-linear convergence rate is strengthened to a Q-linear convergence property. An algorithmic framework is developed for combining SpaRSA with an asymptotically preferred algorithm such as DASA. It is shown that only the preferred algorithm is executed asymptotically. Numerical results are given using the polyhedra associated with the Netlib LP test set. A comparison is made to the interior point method contained in the general purpose open source software package IPOPT for nonlinear optimization, and to the commercial package CPLEX, which contains an implementation of the barrier method that is targeted to problems with the structure of the polyhedral projection problem.
Keywords for this software
References in zbMATH (referenced in 9 articles )
Showing results 1 to 9 of 9.
- Cristofari, Andrea; De Santis, Marianna; Lucidi, Stefano; Rinaldi, Francesco: An active-set algorithmic framework for non-convex optimization problems over the simplex (2020)
- Li, Xudong; Sun, Defeng; Toh, Kim-Chuan: On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope (2020)
- Zhang, Ning: A symmetric Gauss-Seidel based method for a class of multi-period mean-variance portfolio selection problems (2020)
- Ghadimi, Saeed; Lan, Guanghui; Zhang, Hongchao: Generalized uniformly optimal methods for nonlinear programming (2019)
- Hager, William W.; Zhang, Hongchao: Inexact alternating direction methods of multipliers for separable convex optimization (2019)
- Tsachev, Tsvetomir; Veliov, Vladimir M.; Widder, Andreas: Set-membership estimations for the evolution of infectious diseases in heterogeneous populations (2017)
- Xudong Li, Defeng Sun, Kim-Chuan Toh: On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope (2017) arXiv
- Hager, William W.; Zhang, Hongchao: An active set algorithm for nonlinear optimization with polyhedral constraints (2016)
- Hager, William W.; Zhang, Hongchao: Projection onto a polyhedron that exploits sparsity (2016)