BUG: line_search_wolfe2 fails to converge due to a wrong condition

[lidingxu]

Describe your issue.

In scipy/optimize/_linesearch.py#L330, there is a function called scalar_search_wolfe2 that finds alpha that satisfies strong Wolfe conditions. In L403, there is a condition to clip the initial step length alpha1 no more than the maximum step length amax

    if amax is not None:
        alpha1 = min(alpha1, amax)

In the main loop of the algorithm (L416):

    for i in range(maxiter):
        if alpha1 == 0 or (amax is not None and alpha0 == amax):
            # alpha1 == 0: This shouldn't happen. Perhaps the increment has
            # slipped below machine precision?
            alpha_star = None
            phi_star = phi0
            phi0 = old_phi0
            derphi_star = None

            if alpha1 == 0:
                msg = 'Rounding errors prevent the line search from converging'
            else:
                msg = "The line search algorithm could not find a solution " + \
                      "less than or equal to amax: %s" % amax

            warn(msg, LineSearchWarning, stacklevel=2)
            break

When i == 1, alpha0 will be alpha1, which could be amax, if alpha was clipped. This leads to an error msg = "The line search algorithm could not find a solution " + \ "less than or equal to amax: %s" % amax. Therefore, the condition if alpha1 == 0 or (amax is not None and alpha0 == amax): should be avoided to check in this iteration.

Reproducing Code Example

You could just set amax small enough.

Error message

LineSearchWarning: The line search algorithm did not converge
  alpha, *_ = line_search(self._loss, self._gradient, w, d, args=(A, Pindicate, Zindicate, cs), amax = amax, maxiter=40)

SciPy/NumPy/Python version and system information

