Global minimization by reducing the duality gap

We derive a general principle demonstrating that by partitioning the feasible set, the duality gap, existing between a nonconvex program and its lagrangian dual, can be reduced, and in important special cases, even eliminated. The principle can be implemented in a Branch and Bound algorithm which co...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 1994-01, Vol.63 (2), p.193-212
Main Authors: AHARON BEN-TAL, EIGER, G, GERSHOVITZ, V
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
Mathematical programming
Operational research and scientific management
Operational research. Management science
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We derive a general principle demonstrating that by partitioning the feasible set, the duality gap, existing between a nonconvex program and its lagrangian dual, can be reduced, and in important special cases, even eliminated. The principle can be implemented in a Branch and Bound algorithm which computes an approximate global solution and a corresponding lower bound on the global optimal value. The algorithm involves decomposition and a nonsmooth local search. Numerical results for applying the algorithm to the pooling problem in oil refineries are given.
ISSN:0025-5610
1436-4646
DOI:10.1007/BF01582066