In this paper we consider covariance structural models with which we associate semidefinite programming problems. We discuss statistical properties of estimates of the respective optimal value and optimal solutions when the `true’ covariance matrix is estimated by its sample counterpart. The analysis is based on perturbation theory of semidefinite programming. As an example we consider … Read more
Motivated by applications in robotics and computer vision, we study problems related to spatial reasoning of a 3D environment using sublevel sets of polynomials. These include: tightly containing a cloud of points (e.g., representing an obstacle) with convex or nearly-convex basic semialgebraic sets, computation of Euclidean distance between two such sets, separation of two convex … Read more
For a given triangle $\triangle ABC$, Pierre de Fermat posed around 1640 the problem of finding a point $P$ minimizing the sum $s_P$ of the Euclidean distances from $P$ to the vertices $A$, $B$, $C$. Based on geometrical arguments this problem was first solved by Torricelli shortly after, by Simpson in 1750, and by several … Read more
The algorithm proposed in this paper runs in a polynomial oracle time, i.e., in a number of arithmetic operations and calls to the separation oracle bounded by a polynomial in the number of variables and in the maximum binary size of an entry of the coefficient matrix. This algorithm is much simpler than traditional polynomial … Read more
Throughout its evolution, data envelopment analysis (DEA) has mostly relied on linear programming, particularly because of simple primal-dual relations and the existence of standard software for solving linear programs. Although also non-linear models, such as Russell measure or hyperbolic measure models, have been introduced, their use in applications has been limited mainly because of their … Read more
The goal of scenario reduction is to approximate a given discrete distribution with another discrete distribution that has fewer atoms. We distinguish continuous scenario reduction, where the new atoms may be chosen freely, and discrete scenario reduction, where the new atoms must be chosen from among the existing ones. Using the Wasserstein distance as measure … Read more
The problem of minimizing the rank of a symmetric positive semidefinite matrix subject to constraints can be cast equivalently as a semidefinite program with complementarity constraints (SDCMPCC). The formulation requires two positive semidefinite matrices to be complementary. We investigate calmness of locally optimal solutions to the SDCMPCC formulation and hence show that any locally optimal … Read more
In this work we present an extension of Chubanov’s algorithm to the case of homogeneous feasibility problems over a symmetric cone K. As in Chubanov’s method for linear feasibility problems, the algorithm consists of a basic procedure and a step where the solutions are confined to the intersection of a half-space and K. Following an … Read more
In this work we are interested in nonlinear symmetric cone problems (NSCPs), which contain as special cases nonlinear semidefinite programming, nonlinear second order cone programming and the classical nonlinear programming problems. We explore the possibility of reformulating NSCPs as common nonlinear programs (NLPs), with the aid of squared slack variables. Through this connection, we show … Read more
Using the T-algebra machinery we show that the only strictly convex homogeneous cones in R^n with n >= 3 are the 2-cones, also known as Lorentz cones or second order cones. In particular, this shows that the p-cones are not homogeneous when p is not 2, 1 < p <\infty and n >= 3, thus … Read more