Copositive optimization – recent developments and applications. (English) Zbl 1262.90129
An interesting overview on the copositive optimization is presented pointing the diversity of its formulations: continuous, discrete, deterministic, stochastic. Some ideas of approximation hierarchies are sketched, together with some complexity issues. The study of the role of copositivity for local and global optimality conditions reveal new particular results in the case of quadratic optimization. The author pays attention to recursive procedures and to decomposition and adaptive approaches to the copositivity detection. The presentation of the copositive optimization concludes with some interesting success applications: the role of copositivity in the convex underestimation in quadratic optimization problems, finding Lyapunov functions for switched dynamical systems in optimal control, strengthening bounds for a maximum clique problem, finding the best known asymptotic bound for crossing numbers.
Reviewer: Gabriela Cristescu (Arad)
MSC:
| 90C25 | Convex programming |
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 90C46 | Optimality conditions and duality in mathematical programming |
Keywords:
clique number; completely positive matrix; convexity gap; robust optimization; standard quadratic optimizationReferences:
| [1] | P.A. Amaral, I.M. Bomze, J.J. Júdice, Copositivity and constrained fractional quadratic problems. Technical Report 2010-05, ISDS, Univ. Vienna. Available from: <http://www.optimization-online.org/DB_HTML/2010/06/2641.html>; P.A. Amaral, I.M. Bomze, J.J. Júdice, Copositivity and constrained fractional quadratic problems. Technical Report 2010-05, ISDS, Univ. Vienna. Available from: <http://www.optimization-online.org/DB_HTML/2010/06/2641.html> · Zbl 1312.90049 |
| [2] | Anitescu, M.; Cremer, J. F.; Potra, F. A., On the existence of solutions to complementarity formulations of contact problems with friction, (Complementarity and Variational Problems (Baltimore, MD, 1995) (1997), SIAM: SIAM Philadelphia, PA), 12-21 · Zbl 0887.70009 |
| [3] | Anitescu, M.; Potra, F. A., A time-stepping method for stiff multibody dynamics with contact and friction, International Journal for Numerical Methods in Engineering, 55, 753-784 (2002) · Zbl 1027.70001 |
| [4] | Anstreicher, K. M.; Burer, S., Computable representations for convex hulls of low-dimensional quadratic forms, Mathematical Programming, 124, 33-43 (2010) · Zbl 1198.90311 |
| [5] | Azé, D.; Hiriart-Urruty, J.-B., Optimal Hoffman-type estimates in eigenvalue and semidefinite inequality constraints, Journal of Global Optimization, 24, 133-147 (2002) · Zbl 1047.90066 |
| [6] | Bellare, M.; Rogaway, P., The complexity of approximating a nonlinear program, Mathematical Programming, 69, 429-441 (1995) · Zbl 0839.90104 |
| [7] | Berman, A.; Shaked-Monderer, N., Completely Positive Matrices (2003), World Scientific: World Scientific River Edge, NJ · Zbl 1030.15022 |
| [8] | Bomze, I. M., Remarks on the recursive structure of copositivity, Journal of Information and Optimization Sciences, 8, 243-260 (1987) · Zbl 0631.15017 |
| [9] | Bomze, I. M., Copositivity conditions for global optimality in indefinite quadratic programming problems, Czechosl Journal of Operations Research, 1, 7-19 (1992) · Zbl 0972.90051 |
| [10] | Bomze, I. M., Detecting all evolutionarily stable strategies, Journal of Optimization Theory and Applications, 75, 313-329 (1992) · Zbl 0795.92017 |
| [11] | Bomze, I. M., Block pivoting and shortcut strategies for detecting copositivity, Linear Algebra and its Applications, 248, 161-184 (1996) · Zbl 0862.65036 |
| [12] | Bomze, I. M., On standard quadratic optimization problems, Journal of Global Optimization, 13, 369-387 (1998) · Zbl 0916.90214 |
| [13] | Bomze, I. M., Linear-time copositivity detection for tridiagonal matrices and extension to block-tridiagonality, SIAM Journal on Matrix Analysis and Applications, 21, 840-848 (2000) · Zbl 0953.65028 |
| [14] | Bomze, I. M., Regularity versus degeneracy in dynamics, games, and optimization: A unified approach to different aspects, SIAM Review, 44, 394-414 (2002) · Zbl 1021.91007 |
| [15] | Bomze, I. M., Perron-Frobenius property of copositive matrices, and a block copositivity criterion, Linear Algebra and its Applications, 429, 68-71 (2008) · Zbl 1154.15308 |
| [16] | Bomze, I. M., Copositive optimization, (Floudas, C.; Pardalos, P., Encyclopedia of Optimization (2009), Springer: Springer New York), 561-564 |
| [17] | Bomze, I. M., Global optimization: A quadratic programming perspective, (Nonlinear Optimization. Nonlinear Optimization, Lecture Notes in Math, vol. 1989 (2010), Springer: Springer Berlin), 1-53 · Zbl 1193.90005 |
| [18] | Bomze, I. M.; de Klerk, E., Solving standard quadratic optimization problems via linear, semidefinite and copositive programming, Journal of Global Optimization, 24, 163-185 (2002) · Zbl 1047.90038 |
| [19] | Bomze, I. M.; Dür, M.; de Klerk, E.; Roos, C.; Quist, A. J.; Terlaky, T., On copositive programming and standard quadratic optimization problems, Journal of Global Optimization, 18, 301-320 (2000) · Zbl 0970.90057 |
| [20] | I.M. Bomze, G. Eichfelder, Copositivity detection by difference-of-convex decomposition and Ω;<http://www.optimization-online.org/DB_HTML/2010/01/2523.html>; I.M. Bomze, G. Eichfelder, Copositivity detection by difference-of-convex decomposition and Ω;<http://www.optimization-online.org/DB_HTML/2010/01/2523.html> · Zbl 1267.65060 |
| [21] | Bomze, I. M.; Frommlet, F.; Locatelli, M., Copositivity cuts for improving SDP bounds on the clique number, Mathematical Programming, 124, 13-32 (2010) · Zbl 1198.90312 |
| [22] | Bomze, I. M.; Jarre, F., A note on Burer’s copositive representation of mixed-binary QPs, Optimization Letters, 4, 465-472 (2010) · Zbl 1200.90134 |
| [23] | Bomze, I. M.; Jarre, F.; Rendl, F., Quadratic factorization heuristics for copositive programming, Mathematical Programming Computation, 3, 37-57 (2011) · Zbl 1219.90134 |
| [24] | Bomze, I. M.; Lemaréchal, C., Necessary conditions for local optimality in difference-of-convex programming, Journal of Convex Analysis, 17, 673-680 (2010) · Zbl 1201.90199 |
| [25] | Bomze, I. M.; Schachinger, W., Multi-standard quadratic optimization: interior point methods and cone programming reformulation, Computational Optimization and Applications, 45, 237-256 (2010) · Zbl 1187.90210 |
| [26] | I.M. Bomze, W. Schachinger, G. Uchida, Think co(mpletely) positive! - properties, examples and a commented bibliography on copositive optimization, Journal of Global Optimization, in press.; I.M. Bomze, W. Schachinger, G. Uchida, Think co(mpletely) positive! - properties, examples and a commented bibliography on copositive optimization, Journal of Global Optimization, in press. · Zbl 1268.90051 |
| [27] | Borwein, J. M., Necessary and sufficient conditions for for quadratic minimality, Numerical Functional Analysis and Optimization, 5, 127-140 (1982) · Zbl 0507.90091 |
| [28] | Brogliato, B.; ten Dam, A.; Paoli, L.; Génot, F.; Abadie, M., Numerical simulation of finite dimensional multibody nonsmooth mechanical systems, ASME Applied Mechanics Reviews, 55, 107-150 (2002) |
| [29] | Buliga, M., Four applications of majorization to convexity in the calculus of variations, Linear Algebra and its Applications, 429, 1528-1545 (2008) · Zbl 1160.49011 |
| [30] | Bundfuss, S.; Dür, M., Algorithmic copositivity detection by simplicial partition, Linear Algebra and its Applications, 428, 1511-1523 (2008) · Zbl 1138.15007 |
| [31] | Bundfuss, S.; Dür, M., An adaptive linear approximation algorithm for copositive programs, SIAM Journal on Optimization, 20, 30-53 (2009) · Zbl 1187.90187 |
| [32] | Bundfuss, S.; Dür, M., Copositive Lyapunov functions for switched systems over cones, Systems & Control Letters, 58, 342-345 (2009) · Zbl 1159.93021 |
| [33] | Burer, S., On the copositive representation of binary and continuous nonconvex quadratic programs, Mathematical Programming, 120, 479-495 (2009) · Zbl 1180.90234 |
| [34] | S. Burer, Copositive programming. In: M.F. Anjos, J.B. Lasserre, (Eds.), Handbook of Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications, International Series in Operations Research and Management Science, Springer, New York, in press.; S. Burer, Copositive programming. In: M.F. Anjos, J.B. Lasserre, (Eds.), Handbook of Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications, International Series in Operations Research and Management Science, Springer, New York, in press. · Zbl 1334.90098 |
| [35] | Burer, S.; Anstreicher, K. M.; Dür, M., The difference between 5×5 doubly nonnegative and completely positive matrices, Linear Algebra and its Applications, 431, 1539-1552 (2009) · Zbl 1175.15026 |
| [36] | S. Burer, H. Dong, Separation and Relaxation for cones of quadratic forms, Working paper, Department of Management Sciences, University of Iowa, Iowa City IA. Available from: <http://www.optimization-online.org/DB_HTML/2010/05/2621.html>; S. Burer, H. Dong, Separation and Relaxation for cones of quadratic forms, Working paper, Department of Management Sciences, University of Iowa, Iowa City IA. Available from: <http://www.optimization-online.org/DB_HTML/2010/05/2621.html> |
| [37] | Busygin, S., Copositive programming, (Floudas, C.; Pardalos, P., Encyclopedia of Optimization (2009), Springer: Springer New York), 564-567 |
| [38] | Camlıbel, M. K.; Schumacher, J. M., Copositive Lyapunov functions, (Blondel, V.; Megretski, A., Unsolved Problems in Mathematical Systems and Control Theory (2004), Princeton University Press: Princeton University Press Princeton NJ), 189-193, Available from: · Zbl 1052.93002 |
| [39] | Coleman, T.; Liu, J., An interior Newton method for quadratic programming, Mathematical Programming, 85, 491-523 (1999) · Zbl 0980.90099 |
| [40] | Contesse, L. B., Une caractérisation complète des minima locaux, Numerical Mathematics, 34, 315-332 (1980) · Zbl 0422.90061 |
| [41] | Cottle, R. W.; Habetler, G. J.; Lemke, C. E., Quadratic forms semi-definite over convex cones, (Proceedings of the Princeton Symposium on Mathematical Programming (Princeton Univ., 1967) (1970), Princeton Univ. Press: Princeton Univ. Press Princeton, N.J), 551-565 · Zbl 0221.15018 |
| [42] | Dacorogna, B., Necessary and sufficient conditions for strong ellipticity of isotropic functions in any dimension, Discrete and Continuous Dynamic Systems-Series B, 1, 257-263 (2001) · Zbl 1055.35045 |
| [43] | G. Danninger, A recursive algorithm for determining (strict) copositivity of a symmetric matrix, in: XIV Symposium on Operations Research (Ulm, 1989), Frankfurt am Main: Hain, volume 62 of Methods Oper. Res., 1990, pp. 45-52.; G. Danninger, A recursive algorithm for determining (strict) copositivity of a symmetric matrix, in: XIV Symposium on Operations Research (Ulm, 1989), Frankfurt am Main: Hain, volume 62 of Methods Oper. Res., 1990, pp. 45-52. · Zbl 0713.65033 |
| [44] | Danninger, G.; Bomze, I. M., Using copositivity for global optimality criteria in concave quadratic programming problems, Mathematical Programming, 62, 575-580 (1993) · Zbl 0803.90097 |
| [45] | de Klerk, E., The complexity of optimizing over a simplex, hypercube or sphere: A short survey, Central European Journal of Operations Research, 16, 111-125 (2008) · Zbl 1152.90607 |
| [46] | E. de Klerk, C. Dobre, D.V. Pasechnik, Numerical block diagonalization of matrix \(^{∗;}\); E. de Klerk, C. Dobre, D.V. Pasechnik, Numerical block diagonalization of matrix \(^{∗;}\) · Zbl 1225.90098 |
| [47] | de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R.; Salazar, G., Improved bounds for the crossing numbers of \(K_{m,n}\) and \(K_n\), SIAM Journal on Discrete Mathematics, 20, 189-202 (2006) · Zbl 1111.05029 |
| [48] | de Klerk, E.; Pasechnik, D. V., Approximation of the stability number of a graph via copositive programming, SIAM Journal on Optimization, 12, 875-892 (2002) · Zbl 1035.90058 |
| [49] | de Klerk, E.; Pasechnik, D. V., A linear programming reformulation of the standard quadratic optimization problem, Journal of Global Optimization, 37, 75-84 (2007) · Zbl 1127.90051 |
| [50] | de Klerk, E.; Pasechnik, D. V.; Schrijver, A., Reduction of symmetric semidefinite programs using the regular \(^∗\)-representation, Mathematical Programming Series B, 109, 613-624 (2007) · Zbl 1200.90136 |
| [51] | Diananda, P. H., On non-negative forms in real variables some or all of which are non-negative, Proceedings of the Cambridge Philosophical Society, 58, 17-25 (1962) · Zbl 0108.04803 |
| [52] | C. Dobre, Semidefinite programming approaches for structured combinatorial optimization problems. Ph.d. dissertation, Univ. Tilburg, The Netherlands, 2011.; C. Dobre, Semidefinite programming approaches for structured combinatorial optimization problems. Ph.d. dissertation, Univ. Tilburg, The Netherlands, 2011. |
| [53] | H. Dong, Symmetric tensor approximation hierarchies for the completely positive cone. Working paper, Department of Management Sciences, University of Iowa, Iowa City, IA. Available from: <http://www.optimization-online.org/DB_HTML/2010/11/2791.html>; H. Dong, Symmetric tensor approximation hierarchies for the completely positive cone. Working paper, Department of Management Sciences, University of Iowa, Iowa City, IA. Available from: <http://www.optimization-online.org/DB_HTML/2010/11/2791.html> |
| [54] | Dong, H.; Anstreicher, K., A note on “5×5 completely positive matrices”, Linear Algebra and its Application, 433, 1001-1004 (2010) · Zbl 1191.15027 |
| [55] | H. Dong, K. Anstreicher, Separating Doubly Nonnegative and Completely Positive Matrices. Working paper, Department of Management Sciences, University of Iowa, Iowa City, IA. Available from: <http://www.optimization-online.org/DB_HTML/2010/03/2562.html>; H. Dong, K. Anstreicher, Separating Doubly Nonnegative and Completely Positive Matrices. Working paper, Department of Management Sciences, University of Iowa, Iowa City, IA. Available from: <http://www.optimization-online.org/DB_HTML/2010/03/2562.html> |
| [56] | Dukanovic, I.; Rendl, F., Copositive programming motivated bounds on the stability and the chromatic numbers, Mathematical Programming, 121, 249-268 (2010) · Zbl 1194.90109 |
| [57] | Dür, M., Copositive programming - A survey, (Diehl, M.; Glineur, F.; Jarlebring, E.; Michiels, W., Recent Advances in Optimization and its Applications in Engineering (2010), Springer: Springer Berlin Heidelberg New York), 3-20 |
| [58] | Eichfelder, G.; Jahn, J., Set-semidefinite optimization, Journal of Convex Analysis, 15, 767-801 (2008) · Zbl 1172.90013 |
| [59] | G. Eichfelder, J. Povh, On reformulations of nonconvex quadratic programs over convex cones by set-semidefinite constraints. Preprint 342 Institut fuer Angewandte Mathematik, Martensstraße 3, D-91058 Erlangen. Available from: <http://www.optimization-online.org/DB_HTML/2010/12/2843.html>; G. Eichfelder, J. Povh, On reformulations of nonconvex quadratic programs over convex cones by set-semidefinite constraints. Preprint 342 Institut fuer Angewandte Mathematik, Martensstraße 3, D-91058 Erlangen. Available from: <http://www.optimization-online.org/DB_HTML/2010/12/2843.html> · Zbl 1244.90182 |
| [60] | A. Engau, M.F. Anjos, I.M. Bomze, Cutting planes and copositive programming for stable set. Technical Report 2011-04, ISOR, Univ. Vienna, 2011.; A. Engau, M.F. Anjos, I.M. Bomze, Cutting planes and copositive programming for stable set. Technical Report 2011-04, ISOR, Univ. Vienna, 2011. · Zbl 1272.90045 |
| [61] | Facchinei, F.; Pang, J.-S., Finite-dimensional variational inequalities and complementarity problems, Springer Series in Operations Research, vol. I (2003), Springer-Verlag: Springer-Verlag New York · Zbl 1062.90001 |
| [62] | Facchinei, F.; Pang, J.-S., Finite-dimensional variational inequalities and complementarity problems, Springer Series in Operations Research, vol. II (2003), Springer-Verlag: Springer-Verlag New York · Zbl 1062.90002 |
| [63] | Fletcher, R., Practical Methods of Optimization, Constrained Optimization, vol. 2 (1981), Wiley: Wiley New York · Zbl 0474.65043 |
| [64] | Gill, P. E.; Murray, W.; Wright, M. H., Practical Optimization (1981), Academic Press: Academic Press London · Zbl 0503.90062 |
| [65] | Gourion, D.; Seeger, A., Critical angles in polyhedral convex cones: Numerical and statistical considerations, Mathematical Programming, 123, 173-198 (2010) · Zbl 1188.52004 |
| [66] | E. Guslitser, Uncertatinty-immunized solutions in linear programming. Master thesis, Technion, Israeli Institute of Technology, IE&M faculty, 2002.; E. Guslitser, Uncertatinty-immunized solutions in linear programming. Master thesis, Technion, Israeli Institute of Technology, IE&M faculty, 2002. |
| [67] | Gvozdenović, N.; Laurent, M., The operator Ψ for the chromatic number of a graph, SIAM Journal on Optimization, 19, 572-591 (2008) · Zbl 1213.05080 |
| [68] | Hadeler, K. P., On copositive matrices, Linear Algebra and its Applications, 49, 79-89 (1983) · Zbl 0506.15016 |
| [69] | Hadjicostas, P., Copositive matrices and Simpson’s paradox, Linear Algebra and its Applications, 264, 475-488 (1997) · Zbl 0955.62063 |
| [70] | Hahnloser, R. H.R.; Seung, H. S.; Slotine, J.-J. E., Permitted and forbidden sets in symmetric threshold-linear networks, Neural Comput., 15, 621-638 (2003) · Zbl 1046.92003 |
| [71] | Hall, M.; Newman, M., Copositive and completely positive quadratic forms, Proceedings of the Cambridge Philosophical Society, 59, 329-339 (1963) · Zbl 0124.25302 |
| [72] | Håstad, J., Clique is hard to approximate within ∣\(V∣^{1− &z.epsiv; } \), Acta Math., 182, 105-142 (1999) · Zbl 0989.68060 |
| [73] | Haynsworth, E.; Hoffman, A. J., Two remarks on copositive matrices, Linear Algebra and its Application, 2, 387-392 (1969) · Zbl 0185.08004 |
| [74] | Hiriart-Urruty, J.-B.; Seeger, A., A variational approach to copositive matrices, SIAM Review, 52, 593-629 (2010) · Zbl 1207.15037 |
| [75] | Humes, C.; Ou, J.; Kumar, P. R., The delay of open Markovian queueing networks: Uniform functional bounds, heavy traffic pole multiplicities, and stability, Mathematics of Operations Research, 22, 921-954 (1997) · Zbl 0904.60074 |
| [76] | Ikramov, K. D., An algorithm, linear with respect to time, for verifying the copositivity of an acyclic matrix, Computational Mathematics and Mathematical Physics, 42, 1701-1703 (2002) · Zbl 1081.15538 |
| [77] | Ikramov, K. D.; Savel’eva, N. V., Conditionally definite matrices, Journal of Mathematical Sciences, 98, 1-50 (2000) · Zbl 0954.65035 |
| [78] | Iusem, A.; Seeger, A., Searching for critical angles in a convex cone, Mathematical Programming, 120, 3-25 (2009) · Zbl 1163.52003 |
| [79] | D.H. Jacobson, Extensions of linear-quadratic control, optimization and matrix theory. London: Academic Press [Harcourt Brace Jovanovich Publishers], Mathematics in Science and Engineering, vol. 133, 1977.; D.H. Jacobson, Extensions of linear-quadratic control, optimization and matrix theory. London: Academic Press [Harcourt Brace Jovanovich Publishers], Mathematics in Science and Engineering, vol. 133, 1977. · Zbl 0446.49001 |
| [80] | F. Jarre, Burer’s key assumption for semidefinite and doubly nonnegative relaxations. Optimization Letters. Available from: <http://www.optimization-online.org/DB_HTML/2010/09/2744.html>; F. Jarre, Burer’s key assumption for semidefinite and doubly nonnegative relaxations. Optimization Letters. Available from: <http://www.optimization-online.org/DB_HTML/2010/09/2744.html> |
| [81] | Johnson, C. R.; Reams, R., Spectral theory of copositive matrices, Linear Algebra and its Applications, 395, 275-281 (2005) · Zbl 1064.15007 |
| [82] | Júdice, J. J.; Sherali, H. D.; Ribeiro, I. M., The eigenvalue complementarity problem, Computational Optimization and Applications, 37, 139-156 (2007) · Zbl 1181.90261 |
| [83] | Kumar, P. R.; Meyn, S. P., Duality and linear programs for stability and performance analysis of queueing networks and scheduling policies, IEEE Transactions on Automatic Control, 41, 4-17 (1996) · Zbl 0845.90053 |
| [84] | Kwon, Y., On Hadamard stability for compressible viscoelastic constitutive equations, Journal of Non-Newtonian Fluid Mechanics, 65, 151-163 (1996) |
| [85] | C. Lacoursière, Splitting methods for dry frictional contact problems in rigid multibody systems: Preliminary performance results, in: Conference Proceedings from SIGRAD2003, Umea˚, Sweden, 2003, pp. 20-21.; C. Lacoursière, Splitting methods for dry frictional contact problems in rigid multibody systems: Preliminary performance results, in: Conference Proceedings from SIGRAD2003, Umea˚, Sweden, 2003, pp. 20-21. |
| [86] | Lasserre, J. B., Global optimization with polynomials and the problem of moments, SIAM Journal on Optimization, 11, 796-817 (2000/01) · Zbl 1010.90061 |
| [87] | Laurent, M.; Rendl, F., Semidefinite programming and integer programming, (Aardal, K.; Nemhauser, G.; Weismantel, R., Handbook on Discrete Optimization (2005), Elsevier: Elsevier Amsterdam), 393-514 · Zbl 1194.90066 |
| [88] | Leonardi, E.; Mellia, M.; Ajmone Marsan, M.; Neri, F., On the throughput achievable by isolated and interconnected input-queueing switches under multiclass traffic, (INFOCOM 2002. INFOCOM 2002, Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3 (2002), IEEE), 1605-1614 |
| [89] | Liu, J.-Q.; Song, T.-T.; Du, D.-Z., On the necessary and sufficient condition of the local optimal solution of quadratic programming, Chinese Annals of Mathematics, 3, 625-630 (1982), (English abstract) · Zbl 0514.90068 |
| [90] | M. Locatelli, F. Schoen, On convex envelopes and underestimators for bivariate functions. Available from: <http://www.optimization-online.org/DB_HTML/2009/11/2462.html>; M. Locatelli, F. Schoen, On convex envelopes and underestimators for bivariate functions. Available from: <http://www.optimization-online.org/DB_HTML/2009/11/2462.html> |
| [91] | Lovász, L., On the Shannon capacity of a graph, IEEE Transactions on Information Theory, IT-25, 1-7 (1979) · Zbl 0395.94021 |
| [92] | Lovász, L.; Schrijver, A., Cones of matrices and set-functions and 0-1 optimization, SIAM Journal on Optimization, 1, 166-190 (1991) · Zbl 0754.90039 |
| [93] | Majthay, A., Optimality conditions for quadratic programming, Mathematical Programming, 1, 359-365 (1971) · Zbl 0246.90038 |
| [94] | Martin, D. H.; Jacobson, D. H., Copositive matrices and definiteness of quadratic forms subject to homogeneous linear inequality constraints, Linear Algebra and its Applications, 35, 227-258 (1981) · Zbl 0451.15015 |
| [95] | Matsubayashi, N.; Nishino, H., An application of Lemke’s method to a class of Markov decision problems, European Journal of Operational Research, 116, 584-590 (1999) · Zbl 1009.90124 |
| [96] | McEliece, R.; Rodemich, E.; Rumsey, H., The Lovász’ bound and some generalizations, Journal of Combinatorics, Information & System Sciences, 3, 134-152 (1978) · Zbl 0408.05031 |
| [97] | Mesbahi, M.; Safonov, M. G.; Papavassilopoulos, G. P., Bilinearity and complementarity in robust control, (Advances in Linear Matrix Inequality Methods in Control. Advances in Linear Matrix Inequality Methods in Control, Advances in Design and Control, vol. 2 (2000), SIAM: SIAM Philadelphia, PA), 269-292 · Zbl 0965.93046 |
| [98] | Morrison, J. R.; Kumar, P. R., New linear program performance bounds for queueing networks, Journal of Optimization Theory and Applications, 100, 575-597 (1999) · Zbl 0949.90019 |
| [99] | Morrison, J. R.; Kumar, P. R., New linear program performance bounds for closed queueing networks, Discrete Event Dynamics Systems, 11, 291-317 (2001) · Zbl 1027.90017 |
| [100] | Motzkin, T. S.; Straus, E. G., Maxima for graphs and a new proof of a theorem of Turán, Canadian Journal of Mathematics, 17, 533-540 (1965) · Zbl 0129.39902 |
| [101] | Murty, K. G., Linear complementarity, linear and nonlinear programming, Sigma Series in Applied Mathematics, vol. 3 (1988), Heldermann Verlag: Heldermann Verlag Berlin · Zbl 0634.90037 |
| [102] | Murty, K. G.; Kabadi, S. N., Some NP-complete problems in quadratic and nonlinear programming, Mathematical Programming, 39, 117-129 (1987) · Zbl 0637.90078 |
| [103] | Nadler, E., Nonnegativity of bivariate quadratic functions on a triangle, Computer Aided Geometric Design, 9, 195-205 (1992) · Zbl 0758.65007 |
| [104] | Nahas, N. H., On the crossing number of \(K_{m,n}\), Electronic Journal of Combinatorics, 10 (2003) · Zbl 1023.05039 |
| [105] | K. Natarajan, C.P. Teo, Z. Zheng, Mixed zero-one linear programs under objective uncertainty: a completely positive representation. Operations Research. Available from: <http://www.optimization-online.org/DB_FILE/2009/08/2365.pdf>; K. Natarajan, C.P. Teo, Z. Zheng, Mixed zero-one linear programs under objective uncertainty: a completely positive representation. Operations Research. Available from: <http://www.optimization-online.org/DB_FILE/2009/08/2365.pdf> |
| [106] | National Bureau of Standards Report 1818 (1952). Projects and Publications of the National Applied Mathematics Laboratories, pp. 11-12. Quarterly Report, April through June 1952.; National Bureau of Standards Report 1818 (1952). Projects and Publications of the National Applied Mathematics Laboratories, pp. 11-12. Quarterly Report, April through June 1952. |
| [107] | Ozdaglar, A.; Tseng, P., Existence of global minima for constrained optimization, Journal of Optimization Theory and Applications, 128, 523-546 (2006) · Zbl 1144.90016 |
| [108] | Parrilo, P. A., Semidefinite programming relaxations for semialgebraic problems, Mathematical Programming, 96, 293-320 (2003) · Zbl 1043.14018 |
| [109] | Peña, J.; Vera, J.; Zuluaga, L. F., Computing the stability number of a graph via linear and semidefinite programming, SIAM Journal on Optimization, 18, 87-105 (2007) · Zbl 1176.90611 |
| [110] | Pinto da Costa, A.; Seeger, A., Cone-constrained eigenvalue problems: Theory and algorithms, Computational Optimization and Applications, 45, 25-57 (2010) · Zbl 1193.65039 |
| [111] | Povh, J.; Rendl, F., A copositive programming approach to graph partitioning, SIAM Journal on Optimization, 18, 223-241 (2007) · Zbl 1143.90025 |
| [112] | Povh, J.; Rendl, F., Copositive and semidefinite relaxations of the quadratic assignment problem, Discrete Optimization, 6, 231-241 (2009) · Zbl 1167.90597 |
| [113] | Preisig, J. C., Copositivity and the minimization of quadratic functions with nonnegativity and quadratic equality constraints, SIAM Journal on Control and Optimization, 34, 1135-1150 (1996) · Zbl 0853.90105 |
| [114] | Putinar, M., Positive polynomials on compact semi-algebraic sets, Indiana University Mathematics Journal, 42, 969-984 (1993) · Zbl 0796.12002 |
| [115] | Qian, R. X.; DeMarco, C. L., An approach to robust stability of matrix polytopes through copositive homogeneous polynomials, IEEE Transactions on Automatic Control, 37, 848-852 (1992) · Zbl 0760.93064 |
| [116] | Quist, A. J.; de Klerk, E.; Roos, C.; Terlaky, T., Copositive relaxation for general quadratic programming, Optimization Methods and Software, 9, 185-208 (1998) · Zbl 0904.90126 |
| [117] | Schachinger, W.; Bomze, I., A conic duality Frank-Wolfe-type theorem via exact penalization in quadratic optimization, Mathematics of Operations Research, 34, 83-91 (2009) · Zbl 1218.90151 |
| [118] | Schmüdgen, K., The K-moment problem for compact semi-algebraic sets, Annals of Mathematics, 289, 203-206 (1991) · Zbl 0744.44008 |
| [119] | Schrijver, A., A comparison of the Delsarte and Lovasz bounds, IEEE Transactions on Information Theory, IT-25, 425-429 (1979) · Zbl 0444.94009 |
| [120] | Stengle, G., A Nullstellensatz and a Positivstellensatz in semialgebraic geometry, Annals of Mathematics, 207, 87-97 (1973) · Zbl 0253.14001 |
| [121] | Tawarmalani, M.; Sahinidis, N. V., Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Mathematical Programming, 99, 563-591 (2004) · Zbl 1062.90041 |
| [122] | Turán, P., A note of welcome, Journal of Graph Theory, 1, 7-9 (1977) |
| [123] | Väliaho, H., Testing the definiteness of matrices on polyhedral cones, Linear Algebra and its Applications, 101, 135-165 (1988) · Zbl 0646.65039 |
| [124] | Vandenberghe, L.; Boyd, S.; Comanor, C., Generalized Chebychev bounds via semidefinite programming, SIAM Review, 49, 52-64 (2007) · Zbl 1151.90512 |
| [125] | V.A. Yakubovich, S-procedure in nonlinear control theory, Vestnik Leningradskogo Universiteta, Ser. Matematika, Series 1, vol. 13, 1997, pp. 62-77. English translation in Vestnik Leningrad Univ., 1977, vol. 4, pp. 73-93.; V.A. Yakubovich, S-procedure in nonlinear control theory, Vestnik Leningradskogo Universiteta, Ser. Matematika, Series 1, vol. 13, 1997, pp. 62-77. English translation in Vestnik Leningrad Univ., 1977, vol. 4, pp. 73-93. · Zbl 0232.93010 |
| [126] | E.A. Yıldırım, On the accuracy of uniform polyhedral approximations of the copositive cone, Optimization Methods and Software. Available from: <http://www.optimization-online.org/DB_HTML/2009/07/2342.html>; E.A. Yıldırım, On the accuracy of uniform polyhedral approximations of the copositive cone, Optimization Methods and Software. Available from: <http://www.optimization-online.org/DB_HTML/2009/07/2342.html> |
| [127] | Zarankiewicz, K., On a problem of P. Turán concerning graphs, Fundamenta Mathematicae, 41, 137-145 (1954) · Zbl 0055.41605 |
| [128] | J. Zilinskas, M. Dür, Depth-first simplicial partition for copositivity detection, with an application to maxclique, Optimization Methods and Software, in press.; J. Zilinskas, M. Dür, Depth-first simplicial partition for copositivity detection, with an application to maxclique, Optimization Methods and Software, in press. · Zbl 1226.65037 |
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.
