← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/python-scipy/oneiric-proposed

« back to all changes in this revision

Viewing changes to Lib/optimize/tnc.py

  • Committer: Bazaar Package Importer
  • Author(s): Ondrej Certik
  • Date: 2008-06-16 22:58:01 UTC
  • mfrom: (2.1.24 intrepid)
  • Revision ID: james.westby@ubuntu.com-20080616225801-irdhrpcwiocfbcmt
Tags: 0.6.0-12
http://bugs.debian.org/489149
* The description updated to match the current SciPy (Closes: #489149).
* Standards-Version bumped to 3.8.0 (no action needed)
* Build-Depends: netcdf-dev changed to libnetcdf-dev

Show diffs side-by-side

added added

removed removed

Lines of Context:
Lib/optimize/tnc.py
1
 
## Automatically adapted for scipy Oct 07, 2005 by convertcode.py
2
 
 
3
 
# TNC Python interface
4
 
# @(#) $Jeannot: tnc.py,v 1.7 2004/04/02 20:40:21 js Exp $
5
 
 
6
 
# Copyright (c) 2004, Jean-Sebastien Roy (js@jeannot.org)
7
 
 
8
 
# Permission is hereby granted, free of charge, to any person obtaining a
9
 
# copy of this software and associated documentation files (the
10
 
# "Software"), to deal in the Software without restriction, including
11
 
# without limitation the rights to use, copy, modify, merge, publish,
12
 
# distribute, sublicense, and/or sell copies of the Software, and to
13
 
# permit persons to whom the Software is furnished to do so, subject to
14
 
# the following conditions:
15
 
 
16
 
# The above copyright notice and this permission notice shall be included
17
 
# in all copies or substantial portions of the Software.
18
 
 
19
 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
20
 
# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21
 
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
22
 
# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
23
 
# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
24
 
# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
25
 
# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
26
 
 
27
 
"""
28
 
TNC: A python interface to the TNC non-linear optimizer
29
 
 
30
 
TNC is a non-linear optimizer. To use it, you must provide a function to
31
 
minimize. The function must take one argument: the list of coordinates where to
32
 
evaluate the function; and it must return either a tuple, whose first element is the
33
 
value of the function, and whose second argument is the gradient of the function
34
 
(as a list of values); or None, to abort the minimization.
35
 
"""
36
 
 
37
 
import moduleTNC
38
 
from numpy import asarray
39
 
 
40
 
MSG_NONE = 0 # No messages
41
 
MSG_ITER = 1 # One line per iteration
42
 
MSG_INFO = 2 # Informational messages
43
 
MSG_VERS = 4 # Version info
44
 
MSG_EXIT = 8 # Exit reasons
45
 
MSG_ALL = MSG_ITER + MSG_INFO + MSG_VERS + MSG_EXIT
46
 
 
47
 
MSGS = {
48
 
        MSG_NONE : "No messages",
49
 
        MSG_ITER : "One line per iteration",
50
 
        MSG_INFO : "Informational messages",
51
 
        MSG_VERS : "Version info",
52
 
        MSG_EXIT : "Exit reasons",
53
 
        MSG_ALL  : "All messages"
54
 
}
55
 
 
56
 
HUGE_VAL=1e500 # No standard representation of Infinity in Python 2.3.3
57
 
               # FIXME: can we use inf now that we have numpy and IEEE floats?
58
 
 
59
 
EINVAL       = -2 # Invalid parameters (n<1)
60
 
INFEASIBLE   = -1 # Infeasible (low > up)
61
 
LOCALMINIMUM =  0 # Local minima reach (|pg| ~= 0)
62
 
CONVERGED    =  1 # Converged (|f_n-f_(n-1)| ~= 0)
63
 
MAXFUN       =  2 # Max. number of function evaluations reach
64
 
LSFAIL       =  3 # Linear search failed
65
 
CONSTANT     =  4 # All lower bounds are equal to the upper bounds
66
 
NOPROGRESS   =  5 # Unable to progress
67
 
USERABORT    =  6 # User requested end of minimization
68
 
 
69
 
RCSTRINGS = {
70
 
        EINVAL       : "Invalid parameters (n<1)",
71
 
        INFEASIBLE   : "Infeasible (low > up)",
72
 
        LOCALMINIMUM : "Local minima reach (|pg| ~= 0)",
73
 
        CONVERGED    : "Converged (|f_n-f_(n-1)| ~= 0)",
74
 
        MAXFUN       : "Max. number of function evaluations reach",
75
 
        LSFAIL       : "Linear search failed",
76
 
        CONSTANT     : "All lower bounds are equal to the upper bounds",
77
 
        NOPROGRESS   : "Unable to progress",
78
 
        USERABORT    : "User requested end of minimization"
79
 
}
80
 
 
81
 
 
82
 
# Changes to interface made by Travis Oliphant, Apr. 2004 for inclusion in
83
 
#  SciPy
84
 
 
85
 
import optimize
86
 
approx_fprime = optimize.approx_fprime
87
 
 
88
 
 
89
 
def fmin_tnc(func, x0, fprime=None, args=(), approx_grad=0, bounds=None, epsilon=1e-8,
90
 
             scale=None, messages=MSG_ALL, maxCGit=-1, maxfun=None, eta=-1,
91
 
             stepmx=0, accuracy=0, fmin=0, ftol=0, rescale=-1):
92
 
    """Minimize a function with variables subject to bounds, using gradient
93
 
    information.
94
 
 
95
 
    returns (rc, nfeval, x).
96
 
 
97
 
    Inputs:
98
 
 
99
 
    func    -- function to minimize. Called as func(x, *args)
100
 
 
101
 
    x0      -- initial guess to minimum
102
 
 
103
 
    fprime  -- gradient of func. If None, then func returns the function
104
 
               value and the gradient ( f, g = func(x, *args) ).
105
 
               Called as fprime(x, *args)
106
 
 
107
 
    args    -- arguments to pass to function
108
 
 
109
 
    approx_grad -- if true, approximate the gradient numerically
110
 
 
111
 
    bounds  -- a list of (min, max) pairs for each element in x, defining
112
 
               the bounds on that parameter. Use None for one of min or max
113
 
               when there is no bound in that direction
114
 
 
115
 
        scale     : scaling factors to apply to each variable (a list of floats)
116
 
                    if None, the factors are up-low for interval bounded variables
117
 
                    and 1+|x] fo the others.
118
 
                    defaults to None
119
 
        messages  : bit mask used to select messages display during minimization
120
 
                    values defined in the optimize.tnc.MSGS dict.
121
 
                    defaults to optimize.tnc.MGS_ALL
122
 
        maxCGit   : max. number of hessian*vector evaluation per main iteration
123
 
                    if maxCGit == 0, the direction chosen is -gradient
124
 
                    if maxCGit < 0, maxCGit is set to max(1,min(50,n/2))
125
 
                    defaults to -1
126
 
        maxfun    : max. number of function evaluation
127
 
                    if None, maxnfeval is set to max(1000, 100*len(x0))
128
 
                    defaults to None
129
 
        eta       : severity of the line search. if < 0 or > 1, set to 0.25
130
 
                    defaults to -1
131
 
        stepmx    : maximum step for the line search. may be increased during call
132
 
                    if too small, will be set to 10.0
133
 
                    defaults to 0
134
 
        accuracy  : relative precision for finite difference calculations
135
 
                    if <= machine_precision, set to sqrt(machine_precision)
136
 
                    defaults to 0
137
 
        fmin      : minimum function value estimate
138
 
                    defaults to 0
139
 
        ftol      : precision goal for the value of f in the stoping criterion
140
 
                    relative to the machine precision and the value of f.
141
 
                    if ftol < 0.0, ftol is set to 0.0
142
 
                    defaults to 0
143
 
        rescale   : Scaling factor (in log10) used to trigger rescaling
144
 
                    if 0, rescale at each iteration
145
 
                    if a large value, never rescale
146
 
                    if < 0, rescale is set to 1.3
147
 
 
148
 
    Outputs:
149
 
 
150
 
        x         : the solution (a list of floats)
151
 
        nfeval    : the number of function evaluations
152
 
        rc        : return code (corresponding message in optimize.tnc.RCSTRINGS)
153
 
 
154
 
    See also:
155
 
 
156
 
      fmin, fmin_powell, fmin_cg,
157
 
             fmin_bfgs, fmin_ncg -- multivariate local optimizers
158
 
      leastsq -- nonlinear least squares minimizer
159
 
 
160
 
      fmin_l_bfgs_b, fmin_tnc,
161
 
             fmin_cobyla -- constrained multivariate optimizers
162
 
 
163
 
      anneal, brute -- global optimizers
164
 
 
165
 
      fminbound, brent, golden, bracket -- local scalar minimizers
166
 
 
167
 
      fsolve -- n-dimenstional root-finding
168
 
 
169
 
      brentq, brenth, ridder, bisect, newton -- one-dimensional root-finding
170
 
 
171
 
      fixed_point -- scalar fixed-point finder
172
 
 
173
 
    """
174
 
 
175
 
    n = len(x0)
176
 
 
177
 
    if bounds is None:
178
 
        bounds = [(None,None)] * n
179
 
    if len(bounds) != n:
180
 
        raise ValueError('length of x0 != length of bounds')
181
 
 
182
 
    if approx_grad:
183
 
        def func_and_grad(x):
184
 
            x = asarray(x)
185
 
            f = func(x, *args)
186
 
            g = approx_fprime(x, func, epsilon, *args)
187
 
            return f, list(g)
188
 
    elif fprime is None:
189
 
        def func_and_grad(x):
190
 
            x = asarray(x)
191
 
            f, g = func(x, *args)
192
 
            return f, list(g)
193
 
    else:
194
 
        def func_and_grad(x):
195
 
            x = asarray(x)
196
 
            f = func(x, *args)
197
 
            g = fprime(x, *args)
198
 
            return f, list(g)
199
 
 
200
 
    low = [0]*n
201
 
    up = [0]*n
202
 
    for i in range(n):
203
 
        l,u = bounds[i]
204
 
        if l is None:
205
 
            low[i] = -HUGE_VAL
206
 
        else:
207
 
            low[i] = l
208
 
        if u is None:
209
 
            up[i] = HUGE_VAL
210
 
        else:
211
 
            up[i] = u
212
 
 
213
 
    if scale == None:
214
 
        scale = []
215
 
 
216
 
    if maxfun == None:
217
 
        maxfun = max(1000, 100*len(x0))
218
 
 
219
 
    return moduleTNC.minimize(func_and_grad, x0, low, up, scale, messages,
220
 
                              maxCGit, maxfun, eta, stepmx, accuracy,
221
 
                              fmin, ftol, rescale)
222
 
 
223
 
if __name__ == '__main__':
224
 
        # Examples for TNC
225
 
 
226
 
    def example():
227
 
        print "Example"
228
 
        # A function to minimize
229
 
        def function(x):
230
 
            f = pow(x[0],2.0)+pow(abs(x[1]),3.0)
231
 
            g = [0,0]
232
 
            g[0] = 2.0*x[0]
233
 
            g[1] = 3.0*pow(abs(x[1]),2.0)
234
 
            if x[1]<0:
235
 
                g[1] = -g[1]
236
 
            return f, g
237
 
 
238
 
        # Optimizer call
239
 
        rc, nf, x = fmin_tnc(function, [-7, 3], bounds=([-10, 10], [1, 10]))
240
 
 
241
 
        print "After", nf, "function evaluations, TNC returned:", RCSTRINGS[rc]
242
 
        print "x =", x
243
 
        print "exact value = [0, 1]"
244
 
        print
245
 
 
246
 
    example()
247
 
 
248
 
    # Tests
249
 
    # These tests are taken from Prof. K. Schittkowski test examples for
250
 
    # constrained nonlinear programming.
251
 
    # http://www.uni-bayreuth.de/departments/math/~kschittkowski/home.htm
252
 
    tests = []
253
 
    def test1fg(x):
254
 
        f = 100.0*pow((x[1]-pow(x[0],2)),2)+pow(1.0-x[0],2)
255
 
        dif = [0,0]
256
 
        dif[1] = 200.0*(x[1]-pow(x[0],2))
257
 
        dif[0] = -2.0*(x[0]*(dif[1]-1.0)+1.0)
258
 
        return f, dif
259
 
    tests.append ((test1fg, [-2,1], ([-HUGE_VAL,None],[-1.5,None]), [1,1]))
260
 
 
261
 
    def test2fg(x):
262
 
        f = 100.0*pow((x[1]-pow(x[0],2)),2)+pow(1.0-x[0],2)
263
 
        dif = [0,0]
264
 
        dif[1] = 200.0*(x[1]-pow(x[0],2))
265
 
        dif[0] = -2.0*(x[0]*(dif[1]-1.0)+1.0)
266
 
        return f, dif
267
 
    tests.append ((test2fg, [-2,1], [(-HUGE_VAL,None),(1.5,None)], [-1.2210262419616387,1.5]))
268
 
 
269
 
    def test3fg(x):
270
 
        f = x[1]+pow(x[1]-x[0],2)*1.0e-5
271
 
        dif = [0,0]
272
 
        dif[0] = -2.0*(x[1]-x[0])*1.0e-5
273
 
        dif[1] = 1.0-dif[0]
274
 
        return f, dif
275
 
    tests.append ((test3fg, [10,1], [(-HUGE_VAL,None),(0.0, None)], [0,0]))
276
 
 
277
 
    def test4fg(x):
278
 
        f = pow(x[0]+1.0,3)/3.0+x[1]
279
 
        dif = [0,0]
280
 
        dif[0] = pow(x[0]+1.0,2)
281
 
        dif[1] = 1.0
282
 
        return f, dif
283
 
    tests.append ((test4fg, [1.125,0.125], [(1, None),(0, None)], [1,0]))
284
 
 
285
 
    from math import *
286
 
 
287
 
    def test5fg(x):
288
 
        f = sin(x[0]+x[1])+pow(x[0]-x[1],2)-1.5*x[0]+2.5*x[1]+1.0
289
 
        dif = [0,0]
290
 
        v1 = cos(x[0]+x[1]);
291
 
        v2 = 2.0*(x[0]-x[1]);
292
 
 
293
 
        dif[0] = v1+v2-1.5;
294
 
        dif[1] = v1-v2+2.5;
295
 
        return f, dif
296
 
    tests.append ((test5fg, [0,0], [(-1.5, 4),(-3,3)], [-0.54719755119659763, -1.5471975511965976]))
297
 
 
298
 
    def test38fg(x):
299
 
        f = (100.0*pow(x[1]-pow(x[0],2),2)+pow(1.0-x[0],2)+90.0*pow(x[3]-pow(x[2],2),2) \
300
 
                +pow(1.0-x[2],2)+10.1*(pow(x[1]-1.0,2)+pow(x[3]-1.0,2)) \
301
 
                +19.8*(x[1]-1.0)*(x[3]-1.0))*1.0e-5
302
 
        dif = [0,0,0,0]
303
 
        dif[0] = (-400.0*x[0]*(x[1]-pow(x[0],2))-2.0*(1.0-x[0]))*1.0e-5
304
 
        dif[1] = (200.0*(x[1]-pow(x[0],2))+20.2*(x[1]-1.0)+19.8*(x[3]-1.0))*1.0e-5
305
 
        dif[2] = (-360.0*x[2]*(x[3]-pow(x[2],2))-2.0*(1.0-x[2]))*1.0e-5
306
 
        dif[3] = (180.0*(x[3]-pow(x[2],2))+20.2*(x[3]-1.0)+19.8*(x[1]-1.0))*1.0e-5
307
 
        return f, dif
308
 
    tests.append ((test38fg, [-3,-1,-3,-1], [(-10,10)]*4, [1]*4))
309
 
 
310
 
    def test45fg(x):
311
 
        f = 2.0-x[0]*x[1]*x[2]*x[3]*x[4]/120.0
312
 
        dif = [0]*5
313
 
        dif[0] = -x[1]*x[2]*x[3]*x[4]/120.0
314
 
        dif[1] = -x[0]*x[2]*x[3]*x[4]/120.0
315
 
        dif[2] = -x[0]*x[1]*x[3]*x[4]/120.0
316
 
        dif[3] = -x[0]*x[1]*x[2]*x[4]/120.0
317
 
        dif[4] = -x[0]*x[1]*x[2]*x[3]/120.0
318
 
        return f, dif
319
 
    tests.append ((test45fg, [2]*5, [(0,1),(0,2),(0,3),(0,4),(0,5)], [1,2,3,4,5]))
320
 
 
321
 
    def test(fg, x, bounds, xopt):
322
 
        print "** Test", fg.__name__
323
 
        rc, nf, x = fmin_tnc(fg, x, bounds=bounds,  messages = MSG_NONE, maxnfeval = 200)
324
 
        print "After", nf, "function evaluations, TNC returned:", RCSTRINGS[rc]
325
 
        print "x =", x
326
 
        print "exact value =", xopt
327
 
        enorm = 0.0
328
 
        norm = 1.0
329
 
        for y,yo in zip(x, xopt):
330
 
            enorm += (y-yo)*(y-yo)
331
 
            norm += yo*yo
332
 
        e = pow(enorm/norm, 0.5)
333
 
        print "Error =", e
334
 
        if e > 1e-8:
335
 
            raise "Test "+fg.__name__+" failed"
336
 
 
337
 
    for fg, x, bounds, xopt in tests:
338
 
        test(fg, x, bounds, xopt)
339
 
 
340
 
    print
341
 
    print "** All TNC tests passed."