ML p(r)ior | Solving rank-constrained semidefinite programs in exact arithmetic

### 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.

Highlights - Most important sentences from the article

# 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

Highlights - Most important sentences from the article

2017-01-05
1701.01207 | math.OC

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2019-01-30
1901.11023 | cs.CC

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2017-10-23
1710.08350 | cs.LO

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2018-08-12
1808.03994 | math.OC

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

Highlights - Most important sentences from the article

2018-10-30
1810.12588 | cs.SC

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

Highlights - Most important sentences from the article

2019-01-05
1901.02360 | math.OC

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2017-07-10
1707.02757 | cs.DS

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

Highlights - Most important sentences from the article

2018-04-05
1804.01796 | math.OC

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article