• PDF / 267,744 Bytes
• 6 Pages / 439.37 x 666.142 pts Page_size
• 50 Downloads / 180 Views

DOWNLOAD

REPORT

---

A note on semi-infinite program bounding methods Stuart M. Harwood1

· Dimitri J. Papageorgiou1 · Francisco Trespalacios1

Received: 3 December 2019 / Accepted: 28 August 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020

Abstract Semi-infinite programs are a class of mathematical optimization problems with a finite number of decision variables and infinite constraints. As shown by Blankenship and Falk (J Optim Theory Appl 19(2):261–281, 1976), a sequence of lower bounds which converges to the optimal objective value may be obtained with specially constructed finite approximations of the constraint set. In Mitsos (Optimization 60(10–11):1291– 1308, 2011), it is claimed that a modification of this lower bounding method involving approximate solution of the lower-level program yields convergent lower bounds. We show with a counterexample that this claim is false, and discuss what kind of approximate solution of the lower-level program is sufficient for correct behavior. Keywords Semi-infinite programming · Global optimization · Lower bounds

1 Introduction This note discusses methods for the global solution of semi-infinite programs (SIP). Specifically, the method from [4] is considered, and it is shown with a counterexample that the lower bounds do not always converge. Throughout we use notation as close as possible to that used in [4], embellishing it only as necessary with, for instance, iteration counters. Consider a SIP in the general form f ∗ = inf f (x) x

(SIP)

s.t. x ∈ X , g(x, y) ≤ 0, ∀y ∈ Y ,

B 1

Stuart M. Harwood [email protected] Corporate Strategic Research, ExxonMobil Research and Engineering Company, Annandale, NJ 08801, USA

123

S. M. Harwood et al.

for subsets X , Y of finite dimensional real vector spaces and f : X → R, g : X ×Y → R. We may view Y as an index set, with potentially uncountably infinite cardinality. Important to validating the feasibility of a point x is the lower-level program: sup {g(x, y) : y ∈ Y } .

(LLP)

y

Global solution of (SIP) often involves the construction of convergent upper and lower bounds. The approach in [4] to obtain a lower bound is a modification of the constraint-generation/discretization method of [2]. The claim is that the lower-level program may be solved approximately; the exact nature of the approximation is important to the convergence of the lower bounds and this is the subject of the present note.

2 Sketch of the lower bounding procedure and claim The setting of the method is the following. The method is iterative and at iteration k, for a given finite subset Y L B D,k ⊂ Y , a lower bound of f ∗ is obtained from the finite program f L B D,k = inf f (x) x

(1)

s.t. x ∈ X , g(x, y) ≤ 0, ∀y ∈ Y L B D,k . This is indeed a lower bound since fewer constraints are enforced, and thus (1) is a relaxation of (SIP). Assume that the lower bounding problem (1) is feasible (otherwise we can conclude that (SIP) is infeasible). Let x¯ k be a (global) minimizer of the lower bounding problem  (1). In [4], Lemma 2.2 supposes that we