Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Computer Engineering
Towards An Efficient Bisection Of Ellipsoids, Paden Portillo, Martine Ceberio, Vladik Kreinovich
Towards An Efficient Bisection Of Ellipsoids, Paden Portillo, Martine Ceberio, Vladik Kreinovich
Departmental Technical Reports (CS)
Constraints are often represented as ellipsoids. One of the main advantages of such constrains is that, in contrast to boxes, over which optimization of even quadratic functions is NP-hard, optimization of a quadratic function over an ellipsoid is feasible. Sometimes, the area described by constrains is too large, so it is reasonable to bisect this area (one or several times) and solve the optimization problem for all the sub-areas. Bisecting a box, we still get a box, but bisecting an ellipsoid, we do not get an ellipsoid. Usually, this problem is solved by enclosing the half-ellipsoid in a larger ellipsoid, …
Why Ellipsoid Constraints, Ellipsoid Clusters, And Riemannian Space-Time: Dvoretzky's Theorem Revisited, Karen Villaverde, Olga Kosheleva, Martine Ceberio
Why Ellipsoid Constraints, Ellipsoid Clusters, And Riemannian Space-Time: Dvoretzky's Theorem Revisited, Karen Villaverde, Olga Kosheleva, Martine Ceberio
Departmental Technical Reports (CS)
In many practical applications, we encounter ellipsoid constraints, ellipsoid-shaped clusters, etc. A usual justification for this ellipsoid shape comes from the fact that many real-life quantities are normally distributed, and for a multi-variate normal distribution, a natural confidence set (containing the vast majority of the objects) is an ellipsoid. However, ellipsoid appear more frequently than normal distributions (which occur in about half of the cases). In this paper, we provide a new justification for ellipsoids based on a known mathematical result -- Dvoretzky's Theorem.