Coverage for /usr/lib/python3/dist-packages/scipy/optimize/_tnc.py: 31%
77 statements
« prev ^ index » next coverage.py v7.9.1, created at 2025-06-14 15:55 +0200
1# TNC Python interface
2# @(#) $Jeannot: tnc.py,v 1.11 2005/01/28 18:27:31 js Exp $
4# Copyright (c) 2004-2005, Jean-Sebastien Roy (js@jeannot.org)
6# Permission is hereby granted, free of charge, to any person obtaining a
7# copy of this software and associated documentation files (the
8# "Software"), to deal in the Software without restriction, including
9# without limitation the rights to use, copy, modify, merge, publish,
10# distribute, sublicense, and/or sell copies of the Software, and to
11# permit persons to whom the Software is furnished to do so, subject to
12# the following conditions:
14# The above copyright notice and this permission notice shall be included
15# in all copies or substantial portions of the Software.
17# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
20# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
21# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
22# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
23# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25"""
26TNC: A Python interface to the TNC non-linear optimizer
28TNC is a non-linear optimizer. To use it, you must provide a function to
29minimize. The function must take one argument: the list of coordinates where to
30evaluate the function; and it must return either a tuple, whose first element is the
31value of the function, and whose second argument is the gradient of the function
32(as a list of values); or None, to abort the minimization.
33"""
35from scipy.optimize import _moduleTNC as moduleTNC
36from ._optimize import (MemoizeJac, OptimizeResult, _check_unknown_options,
37 _prepare_scalar_function)
38from ._constraints import old_bound_to_new
40from numpy import inf, array, zeros, asfarray
42__all__ = ['fmin_tnc']
45MSG_NONE = 0 # No messages
46MSG_ITER = 1 # One line per iteration
47MSG_INFO = 2 # Informational messages
48MSG_VERS = 4 # Version info
49MSG_EXIT = 8 # Exit reasons
50MSG_ALL = MSG_ITER + MSG_INFO + MSG_VERS + MSG_EXIT
52MSGS = {
53 MSG_NONE: "No messages",
54 MSG_ITER: "One line per iteration",
55 MSG_INFO: "Informational messages",
56 MSG_VERS: "Version info",
57 MSG_EXIT: "Exit reasons",
58 MSG_ALL: "All messages"
59}
61INFEASIBLE = -1 # Infeasible (lower bound > upper bound)
62LOCALMINIMUM = 0 # Local minimum reached (|pg| ~= 0)
63FCONVERGED = 1 # Converged (|f_n-f_(n-1)| ~= 0)
64XCONVERGED = 2 # Converged (|x_n-x_(n-1)| ~= 0)
65MAXFUN = 3 # Max. number of function evaluations reached
66LSFAIL = 4 # Linear search failed
67CONSTANT = 5 # All lower bounds are equal to the upper bounds
68NOPROGRESS = 6 # Unable to progress
69USERABORT = 7 # User requested end of minimization
71RCSTRINGS = {
72 INFEASIBLE: "Infeasible (lower bound > upper bound)",
73 LOCALMINIMUM: "Local minimum reached (|pg| ~= 0)",
74 FCONVERGED: "Converged (|f_n-f_(n-1)| ~= 0)",
75 XCONVERGED: "Converged (|x_n-x_(n-1)| ~= 0)",
76 MAXFUN: "Max. number of function evaluations reached",
77 LSFAIL: "Linear search failed",
78 CONSTANT: "All lower bounds are equal to the upper bounds",
79 NOPROGRESS: "Unable to progress",
80 USERABORT: "User requested end of minimization"
81}
83# Changes to interface made by Travis Oliphant, Apr. 2004 for inclusion in
84# SciPy
87def fmin_tnc(func, x0, fprime=None, args=(), approx_grad=0,
88 bounds=None, epsilon=1e-8, scale=None, offset=None,
89 messages=MSG_ALL, maxCGit=-1, maxfun=None, eta=-1,
90 stepmx=0, accuracy=0, fmin=0, ftol=-1, xtol=-1, pgtol=-1,
91 rescale=-1, disp=None, callback=None):
92 """
93 Minimize a function with variables subject to bounds, using
94 gradient information in a truncated Newton algorithm. This
95 method wraps a C implementation of the algorithm.
97 Parameters
98 ----------
99 func : callable ``func(x, *args)``
100 Function to minimize. Must do one of:
102 1. Return f and g, where f is the value of the function and g its
103 gradient (a list of floats).
105 2. Return the function value but supply gradient function
106 separately as `fprime`.
108 3. Return the function value and set ``approx_grad=True``.
110 If the function returns None, the minimization
111 is aborted.
112 x0 : array_like
113 Initial estimate of minimum.
114 fprime : callable ``fprime(x, *args)``, optional
115 Gradient of `func`. If None, then either `func` must return the
116 function value and the gradient (``f,g = func(x, *args)``)
117 or `approx_grad` must be True.
118 args : tuple, optional
119 Arguments to pass to function.
120 approx_grad : bool, optional
121 If true, approximate the gradient numerically.
122 bounds : list, optional
123 (min, max) pairs for each element in x0, defining the
124 bounds on that parameter. Use None or +/-inf for one of
125 min or max when there is no bound in that direction.
126 epsilon : float, optional
127 Used if approx_grad is True. The stepsize in a finite
128 difference approximation for fprime.
129 scale : array_like, optional
130 Scaling factors to apply to each variable. If None, the
131 factors are up-low for interval bounded variables and
132 1+|x| for the others. Defaults to None.
133 offset : array_like, optional
134 Value to subtract from each variable. If None, the
135 offsets are (up+low)/2 for interval bounded variables
136 and x for the others.
137 messages : int, optional
138 Bit mask used to select messages display during
139 minimization values defined in the MSGS dict. Defaults to
140 MGS_ALL.
141 disp : int, optional
142 Integer interface to messages. 0 = no message, 5 = all messages
143 maxCGit : int, optional
144 Maximum number of hessian*vector evaluations per main
145 iteration. If maxCGit == 0, the direction chosen is
146 -gradient if maxCGit < 0, maxCGit is set to
147 max(1,min(50,n/2)). Defaults to -1.
148 maxfun : int, optional
149 Maximum number of function evaluation. If None, maxfun is
150 set to max(100, 10*len(x0)). Defaults to None. Note that this function
151 may violate the limit because of evaluating gradients by numerical
152 differentiation.
153 eta : float, optional
154 Severity of the line search. If < 0 or > 1, set to 0.25.
155 Defaults to -1.
156 stepmx : float, optional
157 Maximum step for the line search. May be increased during
158 call. If too small, it will be set to 10.0. Defaults to 0.
159 accuracy : float, optional
160 Relative precision for finite difference calculations. If
161 <= machine_precision, set to sqrt(machine_precision).
162 Defaults to 0.
163 fmin : float, optional
164 Minimum function value estimate. Defaults to 0.
165 ftol : float, optional
166 Precision goal for the value of f in the stopping criterion.
167 If ftol < 0.0, ftol is set to 0.0 defaults to -1.
168 xtol : float, optional
169 Precision goal for the value of x in the stopping
170 criterion (after applying x scaling factors). If xtol <
171 0.0, xtol is set to sqrt(machine_precision). Defaults to
172 -1.
173 pgtol : float, optional
174 Precision goal for the value of the projected gradient in
175 the stopping criterion (after applying x scaling factors).
176 If pgtol < 0.0, pgtol is set to 1e-2 * sqrt(accuracy).
177 Setting it to 0.0 is not recommended. Defaults to -1.
178 rescale : float, optional
179 Scaling factor (in log10) used to trigger f value
180 rescaling. If 0, rescale at each iteration. If a large
181 value, never rescale. If < 0, rescale is set to 1.3.
182 callback : callable, optional
183 Called after each iteration, as callback(xk), where xk is the
184 current parameter vector.
186 Returns
187 -------
188 x : ndarray
189 The solution.
190 nfeval : int
191 The number of function evaluations.
192 rc : int
193 Return code, see below
195 See also
196 --------
197 minimize: Interface to minimization algorithms for multivariate
198 functions. See the 'TNC' `method` in particular.
200 Notes
201 -----
202 The underlying algorithm is truncated Newton, also called
203 Newton Conjugate-Gradient. This method differs from
204 scipy.optimize.fmin_ncg in that
206 1. it wraps a C implementation of the algorithm
207 2. it allows each variable to be given an upper and lower bound.
209 The algorithm incorporates the bound constraints by determining
210 the descent direction as in an unconstrained truncated Newton,
211 but never taking a step-size large enough to leave the space
212 of feasible x's. The algorithm keeps track of a set of
213 currently active constraints, and ignores them when computing
214 the minimum allowable step size. (The x's associated with the
215 active constraint are kept fixed.) If the maximum allowable
216 step size is zero then a new constraint is added. At the end
217 of each iteration one of the constraints may be deemed no
218 longer active and removed. A constraint is considered
219 no longer active is if it is currently active
220 but the gradient for that variable points inward from the
221 constraint. The specific constraint removed is the one
222 associated with the variable of largest index whose
223 constraint is no longer active.
225 Return codes are defined as follows::
227 -1 : Infeasible (lower bound > upper bound)
228 0 : Local minimum reached (|pg| ~= 0)
229 1 : Converged (|f_n-f_(n-1)| ~= 0)
230 2 : Converged (|x_n-x_(n-1)| ~= 0)
231 3 : Max. number of function evaluations reached
232 4 : Linear search failed
233 5 : All lower bounds are equal to the upper bounds
234 6 : Unable to progress
235 7 : User requested end of minimization
237 References
238 ----------
239 Wright S., Nocedal J. (2006), 'Numerical Optimization'
241 Nash S.G. (1984), "Newton-Type Minimization Via the Lanczos Method",
242 SIAM Journal of Numerical Analysis 21, pp. 770-778
244 """
245 # handle fprime/approx_grad
246 if approx_grad:
247 fun = func
248 jac = None
249 elif fprime is None:
250 fun = MemoizeJac(func)
251 jac = fun.derivative
252 else:
253 fun = func
254 jac = fprime
256 if disp is not None: # disp takes precedence over messages
257 mesg_num = disp
258 else:
259 mesg_num = {0:MSG_NONE, 1:MSG_ITER, 2:MSG_INFO, 3:MSG_VERS,
260 4:MSG_EXIT, 5:MSG_ALL}.get(messages, MSG_ALL)
261 # build options
262 opts = {'eps': epsilon,
263 'scale': scale,
264 'offset': offset,
265 'mesg_num': mesg_num,
266 'maxCGit': maxCGit,
267 'maxfun': maxfun,
268 'eta': eta,
269 'stepmx': stepmx,
270 'accuracy': accuracy,
271 'minfev': fmin,
272 'ftol': ftol,
273 'xtol': xtol,
274 'gtol': pgtol,
275 'rescale': rescale,
276 'disp': False}
278 res = _minimize_tnc(fun, x0, args, jac, bounds, callback=callback, **opts)
280 return res['x'], res['nfev'], res['status']
283def _minimize_tnc(fun, x0, args=(), jac=None, bounds=None,
284 eps=1e-8, scale=None, offset=None, mesg_num=None,
285 maxCGit=-1, eta=-1, stepmx=0, accuracy=0,
286 minfev=0, ftol=-1, xtol=-1, gtol=-1, rescale=-1, disp=False,
287 callback=None, finite_diff_rel_step=None, maxfun=None,
288 **unknown_options):
289 """
290 Minimize a scalar function of one or more variables using a truncated
291 Newton (TNC) algorithm.
293 Options
294 -------
295 eps : float or ndarray
296 If `jac is None` the absolute step size used for numerical
297 approximation of the jacobian via forward differences.
298 scale : list of floats
299 Scaling factors to apply to each variable. If None, the
300 factors are up-low for interval bounded variables and
301 1+|x] fo the others. Defaults to None.
302 offset : float
303 Value to subtract from each variable. If None, the
304 offsets are (up+low)/2 for interval bounded variables
305 and x for the others.
306 disp : bool
307 Set to True to print convergence messages.
308 maxCGit : int
309 Maximum number of hessian*vector evaluations per main
310 iteration. If maxCGit == 0, the direction chosen is
311 -gradient if maxCGit < 0, maxCGit is set to
312 max(1,min(50,n/2)). Defaults to -1.
313 eta : float
314 Severity of the line search. If < 0 or > 1, set to 0.25.
315 Defaults to -1.
316 stepmx : float
317 Maximum step for the line search. May be increased during
318 call. If too small, it will be set to 10.0. Defaults to 0.
319 accuracy : float
320 Relative precision for finite difference calculations. If
321 <= machine_precision, set to sqrt(machine_precision).
322 Defaults to 0.
323 minfev : float
324 Minimum function value estimate. Defaults to 0.
325 ftol : float
326 Precision goal for the value of f in the stopping criterion.
327 If ftol < 0.0, ftol is set to 0.0 defaults to -1.
328 xtol : float
329 Precision goal for the value of x in the stopping
330 criterion (after applying x scaling factors). If xtol <
331 0.0, xtol is set to sqrt(machine_precision). Defaults to
332 -1.
333 gtol : float
334 Precision goal for the value of the projected gradient in
335 the stopping criterion (after applying x scaling factors).
336 If gtol < 0.0, gtol is set to 1e-2 * sqrt(accuracy).
337 Setting it to 0.0 is not recommended. Defaults to -1.
338 rescale : float
339 Scaling factor (in log10) used to trigger f value
340 rescaling. If 0, rescale at each iteration. If a large
341 value, never rescale. If < 0, rescale is set to 1.3.
342 finite_diff_rel_step : None or array_like, optional
343 If `jac in ['2-point', '3-point', 'cs']` the relative step size to
344 use for numerical approximation of the jacobian. The absolute step
345 size is computed as ``h = rel_step * sign(x) * max(1, abs(x))``,
346 possibly adjusted to fit into the bounds. For ``method='3-point'``
347 the sign of `h` is ignored. If None (default) then step is selected
348 automatically.
349 maxfun : int
350 Maximum number of function evaluations. If None, `maxfun` is
351 set to max(100, 10*len(x0)). Defaults to None.
352 """
353 _check_unknown_options(unknown_options)
354 fmin = minfev
355 pgtol = gtol
357 x0 = asfarray(x0).flatten()
358 n = len(x0)
360 if bounds is None:
361 bounds = [(None,None)] * n
362 if len(bounds) != n:
363 raise ValueError('length of x0 != length of bounds')
364 new_bounds = old_bound_to_new(bounds)
366 if mesg_num is not None:
367 messages = {0:MSG_NONE, 1:MSG_ITER, 2:MSG_INFO, 3:MSG_VERS,
368 4:MSG_EXIT, 5:MSG_ALL}.get(mesg_num, MSG_ALL)
369 elif disp:
370 messages = MSG_ALL
371 else:
372 messages = MSG_NONE
374 sf = _prepare_scalar_function(fun, x0, jac=jac, args=args, epsilon=eps,
375 finite_diff_rel_step=finite_diff_rel_step,
376 bounds=new_bounds)
377 func_and_grad = sf.fun_and_grad
379 """
380 low, up : the bounds (lists of floats)
381 if low is None, the lower bounds are removed.
382 if up is None, the upper bounds are removed.
383 low and up defaults to None
384 """
385 low = zeros(n)
386 up = zeros(n)
387 for i in range(n):
388 if bounds[i] is None:
389 l, u = -inf, inf
390 else:
391 l,u = bounds[i]
392 if l is None:
393 low[i] = -inf
394 else:
395 low[i] = l
396 if u is None:
397 up[i] = inf
398 else:
399 up[i] = u
401 if scale is None:
402 scale = array([])
404 if offset is None:
405 offset = array([])
407 if maxfun is None:
408 maxfun = max(100, 10*len(x0))
410 rc, nf, nit, x, funv, jacv = moduleTNC.tnc_minimize(
411 func_and_grad, x0, low, up, scale,
412 offset, messages, maxCGit, maxfun,
413 eta, stepmx, accuracy, fmin, ftol,
414 xtol, pgtol, rescale, callback
415 )
416 # the TNC documentation states: "On output, x, f and g may be very
417 # slightly out of sync because of scaling". Therefore re-evaluate
418 # func_and_grad so they are synced.
419 funv, jacv = func_and_grad(x)
421 return OptimizeResult(x=x, fun=funv, jac=jacv, nfev=sf.nfev,
422 nit=nit, status=rc, message=RCSTRINGS[rc],
423 success=(-1 < rc < 3))