=Paper=
{{Paper
|id=Vol-2473/invited3
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-2473/invited3.pdf
|volume=Vol-2473
|dblpUrl=https://dblp.org/rec/conf/itat/Lenger19
}}
==None==
<pdf width="1500px">https://ceur-ws.org/Vol-2473/invited3.pdf</pdf>
<pre>
  Optimization is Hard, but Hillclimbing is Easy –
                      Right?
                             Johannes Lengler
                Institute of Theoretical Computer Science
                     Department of Computer Science
                         ETH Zürich, Switzerland
                       johannes.lengler@inf.ethz.ch
                        https://www.ti.ethz.ch/



                                     Abstract
      Hillclimbing is an integral part of every optimization algorithm. One
      would expect that our standard hillclimbing algorithms can solve nice,
      unimodal functions efficiently. For example, strictly monotone func-
      tions: consider the search space S = {0, 1}n of n-bit strings; then
      a strictly monotone function f : S → R is a function that satisfies
      f (x) < f (y) for all different strings x, y in S such that xi ≤ yi holds
      for all 1 ≤ i ≤ n. Strictly montone functions are the easiest imaginable
      testbed for hillclimbers: The function f always prefers one-bits over
      zero-bits, so there are always short and clearly labelled paths from any
      start point to the unique global optimum 11..1. Surprisingly, it has
      become clear in the last years that many of our standard hillclimbers
      fail miserably on some strictly monotone functions. In many instances,
      they need exponential time to find the optimum. This devastating re-
      sult has deepened our understanding of hillclimbing techniques, and
      has given new insights into the mechanisms that are behind some hill-
      climbing techniques, like selective pressure, step size policies, and pop-
      ulation effects. These insights have also improved our understanding
      of optimization beyond hillclimbing, in particular of optimization in
      dynamic environments.

      Keywords: Optimization, Hillclimbing



   Copyright c 2019 for this paper by its authors. Use permitted under Creative Com-
mons License Attribution 4.0 International (CC BY 4.0).


                                          1

</pre>