Directed modified Cholesky factorizations and convex quadratic relaxations

A directed Cholesky factorization of a symmetric interval matrix \A consists of a permuted upper triangular matrix R such that for all symmetric A \in \A, the residual matrix A – R^T R is positive semidefinite with tiny entries. This must holds with full mathematical rigor, although the computations are done in floating-point arithmetic. Similarly, … Read more

Constraint aggregation for rigorous global optimization

In rigorous constrained global optimization, upper bounds on the objective function help to reduce the search space. Their construction requires finding a narrow box around an approximately feasible solution, verified to contain a feasible point. Approximations are easily found by local optimization, but the verification often fails. In this paper we show that even if … Read more

Rigorous enclosures of ellipsoids and directed Cholesky factorizations

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 … Read more