Quantifying extra functions, herein referred to as outcome functions, over optimal solutions of an optimization problem can provide decision makers with additional information on a system. This bears more importance when the optimization problem is subject to uncertainty in input parameters. In this paper, we consider linear programming problems in which input parameters are described … Read more
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
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
An automatic method for constructing linear relaxations of constrained global optimization problems is proposed. Such a construction is based on affine and interval arithmetics and uses operator overloading. These linear programs have exactly the same numbers of variables and of inequality constraints as the given problems. Each equality constraint is replaced by two inequalities. This … Read more
We show that global optimization techniques, based on interval analysis and constraint propagation, succeed in solving the classical problem of optimization of the Belgium gas network. CitationPublished as Inria Research report RR-7796, November 2011.ArticleDownload View PDF
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
This paper is a contribution to the interval analysis and separability of convex sets. Separation is a familiar principle and is often used not only in optimization theory, but in many economic applications as well. In real problems input data are usually not known exactly. For the purpose of this paper we assume that data … Read more