Catálogo de publicaciones - libros

“Hit-and-run is fast and fun” to generate a random point in a high dimensional convex set (Lovász/Vempala, MSR-TR-2003-05). More precisely, the hit-and-run random walk mixes fast independently of where it is started inside the convex set. To hit-and-run from a point , a line through  is randomly chosen (uniformly over all directions). Subsequently, the walk’s next point is sampled from  ∩  using a membership oracle which tells us whether a point is in or not.

Here the focus is on black-box optimization, however, where the function to be minimized is given as an oracle, namely a black box for -evaluations. We obtain in an obvious way a direct-search method when we substitute the -oracle for the -membership oracle to do a line search over , and, naturally, we are interested in how fast such a hit-and-run direct-search heuristic converges to the optimum point in the search space .

We prove that, even under the assumption of perfect line search, the search converges (at best) linearly at an expected rate larger (i.e. worse) than 1 − 1/. This implies a lower bound of 0.5 on the expected number of line searches necessary to halve the approximation error. Moreover, we show that 0.4 line searches suffice to halve the approximation error only with an exponentially small probability of . Since each line search requires at least one query to the -oracle, the lower bounds obtained hold also for the number of -evaluations.

A two-way finite automaton is if its input head can change direction only on the end-markers. For each  ≥ 2, we exhibit a problem that can be solved by a ()-state sweeping automaton, but needs 2 states on every sweeping automaton.

Orthogonal variable spreading factor (OVSF) codes are widely used to provide variable data rates for supporting different bandwidth requirements in wideband code division multiple access (WCDMA) systems. Many works in the literature have intensively investigated to find an optimal dynamic code assignment scheme for OVSF codes. Unlike earlier studies, which assign OVSF codes using conventional (CCA) or dynamic (DCA) code allocation schemes, in this paper, stochastic optimization methods which are genetic algorithm (GA) and simulated annealing (SA) were applied which population is adaptively constructed according to existing traffic density in the OVSF code-tree. Also, the influences of the GA (selection, crossover and mutation techniques) and the SA (cooling schedules, number of inner loop) parameters were examined on the dynamic OVSF code allocation problem. Simulation results show that the GA and SA provide reduced code blocking probability and improved spectral efficiency when compared to the CCA and DCA schemes.

In this paper we study the support sizes of evolutionary stable strategies (ESS) in random evolutionary games. We prove that, when the elements of the payoff matrix behave either as uniform, or normally distributed independent random variables, almost all ESS have support sizes o(), where is the number of possible types for a player. Our arguments are based exclusively on the severity of a property that the payoff submatrix indicated by the support of an ESS must satisfy. We then combine our normal–random result with a recent result of McLennan and Berg (2005), concerning the expected number of Nash Equilibria in normal–random bimatrix games, to show that the expected number of ESS is significantly smaller than the expected number of symmetric Nash equilibria of the underlying symmetric bimatrix game.

C7 – Game Theory and Bargaining Theory.