×

zbMATH — the first resource for mathematics

Random projections for quadratic programs. (English) Zbl 07241668
Summary: Random projections map a set of points in a high dimensional space to a lower dimensional one while approximately preserving all pairwise Euclidean distances. Although random projections are usually applied to numerical data, we show in this paper that they can be successfully applied to quadratic programming formulations over a set of linear inequality constraints. Instead of solving the higher-dimensional original problem, we solve the projected problem more efficiently. This yields a feasible solution of the original problem. We prove lower and upper bounds of this feasible solution w.r.t. the optimal objective function value of the original problem. We then discuss some computational results on randomly generated instances, as well as a variant of Markowitz’ portfolio problem. It turns out that our method can find good feasible solutions of very large instances.
MSC:
90C20 Quadratic programming
60B20 Random matrices (probabilistic aspects)
Software:
CPLEX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achlioptas, D., Database-friendly random projections: Johnson-Lindenstrauss with binary coins, J. Comput. Syst. Sci., 66, 671-687 (2003) · Zbl 1054.68040
[2] Ailon, N., Chazelle, B.: Approximate nearest neighbors and fast Johnson-Lindenstrauss lemma. In: Proceedings of the Symposium on the Theory Of Computing, Volume ’06 of STOC. ACM, Seattle (2006) · Zbl 1301.68232
[3] Boutsidis, C., Zouzias, A., Drineas, P.: Random projections for \(k\)-means clustering. In: Advances in Neural Information Processing Systems, NIPS. NIPS Foundation, La Jolla, pp. 298-306 (2010)
[4] Dasgupta, S.: Experiments with random projection. In: Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, pp. 143-151. Morgan Kaufman, San Francisco (2000)
[5] Dorn, W., Duality in quadratic programming, Q. Appl. Math., 18, 2, 155-162 (1960) · Zbl 0101.37003
[6] Gould, N., Toint, P.: A quadratic programming bibliography. In: Technical Report 2000-2001. RAL Numerical Analysis Group (2001)
[7] IBM: ILOG CPLEX 12.8 User’s Manual. IBM (2017)
[8] Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the Symposium on the Theory Of Computing, Volume 30 of STOC, pp. 604-613. ACM, New York (1998) · Zbl 1029.68541
[9] Indyk, P.; Naor, A., Nearest neighbor preserving embeddings, ACM Trans. Algorithms, 3, 3, 31 (2007) · Zbl 1192.68748
[10] Johnson, W.; Lindenstrauss, J.; Hedlund, G., Extensions of Lipschitz mappings into a Hilbert space, Conference in Modern Analysis and Probability, 189-206 (1984), Providence, RI: AMS, Providence, RI · Zbl 0539.46017
[11] Kane, D.; Nelson, J., Sparser Johnson-Lindenstrauss transforms, J. ACM, 61, 1, 4 (2014) · Zbl 1295.68134
[12] Liberti, L.; Vu, K., Barvinok’s naive algorithm in distance geometry, Oper. Res. Lett., 46, 476-481 (2018) · Zbl 07165712
[13] Markowitz, H., Portfolio selection, J. Finance, 7, 1, 77-91 (1952)
[14] May, J.; Smith, R., Random polytopes: their definition, generation and aggregate properties, Math. Program., 24, 39-54 (1982) · Zbl 0491.90060
[15] Paul, S.; Boutsidis, C.; Magdon-Ismail, M.; Drineas, P., Random projections for linear support vector machines, ACM Trans Knowl Discov Data, 8, 4, 22:1-22:25 (2014)
[16] Pilanci, M., Wainwright, M.: Randomized sketches of convex programs with sharp guarantees. In: International Symposium on Information Theory (ISIT), pp. 921-925. IEEE, Piscataway (2014) · Zbl 1359.90097
[17] Pilanci, M.; Wainwright, M., Newton sketch: a linear time optimization algorithm with linear-quadratic convergence, SIAM J. Optim., 27, 1, 205-245 (2017) · Zbl 06690582
[18] Shim, J., A survey of quadratic programming applications to business and economics, Int. J. Syst. Sci., 14, 1, 105-115 (1983) · Zbl 0505.90081
[19] Vavasis, S., Quadratic programming is in NP, Inf. Process. Lett., 36, 73-77 (1990) · Zbl 0719.90052
[20] Vempala, S.: The random projection method. In: Number 65 in DIMACS Series in Discrete Mathematics and Theoretical Computer Science. AMS, Providence, RI (2004) · Zbl 1058.68063
[21] Venkatasubramanian, S., Wang, Q.: The Johnson-Lindenstrauss transform: an empirical study. In: Algorithm Engineering and Experiments, Volume 13 of ALENEX, pp. 164-173. SIAM, Providence, RI (2011) · Zbl 1430.68388
[22] Vershynin, R., High-dimensional Probability (2018), Cambridge: CUP, Cambridge
[23] Vu, K.; Poirion, P-L; D’Ambrosio, C.; Liberti, L.; Lodi, A., Random projections for quadratic programs over a Euclidean ball, Integer Programming and Combinatorial Optimization (IPCO), 442-452 (2019), New York: Springer, New York · Zbl 1436.90098
[24] Vu, K.; Poirion, P-L; Liberti, L., Random projections for linear programming, Math. Oper. Res., 43, 4, 1051-1071 (2018) · Zbl 1440.90024
[25] Vu, K.; Poirion, P-L; Liberti, L., Gaussian random projections for Euclidean membership problems, Discrete Appl. Math., 253, 93-102 (2019) · Zbl 1415.68259
[26] Woodruff, D., Sketching as a tool for linear algebra, Found. Trends Theor. Comput. Sci., 10, 1-2, 1-157 (2014)
[27] Yang, J.; Meng, X.; Mahoney, M., Quantile regression for large-scale applications, SIAM J. Sci. Comput., 36, 5, S78-S110 (2014) · Zbl 1314.68391
[28] Zhang, L., Mahdavi, M., Jin, R., Yang, T., Zhu, S.: Recovering the optimal solution by dual random projection. In: Shalev-Shwartz S., Steinwart I. (eds) Conference on Learning Theory (COLT), Volume 30 of Proceedings of Machine Learning Research, pp. \(135-157. \langle\) jmlr.org \(\rangle (2013)\)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.