All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Exact algorithms for semidefinite programs with degenerate feasible set

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F21%3A00348008" target="_blank" >RIV/68407700:21230/21:00348008 - isvavai.cz</a>

  • Result on the web

    <a href="https://doi.org/10.1016/j.jsc.2020.11.001" target="_blank" >https://doi.org/10.1016/j.jsc.2020.11.001</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1016/j.jsc.2020.11.001" target="_blank" >10.1016/j.jsc.2020.11.001</a>

Alternative languages

  • Result language

    angličtina

  • Original language name

    Exact algorithms for semidefinite programs with degenerate feasible set

  • Original language description

    Given symmetric matrices A0,A1,...,An of size m with rational entries, the set of real vectors x=(x1,...,xn) such that the matrix A0+x1A1++xnAn has non-negative eigenvalues is called a spectrahedron. Minimization of linear functions over spectrahedra is called semidefinite programming. Such problems appear frequently in control theory and real algebra, especially in the context of nonnegativity certificates for multivariate polynomials based on sums of squares. Numerical software for semidefinite programming are mostly based on interior point methods, assuming non-degeneracy properties such as the existence of an interior point in the spectrahedron. In this paper, we design an exact algorithm based on symbolic homotopy for solving semidefinite programs without assumptions on the feasible set, and we analyze its complexity. Because of the exactness of the output, it cannot compete with numerical routines in practice. However, we prove that solving such problems can be done in polynomial time if either n or m is fixed.

  • Czech name

  • Czech description

Classification

  • Type

    J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database

  • CEP classification

  • OECD FORD branch

    10102 - Applied mathematics

Result continuities

  • Project

  • Continuities

    I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Others

  • Publication year

    2021

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Name of the periodical

    Journal of Symbolic Computation

  • ISSN

    0747-7171

  • e-ISSN

    1095-855X

  • Volume of the periodical

    104

  • Issue of the periodical within the volume

    May

  • Country of publishing house

    GB - UNITED KINGDOM

  • Number of pages

    18

  • Pages from-to

    942-959

  • UT code for WoS article

    000598670000041

  • EID of the result in the Scopus database

    2-s2.0-85097046553