  


Rigorous enclosures of ellipsoids and directed Cholesky factorizations
Ferenc Domes (ferenc.domesunivie.ac.at) Abstract: This paper discusses the rigorous enclosure of an ellipsoid by a rectangular box, its interval hull, providing a convenient preprocessing step for constrained optimization problems. A quadratic inequality constraint with a positive definite Hessian defines an ellipsoid. The Cholesky factorization can be used to transform a strictly convex quadratic constraint into a norm inequality, for which the interval hull is easy to compute analytically. In exact arithmetic, the Cholesky factorization of a nonsingular symmetric matrix exists iff the matrix is positive definite. However, to cope efficiently with rounding errors in inexact arithmetic is nontrivial. Numerical tests show that even nearly singular problems can be handled successfully by our techniques. To rigorously account for the rounding errors involved in the computation of the interval hull and to handle quadratic inequality constraints having uncertain coefficients, we define the concept of a directed Cholesky factorization, and give two algorithms for computing one. We also discuss how a directed Cholesky factorization can be used for testing positive definiteness. Some numerical test are given in order to exploit the features and boundaries of the directed Cholesky factorization methods. Keywords: quadratic constraints, interval analysis, constraint satisfaction problems, bounding ellipsoids, interval hull, directed Cholesky factorization, verification of positive definiteness, rounding error control, preprocessing, verified computing Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization ) Citation: 2010, University of Vienna Download: [PDF] Entry Submitted: 02/28/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  