original_docstring: Minimize cost given minimum output constraint using golden section/binary search.
  
      Given discrete function f that monotonically increases then monotonically decreases,
      find the minimum integer x such that f(x) >= vmin.
  
      This method uses Fibonacci search to find the upper bound of x.  If the upper bound
      is found, a binary search is performed in the interval to find the solution.  If
      vmin is close to the maximum of f, a golden section search is performed to attempt
      to find x.
  
      Parameters
      ----------
      f : Callable[[int], float]
          a function that takes a single integer and output a scalar value.  Must monotonically
          increase then monotonically decrease.
      vmin : float
          the minimum output value.
      offset : int
          the input lower bound.  We will for x in the range [offset, infinity).
      step : int
          the input step.  function will only be evaulated at the points offset + step * N
      maxiter : Optional[int]
          maximum number of iterations to perform.  If None, will run indefinitely.
  
      Returns
      -------
      result : MinCostResult
          the MinCostResult named tuple, with attributes:
  
          x : Optional[int]
              the minimum integer such that f(x) >= vmin.  If no such x exists, this will be None.
          xmax : Optional[int]
              the value at which f achieves its maximum.  This is set only if x is None
          vmax : Optional[float]
              the maximum value of f.  This is set only if x is None.
          nfev : int
              total number of function calls made.
      
docstring: Minimize cost given minimum output constraint using golden section/binary search.
  Given discrete function f that monotonically increases then monotonically decreases,
  find the minimum integer x such that f(x) >= vmin.
  
  This method uses Fibonacci search to find the upper bound of x.  If the upper bound
  is found, a binary search is performed in the interval to find the solution.  If
  vmin is close to the maximum of f, a golden section search is performed to attempt
  to find x.
  
  Parameters
  
  f : Callable[[int], float]
  a function that takes a single integer and output a scalar value.  Must monotonically
  increase then monotonically decrease.
  vmin : float
  the minimum output value.
  offset : int
  the input lower bound.  We will for x in the range [offset, infinity).
  step : int
  the input step.  function will only be evaulated at the points offset + step * N
  maxiter : Optional[int]
  maximum number of iterations to perform.  If None, will run indefinitely.
  
  Returns
  
  result : MinCostResult
  the MinCostResult named tuple, with attributes.
  
  x : Optional[int]
  the minimum integer such that f(x) >= vmin.  If no such x exists, this will be None.
  xmax : Optional[int]
  the value at which f achieves its maximum.  This is set only if x is None
  vmax : Optional[float]
  the maximum value of f.  This is set only if x is None.
  nfev : int
  total number of function calls made.
docstring_tokens: Minimize cost given minimum output constraint using golden section / binary search . Given discrete function f that monotonically increases then monotonically decreases find the minimum integer x such that f ( x ) > = vmin . This method uses Fibonacci search to find the upper bound of x . If the upper bound is found a binary search is performed in the interval to find the solution . If vmin is close to the maximum of f a golden section search is performed to attempt to find x . Parameters f : Callable [[ int ] float ] a function that takes a single integer and output a scalar value . Must monotonically increase then monotonically decrease . vmin : float the minimum output value . offset : int the input lower bound . We will for x in the range [ offset infinity ) . step : int the input step . function will only be evaulated at the points offset + step * N maxiter : Optional [ int ] maximum number of iterations to perform . If None will run indefinitely . Returns result : MinCostResult the MinCostResult named tuple with attributes . x : Optional [ int ] the minimum integer such that f ( x ) > = vmin . If no such x exists this will be None . xmax : Optional [ int ] the value at which f achieves its maximum . This is set only if x is None vmax : Optional [ float ] the maximum value of f . This is set only if x is None . nfev : int total number of function calls made .
code: def minimize_cost_golden(f, vmin, offset=0, step=1, maxiter=1000):
      # type: (Callable[[int], float], float, int, int, Optional[int]) -> MinCostResult
      """Minimize cost given minimum output constraint using golden section/binary search.
  
      Given discrete function f that monotonically increases then monotonically decreases,
      find the minimum integer x such that f(x) >= vmin.
  
      This method uses Fibonacci search to find the upper bound of x.  If the upper bound
      is found, a binary search is performed in the interval to find the solution.  If
      vmin is close to the maximum of f, a golden section search is performed to attempt
      to find x.
  
      Parameters
      ----------
      f : Callable[[int], float]
          a function that takes a single integer and output a scalar value.  Must monotonically
          increase then monotonically decrease.
      vmin : float
          the minimum output value.
      offset : int
          the input lower bound.  We will for x in the range [offset, infinity).
      step : int
          the input step.  function will only be evaulated at the points offset + step * N
      maxiter : Optional[int]
          maximum number of iterations to perform.  If None, will run indefinitely.
  
      Returns
      -------
      result : MinCostResult
          the MinCostResult named tuple, with attributes:
  
          x : Optional[int]
              the minimum integer such that f(x) >= vmin.  If no such x exists, this will be None.
          xmax : Optional[int]
              the value at which f achieves its maximum.  This is set only if x is None
          vmax : Optional[float]
              the maximum value of f.  This is set only if x is None.
          nfev : int
              total number of function calls made.
      """
      fib2 = fib1 = fib0 = 0
      cur_idx = 0
      nfev = 0
      xmax = vmax = v_prev = None
      while maxiter is None or nfev < maxiter:
          v_cur = f(step * fib0 + offset)
          nfev += 1
  
          if v_cur >= vmin:
              # found upper bound, use binary search to find answer
              stop = step * fib0 + offset
              return minimize_cost_binary(f, vmin, start=step * (fib1 + 1) + offset,
                                          stop=stop, save=stop, step=step, nfev=nfev)
          else:
              if vmax is not None and v_cur <= vmax:
                  if cur_idx <= 3:
                      # special case: 0 <= xmax < 3, and we already checked all possibilities, so
                      # we know vmax < vmin.  There is no solution and just return.
                      return MinCostResult(x=None, xmax=step * xmax + offset, vmax=vmax, nfev=nfev)
                  else:
                      # we found the bracket that encloses maximum, perform golden section search
                      a, x, b = fib2, fib1, fib0
                      fx = v_prev
                      while x > a + 1 or b > x + 1:
                          u = a + b - x
                          fu = f(step * u + offset)
                          nfev += 1
  
                          if fu >= fx:
                              if u > x:
                                  a, x = x, u
                                  fx = fu
                              else:
                                  x, b = u, x
                                  fx = fu
  
                              if fx >= vmin:
                                  # found upper bound, use binary search to find answer
                                  stop = step * x + offset
                                  return minimize_cost_binary(f, vmin, start=step * (a + 1) + offset,
                                                              stop=stop, save=stop, step=step,
                                                              nfev=nfev)
                          else:
                              if u > x:
                                  b = u
                              else:
                                  a = u
  
                      # golden section search terminated, the maximum is less than vmin
                      return MinCostResult(x=None, xmax=step * x + offset, vmax=fx, nfev=nfev)
              else:
                  # still not close to maximum, continue searching
                  vmax = v_prev = v_cur
                  xmax = fib0
                  cur_idx += 1
                  if cur_idx <= 3:
                      fib2, fib1, fib0 = fib1, fib0, cur_idx
                  else:
                      fib2, fib1, fib0 = fib1, fib0, fib1 + fib0
  
      raise ValueError('Maximum number of iteration achieved')
