Thursday, March 14, 2019

SciPy - 6 (optimization with SciPy)

Optimization (finding minima or maxima of a function) is a large field in mathematics. Often we need to find the maximum or minimum of a particular function f(x) where f is a scalar function but x could be a vector. Typical applications are the minimization of entities such as cost, risk and error, or the maximization of productivity, efficiency and profit. Optimization routines typically provide a method to minimize a given function: if we need to maximize f(x) we create a new function g(x) that reverses the sign of f, i.e. g(x) = - f(x) and we minimize g(x).

To use the optimization module in scipy first include the optimize module:

from scipy import optimize

1. Finding minima of a function

Let's make a program to find the minima of a simple function of a single variable. See the code below:

from scipy import optimize
from numpy import *
import numpy as N
from matplotlib import pyplot as plt

def f(x):
   
    return 4*x**3 + (x-2)**2 + x**4

fig, ax = plt.subplots()
x = linspace(-5, 3, 100)
ax.plot(x, f(x))

plt.show()

x_min = optimize.fmin_bfgs(f, -2)
print("x_min is:")
print(x_min)

The program first plots a graph of the function and then calculates the minima as shown below:









Optimization terminated successfully.
         Current function value: -3.506641
         Iterations: 5
         Function evaluations: 24
         Gradient evaluations: 8
x_min is:
[-2.67298151]
------------------
(program exited with code: 0)

Press any key to continue . . .

In our program we use the fmin_bfgs function to find the minima of a function: x_min = optimize.fmin_bfgs(f, -2).

We can also use the brent or fminbound functions. They have a bit different syntax and use different  algorithms as shown in the following program:

from scipy import optimize
from numpy import *
import numpy as N
from matplotlib import pyplot as plt

def f(x):
   
    return 4*x**3 + (x-2)**2 + x**4

print(optimize.brent(f))
print('\n')
print(optimize.fminbound(f, -4, 2))

The output of the program is shown below:

0.46961743402759754


-2.6729822917513886
------------------
(program exited with code: 0)

Press any key to continue . . .

Next , we provide an example showing (i) the definition of the test function and (ii) the call of the
scipy.optimize.fmin function which takes as argument a function f to minimize and an initial value
x0 from which to start the search for the minimum, and which returns the value of x for which f(x) is
(locally) minimized. Typically, the search for the minimum is a local search, i.e. the algorithm follows the local gradient. We repeat the search for the minimum for two values (x0 = 1:0 and x0 = 2:0,respectively) to demonstrate that depending on the starting value we may find different minima of
the function f.

The majority of the commands (after the two calls to fmin) in the program shown below creates the plot of the function, the start points for the searches and the minima obtained:

from scipy import optimize
from numpy import *
import numpy as N
from matplotlib import pyplot as plt
from scipy import arange , cos , exp
import pylab

def f(x):
    return cos(x) - 3 * exp ( -(x - 0.2) ** 2)

# find minima of f(x),
# starting from 1.0 and 2.0 respectively
minimum1 = optimize.fmin_bfgs (f, 1.0)
print (" Start search at x=1. , minimum is")
print(minimum1)
minimum2 = optimize.fmin_bfgs (f, 2.0)
print (" Start search at x=2. , minimum is")
print(minimum2)
# plot function
x = arange (-10, 10, 0.1)
y = f(x)
pylab . plot (x, y, label ='$\cos(x)-3e^{ -(x -0.2)^2} $')
pylab . xlabel ('x')
pylab . grid ()
pylab . axis ([-5, 5, -2.2, 0.5])
# add minimum1 to plot
pylab . plot ( minimum1 , f( minimum1 ), 'vr ',label ='minimum 1')
# add start1 to plot
pylab . plot (1.0 , f(1.0) , 'or ', label ='start 1')
#add minimum2 to plot
pylab . plot ( minimum2 ,f( minimum2 ),'vg ' ,label ='minimum 2')
#add start2 to plot
pylab . plot (2.0 ,f(2.0) , 'og ',label ='start 2')

pylab . legend (loc='lower left ')

pylab . show ()

The output of the program is shown below:


Calling the fmin function, will produce some diagnostic output which can be seen in the following output window:

Optimization terminated successfully.
         Current function value: -2.023866
         Iterations: 5
         Function evaluations: 18
         Gradient evaluations: 6
 Start search at x=1. , minimum is
[0.23961728]


Optimization terminated successfully.
         Current function value: -1.000529
         Iterations: 3
         Function evaluations: 21
         Gradient evaluations: 7
 Start search at x=2. , minimum is
[3.13845708]
------------------
(program exited with code: 0)

Press any key to continue . . .

The return value from the fmin function is a numpy array which (for the example above) contains only one number as we have only one parameter (here x) to vary.

In general, fmin can be used to find the minimum in a higher-dimensional parameter space if there
are several parameters. In that case, the numpy array would contain those parameters that minimise
the objective function. The objective function f(x) has to return a scalar even if there are more
parameters, i.e. even if x is a vector as in f(x).

