Branch-and-Sandwich: a deterministic global optimization algorithm for optimistic bilevel programming problems. Part I: Theoretical development
File(s)art%3A10.1007%2Fs10898-013-0121-7.pdf (646.22 KB)
Published version
Author(s)
Kleniati, Polyxeni-Margarita
Adjiman, Claire S
Type
Journal Article
Abstract
We present a global optimization algorithm, Branch-and-Sandwich, for optimistic bilevel programming problems that satisfy a regularity condition in the inner problem. The functions involved are assumed to be nonconvex and twice continuously differentiable. The proposed approach can be interpreted as the exploration of two solution spaces (corresponding to the inner and the outer problems) using a single branch-and-bound tree. A novel branching scheme is developed such that classical branch-and-bound is applied to both spaces without violating the hierarchy in the decisions and the requirement for (global) optimality in the inner problem. To achieve this, the well-known features of branch-and-bound algorithms are customized appropriately. For instance, two pairs of lower and upper bounds are computed: one for the outer optimal objective value and the other for the inner value function. The proposed bounding problems do not grow in size during the algorithm and are obtained from the corresponding problems at the parent node.
Date Issued
2014-11-01
Date Acceptance
2013-11-15
Citation
Journal of Global Optimization, 2014, 60 (3), pp.425-458
ISSN
0925-5001
Publisher
Springer
Start Page
425
End Page
458
Journal / Book Title
Journal of Global Optimization
Volume
60
Issue
3
Copyright Statement
© The Author(s) 2014. This article is published with open access at Springerlink.com
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000343215200003&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Subjects
Science & Technology
Technology
Physical Sciences
Operations Research & Management Science
Mathematics, Applied
Mathematics
Bilevel programming
Nonconvex inner problem
Branch and bound
DIFFERENTIABLE CONSTRAINED NLPS
CHEMICAL PROCESS DESIGN
GENERALIZED SEMIINFINITE
OPTIMALITY CONDITIONS
ALPHA-BB
MATHEMATICAL PROGRAMS
INTERVAL-METHODS
QUALIFICATIONS
1ST-ORDER
Publication Status
Published
Date Publish Online
2014-01-10