code: """
  Tests for line search routines
  """
  from numpy.testing import (assert_, assert_equal, assert_array_almost_equal,
                             assert_array_almost_equal_nulp, assert_warns,
                             suppress_warnings)
  import scipy.optimize.linesearch as ls
  import scipy.optimize.nonlin as nl #(LS)
  from scipy.linalg import norm
  from scipy.optimize.linesearch import LineSearchWarning
  import numpy as np
  from copy import deepcopy  # (IS)
  
  
  def assert_wolfe(s, phi, derphi, c1=1e-4, c2=0.9, err_msg=""):
      """
      Check that strong Wolfe conditions apply
      """
      phi1 = phi(s)
      phi0 = phi(0)
      derphi0 = derphi(0)
      derphi1 = derphi(s)
      msg = "s = %s; phi(0) = %s; phi(s) = %s; phi'(0) = %s; phi'(s) = %s; %s" % (
          s, phi0, phi1, derphi0, derphi1, err_msg)
  
      assert_(phi1 <= phi0 + c1*s*derphi0, "Wolfe 1 failed: " + msg)
      assert_(abs(derphi1) <= abs(c2*derphi0), "Wolfe 2 failed: " + msg)
  
  
  def assert_armijo(s, phi, c1=1e-4, err_msg=""):
      """
      Check that Armijo condition applies
      """
      phi1 = phi(s)
      phi0 = phi(0)
      msg = "s = %s; phi(0) = %s; phi(s) = %s; %s" % (s, phi0, phi1, err_msg)
      assert_(phi1 <= (1 - c1*s)*phi0, msg)
  
  ###(LS)###
  def assert_rmt(alpha, dx, F0, Fx_new, jacobian, param, c1=1e-4, err_msg=""):
      """
      Check that RMT condition applies
      """
  
  
      parameters = ls.prepare_parameters('rmt',param,jacobian,dx)
      rmt_eta_upper = parameters['rmt_eta_upper']
      rmt_eta_lower = parameters['rmt_eta_lower']
      amin = parameters['amin']
  
      #Step 1: Eval t_dx_omega
      dxbar = jacobian.solve(
                  Fx_new
              )
  
      dx_diff = dxbar + (1 - alpha) * dx # note that dx = - J(x_k)^(-1)F(x_k)
  
      nominator = 2 * norm(dx_diff)
      denominator = alpha * norm(dx)
  
      t_dx_omega = nominator / denominator
  
      tester = (rmt_eta_lower <= t_dx_omega and t_dx_omega <= rmt_eta_upper) or (rmt_eta_lower > t_dx_omega and alpha == 1.0)
  
      msg = "s = %s; phi(0) = %s; phi(s) = %s; %s" % (alpha, F0, Fx_new, err_msg)
      assert_(tester or (alpha<amin), msg)
  
  
  def assert_bsc(alpha, x, dx, func, old_jacobian, param, err_msg):
      parameters = ls.prepare_parameters('bsc',param, old_jacobian, dx)
      H_lower = parameters['H_lower']
      H_upper = parameters['H_upper']
      amin = parameters['amin']
  
      x_new = x + alpha * dx
      Fx_new = func(x_new)
      jacobian = deepcopy(old_jacobian)
      jacobian.update(
          x_new.copy(),
          Fx_new
      )
      dx_next_it = -jacobian.solve(
          Fx_new
      )
      dx_diff = dx_next_it - dx
      H_prime = alpha * norm(dx_diff)
  
      tester = (H_lower <= H_prime and H_prime <= H_upper) or (H_lower > H_prime and alpha >= 1.0)
  
      msg = "s = %s; phi(0) = %s; phi(s) = %s; %s" % (alpha, func(x), Fx_new, err_msg)
  
      assert_(tester or (alpha<amin), msg)
  ###(LS)###
  
  def assert_line_wolfe(x, p, s, f, fprime, **kw):
      assert_wolfe(s, phi=lambda sp: f(x + p*sp),
                   derphi=lambda sp: np.dot(fprime(x + p*sp), p), **kw)
  
  
  def assert_line_armijo(x, p, s, f, **kw):
      assert_armijo(s, phi=lambda sp: f(x + p*sp), **kw)
  
  
  def assert_fp_equal(x, y, err_msg="", nulp=50):
      """Assert two arrays are equal, up to some floating-point rounding error"""
      try:
          assert_array_almost_equal_nulp(x, y, nulp)
      except AssertionError as e:
          raise AssertionError("%s\n%s" % (e, err_msg)) from e
  
  
  class TestLineSearch(object):
      # -- scalar functions; must have dphi(0.) < 0
      def _scalar_func_1(self, s):
          self.fcount += 1
          p = -s - s**3 + s**4
          dp = -1 - 3*s**2 + 4*s**3
          return p, dp
  
      def _scalar_func_2(self, s):
          self.fcount += 1
          p = np.exp(-4*s) + s**2
          dp = -4*np.exp(-4*s) + 2*s
          return p, dp
  
      def _scalar_func_3(self, s):
          self.fcount += 1
          p = -np.sin(10*s)
          dp = -10*np.cos(10*s)
          return p, dp
  
      # -- n-d functions
  
      def _line_func_1(self, x):
          self.fcount += 1
          f = np.dot(x, x)
          df = 2*x
          return f, df
  
      def _line_func_2(self, x):
          self.fcount += 1
          f = np.dot(x, np.dot(self.A, x)) + 1
          df = np.dot(self.A + self.A.T, x)
          return f, df
  
      # --
  
      def setup_method(self):
          self.scalar_funcs = []
          self.line_funcs = []
          self.N = 20
          self.fcount = 0
  
          def bind_index(func, idx):
              # Remember Python's closure semantics!
              return lambda *a, **kw: func(*a, **kw)[idx]
  
          for name in sorted(dir(self)):
              if name.startswith('_scalar_func_'):
                  value = getattr(self, name)
                  self.scalar_funcs.append(
                      (name, bind_index(value, 0), bind_index(value, 1)))
              elif name.startswith('_line_func_'):
                  value = getattr(self, name)
                  self.line_funcs.append(
                      (name, bind_index(value, 0), bind_index(value, 1)))
  
          np.random.seed(1234)
          self.A = np.random.randn(self.N, self.N)
  
      def scalar_iter(self):
          for name, phi, derphi in self.scalar_funcs:
              for old_phi0 in np.random.randn(3):
                  yield name, phi, derphi, old_phi0
  
      def line_iter(self):
          for name, f, fprime in self.line_funcs:
              k = 0
              while k < 9:
                  x = np.random.randn(self.N)
                  p = np.random.randn(self.N)
                  if np.dot(p, fprime(x)) >= 0:
                      # always pick a descent direction
                      continue
                  k += 1
                  old_fv = float(np.random.randn())
                  yield name, f, fprime, x, p, old_fv
  
      # -- Generic scalar searches
  
      def test_scalar_search_wolfe1(self):
          c = 0
          for name, phi, derphi, old_phi0 in self.scalar_iter():
              c += 1
              s, phi1, phi0 = ls.scalar_search_wolfe1(phi, derphi, phi(0),
                                                      old_phi0, derphi(0))
              assert_fp_equal(phi0, phi(0), name)
              assert_fp_equal(phi1, phi(s), name)
              assert_wolfe(s, phi, derphi, err_msg=name)
  
          assert_(c > 3)  # check that the iterator really works...
  
      def test_scalar_search_wolfe2(self):
          for name, phi, derphi, old_phi0 in self.scalar_iter():
              s, phi1, phi0, derphi1 = ls.scalar_search_wolfe2(
                  phi, derphi, phi(0), old_phi0, derphi(0))
              assert_fp_equal(phi0, phi(0), name)
              assert_fp_equal(phi1, phi(s), name)
              if derphi1 is not None:
                  assert_fp_equal(derphi1, derphi(s), name)
              assert_wolfe(s, phi, derphi, err_msg="%s %g" % (name, old_phi0))
  
      def test_scalar_search_wolfe2_with_low_amax(self):
          def phi(alpha):
              return (alpha - 5) ** 2
  
          def derphi(alpha):
              return 2 * (alpha - 5)
  
          s, _, _, _ = assert_warns(LineSearchWarning,
                                    ls.scalar_search_wolfe2, phi, derphi, amax=0.001)
          assert_(s is None)
  
      def test_scalar_search_wolfe2_regression(self):
          # Regression test for gh-12157
          # This phi has its minimum at alpha=4/3 ~ 1.333.
          def phi(alpha):
              if alpha < 1:
                  return - 3*np.pi/2 * (alpha - 1)
              else:
                  return np.cos(3*np.pi/2 * alpha - np.pi)
  
          def derphi(alpha):
              if alpha < 1:
                  return - 3*np.pi/2
              else:
                  return - 3*np.pi/2 * np.sin(3*np.pi/2 * alpha - np.pi)
  
          s, _, _, _ = ls.scalar_search_wolfe2(phi, derphi)
          # Without the fix in gh-13073, the scalar_search_wolfe2
          # returned s=2.0 instead.
          assert_(s < 1.5)
  
      def test_scalar_search_armijo(self):
          for name, phi, derphi, old_phi0 in self.scalar_iter():
              s, phi1 = ls.scalar_search_armijo(phi, phi(0), derphi(0))
              assert_fp_equal(phi1, phi(s), name)
              assert_armijo(s, phi, err_msg="%s %g" % (name, old_phi0))
  
      ###(LS)###
      ##RMT not usefull for scalar functions, thus no need for test_scalar_search_rmt?
  
      def test_line_search_rmt(self):
          #There is at least 1 function R^20->R to be tested, but this leads to s=None
          for name, f, fprime, x, p, old_f in self.line_iter():
              jac = lambda x: fprime(x)
              x0 = nl._as_inexact(x)
              func = lambda z: nl._as_inexact(f(nl._array_like(z, x0))).flatten()
              x = x0.flatten()
              jacobian = nl.asjacobian(jac)
              jacobian.setup(x.copy(), f(x), func)
              options = {'jacobian': jacobian, 'jac_tol': min(1e-03,1e-03*norm(f(x))), 'amin':1e-8}
              #print("1: ",f(x),np.shape(fprime(x)))
              s, dxbar, f_new = ls.scalar_search_rmt(f, x, fprime(x), parameters=options)
              #print("2: ",p_new, s)
              assert_fp_equal(f_new, x+s*fprime(x), name)
              assert_rmt(s, fprime(x), f(x), f_new, jacobian, options, err_msg="%s %g" % name)
  
  
      def test_line_search_bsc(self):
          #There is at least 1 function R^20->R to be tested, but this leads to s=None
          for name, f, fprime, x, p, old_f in self.line_iter():
              jac = lambda x: fprime(x)
              x0 = nl._as_inexact(x)
              func = lambda z: nl._as_inexact(f(nl._array_like(z, x0))).flatten()
              x = x0.flatten()
              jacobian = nl.asjacobian(jac)
              jacobian.setup(x.copy(), f(x), func)
              options = {'jacobian': jacobian, 'jac_tol': min(1e-03,1e-03*norm(f(x))), 'amin':1e-8}
              #print("1: ",f(x),np.shape(dp(x)))
              s, f_new= ls.scalar_search_bsc(func, x, fprime(x), f(x), parameters=options)
              #print("2: ",p_new, s)
              assert_fp_equal(f_new, x+s*fprime(x), name)
              assert_bsc(s, x, fprime(x), func, jacobian, options, err_msg="%s %g" % name)
      ###(LS)###
      
      # -- Generic line searches
  
      def test_line_search_wolfe1(self):
          c = 0
          smax = 100
          for name, f, fprime, x, p, old_f in self.line_iter():
              f0 = f(x)
              g0 = fprime(x)
              self.fcount = 0
              s, fc, gc, fv, ofv, gv = ls.line_search_wolfe1(f, fprime, x, p,
                                                             g0, f0, old_f,
                                                             amax=smax)
              assert_equal(self.fcount, fc+gc)
              assert_fp_equal(ofv, f(x))
              if s is None:
                  continue
              assert_fp_equal(fv, f(x + s*p))
              assert_array_almost_equal(gv, fprime(x + s*p), decimal=14)
              if s < smax:
                  c += 1
                  assert_line_wolfe(x, p, s, f, fprime, err_msg=name)
  
          assert_(c > 3)  # check that the iterator really works...
  
      def test_line_search_wolfe2(self):
          c = 0
          smax = 512
          for name, f, fprime, x, p, old_f in self.line_iter():
              f0 = f(x)
              g0 = fprime(x)
              self.fcount = 0
              with suppress_warnings() as sup:
                  sup.filter(LineSearchWarning,
                             "The line search algorithm could not find a solution")
                  sup.filter(LineSearchWarning,
                             "The line search algorithm did not converge")
                  s, fc, gc, fv, ofv, gv = ls.line_search_wolfe2(f, fprime, x, p,
                                                                 g0, f0, old_f,
                                                                 amax=smax)
              assert_equal(self.fcount, fc+gc)
              assert_fp_equal(ofv, f(x))
              assert_fp_equal(fv, f(x + s*p))
              if gv is not None:
                  assert_array_almost_equal(gv, fprime(x + s*p), decimal=14)
              if s < smax:
                  c += 1
                  assert_line_wolfe(x, p, s, f, fprime, err_msg=name)
          assert_(c > 3)  # check that the iterator really works...
  
      def test_line_search_wolfe2_bounds(self):
          # See gh-7475
  
          # For this f and p, starting at a point on axis 0, the strong Wolfe
          # condition 2 is met if and only if the step length s satisfies
          # |x + s| <= c2 * |x|
          f = lambda x: np.dot(x, x)
          fp = lambda x: 2 * x
          p = np.array([1, 0])
  
          # Smallest s satisfying strong Wolfe conditions for these arguments is 30
          x = -60 * p
          c2 = 0.5
  
          s, _, _, _, _, _ = ls.line_search_wolfe2(f, fp, x, p, amax=30, c2=c2)
          assert_line_wolfe(x, p, s, f, fp)
  
          s, _, _, _, _, _ = assert_warns(LineSearchWarning,
                                          ls.line_search_wolfe2, f, fp, x, p,
                                          amax=29, c2=c2)
          assert_(s is None)
  
          # s=30 will only be tried on the 6th iteration, so this won't converge
          assert_warns(LineSearchWarning, ls.line_search_wolfe2, f, fp, x, p,
                       c2=c2, maxiter=5)
  
      def test_line_search_armijo(self):
          c = 0
          for name, f, fprime, x, p, old_f in self.line_iter():
              f0 = f(x)
              g0 = fprime(x)
              self.fcount = 0
              s, fc, fv = ls.line_search_armijo(f, x, p, g0, f0)
              c += 1
              assert_equal(self.fcount, fc)
              assert_fp_equal(fv, f(x + s*p))
              assert_line_armijo(x, p, s, f, err_msg=name)
          assert_(c >= 9)
  
      # -- More specific tests
  
      def test_armijo_terminate_1(self):
          # Armijo should evaluate the function only once if the trial step
          # is already suitable
          count = [0]
  
          def phi(s):
              count[0] += 1
              return -s + 0.01*s**2
          s, phi1 = ls.scalar_search_armijo(phi, phi(0), -1, alpha0=1)
          assert_equal(s, 1)
          assert_equal(count[0], 2)
          assert_armijo(s, phi)
  
      def test_wolfe_terminate(self):
          # wolfe1 and wolfe2 should also evaluate the function only a few
          # times if the trial step is already suitable
  
          def phi(s):
              count[0] += 1
              return -s + 0.05*s**2
  
          def derphi(s):
              count[0] += 1
              return -1 + 0.05*2*s
  
          for func in [ls.scalar_search_wolfe1, ls.scalar_search_wolfe2]:
              count = [0]
              r = func(phi, derphi, phi(0), None, derphi(0))
              assert_(r[0] is not None, (r, func))
              assert_(count[0] <= 2 + 2, (count, func))
              assert_wolfe(r[0], phi, derphi, err_msg=str(func))
  
apis: scipy.optimize.nonlin._array_like numpy.testing.assert_equal numpy.random.seed numpy.testing.assert_warns scipy.optimize.linesearch.line_search_armijo scipy.optimize.nonlin._as_inexact scipy.optimize.linesearch.line_search_wolfe1 scipy.optimize.nonlin.asjacobian scipy.linalg.norm numpy.cos scipy.optimize.linesearch.prepare_parameters scipy.optimize.linesearch.line_search_wolfe2 scipy.optimize.linesearch.scalar_search_wolfe2 numpy.testing.assert_array_almost_equal_nulp numpy.random.randn numpy.exp numpy.array numpy.sin numpy.dot numpy.testing.suppress_warnings numpy.testing.assert_