×

Multi-standard quadratic optimization: Interior point methods and cone programming reformulation. (English) Zbl 1187.90210

Summary: A Standard Quadratic Optimization Problem (StQP) consists of maximizing a (possibly indefinite) quadratic form over the standard simplex. Likewise, in a multi-StQP we have to maximize a (possibly indefinite) quadratic form over the Cartesian product of several standard simplices (of possibly different dimensions). Among many other applications, multi-StQPs occur in machine learning problems. Several converging monotone interior point methods are established, which differ from the usual ones used in cone programming. Further, we prove an exact cone programming reformulation for establishing rigorous yet affordable bounds and finding improving directions.

MSC:

90C20 Quadratic programming
90C51 Interior-point methods

Software:

NewtonKKTqp; PRMLT
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Absil, P.-A., Tits, A.: Newton-KKT interior-point methods for indefinite quadratic programming. Comput. Optim. Appl. 36, 5–41 (2007) · Zbl 1278.90288 · doi:10.1007/s10589-006-8717-1
[2] Baratchart, L., Berthod, M., Pottier, L.: Optimization of positive generalized polynomials under p constraints. J. Convex Anal. 5, 353–379 (1998) · Zbl 0914.90237
[3] Baum, L.E., Eagon, J.A.: An inequality with applications to statistical prediction for function of Markov processes and to a model of ecology. Bull. Am. Math. Soc. 73, 360–363 (1967) · Zbl 0157.11101 · doi:10.1090/S0002-9904-1967-11751-8
[4] Bishop, C.M.: Pattern Recognition and Machine Learning. Springer, Berlin (2007) · Zbl 1107.68072
[5] Bomze, I.M.: On standard quadratic optimization problems. J. Glob. Optim. 13, 369–387 (1998) · Zbl 0916.90214 · doi:10.1023/A:1008369322970
[6] Bomze, I.M.: Regularity vs. degeneracy in dynamics, games, and optimization: a unified approach to different aspects. SIAM Rev. 44, 394–414 (2002) · Zbl 1021.91007 · doi:10.1137/S00361445003756
[7] Bomze, I.M., Danninger, G.: A finite algorithm for solving general quadratic problems. J. Glob. Optim. 4, 1–16 (1994) · Zbl 0809.90107 · doi:10.1007/BF01096531
[8] Bomze, I.M., de Klerk, E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Glob. Optim. 24, 163–185 (2002) · Zbl 1047.90038 · doi:10.1023/A:1020209017701
[9] Bomze, I.M., Dür, M., de Klerk, E., Quist, A., Roos, C., Terlaky, T.: On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18, 301–320 (2000) · Zbl 0970.90057 · doi:10.1023/A:1026583532263
[10] Bouveyron, C., Girard, S.: Robust supervised classification with Gaussian mixtures: learning from data with uncertain labels. In: Brito, P. (ed.) Compstat 2008, vol. II (CD), pp. 129–136. Physica-Verlag, Heidelberg (2008)
[11] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge Univ. Press, Cambridge (2004) · Zbl 1058.90049
[12] Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. (2009). doi: 10.1007/s10107-008-0223-z · Zbl 1180.90234
[13] Chang, C.-C., Lin, C.-J.: Training {\(\nu\)}-support vector classifiers: theory and algorithms. Neural Comput. 13, 2119–2147 (2001) · Zbl 0993.68080 · doi:10.1162/089976601750399335
[14] de Angelis, P.L., Pardalos, P.M., Toraldo, G.: Quadratic problems with box constraints. In: Bomze, I.M., Csendes, T., Horst, R., Pardalos, P.M. (eds.) Developments in Global Optimization, pp. 73–93. Kluwer, Dordrecht (1997) · Zbl 0886.90130
[15] Ferris, M.C., Munson, T.S.: Interior-point methods for massive support vector machines. SIAM J. Optim. 13, 783–804 (2003) · Zbl 1039.90092 · doi:10.1137/S1052623400374379
[16] Fine, S., Scheinberg, K.: Efficient SVM training using low-rank kernel representations. J. Mach. Learn. Res. 2, 243–264 (2001) · Zbl 1037.68112 · doi:10.1162/15324430260185619
[17] Grippo, L., Sciandrone, M.: On the convergence of the block nonlinear Gauss–Seidel method under convex constraints. Oper. Res. Lett. 26, 127–136 (2000) · Zbl 0955.90128 · doi:10.1016/S0167-6377(99)00074-7
[18] Hofbauer, J., Sigmund, K.: Evolutionary Games and Population Dynamics. Cambridge Univ. Press, Cambridge (1998) · Zbl 0914.90287
[19] Hummel, R.A., Zucker, S.W.: On the foundations of relaxation labeling processes. IEEE Trans. Pattern Anal. Mach. Intell. 5, 267–287 (1983) · Zbl 0523.90086 · doi:10.1109/TPAMI.1983.4767390
[20] Joachims, T.: Learning to Classify Text Using Support Vector Machines–Methods, Theory and Algorithms. Springer, New York (2002)
[21] Lucidi, S., Palagi, L., Risi, A., Sciandrone, M.: A convergent decomposition algorithm for support vector machines. Comput. Optim. Appl. 38, 217–234 (2007) · Zbl 1172.90443 · doi:10.1007/s10589-007-9044-x
[22] Lyubich, Y., Maistrowskii, G.D., Ol’khovskii, Yu.G.: Selection-induced convergence to equilibrium in a single-locus autosomal population. Prob. Inform. Transm. 16, 66–75 (1980) · Zbl 0458.92011
[23] Pelillo, M.: The dynamics of nonlinear relaxation labeling processes. J. Math. Imaging Vis. 7, 309–323 (1997) · Zbl 1493.68385 · doi:10.1023/A:1008255111261
[24] Schachinger, W., Bomze, I.M.: A conic duality Frank–Wolfe type theorem via exact penalization in quadratic optimization. Math. Oper. Res. 34, 83–91 (2009) · Zbl 1218.90151 · doi:10.1287/moor.1080.0345
[25] Torsello, A., Pelillo, M.: Continuous-time relaxation labeling processes. Pattern Recogn. 33, 1897–1908 (2000) · Zbl 02180914 · doi:10.1016/S0031-3203(99)00174-0
[26] Tseng, P.: Convergence properties of Dikin’s affine scaling algorithm for nonconvex quadratic minimization. J. Glob. Optim. 30, 285–300 (2004) · Zbl 1066.90076 · doi:10.1007/s10898-004-8276-x
[27] Tseng, P.: A scaled projected reduced-gradient method for linearly constrained smooth optimization. Preprint, Univ. of Washington. Available at http://www.math.washington.edu/\(\sim\)tseng/papers/sprg.pdf , last accessed Aug. 08 (2007, submitted)
[28] Ye, Y.: On affine scaling algorithms for nonconvex quadratic programming. Math. Program. 56, 285–300 (1992) · Zbl 0767.90065 · doi:10.1007/BF01580903
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.