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.

Contact details are reproduced from the original publication and may be historical.

Johannes Jahn

Department Mathematik, Universität Erlangen-Nürnberg, Martensstr. 3, 91058 Erlangen, Germany

jahn@am.uni-erlangen.de
  1. 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
  2. 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
  3. E. Blum, W. Oettli: From optimization and variational inequalities to equilibrium problems, Math. Stud. 63 (1994) 123–145.Google Scholar
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. M. Fukuda, M. Yamashita, M. Kojima: Computational prospects on copositive programming, RIMS Kokyuroku 1526 (2006) 207–213.Google Scholar
  19. 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
  20. M. S. Gowda: Complementarity problems over locally compact cones, SIAM J. Control Optimization 27 (1989) 836–841.https://doi.org/10.1137/0327044Google Scholar
  21. K. P. Hadeler: On copositive matrices, Linear Algebra Appl. 49 (1983) 79–89.https://doi.org/10.1016/0024-3795(83)90095-2Google Scholar
  22. 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
  23. 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
  24. 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
  25. 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
  26. 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
  27. J. Jahn: Vector Optimization. Theory, Applications, and Extensions, Springer, Berlin (2004).https://doi.org/10.1007/978-3-540-24828-6Google Scholar
  28. 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
  29. F. Jarre, J. Stoer: Optimierung, Springer, Berlin (2004).https://doi.org/10.1007/978-3-642-18785-8Google Scholar
  30. 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
  31. W. Kaplan: A copositivity probe, Linear Algebra Appl. 337 (2001) 237–251.https://doi.org/10.1016/S0024-3795(01)00351-2Google Scholar
  32. H. Länger: Strictly copositive matrices and ESS’s, Arch. Math. 55 (1990) 516–520.https://doi.org/10.1007/BF01190275Google Scholar
  33. 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
  34. K. Löwner: Über monotone Matrixfunktionen, Math. Z. 38 (1934) 177–216.https://doi.org/10.1007/BF01170633Google Scholar
  35. 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
  36. 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
  37. 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
  38. T. S. Motzkin: Copositive quadratic forms, National Bureau of Standards Report 1818 (1952) 11–22.Google Scholar
  39. 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
  40. 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
  41. 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
  42. J. Povh, F. Rendl: Copositive and semidefinite relaxations of the quadratic assignment problem, Manuscript, Department of Mathematics, University of Klagenfurt (2006).Google Scholar
  43. 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
  44. 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
  45. Y. Sawaragi, H. Nakayama, T. Tanino: Theory of Multiobjective Optimization, Academic Press, London (1985).Google Scholar
  46. 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
  47. 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
  48. L. Vandenberghe, S. Boyd: Semidefinite programming, SIAM Rev. 38 (1996) 49–95.https://doi.org/10.1137/1038003Google Scholar
  49. 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
  50. 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
  51. 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
  52. 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
  53. J. Werner: Optimization, Theory and Applications, Vieweg, Braunschweig (1984).https://doi.org/10.1007/978-3-322-84035-6Google Scholar

G. Eichfelder, J. Jahn. “Set-Semidefinite Optimization.” Journal of Convex Analysis 15 (2008), No. 4, 767–801. https://doi.org/10.68381/jca15051