A conjugate direction based simplicial decomposition framework for solving a specific class of dense convex quadratic programs. (English) Zbl 1432.90099
Summary: Many real-world applications can usually be modeled as convex quadratic problems. In the present paper, we want to tackle a specific class of quadratic programs having a dense Hessian matrix and a structured feasible set. We hence carefully analyze a simplicial decomposition like algorithmic framework that handles those problems in an effective way. We introduce a new master solver, called Adaptive Conjugate Direction Method, and embed it in our framework. We also analyze the interaction of some techniques for speeding up the solution of the pricing problem. We report extensive numerical experiments based on a benchmark of almost 1400 instances from specific and generic quadratic problems. We show the efficiency and robustness of the method when compared to a commercial solver (CPLEX).
MSC:
| 90C20 | Quadratic programming |
| 65K05 | Numerical mathematical programming methods |
| 90C25 | Convex programming |
Keywords:
simplicial decomposition; convex quadratic programming; dense Hessian matrix; column generationReferences:
| [1] | Beasley, J.E.: Portfolio optimization data. http://people.brunel.ac.uk/ mastjjb/jeb/orlib/files/ (2016) |
| [2] | Bertsekas, Dp, Convex Optimization Algorithms (2015), Belmont: Athena Scientific, Belmont · Zbl 1347.90001 |
| [3] | Bertsekas, Dp; Yu, H., A unifying polyhedral approximation framework for convex optimization, SIAM J. Optim., 21, 1, 333-360 (2011) · Zbl 1218.90154 · doi:10.1137/090772204 |
| [4] | Birgin, Eg; Martínez, Jm; Raydan, M., Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim., 10, 4, 1196-1211 (2000) · Zbl 1047.90077 · doi:10.1137/S1052623497330963 |
| [5] | Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049 |
| [6] | Buchheim, C.; Traversi, E., Quadratic combinatorial optimization using separable underestimators, INFORMS J. Comput., 30, 3, 424-437 (2018) · Zbl 1528.90208 · doi:10.1287/ijoc.2017.0789 |
| [7] | Cesarone, F., Tardella, F.: Portfolio datasets. http://host.uniroma3.it/docenti/cesarone/datasetsw3_tardella.html (2010) · Zbl 1411.91489 |
| [8] | Chen, Ss; Donoho, Dl; Saunders, Ma, Atomic decomposition by basis pursuit, SIAM Rev., 43, 1, 129-159 (2001) · Zbl 0979.94010 · doi:10.1137/S003614450037906X |
| [9] | Chu, Pc; Beasley, Je, A genetic algorithm for the multidimensional knapsack problem, J. Heuristics, 4, 1, 63-86 (1998) · Zbl 0913.90218 · doi:10.1023/A:1009642405419 |
| [10] | Clarkson, Kl, Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm, ACM Trans. Algorithms (TALG), 6, 4, 63 (2010) · Zbl 1300.90026 |
| [11] | Condat, L., Fast projection onto the simplex and the l1-ball, Math. Program., 158, 1, 575-585 (2016) · Zbl 1347.49050 · doi:10.1007/s10107-015-0946-6 |
| [12] | Cristofari, A., An almost cyclic 2-coordinate descent method for singly linearly constrained problems, Comput. Optim. Appl., 73, 2, 411-452 (2019) · Zbl 1414.90226 · doi:10.1007/s10589-019-00082-0 |
| [13] | Cristofari, A.; De Santis, M.; Lucidi, S.; Rinaldi, F., A two-stage active-set algorithm for bound-constrained optimization, J. Optim. Theory Appl., 172, 2, 369-401 (2017) · Zbl 1398.90170 · doi:10.1007/s10957-016-1024-9 |
| [14] | Curtis, Fe; Han, Z.; Robinson, Dp, A globally convergent primal-dual active-set framework for large-scale convex quadratic optimization, Comput. Optim. Appl., 60, 2, 311-341 (2015) · Zbl 1309.90072 · doi:10.1007/s10589-014-9681-9 |
| [15] | De Santis, M.; Di Pillo, G.; Lucidi, S., An active set feasible method for large-scale minimization problems with bound constraints, Comput. Optim. Appl., 53, 2, 395-423 (2012) · Zbl 1284.90075 · doi:10.1007/s10589-012-9506-7 |
| [16] | Demetrescu, C.; Goldberg, Av; Johnson, Ds, The Shortest Path Problem: Ninth DIMACS Implementation Challenge (2009), Providence: American Mathematical Soc., Providence |
| [17] | Desaulniers, G.; Desrosiers, J.; Solomon, Mm, Column Generation (2006), Berlin: Springer, Berlin |
| [18] | Djerdjour, M.; Mathur, K.; Salkin, H., A surrogate relaxation based algorithm for a general quadratic multi-dimensional knapsack problem, Oper. Res. Lett., 7, 5, 253-258 (1988) · Zbl 0654.90058 · doi:10.1016/0167-6377(88)90041-7 |
| [19] | Dolan, Ed; Moré, Jj, Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263 |
| [20] | Drake, J.: Benchmark instances for the multidimensional knapsack problem (2015) |
| [21] | Elzinga, J.; Moore, Tg, A central cutting plane algorithm for the convex programming problem, Math. Program., 8, 1, 134-145 (1975) · Zbl 0318.90048 · doi:10.1007/BF01580439 |
| [22] | Ferreau, Hj; Kirches, C.; Potschka, A.; Bock, Hg; Diehl, M., qpoases: a parametric active-set algorithm for quadratic programming, Math. Program. Comput., 6, 4, 327-363 (2014) · Zbl 1302.90146 · doi:10.1007/s12532-014-0071-1 |
| [23] | Furini, F.; Traversi, E.; Belotti, P.; Frangioni, A.; Gleixner, A.; Gould, N.; Liberti, L.; Lodi, A.; Misener, R.; Mittelmann, H.; Sahinidis, N.; Vigerske, S.; Wiegele, A., Qplib: a library of quadratic programming instances, Math. Program. Comput., 11, 237-265 (2018) · Zbl 1435.90099 · doi:10.1007/s12532-018-0147-4 |
| [24] | Glover, F., Kochenberger, G.: Critical event tabu search for multidimensional knapsack problems. In: Meta-Heuristics, pp. 407-427. Springer (1996) · Zbl 0877.90055 |
| [25] | Glover, F., Kochenberger, G., Alidaee, B., Amini, M.: Solving quadratic knapsack problems by reformulation and tabu search: single constraint case. In: Combinatorial and Global Optimization, pp. 111-121. World Scientific (2002) · Zbl 1041.90046 |
| [26] | Goffin, Jl; Gondzio, J.; Sarkissian, R.; Vial, Jp, Solving nonlinear multicommodity flow problems by the analytic center cutting plane method, Math. Program., 76, 1, 131-154 (1997) · Zbl 0881.90050 · doi:10.1007/BF02614381 |
| [27] | Goffin, Jl; Vial, Jp, Cutting planes and column generation techniques with the projective algorithm, J. Optim. Theory Appl., 65, 3, 409-429 (1990) · Zbl 0676.90041 · doi:10.1007/BF00939559 |
| [28] | Goffin, Jl; Vial, Jp, On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm, Math. Program., 60, 1, 81-92 (1993) · Zbl 0804.90087 · doi:10.1007/BF01580602 |
| [29] | Gondzio, J., Interior point methods 25 years later, Eur. J. Oper. Res., 218, 3, 587-601 (2012) · Zbl 1244.90007 · doi:10.1016/j.ejor.2011.09.017 |
| [30] | Gondzio, J.; González-Brevis, P., A new warmstarting strategy for the primal-dual column generation method, Math. Program., 152, 1-2, 113-146 (2015) · Zbl 1327.90389 · doi:10.1007/s10107-014-0779-8 |
| [31] | Gondzio, J.; González-Brevis, P.; Munari, P., New developments in the primal-dual column generation technique, Eur. J. Oper. Res., 224, 1, 41-51 (2013) · Zbl 1292.90318 · doi:10.1016/j.ejor.2012.07.024 |
| [32] | Gondzio, J.; González-Brevis, P.; Munari, P., Large-scale optimization with the primal-dual column generation method, Math. Program. Comput., 8, 1, 47-82 (2016) · Zbl 1334.90072 · doi:10.1007/s12532-015-0090-6 |
| [33] | Gondzio, J.; Kouwenberg, R., High-performance computing for asset-liability management, Oper. Res., 49, 6, 879-891 (2001) · Zbl 1163.90548 · doi:10.1287/opre.49.6.879.10015 |
| [34] | Gondzio, J.; Du Merle, O.; Sarkissian, R.; Vial, Jp, Accpm—a library for convex optimization based on an analytic center cutting plane method, Eur. J. Oper. Res., 94, 1, 206-211 (1996) · doi:10.1016/0377-2217(96)00169-5 |
| [35] | Gondzio, J.; Sarkissian, R.; Vial, Jp, Using an interior point method for the master problem in a decomposition approach, Eur. J. Oper. Res., 101, 3, 577-587 (1997) · Zbl 0916.90220 · doi:10.1016/S0377-2217(96)00182-8 |
| [36] | Gondzio, J.; Vial, Jp, Warm start and -subgradients in a cutting plane scheme for block-angular linear programs, Comput. Optim. Appl., 14, 17-36 (1999) · Zbl 0958.90057 · doi:10.1023/A:1008748810765 |
| [37] | Grippo, L.; Lampariello, F.; Lucidi, S., A nonmonotone line search technique for newton’s method, SIAM J. Numer. Anal., 23, 4, 707-716 (1986) · Zbl 0616.65067 · doi:10.1137/0723046 |
| [38] | Grippo, L.; Lampariello, F.; Lucidi, S., A truncated newton method with nonmonotone line search for unconstrained optimization, J. Optim. Theory Appl., 60, 3, 401-419 (1989) · Zbl 0632.90059 · doi:10.1007/BF00940345 |
| [39] | Grippo, L.; Lampariello, F.; Lucidi, S., A class of nonmonotone stabilization methods in unconstrained optimization, Numer. Math., 59, 1, 779-805 (1991) · Zbl 0724.90060 · doi:10.1007/BF01385810 |
| [40] | Hager, Ww; Zhang, H., A new active set algorithm for box constrained optimization, SIAM J. Optim., 17, 2, 526-557 (2006) · Zbl 1165.90570 · doi:10.1137/050635225 |
| [41] | Hearn, D.W., Lawphongpanich, S., Ventura, J.A.: Restricted simplicial decomposition: computation and extensions. In: Computation Mathematical Programming, pp. 99-118 (1987) · Zbl 0636.90027 |
| [42] | Holloway, Ca, An extension of the Frank and Wolfe method of feasible directions, Math. Program., 6, 1, 14-27 (1974) · Zbl 0283.90042 · doi:10.1007/BF01580219 |
| [43] | IBM: Cplex (version 12.6.3). https://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/ (2015) |
| [44] | Kiwiel, Kc, Methods of Descent for Nondifferentiable Optimization (2006), Berlin: Springer, Berlin |
| [45] | Levin, Ay, On an algorithm for the minimization of convex functions, Sov. Math. Dokl., 160, 1244-1247 (1965) · Zbl 0154.45001 |
| [46] | Markowitz, H., Portfolio selection, J. Finance, 7, 1, 77-91 (1952) |
| [47] | Michelot, C., 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 (1986) · Zbl 0571.90074 · doi:10.1007/BF00938486 |
| [48] | Munari, P.; Gondzio, J., Using the primal-dual interior point algorithm within the branch-price-and-cut method, Comput. Oper. Res., 40, 8, 2026-2036 (2013) · Zbl 1348.90478 · doi:10.1016/j.cor.2013.02.028 |
| [49] | Nesterov, Y.; Nemirovskii, A., Interior-Point Polynomial Algorithms in Convex Programming (1994), Philadelphia: SIAM, Philadelphia · Zbl 0824.90112 |
| [50] | Newman, Dj, Location of the maximum on unimodal surfaces, J. ACM (JACM), 12, 3, 395-398 (1965) · Zbl 0139.10402 · doi:10.1145/321281.321291 |
| [51] | Nocedal, J., Wright, S.J.: Conjugate gradient methods. In: Numerical Optimization, pp. 101-134 (2006) |
| [52] | Nocedal, J.; Wright, Sj, Sequential Quadratic Programming (2006), Berlin: Springer, Berlin |
| [53] | Palomar, Dp; Eldar, Yc, Convex Optimization in Signal Processing and Communications (2010), Cambridge: Cambridge University Press, Cambridge · Zbl 1200.90009 |
| [54] | Patriksson, M., The Traffic Assignment Problem: Models and Methods (2015), Mineola: Courier Dover Publications, Mineola |
| [55] | Rostami, B.; Chassein, A.; Hopf, M.; Frey, D.; Buchheim, C.; Malucelli, F.; Goerigk, M., The quadratic shortest path problem: complexity, approximability, and solution methods, Eur. J. Oper. Res., 268, 2, 473-485 (2018) · Zbl 1403.90645 · doi:10.1016/j.ejor.2018.01.054 |
| [56] | Rostami, B., Malucelli, F., Frey, D., Buchheim, C.: On the quadratic shortest path problem. In: International Symposium on Experimental Algorithms, pp. 379-390. Springer (2015) |
| [57] | Syam, Ss, A dual ascent method for the portfolio selection problem with multiple constraints and linked proposals, Eur. J. Oper. Res., 108, 1, 196-207 (1998) · Zbl 0952.91035 · doi:10.1016/S0377-2217(97)00048-9 |
| [58] | Tarasov, S.; Khachiian, L.; Erlikh, I., The method of inscribed ellipsoids, Dokl. Akad. Nauk SSSR, 298, 5, 1081-1085 (1988) · Zbl 0685.90077 |
| [59] | Tibshirani, R., Regression shrinkage and selection via the lasso, J. R. Stat. Soc. Ser. B (Methodol.), 58, 1, 267-288 (1996) · Zbl 0850.62538 |
| [60] | Ventura, Ja; Hearn, Dw, Restricted simplicial decomposition for convex constrained problems, Math. Program., 59, 1, 71-85 (1993) · Zbl 0801.90092 · doi:10.1007/BF01581238 |
| [61] | Von Hohenbalken, B., Simplicial decomposition in nonlinear programming algorithms, Math. Program., 13, 1, 49-68 (1977) · Zbl 0362.90086 · doi:10.1007/BF01584323 |
| [62] | WolframAlpha: Mathematica (version 11.3). http://www.wolfram.com/mathematica/ (2018) |
| [63] | Wright, M., The interior-point revolution in optimization: history, recent developments, and lasting consequences, Bull. Am. Math. Soc., 42, 1, 39-56 (2005) · Zbl 1114.90153 · doi:10.1090/S0273-0979-04-01040-7 |
| [64] | Wright, Sj, Primal-Dual Interior-Point Methods (1997), Philadelphia: SIAM, Philadelphia · Zbl 0863.65031 |
| [65] | Ye, Y., Interior Point Algorithms: Theory and Analysis (2011), Hoboken: Wiley, Hoboken |
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.
