×

Projection onto a polyhedron that exploits sparsity. (English) Zbl 1346.90653

Summary: 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.

MSC:

90C20 Quadratic programming
90C06 Large-scale problems in mathematical programming
90C25 Convex programming
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. D. Andersen and K. D. Andersen, {\it Presolving in linear programming}, Math. Program., 71 (1995), pp. 221-245. · Zbl 0846.90068
[2] E. Anderson, Z. Bai, C. H. Bischof, S. Blackford, J. W. Demmel, J. J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. C. Sorensen, {\it LAPACK Users’ Guide}, 3rd ed., SIAM, Philadelphia, 1999. · Zbl 0934.65030
[3] J. Barzilai and J. M. Borwein, {\it Two point step size gradient methods}, IMA J. Numer. Anal., 8 (1988), pp. 141-148. · Zbl 0638.65055
[4] A. Beck and M. Teboulle, {\it Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems}, IEEE Trans. Image Process., 18 (2009), pp. 2419-2434. · Zbl 1371.94049
[5] A. Beck and M. Teboulle, {\it A fast iterative shrinkage-thresholding algorithm for linear inverse problems}, SIAM J. Imaging Sci., 2 (2009), pp. 183-202. · Zbl 1175.94009
[6] M. Bergounioux, K. Ito, and K. Kunisch, {\it Primal-dual strategy for optimal control problems}, SIAM J. Control Optim., 37 (1999), pp. 1176-1999. · Zbl 0937.49017
[7] M. Bergounioux and K. Kunisch, {\it Primal-dual strategy for state-constrained optimal control problem}, Comput. Optim. Appl., 22 (2002), pp. 193-224. · Zbl 1015.49026
[8] D. P. Bertsekas, {\it Nonlinear Programming}, Athena Scientific, Belmont, MA, 1999. · Zbl 1015.90077
[9] R. H. Byrd, J. Nocedal, and S. Solntsev, {\it An Algorithm for Quadratic \(ℓ_1\)-Regularized Optimization with a Flexible Active-Set Strategy}, Technical report, Northwestern University, 2014. · Zbl 1328.90097
[10] S. S. Chen, D. L. Donoho, and M. A. Saunders, {\it Atomic decomposition by basis pursuit}, SIAM J. Sci. Comput., 20 (1998), pp. 33-61. · Zbl 0919.94002
[11] Y. Chen, T. A. Davis, W. W. Hager, and S. Rajamanickam, {\it Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate}, ACM Trans. Math. Software, 35 (2009).
[12] F. H. Clarke, {\it Generalized gradients and applications}, Trans. Amer. Math. Soc., 205 (1975), pp. 247-262. · Zbl 0307.26012
[13] P. L. Combettes and J.-C. Pesquet, {\it Proximal splitting methods in signal processing}, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, H. H. Bauschke, R. S. Burachik, P. L. Combettes, V. Elser, D. R. Luke, and H. Wolkowicz, eds., Optim. Appl. 49, Springer, New York, 2011, pp. 185-212. · Zbl 1242.90160
[14] R. Cominetti, W. F. Mascarenhas, and P. J. S. Silva, {\it A Newton’s method for the continuous quadratic knapsack problem}, Math. Program Comput., 6 (2014), pp. 151-169. · Zbl 1328.65135
[15] A. R. Conn, N. I. M. Gould, D. Orban, and P. L. Toint, {\it A primal-dual trust-region algorithm for minimizing a non-convex function subject to general inequality and linear equality constraints}, Math. Program., 87 (1999), pp. 219-249.
[16] F. E. Curtis, Z. Han, and D. P. Robinson, {\it A globally convergent primal-dual active-set framework for large-scale convex quadratic optimization}, Comput. Optim. Appl., 60 (2015), pp. 311-341, http://dx.doi.org/10.1007/s10589-014-9681-9 doi:10.1007/s10589-014-9681-9. · Zbl 1309.90072
[17] J. M. Danskin, {\it The Theory of Max-Min and Its Applications to Weapons Allocation Problems}, Springer, New York, 1967. · Zbl 0154.20009
[18] T. A. Davis and W. W. Hager, {\it Modifying a sparse Cholesky factorization}, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 606-627. · Zbl 0929.65012
[19] T. A. Davis and W. W. Hager, {\it Multiple-rank modifications of a sparse Cholesky factorization}, SIAM J. Matrix Anal. Appl., 22 (2001), pp. 997-1013. · Zbl 1049.65021
[20] T. A. Davis and W. W. Hager, {\it Row modifications of a sparse Cholesky factorization}, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 621-639. · Zbl 1077.65026
[21] T. A. Davis and W. W. Hager, {\it Dual multilevel optimization}, Math. Program., 112 (2008), pp. 403-425. · Zbl 1145.90038
[22] T. A. Davis and W. W. Hager, {\it A sparse proximal implementation of the LP Dual Active Set Algorithm}, Math. Program., 112 (2008), pp. 275-301. · Zbl 1146.90037
[23] T. A. Davis and W. W. Hager, {\it Dynamic supernodes in sparse Cholesky update/downdate and triangular solves}, ACM Trans. Math. Software, 35 (2009).
[24] T. A. Davis, W. W. Hager, and J. T. Hungerford, {\it The separable convex quadratic knapsack problem}, ACM Trans. Math. Software, 42 (2016), pp. 1-25, http://dx.doi.org/10.1145/2828635 doi:10.1145/2828635. · Zbl 1369.65072
[25] E. D. Dolan and J. J. Moré, {\it Benchmarking optimization software with performance profiles}, Math. Program., 91 (2002), pp. 201-213. · Zbl 1049.90004
[26] J. J. Dongarra, J. D. Croz, S. Hammarling, and R. J. Hanson, {\it Algorithm 656: An extended set of Fortran basic linear algebra subprograms}, ACM Trans. Math. Software, 14 (1988), pp. 1-17, 18-32. · Zbl 0639.65016
[27] J. Dongarra, J. D. Croz, I. S. Duff, and S. Hammarling, {\it Algorithm 679: A set of level 3 basic linear algebra subprograms}, ACM Trans. Math. Software, 16 (1990), pp. 1-17, 18-28. · Zbl 0900.65116
[28] I. S. Duff, {\it MA57–A code for the solution of sparse symmetric definite and indefinite systems}, ACM Trans. Math. Software, 30 (2004), pp. 118-144. · Zbl 1070.65525
[29] N. I. M. Gould, D. Orban, and P. L. Toint, {\it GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization}, ACM Trans. Math. Software, 29 (2004), pp. 253-372. · Zbl 1068.90525
[30] L. Grippo, F. Lampariello, and S. Lucidi, {\it A nonmonotone line search technique for Newton’s method}, SIAM J. Numer. Anal., 23 (1986), pp. 707-716. · Zbl 0616.65067
[31] I. Griva, S. G. Nash, and A. Sofer, {\it Linear and Nonlinear Optimization}, SIAM, Philadelphia, 2009. · Zbl 1159.90002
[32] W. W. Hager and D. W. Hearn, {\it Application of the dual active set algorithm to quadratic network optimization}, Comput. Optim. Appl., 1 (1993), pp. 349-373. · Zbl 0791.90053
[33] W. W. Hager and G. Ianculescu, {\it Dual approximations in optimal control}, SIAM J. Control Optim., 22 (1984), pp. 423-465. · Zbl 0555.49022
[34] W. W. Hager, D. T. Phan, and H. Zhang, {\it Gradient-based methods for sparse recovery}, SIAM J. Imaging Sci., 4 (2011), pp. 146-165. · Zbl 1209.90266
[35] W. W. Hager and H. Zhang, {\it A new active set algorithm for box constrained optimization}, SIAM J. Optim., 17 (2006), pp. 526-557. · Zbl 1165.90570
[36] W. W. Hager, {\it The dual active set algorithm}, in Advances in Optimization and Parallel Computing, P. M. Pardalos, ed., North-Holland, Amsterdam, 1992, pp. 137-142. · Zbl 0814.90106
[37] W. W. Hager, {\it Analysis and implementation of a dual algorithm for constrained optimization}, J. Optim. Theory Appl., 79 (1993), pp. 427-462. · Zbl 0797.90092
[38] W. W. Hager, {\it The LP dual active set algorithm}, in High Performance Algorithms and Software in Nonlinear Optimization, R. D. Leone, A. Murli, P. M. Pardalos, and G. Toraldo, eds., Kluwer, Dordrecht, 1998, pp. 243-254. · Zbl 0942.65060
[39] W. W. Hager, {\it The dual active set algorithm and its application to linear programming}, Comput. Optim. Appl., 21 (2002), pp. 263-275. · Zbl 1017.90061
[40] W. W. Hager, {\it The dual active set algorithm and the iterative solution of linear programs}, in Novel Approaches to Hard Discrete Optimization, P. M. Pardalos and H. Wolkowicz, eds., Fields Inst. Commun. 37, 2003, pp. 95-107.
[41] A. J. Hoffman, {\it On approximate solutions of systems of linear inequalities}, J. Res. National Bureau Standards, 49 (1952), pp. 263-265.
[42] C. L. Lawson, R. J. Hanson, D. R. Kincaid, and F. T. Krogh, {\it Basic linear algebra subprograms for Fortran usage}, ACM Trans. Math. Software, 5 (1979), pp. 308-323. · Zbl 0412.65022
[43] W. Li, {\it Error bounds for piecewise convex quadratic programs and applications}, SIAM J. Control Optim., 33 (1995), pp. 1510-1529. · Zbl 0836.90125
[44] D. G. Luenberger and Y. Ye, {\it Linear and Nonlinear Programming}, Springer, New York, 2008. · Zbl 1207.90003
[45] D. G. Luenberger, {\it Optimization by Vector Space Methods}, John Wiley, New York, 1969. · Zbl 0176.12701
[46] Z.-Q. Luo and P. Tseng, {\it On the linear convergence of descent methods for convex essentially smooth minimization}, SIAM J. Control Optim., 30 (1992), pp. 408-425. · Zbl 0756.90084
[47] Z.-Q. Luo and P. Tseng, {\it Error bounds and convergence analysis of feasible descent methods: A general approach}, Ann. Oper. Res., 46 (1993), pp. 157-178. · Zbl 0793.90076
[48] Z.-Q. Luo and P. Tseng, {\it On the convergence rate of dual ascent methods for linearly constrained convex minimization}, Math. Oper. Res., 18 (1993), pp. 846-867. · Zbl 0804.90103
[49] Z. Lu and Y. Zhang, {\it An augmented Lagrangian approach for sparse principal component analysis}, Math. Program., 135 (2012), pp. 149-193. · Zbl 1263.90093
[50] J. Nocedal and S. J. Wright, {\it Numerical Optimization}, Springer, New York, 1999. · Zbl 0930.65067
[51] P. Tseng and S. Yun, {\it A coordinate gradient descent method for nonsmooth separable minimization}, Math. Program., 117 (2009), pp. 387-423. · Zbl 1166.90016
[52] M. Ulbrich, S. Ulbrich, and M. Heinkenschloss, {\it Semismooth Newton methods for operator equations in function spaces}, SIAM J. Optim., 13 (2003), pp. 805-842. · Zbl 1033.49039
[53] A. Wächter and L. T. Biegler, {\it On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming}, Math. Program., 106 (2006), pp. 25-57. · Zbl 1134.90542
[54] P.-W. Wang and C.-H. Lin, {\it Iteration complexity of feasible descent methods for convex optimization}, J. Mach. Learn. Res., 15 (2014), pp. 1523-1548. · Zbl 1319.90051
[55] P. Wolfe, {\it Convergence conditions for ascent methods}, SIAM Rev., 11 (1969), pp. 226-235. · Zbl 0177.20603
[56] P. Wolfe, {\it Convergence conditions for ascent methods II: Some corrections}, SIAM Rev., 13 (1971), pp. 185-188. · Zbl 0216.26901
[57] S. J. Wright, R. D. Nowak, and M. A. T. Figueiredo, {\it Sparse reconstruction by separable approximation}, IEEE Trans. Signal Process., 57 (2009), pp. 2479-2493. · Zbl 1391.94442
[58] Y. Zhang, {\it On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem}, SIAM J. Optim., 4 (1994), pp. 208-227. · Zbl 0803.90092
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.