Optimization Online


Constraint aggregation for rigorous global optimization

Ferenc Domes(Ferenc.Domes***at***univie.ac.at)
Arnold Neumaier(Arnold.Neumaier***at***univie.ac.at)

Abstract: 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 the verification of an approximate feasible point fails, the information extracted from the local optimization can still be used in many cases to reduce the search space. This is done by a rigorous filtering technique called constraint aggregation. It forms an aggregated redundant constraint, based on approximate Lagrange multipliers or on a vector valued measure of constraint violation. Using the optimality conditions, two sided linear relaxations, the Gauss-Jordan algorithm and a directed modified Cholesky factorization, the information in the redundant constraint is turned into powerful bounds on the feasible set. Constraint aggregation is especially useful since it also works in a tiny neighborhood of the global optimizer, thereby reducing the cluster effect. A simple introductory example demonstrates how our new method works. Extensive tests show the performance on a large benchmark.

Keywords: constraint aggregation, global optimization, constraint satisfaction, filtering method, verified computing, interval analysis

Category 1: Global Optimization

Citation: University of Vienna, 2014

Download: [PDF]

Entry Submitted: 07/03/2014
Entry Accepted: 07/04/2014
Entry Last Modified: 07/03/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society