Bilevel Programming: Global Optimization
- PDF / 9,406,853 Bytes
- 101 Pages / 594 x 828 pts Page_size
- 30 Downloads / 228 Views
(1) 1
~,,(~1 dz, f min(cn, z)e -~(1 ~_m,(~))2
Here, cn = m i n i z i - e, zi = f(xi), mn(x)is the conditional expectation given the values of zi, i = 1 , . . . , n, dn(x) is the conditional variance, and e > 0 is a correction parameter.
The objective of DBA (used mainly in continuous cases) is to provide as small average error as possible while keeping the convergence conditions. The Bayesian heuristic approach (BHA) means fixing a prior distribution P on a set of functions fg(x) that define the best values obtained using K times some heuristic h(x) to optimize a function v(y) of variables y E R n [15]. As usual, the components of y are discrete variables. The heuristic h(x) defines an expert opinion about the decision priorities. It is assumed that the heuristics or their 'mixture' depend on some continuous parameters x E R m, where m < n. The Bayesian stopping rules (BSR) [3] define the best on average stopping rule. In the BSR, the prior distribution is determined regarding only those features of the objective function f(x) which are relevant for the stopping of the algorithm of global optimization. Now all these ways will be considered in detail starting from the DBA. The Wiener process is common [11], [16], [19] as a stochastic model applying the DBA in the one-dimensional case m = 1. The Wiener model implies that almost all the sample functions f(x) are continuous, that increments f ( x 4 ) - f(x3) and f ( x 2 ) - f(xl), xl < x2 < x3 < x4 are stochastically independent, and that f(x) is Gaussian (0, ax) at any fixed x > 0. Note that the Wiener process originally provided a mathematical model of a particle in Brownian motion. The Wiener model is extended to multidimensional case, too [14]. However, simple approximate stochastic models are preferable, if m > 1.
Bayesian global optimization These models are designed by replacing the traditional Kolmogorov consistency conditions because they require the inversion of matrices of nth order for computing the conditional expectation ran(X) and variance dn (x). The favorable exception is the Markov process, including the Wiener one. Extending the Wiener process to m > 1 the Markovian property disappears. 7
,
,
,
,
" ~Ixl -
R(x) ..... 6
5
4
"'" """"'"'...... ..................... .......i i.... ...... i ...... "'""'''''''*''/"
""................ "'"
////.,--*"........"-... \\
°(1)
x(2)
xl/xt)
V
V
x(3)
x(41
xlS)
Fig. 1: T h e Wiener model.
Replacing the regular consistency conditions by: • continuity of the risk function R(x); • convergence of Xn to the global minimum; • simplicity of expressions of mn(x) and sn(x), the following simple expression of R(x) is obtained using the results of [14]: R(x)-
min z i -
l0,
u>0,
v>0.
(11)
Bilevel linear programming This formulation has played a key role in the development of algorithms. One advantage that it offers is that it allows for a more robust model to be solved without introducing any new computational difficulties. In particular, by replacing the follower's objective function (3) with a qu
Data Loading...
