Numerical Methods and Optimization

Complexity Issues 205

where

B

n

=[0, 1]

n

= {x ∈ IR

n

:0≤ x

i

≤ 1,i=1,...,n}

and f is Lipschitz continuous on B

n

with respect to the infinity norm:

|f(x) − f(y)|≤Lx − y

∞

∀x, y ∈ B

n

,

with L being a Lipschitz constant. According to the Weierstrass theorem, this

problem has an optimal solution. Assume that f

∗

is the optimal objective

value. Given a small >0, we will be satisfied with an approximate solution

˜x ∈ B

n

such that

f(˜x) − f

∗

≤ . (9.15)

Our goal in this subsection is to determine the minimum running time a zero-

order method will require in order to guarantee such a solution. In other words,

we want to establish the lower complexity bounds on zero-order metho ...