We address the long-standing problem of computing the region of attraction (ROA) of a target set (typically a neighborhood of an equilibrium point) of a controlled nonlinear system with polynomial dynamics and semialgebraic state and input constraints. We show that the ROA can be computed by solving a convex linear programming (LP) problem over the … Read more
We study the numerical solution of the problem $\min_{X \ge 0} \|BX-c\|2$, where $X$ is a symmetric square matrix, and $B$ a linear operator, such that $B^*B$ is invertible. With $\rho$ the desired fractional duality gap, we prove $O(\sqrt{m}\log\rho^{-1})$ iteration complexity for a simple primal-dual interior point method directly based on those for linear programs … Read more
We introduce in this paper an optimal first-order method that allows an easy and cheap evaluation of the local Lipschitz constant of the objective’s gradient. This constant must ideally be chosen at every iteration as small as possible, while serving in an indispensable upper bound for the value of the objective function. In the previously … Read more
Chance constrained programming is an effective and convenient approach to control risk in decision making under uncertainty. However, due to unknown probability distributions of random parameters, the solution obtained from a chance constrained optimization problem can be biased. In practice, instead of knowing the true distribution of a random parameter, only a series of historical … Read more
The positive semidefinite (psd) rank of a polytope is the smallest $k$ for which the cone of $k \times k$ real symmetric psd matrices admits an affine slice that projects onto the polytope. In this paper we show that the psd rank of a polytope is at least the dimension of the polytope plus one, … Read more
group of analytical formulas formulas for calculating the global maximal and minimal ranks and inertias of the quadratic matrix-valued function $$ \phi(X) = \left(\, AXB + C\,\right)\!M\!\left(\, AXB + C \right)^{*} + D $$ are established and their consequences are presented, where $A$, $B$, $C$ and $D$ are given complex matrices with $A$ and $C$ … Read more
We study a new geometric graph parameter $\egd(G)$, defined as the smallest integer $r\ge 1$ for which any partial symmetric matrix which is completable to a correlation matrix and whose entries are specified at the positions of the edges of $G$, can be completed to a matrix in the convex hull of correlation matrices of … Read more
We study the computational question whether a given polytope or spectrahedron $S_A$ (as given by the positive semidefiniteness region of a linear matrix pencil $A(x)$) is contained in another one $S_B$. First we classify the computational complexity, extending results on the polytope/poly\-tope-case by Gritzmann and Klee to the polytope/spectrahedron-case. For various restricted containment problems, NP-hardness … Read more
We consider the decision problem asking whether a partial rational symmetric matrix with an all-ones diagonal can be completed to a full positive semidefinite matrix of rank at most $k$. We show that this problem is $\NP$-hard for any fixed integer $k\ge 2$. Equivalently, for $k\ge 2$, it is $\NP$-hard to test membership in the … Read more
Algorithms are presented for evaluating gradients and Hessians of logarithmic barrier functions for two types of convex cones: the cone of positive semidefinite matrices with a given sparsity pattern, and its dual cone, the cone of sparse matrices with the same pattern that have a positive semidefinite completion. Efficient large-scale algorithms for evaluating these barriers … Read more