2. Finding a solution to a function

To find the root for a function of the form f(x) = 0 we can use the fsolve function. It requires an initial
guess. Let's make our program which defines the function and then plot the graph:

from scipy import optimize
from numpy import *
import numpy as N
from matplotlib import pyplot as plt
from scipy import arange , cos , exp
import pylab

omega_c = 3.0
def f(omega):
   
    # a transcendental equation: resonance frequencies of a low-Q SQUID terminated microwave re
    return tan(2*pi*omega) - omega_c/omega

fig, ax = plt.subplots(figsize=(10,4))
x = linspace(0, 3, 1000)
y = f(x)
mask = where(abs(y) > 50)
x[mask] = y[mask] = NaN # get rid of vertical line when the function flip sign
ax.plot(x, y)
ax.plot([0, 3], [0, 0], 'k')
ax.set_ylim(-5,5);   
plt.show()


The output of the program plots the following graph:



Now we find the root for a function using optimize.fsolve() as shown below:

print(optimize.fsolve(f, 0.1))
print('\n')
print(optimize.fsolve(f, 0.6))
print('\n')
print(optimize.fsolve(f, 0.6))

The output of the program is shown below:

[0.23743014]
[0.71286972]
[0.71286972]
------------------
(program exited with code: 0)

Press any key to continue . . .

Here I am ending this post regarding optimization with SciPy. Next post will discuss about Interpolation. Till we meet next keep learning and practicing Python as Python is easy to learn!  
Share:

Wednesday, March 13, 2019

SciPy - 5 (linear algebra module)

The linear algebra module contains a lot of matrix related functions, including linear equation solving, eigenvalue solvers, matrix functions (for example matrix-exponentiation), a number of different decomposition (SVD, LU, cholesky), etc. In this post we will look at how to use some of these functions:

1. Linear equation systems

Linear equation systems on the matrix form Ax = b where A is a matrix and x; b are vectors can be solved as shown in the program below:

from scipy.linalg import *
from numpy import array

A = array([[1,2,3], [4,5,6], [7,8,9]])
b = array([1,2,3])

x = solve(A, b)
print('\n')
print(x)

print('\n')
print(N.dot(A, x) - b)


The output of this program is shown below:

[-0.33333333  0.66666667  0.        ]


[ 0.00000000e+00 -2.22044605e-16  0.00000000e+00]
------------------
(program exited with code: 0)

Press any key to continue . . .


Linear equation systems on the matrix form AX = B where A;B;X are matrices, can be solved as shown in the program below:

from scipy.linalg import *
import numpy as N
from numpy import array

A = N.random.rand(3,3)
B = N.random.rand(3,3)

X = solve(A, B)
print('\n')
print(X)


The output of this program is shown below:

[[ 0.07324201  2.28354346  0.78679028]
 [ 0.310878   -0.99860178 -0.56368695]
 [ 0.24402283 -0.72520934  0.32563823]]

------------------
(program exited with code: 0)

Press any key to continue . . . 


2. Eigenvalues and eigenvectors

To calculate eigenvalues of a matrix, use the eigvals and for calculating both eigenvalues and eigenvectors, use the function eig as shown in the program below:

from scipy.linalg import *
import numpy as N
from numpy import array

A = N.random.rand(3,3)
evals = eigvals(A)
print('\n')
print(evals)

evals, evecs = eig(A)

print('\n')
print(evals)
print('\n')
print(evecs)

The output of this program is shown below:

[ 1.45980689+0.j -0.12519707+0.j  0.51421045+0.j]

[ 1.45980689+0.j -0.12519707+0.j  0.51421045+0.j]

[[ 0.52090604  0.49412854 -0.27850149]
 [ 0.45795772 -0.77200849 -0.19138167]
 [ 0.72036909  0.3997998   0.94117479]]
------------------
(program exited with code: 0)

Press any key to continue . . .

The eigenvectors corresponding to the nth eigenvalue (stored in evals[n]) is the nth column in evecs,
i.e., evecs[:,n]. We can verify this by multiplying eigenvectors with the matrix and compare to the product of the eigenvector and the eigenvalue:

n = 1
print('\n')
print(norm(N.dot(A, evecs[:,n]) - evals[n] * evecs[:,n]))

Add this code to the above program and the output will be as shown below:

5.453105385130469e-16
------------------
(program exited with code: 0)

Press any key to continue . . .

3. Matrix operations

The following program shows some of the matrix operations performed using scipy:

from scipy.linalg import *
import numpy as N
import math
from numpy import array

A = N.random.rand(3,3)
# the matrix inverse
inv(A)
print('\n')
print(A)

# determinant
det(A)

print('\n')
print(A)

print('\n')
# norms of various orders
print(norm(A, ord=2), norm(A, ord=math.inf))

The output of this program is shown below:


