### Solving rank-constrained semidefinite programs in exact arithmetic

**2016-02-01**

1602.00431 | cs.SY

We consider the problem of minimizing a linear function over an affine
section of the cone of positive semidefinite matrices, with the additional
constraint that the feasible matrix has prescribed rank. When the rank
constraint is active, this is a non-convex optimization problem, otherwise it
is a semidefinite program. Both find numerous applications especially in
systems control theory and combinatorial optimization, but even in more general
contexts such as polynomial optimization or real algebra. While numerical
algorithms exist for solving this problem, such as interior-point or
Newton-like algorithms, in this paper we propose an approach based on symbolic
computation. We design an exact algorithm for solving rank-constrained
semidefinite programs, whose complexity is essentially quadratic on natural
degree bounds associated to the given optimization problem: for subfamilies of
the problem where the size of the feasible matrix is fixed, the complexity is
polynomial in the number of variables. The algorithm works under assumptions on
the input data: we prove that these assumptions are generically satisfied. We
also implement it in Maple and discuss practical experiments.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2015-06-01**

1506.00575 | math.OC

We propose a new algorithm to solve optimization problems of the form $\min
f(X)$ for a smooth funct… show more

**2017-01-05**

1701.01207 | math.OC

Regularization techniques are widely employed in optimization-based
approaches for solving ill-posed… show more

**2016-01-12**

1601.02712 | cs.DS

In this paper we present a connection between two dynamical systems arising
in entirely different co… show more

**2019-02-28**

1902.11281 | cs.DM

We model "fair" dimensionality reduction as an optimization problem. A
central example is the fair P… show more

**2019-01-30**

1901.11023 | cs.CC

The Semialgebraic Orbit Problem is a fundamental reachability question that
arises in the analysis o… show more

**2018-10-12**

1810.05440 | cs.LG

Shuffled linear regression is the problem of performing a linear regression
fit to a dataset for whi… show more

**2017-10-23**

1710.08350 | cs.LO

We consider reasoning and minimization in systems of polynomial ordinary
differential equations (ode… show more

**2018-11-25**

1811.10062 | cs.SC

We consider the problem of finding exact sums of squares (SOS) decompositions
for certain classes of… show more

**2018-08-12**

1808.03994 | math.OC

We study time-varying semidefinite programs (TV-SDPs), which are semidefinite
programs whose data (a… show more

**2018-10-30**

1810.12588 | cs.SC

Symmetric tensor decomposition is an important problem with applications in
several areas for exampl… show more

**2019-01-05**

1901.02360 | math.OC

The paper proves sum-of-square-of-rational-function based representations
(shortly, sosrf-based repr… show more

**2017-04-24**

1704.07462 | math.OC

In this paper, we study polynomial norms, i.e. norms that are the
$d^{\text{th}}$ root of a degree-$… show more

**2017-07-10**

1707.02757 | cs.DS

Several fundamental problems that arise in optimization and computer science
can be cast as follows:… show more

**2018-04-05**

1804.01796 | math.OC

Consider the problem of minimizing a quadratic objective subject to quadratic
equations. We study th… show more

**2018-03-21**

1803.07974 | math.AG

We consider the problem of finding the isolated common roots of a set of
polynomial functions defini… show more

**2015-11-11**

1511.03730 | cs.CC

In this paper we present a deterministic polynomial time algorithm for
testing if a symbolic matrix … show more