1.12.0 1.26.4 sys.version_info(major=3, minor=12, micro=2, releaselevel='final', serial=0)
/home/ldx/Projects/miniconda/envs/rg/lib/python3.12/site-packages/scipy/__config__.py:154: UserWarning: Install `pyyaml` for better output
  warnings.warn("Install `pyyaml` for better output", stacklevel=1)
{
  "Compilers": {
    "c": {
      "name": "gcc",
      "linker": "ld.bfd",
      "version": "11.2.0",
      "commands": "/croot/scipy_1710947333060/_build_env/bin/x86_64-conda-linux-gnu-cc",
      "args": "-march=nocona, -mtune=haswell, -ftree-vectorize, -fPIC, -fstack-protector-strong, -fno-plt, -O2, -ffunction-sections, -pipe, -isystem, /home/ldx/Projects/miniconda/envs/rg/include, -fdebug-prefix-map=/croot/scipy_1710947333060/work=/usr/local/src/conda/scipy-1.12.0, -fdebug-prefix-map=/home/ldx/Projects/miniconda/envs/rg=/usr/local/src/conda-prefix, -DNDEBUG, -D_FORTIFY_SOURCE=2, -O2, -isystem, /home/ldx/Projects/miniconda/envs/rg/include",
      "linker args": "-Wl,-O2, -Wl,--sort-common, -Wl,--as-needed, -Wl,-z,relro, -Wl,-z,now, -Wl,--disable-new-dtags, -Wl,--gc-sections, -Wl,-rpath,/home/ldx/Projects/miniconda/envs/rg/lib, -Wl,-rpath-link,/home/ldx/Projects/miniconda/envs/rg/lib, -L/home/ldx/Projects/miniconda/envs/rg/lib, -march=nocona, -mtune=haswell, -ftree-vectorize, -fPIC, -fstack-protector-strong, -fno-plt, -O2, -ffunction-sections, -pipe, -isystem, /home/ldx/Projects/miniconda/envs/rg/include, -fdebug-prefix-map=/croot/scipy_1710947333060/work=/usr/local/src/conda/scipy-1.12.0, -fdebug-prefix-map=/home/ldx/Projects/miniconda/envs/rg=/usr/local/src/conda-prefix, -DNDEBUG, -D_FORTIFY_SOURCE=2, -O2, -isystem, /home/ldx/Projects/miniconda/envs/rg/include"
    },
    "cython": {
      "name": "cython",
      "linker": "cython",
      "version": "3.0.8",
      "commands": "cython"
    },
    "c++": {
      "name": "gcc",
      "linker": "ld.bfd",
      "version": "11.2.0",
      "commands": "/croot/scipy_1710947333060/_build_env/bin/x86_64-conda-linux-gnu-c++",
      "args": "-fvisibility-inlines-hidden, -std=c++17, -fmessage-length=0, -march=nocona, -mtune=haswell, -ftree-vectorize, -fPIC, -fstack-protector-strong, -fno-plt, -O2, -ffunction-sections, -pipe, -isystem, /home/ldx/Projects/miniconda/envs/rg/include, -fdebug-prefix-map=/croot/scipy_1710947333060/work=/usr/local/src/conda/scipy-1.12.0, -fdebug-prefix-map=/home/ldx/Projects/miniconda/envs/rg=/usr/local/src/conda-prefix, -DNDEBUG, -D_FORTIFY_SOURCE=2, -O2, -isystem, /home/ldx/Projects/miniconda/envs/rg/include",
      "linker args": "-Wl,-O2, -Wl,--sort-common, -Wl,--as-needed, -Wl,-z,relro, -Wl,-z,now, -Wl,--disable-new-dtags, -Wl,--gc-sections, -Wl,-rpath,/home/ldx/Projects/miniconda/envs/rg/lib, -Wl,-rpath-link,/home/ldx/Projects/miniconda/envs/rg/lib, -L/home/ldx/Projects/miniconda/envs/rg/lib, -fvisibility-inlines-hidden, -std=c++17, -fmessage-length=0, -march=nocona, -mtune=haswell, -ftree-vectorize, -fPIC, -fstack-protector-strong, -fno-plt, -O2, -ffunction-sections, -pipe, -isystem, /home/ldx/Projects/miniconda/envs/rg/include, -fdebug-prefix-map=/croot/scipy_1710947333060/work=/usr/local/src/conda/scipy-1.12.0, -fdebug-prefix-map=/home/ldx/Projects/miniconda/envs/rg=/usr/local/src/conda-prefix, -DNDEBUG, -D_FORTIFY_SOURCE=2, -O2, -isystem, /home/ldx/Projects/miniconda/envs/rg/include"
    },
    "fortran": {
      "name": "gcc",
      "linker": "ld.bfd",
      "version": "11.2.0",
      "commands": "/croot/scipy_1710947333060/_build_env/bin/x86_64-conda-linux-gnu-gfortran",
      "args": "-fopenmp, -march=nocona, -mtune=haswell, -ftree-vectorize, -fPIC, -fstack-protector-strong, -fno-plt, -O2, -ffunction-sections, -pipe, -isystem, /home/ldx/Projects/miniconda/envs/rg/include, -fdebug-prefix-map=/croot/scipy_1710947333060/work=/usr/local/src/conda/scipy-1.12.0, -fdebug-prefix-map=/home/ldx/Projects/miniconda/envs/rg=/usr/local/src/conda-prefix",
      "linker args": "-Wl,-O2, -Wl,--sort-common, -Wl,--as-needed, -Wl,-z,relro, -Wl,-z,now, -Wl,--disable-new-dtags, -Wl,--gc-sections, -Wl,-rpath,/home/ldx/Projects/miniconda/envs/rg/lib, -Wl,-rpath-link,/home/ldx/Projects/miniconda/envs/rg/lib, -L/home/ldx/Projects/miniconda/envs/rg/lib, -fopenmp, -march=nocona, -mtune=haswell, -ftree-vectorize, -fPIC, -fstack-protector-strong, -fno-plt, -O2, -ffunction-sections, -pipe, -isystem, /home/ldx/Projects/miniconda/envs/rg/include, -fdebug-prefix-map=/croot/scipy_1710947333060/work=/usr/local/src/conda/scipy-1.12.0, -fdebug-prefix-map=/home/ldx/Projects/miniconda/envs/rg=/usr/local/src/conda-prefix"
    },
    "pythran": {
      "version": "0.15.0",
      "include directory": "../../_h_env_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_p/lib/python3.12/site-packages/pythran"
    }
  },
  "Machine Information": {
    "host": {
      "cpu": "x86_64",
      "family": "x86_64",
      "endian": "little",
      "system": "linux"
    },
    "build": {
      "cpu": "x86_64",
      "family": "x86_64",
      "endian": "little",
      "system": "linux"
    },
    "cross-compiled": false
  },
  "Build Dependencies": {
    "blas": {
      "name": "mkl-sdl",
      "found": true,
      "version": "2023.1",
      "detection method": "pkgconfig",
      "include directory": "/home/ldx/Projects/miniconda/envs/rg/include",
      "lib directory": "/home/ldx/Projects/miniconda/envs/rg/lib",
      "openblas configuration": "unknown",
      "pc file directory": "/home/ldx/Projects/miniconda/envs/rg/lib/pkgconfig"
    },
    "lapack": {
      "name": "mkl-sdl",
      "found": true,
      "version": "2023.1",
      "detection method": "pkgconfig",
      "include directory": "/home/ldx/Projects/miniconda/envs/rg/include",
      "lib directory": "/home/ldx/Projects/miniconda/envs/rg/lib",
      "openblas configuration": "unknown",
      "pc file directory": "/home/ldx/Projects/miniconda/envs/rg/lib/pkgconfig"
    },
    "pybind11": {
      "name": "pybind11",
      "version": "2.10.4",
      "detection method": "pkgconfig",
      "include directory": "/home/ldx/Projects/miniconda/envs/rg/include"
    }
  },
  "Python Information": {
    "path": "/home/ldx/Projects/miniconda/envs/rg/bin/python",
    "version": "3.12"
  }
}