sums-of-squares – Optimization Online

Solving rank-constrained semidefinite programs in exact arithmetic

Published: 2016/02/01, Updated: 2016/09/19

Semi-definite Programming computer algebra, determinantal varieties, exact algorithms, linear matrix inequalities, polynomial optimization, rank constraints, semidefinite programming, spectrahedra, sums-of-squares

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 … Read more

A Hierarchy of Near-Optimal Policies for Multi-stage Adaptive Optimization

Published: 2009/06/26, Updated: 2009/06/27

Dimitris Bertsimas

Dan Iancu

Pablo A. Parrilo

Robust Optimization, Semi-definite Programming, Supply Chain Management inventory management, robust adaptive optimization, semidefinite programming, sums-of-squares

In this paper, we propose a new tractable framework for dealing with multi-stage decision problems affected by uncertainty, applicable to robust optimization and stochastic programming. We introduce a hierarchy of polynomial disturbance-feedback control policies, and show how these can be computed by solving a single semidefinite programming problem. The approach yields a hierarchy parameterized by … Read more