[[0.32326371 0.7398846  0.15224097]
 [0.27898164 0.65034488 0.77975491]
 [0.49160609 0.71130144 0.5823993 ]]


[[0.32326371 0.7398846  0.15224097]
 [0.27898164 0.65034488 0.77975491]
 [0.49160609 0.71130144 0.5823993 ]]


1.6385878124754003 1.7853068270024153
------------------
(program exited with code: 0)

Press any key to continue . . .

4. Sparse matrices

Scipy has a good support for sparse matrices, with basic linear algebra operations (such as equation solving, eigenvalue calculations, etc). There are many possible strategies for storing sparse matrices in an efficient  way. Some of the most common are the so-called coordinate form (COO), list of list (LIL) form, and compressed-sparse column CSC (and row, CSR). Each format has some advantages and disadvantages. Most computational algorithms (equation solving, matrix-matrix multiplication, etc) can be efficiently implemented using CSR or CSC formats, but they are not so intuitive and not so easy to initialize. So often a sparse matrix is initially created in COO or LIL format (where we can e efficiently add elements to the sparse matrix data), and then converted to CSC or CSR before used in real calculations.

When we create a sparse matrix we have to choose which format it should be stored in. See the following example:

from scipy.linalg import *
from scipy.sparse import *
import numpy as N
import math
from numpy import array


# dense matrix
M = array([[1,0,0,0], [0,3,0,0], [0,1,1,0], [1,0,0,1]])

print('\n')
print(M)

# convert from dense to sparse
A = csr_matrix(M)

print('\n')
print(A)

print('\n')
# convert from sparse to dense
print(A.todense())

The output of this program is shown below: 


[[1 0 0 0]
 [0 3 0 0]
 [0 1 1 0]
 [1 0 0 1]]


  (0, 0)        1
  (1, 1)        3
  (2, 1)        1
  (2, 2)        1
  (3, 0)        1
  (3, 3)        1


[[1 0 0 0]
 [0 3 0 0]
 [0 1 1 0]
 [1 0 0 1]]


------------------
(program exited with code: 0)

Press any key to continue . . .

There is a more e efficient way to create sparse matrices: first create an empty matrix and populate it with using matrix indexing (avoids creating a potentially large dense matrix) . See the following program:

from scipy.linalg import *
from scipy.sparse import *
import numpy as N
import math
from numpy import array


A = lil_matrix((4,4)) # empty 4x4 sparse matrix
A[0,0] = 1
A[1,1] = 3
A[2,2] = A[2,1] = 1
A[3,3] = A[3,0] = 1

print('\n')
print(A)
print('\n')

# convert from sparse to dense
print(A.todense())
print('\n')
print(A)
print('\n')

print(csr_matrix(A))
print('\n')
print(csc_matrix(A))
print('\n')

The output of this program is shown below:  


  (0, 0)        1.0
  (1, 1)        3.0
  (2, 1)        1.0
  (2, 2)        1.0
  (3, 0)        1.0
  (3, 3)        1.0


[[1. 0. 0. 0.]
 [0. 3. 0. 0.]
 [0. 1. 1. 0.]
 [1. 0. 0. 1.]]


  (0, 0)        1.0
  (1, 1)        3.0
  (2, 1)        1.0
  (2, 2)        1.0
  (3, 0)        1.0
  (3, 3)        1.0


  (0, 0)        1.0
  (1, 1)        3.0
  (2, 1)        1.0
  (2, 2)        1.0
  (3, 0)        1.0
  (3, 3)        1.0


  (0, 0)        1.0
  (3, 0)        1.0
  (1, 1)        3.0
  (2, 1)        1.0
  (2, 2)        1.0
  (3, 3)        1.0
------------------
(program exited with code: 0)

Press any key to continue . . .

It is possible to compute with sparse matrices like we compute with dense matrices. See the following program:

from scipy.linalg import *
from scipy.sparse import *
import numpy as N
import math
from numpy import array


A = lil_matrix((4,4)) # empty 4x4 sparse matrix


print('\n')
print(A.todense())
print('\n')


print((A * A).todense())
print('\n')
print(A.todense())
print('\n')

print(A.dot(A).todense())
print('\n')

v = array([1,2,3,4])[:,N.newaxis]

print(v)
print('\n')
# sparse matrix - dense vector multiplication
print(A*v)
print('\n')

# same result with dense matrix - dense vector multiplcation

print(A.todense() * v)

The output of this program is shown below:


[[0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]]


[[0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]]


[[0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]]


[[0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]]


[[1]
 [2]
 [3]
 [4]]


[[0.]
 [0.]
 [0.]
 [0.]]


[[0.]
 [0.]
 [0.]
 [0.]]


------------------
(program exited with code: 0)

Press any key to continue . . .

Here I am ending this post regarding SciPy linear algebra module. Next post will discuss about optimization with SciPy. Till we meet next keep learning and practicing Python as Python is easy to learn!



















Share: