Repository: scipy/scipy
Pull request: BUG: Optimize: NewtonCG min crashes with xtol=0
The minimize function crashes if `xtol` is set to `0`. This is because the initial value of a loop variable is `2 * xtol`, which is intended to ensure the loop runs at least once. However, if `xtol = 0` then the loop never runs, a variable isn't instantiated that is used outside of the loop, and an `UnboundLocalError` is raised.

To fix this, the initial value of the loop variable is set to the max float value.

<!-- 
Thanks for contributing a pull request! Please ensure that
your PR satisfies the checklist before submitting:
http://scipy.github.io/devdocs/dev/contributor/development_workflow.html#checklist-before-submitting-a-pr

Also, please name and describe your PR as you would write a
commit message:
http://scipy.github.io/devdocs/dev/contributor/development_workflow.html#writing-the-commit-message

Depending on your changes, you can skip CI operations and save time and energy: 
http://scipy.github.io/devdocs/dev/contributor/continuous_integration.html#skipping

Note that we are a team of volunteers; we appreciate your
patience during the review process.

Again, thanks for contributing!
-->

#### Reference issue
Closes #20214 

#### What does this implement/fix?
UnboundLocalError is thrown if `xtol` is set to 0 for the `newton-cg` method in `minimize`.

#### Additional information



Problem statement:
BUG: minimize(method="newton-cg") crashes with UnboundLocalError if xtol=0
### Describe your issue.

I was trying to debug an issue where I was unable to find the minimum of a function with Newton-CG. As one of my debugging steps, I tried setting the solver option `xtol` to zero. I expected this to disable termination due to x convergence, but what actually happens is that it crashes.

### Reproducing Code Example

```python
import math
import scipy.optimize


def cosine(x):
    f = math.cos(x[0])
    print(f"f({x[0]}) = {f}")
    return f


def jac(x):
    ret = -math.sin(x)
    return ret


x0 = [0.1]
xtol = 0  # crashes with UnboundLocalError
# xtol = 1e-10  # works
result = scipy.optimize.minimize(cosine, x0=x0, jac=jac, method="newton-cg", options=dict(xtol=xtol))

print(result)
```


### Error message

```shell
---------------------------------------------------------------------------
UnboundLocalError                         Traceback (most recent call last)
Input In [41], in <cell line: 19>()
     17 xtol = 0  # crashes with UnboundLocalError
     18 # xtol = 1e-10  # works
---> 19 result = scipy.optimize.minimize(cosine, x0=x0, jac=jac, method="newton-cg", options=dict(xtol=xtol))
     21 print(result)

File ~/.local/lib/python3.10/site-packages/scipy/optimize/_minimize.py:710, in minimize(fun, x0, args, method, jac, hess, hessp, bounds, constraints, tol, callback, options)
    708     res = _minimize_bfgs(fun, x0, args, jac, callback, **options)
    709 elif meth == 'newton-cg':
--> 710     res = _minimize_newtoncg(fun, x0, args, jac, hess, hessp, callback,
    711                              **options)
    712 elif meth == 'l-bfgs-b':
    713     res = _minimize_lbfgsb(fun, x0, args, jac, bounds,
    714                            callback=callback, **options)

File ~/.local/lib/python3.10/site-packages/scipy/optimize/_optimize.py:2233, in _minimize_newtoncg(fun, x0, args, jac, hess, hessp, callback, xtol, eps, maxiter, disp, return_all, c1, c2, **unknown_options)
   2230     update_l1norm = np.linalg.norm(update, ord=1)
   2232 else:
-> 2233     if np.isnan(old_fval) or np.isnan(update).any():
   2234         return terminate(3, _status_message['nan'])
   2236     msg = _status_message['success']

UnboundLocalError: local variable 'update' referenced before assignment
```


### SciPy/NumPy/Python version and system information

```shell
1.12.0 1.23.5 sys.version_info(major=3, minor=10, micro=12, releaselevel='final', serial=0)
Build Dependencies:
  blas:
    detection method: pkgconfig
    found: true
    include directory: /usr/local/include
    lib directory: /usr/local/lib
    name: openblas
    openblas configuration: USE_64BITINT= DYNAMIC_ARCH=1 DYNAMIC_OLDER= NO_CBLAS=
      NO_LAPACK= NO_LAPACKE= NO_AFFINITY=1 USE_OPENMP= HASWELL MAX_THREADS=2
    pc file directory: /usr/local/lib/pkgconfig
    version: 0.3.21.dev
  lapack:
    detection method: pkgconfig
    found: true
    include directory: /usr/local/include
    lib directory: /usr/local/lib
    name: openblas
    openblas configuration: USE_64BITINT= DYNAMIC_ARCH=1 DYNAMIC_OLDER= NO_CBLAS=
      NO_LAPACK= NO_LAPACKE= NO_AFFINITY=1 USE_OPENMP= HASWELL MAX_THREADS=2
    pc file directory: /usr/local/lib/pkgconfig
    version: 0.3.21.dev
  pybind11:
    detection method: config-tool
    include directory: unknown
    name: pybind11
    version: 2.11.1
Compilers:
  c:
    commands: cc
    linker: ld.bfd
    name: gcc
    version: 10.2.1
  c++:
    commands: c++
    linker: ld.bfd
    name: gcc
    version: 10.2.1
  cython:
    commands: cython
    linker: cython
    name: cython
    version: 3.0.8
  fortran:
    commands: gfortran
    linker: ld.bfd
    name: gcc
    version: 10.2.1
  pythran:
    include directory: ../../tmp/pip-build-env-oj5r1eje/overlay/lib/python3.10/site-packages/pythran
    version: 0.15.0
Machine Information:
  build:
    cpu: x86_64
    endian: little
    family: x86_64
    system: linux
  cross-compiled: false
  host:
    cpu: x86_64
    endian: little
    family: x86_64
    system: linux
Python Information:
  path: /opt/python/cp310-cp310/bin/python
  version: '3.10'
```

Hints from issue discussion:
I've done some reading of the code involved, and it seems to be related to the termination condition of this loop:

https://github.com/scipy/scipy/blob/4edfcaa3ce8a387450b6efce968572def71be089/scipy/optimize/_optimize.py#L2151

`update_l1norm` is the l1norm of the previous update. Before the loop, it is set to 2 * xtol, which is intended to cause the loop to run at least once. However, if xtol = 0, then it is comparing 0 > 0, which is false, which then checks this condition.

https://github.com/scipy/scipy/blob/4edfcaa3ce8a387450b6efce968572def71be089/scipy/optimize/_optimize.py#L2233

Since `update` is defined in the loop, this is implicitly assuming that the previous loop ran at least once.
I've raised a PR to close this issue: https://github.com/scipy/scipy/pull/20299

I agree that the initial value of `update_l1norm` was chosen to ensure the loop runs at least once, but this fails for `xtol = 0`, so a simple fix.
`UnboundLocalError: local variable 'update' referenced before assignment` is a trivial Python programming error, and should be fixed ASAP, especially if the fix is small. I'm milestoning this for 1.13, though it's of course not a release blocker.

Commit message: TST: Optimize: NewtonCF Minimize when xtol=0

Regression test for gh-20214 which addressed an issue in the
Newton CG method which would raise an UnboundLocalVariable error
if `xtol` was set to zero. It also ensures the method finds the
solution in this case.

Patch to review:
diff --git a/scipy/optimize/_optimize.py b/scipy/optimize/_optimize.py
index d16b4512be71..c4c0c717f697 100644
--- a/scipy/optimize/_optimize.py
+++ b/scipy/optimize/_optimize.py
@@ -1153,7 +1153,7 @@ def _line_search_wolfe12(f, fprime, xk, pk, gfk, old_fval, old_old_fval,
 
 def fmin_bfgs(f, x0, fprime=None, args=(), gtol=1e-5, norm=np.inf,
               epsilon=_epsilon, maxiter=None, full_output=0, disp=1,
-              retall=0, callback=None, xrtol=0, c1=1e-4, c2=0.9, 
+              retall=0, callback=None, xrtol=0, c1=1e-4, c2=0.9,
               hess_inv0=None):
     """
     Minimize a function using the BFGS algorithm.
@@ -1226,7 +1226,7 @@ def fmin_bfgs(f, x0, fprime=None, args=(), gtol=1e-5, norm=np.inf,
     Optimize the function, `f`, whose gradient is given by `fprime`
     using the quasi-Newton method of Broyden, Fletcher, Goldfarb,
     and Shanno (BFGS).
-    
+
     Parameters `c1` and `c2` must satisfy ``0 < c1 < c2 < 1``.
 
     See Also
@@ -1298,7 +1298,7 @@ def fmin_bfgs(f, x0, fprime=None, args=(), gtol=1e-5, norm=np.inf,
 def _minimize_bfgs(fun, x0, args=(), jac=None, callback=None,
                    gtol=1e-5, norm=np.inf, eps=_epsilon, maxiter=None,
                    disp=False, return_all=False, finite_diff_rel_step=None,
-                   xrtol=0, c1=1e-4, c2=0.9, 
+                   xrtol=0, c1=1e-4, c2=0.9,
                    hess_inv0=None, **unknown_options):
     """
     Minimization of scalar function of one or more variables using the
@@ -2025,7 +2025,7 @@ def terminate(warnflag, msg):
     cg_maxiter = 20*len(x0)
 
     xtol = len(x0) * avextol
-    update_l1norm = 2 * xtol
+    update_l1norm = np.finfo(float).max
     xk = np.copy(x0)
     if retall:
         allvecs = [xk]
@@ -2116,7 +2116,7 @@ def terminate(warnflag, msg):
         update_l1norm = np.linalg.norm(update, ord=1)
 
     else:
-        if np.isnan(old_fval) or np.isnan(update).any():
+        if np.isnan(old_fval) or np.isnan(update_l1norm):
             return terminate(3, _status_message['nan'])
 
         msg = _status_message['success']
diff --git a/scipy/optimize/tests/test_optimize.py b/scipy/optimize/tests/test_optimize.py
index 2953076aaee5..b9a7c596f772 100644
--- a/scipy/optimize/tests/test_optimize.py
+++ b/scipy/optimize/tests/test_optimize.py
@@ -213,9 +213,9 @@ def test_bfgs(self):
                         [[0, -5.25060743e-01, 4.87748473e-01],
                          [0, -5.24885582e-01, 4.87530347e-01]],
                         atol=1e-14, rtol=1e-7)
-    
+
     def test_bfgs_hess_inv0_neg(self):
-        # Ensure that BFGS does not accept neg. def. initial inverse 
+        # Ensure that BFGS does not accept neg. def. initial inverse
         # Hessian estimate.
         with pytest.raises(ValueError, match="'hess_inv0' matrix isn't "
                            "positive definite."):
@@ -223,9 +223,9 @@ def test_bfgs_hess_inv0_neg(self):
             opts = {'disp': self.disp, 'hess_inv0': -np.eye(5)}
             optimize.minimize(optimize.rosen, x0=x0, method='BFGS', args=(),
                               options=opts)
-    
+
     def test_bfgs_hess_inv0_semipos(self):
-        # Ensure that BFGS does not accept semi pos. def. initial inverse 
+        # Ensure that BFGS does not accept semi pos. def. initial inverse
         # Hessian estimate.
         with pytest.raises(ValueError, match="'hess_inv0' matrix isn't "
                            "positive definite."):
@@ -235,18 +235,18 @@ def test_bfgs_hess_inv0_semipos(self):
             opts = {'disp': self.disp, 'hess_inv0': hess_inv0}
             optimize.minimize(optimize.rosen, x0=x0, method='BFGS', args=(),
                               options=opts)
-    
+
     def test_bfgs_hess_inv0_sanity(self):
         # Ensure that BFGS handles `hess_inv0` parameter correctly.
         fun = optimize.rosen
         x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
         opts = {'disp': self.disp, 'hess_inv0': 1e-2 * np.eye(5)}
-        res = optimize.minimize(fun, x0=x0, method='BFGS', args=(), 
+        res = optimize.minimize(fun, x0=x0, method='BFGS', args=(),
                                 options=opts)
-        res_true = optimize.minimize(fun, x0=x0, method='BFGS', args=(), 
+        res_true = optimize.minimize(fun, x0=x0, method='BFGS', args=(),
                                      options={'disp': self.disp})
         assert_allclose(res.fun, res_true.fun, atol=1e-6)
-            
+
     @pytest.mark.filterwarnings('ignore::UserWarning')
     def test_bfgs_infinite(self):
         # Test corner case where -Inf is the minimum.  See gh-2019.
@@ -293,7 +293,7 @@ def test_bfgs_c2(self):
         res_mod = optimize.minimize(optimize.rosen,
                                     x0, method='bfgs', options={'c2': 1e-2})
         assert res_default.nit > res_mod.nit
-    
+
     @pytest.mark.parametrize(["c1", "c2"], [[0.5, 2],
                                             [-0.1, 0.1],
                                             [0.2, 0.1]])
@@ -507,6 +507,23 @@ def test_ncg_negative_maxiter(self):
                                    args=(), options=opts)
         assert result.status == 1
 
+    def test_ncg_zero_xtol(self):
+        # Regression test for gh-20214
+        def cosine(x):
+            return np.cos(x[0])
+
+        def jac(x):
+            return -np.sin(x)
+
+        x0 = [0.1]
+        xtol = 0
+        result = optimize.minimize(cosine,
+                                   x0=x0,
+                                   jac=jac,
+                                   method="newton-cg",
+                                   options=dict(xtol=xtol))
+        assert result.status == 0
+
     def test_ncg(self):
         # line-search Newton conjugate gradient optimization routine
         if self.use_wrapper:


Code review comments:
diff_hunk: @@ -2025,7 +2025,7 @@ def terminate(warnflag, msg):
     cg_maxiter = 20*len(x0)
 
     xtol = len(x0) * avextol
-    update_l1norm = 2 * xtol
+    update_l1norm = np.finfo(float).max
path: scipy/optimize/_optimize.py
text: @user1:
```suggestion
    # Make sure we enter the while loop.
    update_l1norm = np.finfo(float).max
```