We consider a primal-dual potential reduction algorithm for nonlinear convex optimization problems over symmetric cones. The same complexity estimates as in the case of linear objective function are obtained provided a certain nonlinear system of equations can be solved with a given accuracy. This generalizes the result of K. Kortanek, F. Potra and Y.Ye. We … Read more
The interval Distance Geometry Problem (iDGP) consists in finding a realization in R^K of a simple undirected graph G=(V,E) with nonnegative intervals assigned to the edges in such a way that, for each edge, the Euclidean distance between the realization of the adjacent vertices is within the edge interval bounds. Our aim is to determine … Read more
One often encounters numerical difficulties in solving linear matrix inequality (LMI) problems obtained from $H_\infty$ control problems. We discuss the reason from the viewpoint of optimization, and provide necessary and sufficient conditions for LMI problem and its dual not to be strongly feasible. Moreover, we interpret them in terms of control system. In this analysis, … Read more
We consider semidefinite optimization problems that include constraints that G(x) and H(x) are positive semidefinite (PSD), where the components of the symmetric matrices G(x) and H(x) are affine functions of an n-vector x. In such a case we obtain a new constraint that a matrix K(x,X) is PSD, where the components of K(x,X) are affine … Read more
A framework, PhaseLift, was recently proposed to solve the phase retrieval problem. In this framework, the problem is solved by optimizing a cost function over the set of complex Hermitian positive semidefinite matrices. This approach to phase retrieval motivates a more general consideration of optimizing cost functions on semidefinite Hermitian matrices where the desired minimizers … Read more
We derive sharp probability bounds on the tails of a product of symmetric non-negative random variables using only information about their first two moments. If the covariance matrix of the random variables is known exactly, these bounds can be computed numerically using semidefinite programming. If only an upper bound on the covariance matrix is available, … Read more
In Riemannian optimization problems, commonly encountered manifolds are $d$-dimensional matrix manifolds whose tangent spaces can be represented by $d$-dimensional linear subspaces of a $w$-dimensional Euclidean space, where $w > d$. Therefore, representing tangent vectors by $w$-dimensional vectors has been commonly used in practice. However, using $w$-dimensional vectors may be the most natural but may not … Read more
A real symmetric matrix M is completely positive semidefinite if it admits a Gram representation by positive semidefinite matrices (of any size d). The smallest such d is called the completely positive semidefinite rank of M, and it is an open question whether there exists an upper bound on this number as a function of … Read more
The bounded degree sum-of-squares (BSOS) hierarchy of Lasserre, Toh, and Yang [EURO J. Comput. Optim., 2015] constructs lower bounds for a general polynomial optimization problem with compact feasible set, by solving a sequence of semi-definite programming (SDP) problems. Lasserre, Toh, and Yang prove that these lower bounds converge to the optimal value of the original … Read more
An $n\times n$ matrix $X$ is called completely positive semidefinite (cpsd) if there exist $d\times d$ Hermitian positive semidefinite {matrices} $\{P_i\}_{i=1}^n$ (for some $d\ge 1$) such that $X_{ij}= {\rm Tr}(P_iP_j),$ for all $i,j \in \{ 1, \ldots, n \}$. The cpsd-rank of a cpsd matrix is the smallest $d\ge 1$ for which such a representation … Read more