code_tokens: def minimize_cost_golden ( f , vmin , offset = 0 , step = 1 , maxiter = 1000 ) : fib2 = fib1 = fib0 = 0 cur_idx = 0 nfev = 0 xmax = vmax = v_prev = None while maxiter is None or nfev < maxiter : v_cur = f ( step * fib0 + offset ) nfev += 1 if v_cur >= vmin : stop = step * fib0 + offset return minimize_cost_binary ( f , vmin , start = step * ( fib1 + 1 ) + offset , stop = stop , save = stop , step = step , nfev = nfev ) else : if vmax is not None and v_cur <= vmax : if cur_idx <= 3 : return MinCostResult ( x = None , xmax = step * xmax + offset , vmax = vmax , nfev = nfev ) else : a , x , b = fib2 , fib1 , fib0 fx = v_prev while x > a + 1 or b > x + 1 : u = a + b - x fu = f ( step * u + offset ) nfev += 1 if fu >= fx : if u > x : a , x = x , u fx = fu else : x , b = u , x fx = fu if fx >= vmin : stop = step * x + offset return minimize_cost_binary ( f , vmin , start = step * ( a + 1 ) + offset , stop = stop , save = stop , step = step , nfev = nfev ) else : if u > x : b = u else : a = u return MinCostResult ( x = None , xmax = step * x + offset , vmax = fx , nfev = nfev ) else : vmax = v_prev = v_cur xmax = fib0 cur_idx += 1 if cur_idx <= 3 : fib2 , fib1 , fib0 = fib1 , fib0 , cur_idx else : fib2 , fib1 , fib0 = fib1 , fib0 , fib1 + fib0 raise ValueError ( 'Maximum number of iteration achieved' )
short_docstring: Minimize cost given minimum output constraint using golden section/binary search.
short_docstring_tokens: Minimize cost given minimum output constraint using golden section / binary search .
comment: # type: (Callable[[int], float], float, int, int, Optional[int]) -> MinCostResult$SEP$"""Minimize cost given minimum output constraint using golden section/binary search.
  
      Given discrete function f that monotonically increases then monotonically decreases,
      find the minimum integer x such that f(x) >= vmin.
  
      This method uses Fibonacci search to find the upper bound of x.  If the upper bound
      is found, a binary search is performed in the interval to find the solution.  If
      vmin is close to the maximum of f, a golden section search is performed to attempt
      to find x.
  
      Parameters
      ----------
      f : Callable[[int], float]
          a function that takes a single integer and output a scalar value.  Must monotonically
          increase then monotonically decrease.
      vmin : float
          the minimum output value.
      offset : int
          the input lower bound.  We will for x in the range [offset, infinity).
      step : int
          the input step.  function will only be evaulated at the points offset + step * N
      maxiter : Optional[int]
          maximum number of iterations to perform.  If None, will run indefinitely.
  
      Returns
      -------
      result : MinCostResult
          the MinCostResult named tuple, with attributes:
  
          x : Optional[int]
              the minimum integer such that f(x) >= vmin.  If no such x exists, this will be None.
          xmax : Optional[int]
              the value at which f achieves its maximum.  This is set only if x is None
          vmax : Optional[float]
              the maximum value of f.  This is set only if x is None.
          nfev : int
              total number of function calls made.
      """$SEP$# found upper bound, use binary search to find answer$SEP$# special case: 0 <= xmax < 3, and we already checked all possibilities, so$SEP$# we know vmax < vmin.  There is no solution and just return.$SEP$# we found the bracket that encloses maximum, perform golden section search$SEP$# found upper bound, use binary search to find answer$SEP$# golden section search terminated, the maximum is less than vmin$SEP$# still not close to maximum, continue searching