Abstract
We introduce set-semidefinite optimization as a new field of vector optimization in infinite dimensions covering semidefinite and copositive programming. This unified approach is based on a special ordering cone, the so-called K-semidefinite cone for which properties are given in detail. Optimality conditions in the KKT form and duality results including the linear case are presented for K-semidefinite optimization problems. A penalty approach is developed for the treatment of the special constraint arising in K-semidefinite optimization problems.
References
- L.-F. Andersson, G. Chang, T. Elfving: Criteria for copositive matrices using simplices and barycentric coordinates, Linear Algebra Appl. 220 (1995) 9–30.https://doi.org/10.1016/0024-3795(94)00161-6Google Scholar
- A. Berman, R. J. Plemmons: Nonnegative Matrices in the Mathematical Sciences, Academic Press, New York (1979).https://doi.org/10.1016/B978-0-12-092250-5.50009-6Google Scholar
- E. Blum, W. Oettli: From optimization and variational inequalities to equilibrium problems, Math. Stud. 63 (1994) 123–145.Google Scholar
- I. M. Bomze: Linear-time copositivity detection for tridiagonal matrices and extension to block-tridiagonality, SIAM J. Matrix Anal. Appl. 21 (2000) 840–848.https://doi.org/10.1137/S0895479898341487Google Scholar
- I. M. Bomze, E. de Klerk: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming, J. Glob. Optim. 24 (2002) 163–185.https://doi.org/10.1023/A:1020209017701Google Scholar
- I. M. Bomze, M. Dür, E. de Klerk, C. Roos, A. J. Quist, T. Terlaky: On copositive programming and standard quadratic optimization problems, J. Glob. Optim. 18 (2000) 301–320.https://doi.org/10.1023/A:1026583532263Google Scholar
- I. M. Bomze, B. M. Pötscher: Game Theoretic Foundations of Evolutionary Stability, Springer, Berlin (1989).https://doi.org/10.1007/978-3-642-45660-2Google Scholar
- J. M. Borwein: Necessary and sufficient conditions for quadratic minimality, Numer. Funct. Anal. Optimization 5 (1982) 127–140.https://doi.org/10.1080/01630568208816135Google Scholar
- S. Bundfuss, M. Dür: Criteria for copositivity and approximations of the copositive cone, Preprint, Department of Mathematics, Darmstadt University of Technology, Darmstadt (2006).Google Scholar
- S. Bundfuss, M. Dür: Algorithmic copositivity detection by simplicial partition, Linear Algebra Appl. 428 (2008) 1511–1523.https://doi.org/10.1016/j.laa.2007.09.035Google Scholar
- S. Burer: On the copositive representation of binary and continuous nonconvex quadratic programs, Working paper, Department of Management Sciences, University of Iowa, Iowa City (2007).Google Scholar
- R. W. Cottle, G. J. Habetler, C. E. Lemke: On classes of copositive matrices, Linear Algebra Appl. 3 (1970) 295–310.https://doi.org/10.1016/0024-3795(70)90002-9Google Scholar
- R. W. Cottle, G. J. Habetler, C. E. Lemke: Quadratic forms semi-definite over convex cones, in: Proc. Princeton Sympos. Math. Programming (Princeton, 1967), H. W. Kuhn (ed.), Princeton University Press, Princeton (1970) 551–565.https://doi.org/10.1515/9781400869930-033Google Scholar
- G. Danninger: Role of copositivity in optimality criteria for nonconvex optimization problems, J. Optimization Theory Appl. 75 (1992) 535–558.https://doi.org/10.1007/BF00940491Google Scholar
- G. Danninger, I. M. Bomze: Using copositivity for global optimality criteria in concave quadratic programming problems, Math. Program. 62 (1993) 575–580.https://doi.org/10.1007/BF01585185Google Scholar
- E. de Klerk, M. Laurent, P. Parrillo: On the equivalence of algebraic approaches to the minimization of forms on the simplex, in: Positive Polynomials in Control, D. Henrion, A. Garulli (eds.), Lecture Notes in Control and Information Sciences 312, Springer, Berlin (2005) 121–132.https://doi.org/10.1007/10997703_7Google Scholar
- E. de Klerk, D. V. Pasechnik: Approximation of the stability number of a graph via copositive programming, SIAM J. Optim. 12 (2002) 875–892.https://doi.org/10.1137/S1052623401383248Google Scholar
- M. Fukuda, M. Yamashita, M. Kojima: Computational prospects on copositive programming, RIMS Kokyuroku 1526 (2006) 207–213.Google Scholar
- M. S. Gowda: A characterization of positive semidefinite operators on a Hilbert space, J. Optimization Theory Appl. 48 (1986) 419–425.https://doi.org/10.1007/BF00940568Google Scholar
- M. S. Gowda: Complementarity problems over locally compact cones, SIAM J. Control Optimization 27 (1989) 836–841.https://doi.org/10.1137/0327044Google Scholar
- K. P. Hadeler: On copositive matrices, Linear Algebra Appl. 49 (1983) 79–89.https://doi.org/10.1016/0024-3795(83)90095-2Google Scholar
- S.-P. Han, O. L. Mangasarian: A conjugate decomposition of the Euclidean space, Proc. Natl. Acad. Sci. USA 80 (1983) 5156–5157.https://doi.org/10.1073/pnas.80.16.5156Google Scholar
- S.-P. Han, O. L. Mangasarian: Conjugate cone characterization of positive definite and semidefinite matrices, Linear Algebra Appl. 56 (1984) 89–103.https://doi.org/10.1016/0024-3795(84)90116-2Google Scholar
- T. L. Hayden, J. Wells: Approximation by matrices positive semidefinite on a subspace, Linear Algebra Appl. 109 (1988) 115–130.https://doi.org/10.1016/0024-3795(88)90202-9Google Scholar
- L. Hogben, C. R. Johnson, R. Reams: The copositive completion problem, Linear Algebra Appl. 408 (2005) 207–211.https://doi.org/10.1016/j.laa.2005.06.019Google Scholar
- K. D. Ikramov, N. V. Savel’eva: Conditionally definite matrices, J. Math. Sci., New York 98 (2000) 1–50.https://doi.org/10.1007/BF02355379Google Scholar
- J. Jahn: Vector Optimization. Theory, Applications, and Extensions, Springer, Berlin (2004).https://doi.org/10.1007/978-3-540-24828-6Google Scholar
- J. Jahn: Introduction to the Theory of Nonlinear Optimization, 3rd Ed., Springer, Berlin (2007).https://doi.org/10.1007/978-3-540-49379-2Google Scholar
- F. Jarre, J. Stoer: Optimierung, Springer, Berlin (2004).https://doi.org/10.1007/978-3-642-18785-8Google Scholar
- W. Kaplan: A test for copositive matrices, Linear Algebra Appl. 313 (2000) 203–206.https://doi.org/10.1016/S0024-3795(00)00138-5Google Scholar
- W. Kaplan: A copositivity probe, Linear Algebra Appl. 337 (2001) 237–251.https://doi.org/10.1016/S0024-3795(01)00351-2Google Scholar
- H. Länger: Strictly copositive matrices and ESS’s, Arch. Math. 55 (1990) 516–520.https://doi.org/10.1007/BF01190275Google Scholar
- R. Loewy, H. Schneider: Positive operators on the n-dimensional ice cream cone, J. Math. Anal. Appl. 49 (1975) 375–392.https://doi.org/10.1016/0022-247X(75)90186-9Google Scholar
- K. Löwner: Über monotone Matrixfunktionen, Math. Z. 38 (1934) 177–216.https://doi.org/10.1007/BF01170633Google Scholar
- D. H. Martin: Conditional positivity of quadratic forms in Hilbert space, SIAM J. Math. Anal. 11 (1980) 1047–1057.https://doi.org/10.1137/0511092Google Scholar
- D. H. Martin: Finite criteria for conditional definiteness of quadratic forms, Linear Algebra Appl. 39 (1981) 9–21.https://doi.org/10.1016/0024-3795(81)90286-XGoogle Scholar
- H. Maurer, J. Zowe: First and second-order necessary and sufficient optimality conditions for infinite-dimensional programming problems, Math. Program. 16 (1979) 98–110.https://doi.org/10.1007/BF01582096Google Scholar
- T. S. Motzkin: Copositive quadratic forms, National Bureau of Standards Report 1818 (1952) 11–22.Google Scholar
- K. G. Murty, S. N. Kabadi: Some NP-complete problems in quadratic and linear programming, Math. Program. 39 (1987) 117–129.https://doi.org/10.1007/BF02592948Google Scholar
- P. A. Parrillo: Structured Semidefinite Programs and Semi-Algebraic Geometry Methods in Robustness and Optimization, PhD Thesis, California Institute of Technology, Pasadena (2000).Google Scholar
- J. Povh: Application of Semidefinite and Copositive Programming in Combinatorial Optimization, PhD Thesis, Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana (2006).Google Scholar
- J. Povh, F. Rendl: Copositive and semidefinite relaxations of the quadratic assignment problem, Manuscript, Department of Mathematics, University of Klagenfurt (2006).Google Scholar
- J. Povh, F. Rendl: A copositive programming approach to graph partitioning, SIAM J. Optim. 18 (2007) 223–241.https://doi.org/10.1137/050637467Google Scholar
- A. J. Quist, E. de Klerk, C. Roos, T. Terlaky: Copositive relaxation for general quadratic programming, Optim. Methods Softw. 9 (1998) 185–208.https://doi.org/10.1080/10556789808805692Google Scholar
- Y. Sawaragi, H. Nakayama, T. Tanino: Theory of Multiobjective Optimization, Academic Press, London (1985).Google Scholar
- H. C. Simpson, S. J. Spector: On copositive matrices and strong ellipticity for isotropic elastic materials, Arch. Ration. Mech. Anal. 84 (1983) 55–68.https://doi.org/10.1007/BF00251549Google Scholar
- J. F. Sturm, S. Zhang: On cones of nonnegative quadratic functions, Math. Oper. Res. 28 (2003) 246–267.https://doi.org/10.1287/moor.28.2.246.14485Google Scholar
- L. Vandenberghe, S. Boyd: Semidefinite programming, SIAM Rev. 38 (1996) 49–95.https://doi.org/10.1137/1038003Google Scholar
- H. Wolkowicz, R. Saigal, L. Vandenberghe (eds.): Handbook on Semidefinite Programming, Kluwer, Dordrecht (2000).https://doi.org/10.1007/978-1-4615-4381-7Google Scholar
- H. Väliaho: Criteria for copositive matrices, Linear Algebra Appl. 81 (1986) 19–34.https://doi.org/10.1016/0024-3795(86)90246-6Google Scholar
- H. Väliaho: Testing the definiteness of matrices on polyhedral cones, Linear Algebra Appl. 101 (1988) 136–165.https://doi.org/10.1016/0024-3795(88)90148-6Google Scholar
- H. Väliaho: Quadratic-programming criteria for copositive matrices, Linear Algebra Appl. 119 (1989) 163–182.https://doi.org/10.1016/0024-3795(89)90076-1Google Scholar
- J. Werner: Optimization, Theory and Applications, Vieweg, Braunschweig (1984).https://doi.org/10.1007/978-3-322-84035-6Google Scholar
Suggested citation
Published by Heldermann Verlag, 2008. Rights now held by Banach Press LLC.
