The algebraic degree of semidefinite programming

被引：64
|
作者：
Nie, Jiawang [1 ]
Ranestad, Kristian [2 ]
Sturmfels, Bernd [3 ]
机构：
[1] Univ Calif San Diego, Dept Math, La Jolla, CA 92093 USA
[2] Univ Oslo, Dept Math, N-0316 Oslo, Norway
[3] Univ Calif Berkeley, Dept Math, Berkeley, CA 94720 USA
来源：
MATHEMATICAL PROGRAMMING | 2010年 / 122卷 / 02期
基金：
美国国家科学基金会;
关键词：
Semidefinite programming; Algebraic degree; Genericity; Determinantal variety; Dual variety; Multidegree; Euler-Poincare characteristic; Chern class; OPTIMIZATION; VARIETIES; CURVES;
D O I：
10.1007/s10107-008-0253-6
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
Given a generic semidefinite program, specified by matrices with rational entries, each coordinate of its optimal solution is an algebraic number. We study the degree of the minimal polynomials of these algebraic numbers. Geometrically, this degree counts the critical points attained by a linear functional on a fixed rank locus in a linear space of symmetric matrices. We determine this degree using methods from complex algebraic geometry, such as projective duality, determinantal varieties, and their Chern classes.
引用
收藏
页码：379 / 405
页数：27
相关论文
共 50 条
  • [1] The algebraic degree of semidefinite programming
    Jiawang Nie
    Kristian Ranestad
    Bernd Sturmfels
    Mathematical Programming, 2010, 122 : 379 - 405
  • [2] A FORMULA FOR THE ALGEBRAIC DEGREE IN SEMIDEFINITE PROGRAMMING
    Dang Tuan Hiep
    KODAI MATHEMATICAL JOURNAL, 2016, 39 (03) : 484 - 488
  • [3] A characterization of the algebraic degree in semidefinite programming
    Hiep, Dang Tuan
    Giao, Nguyen Thi Ngoc
    Van, Nguyen Thi Mai
    COLLECTANEA MATHEMATICA, 2023, 74 (02) : 443 - 455
  • [4] A characterization of the algebraic degree in semidefinite programming
    Dang Tuan Hiep
    Nguyen Thi Ngoc Giao
    Nguyen Thi Mai Van
    Collectanea Mathematica, 2023, 74 : 443 - 455
  • [5] A general formula for the algebraic degree in semidefinite programming
    Graf von Bothmer, Hans-Christian
    Ranestad, Kristian
    BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 2009, 41 : 193 - 197
  • [6] Numerical algebraic geometry and semidefinite programming
    Hauenstein, Jonathan D.
    Liddell, Jr Alan C.
    McPherson, Sanesha
    Zhang, Yi
    RESULTS IN APPLIED MATHEMATICS, 2021, 11
  • [7] Semidefinite programming relaxations and algebraic optimization in control
    Parrilo, PA
    Lall, S
    EUROPEAN JOURNAL OF CONTROL, 2003, 9 (2-3) : 307 - 321
  • [8] ERROR BOUNDS AND SINGULARITY DEGREE IN SEMIDEFINITE PROGRAMMING
    Sremac, Stefan
    Woerdeman, Hugo J.
    Wolkowicz, Henry
    SIAM JOURNAL ON OPTIMIZATION, 2021, 31 (01) : 812 - 836
  • [9] THE DEGREE OF THE CENTRAL CURVE IN SEMIDEFINITE, LINEAR, AND QUADRATIC PROGRAMMING
    Hosten, S.
    Shankar, I
    Torres, A.
    MATEMATICHE, 2021, 76 (02): : 483 - 499
  • [10] A Semidefinite Programming Method for Moment Approximation in Stochastic Differential Algebraic Systems
    Lamperski, Andrew
    Dhople, Sairaj
    2017 IEEE 56TH ANNUAL CONFERENCE ON DECISION AND CONTROL (CDC), 2017,
12345