Optimization: principles and algorithms

Bierlaire, M. (2015). Optimization: Principles and Algorithms. EPFL Press.
The numbering of the algorithms, tables and page refer to the book.

Chapter 15: Direct search method

Algorithm 15.1: Nelder-Mead

In [1]:
import numpy as np
from scipy import linalg
# Define a function simple to call for the inner product
def scalarInner(a,b):
    return(np.asscalar(a.T.dot(b)))
In [2]:
import optimizationExceptions

def nelderMead(obj,x0,eps=1.0e-5,maxiter=100):
    n,m = x0.shape
    x = x0
    it = 0
    if m != n+1: 
        raise OptimizationInputError("Incorrect size")
    iters=list()
    while True:  
        it = it + 1
        f = [obj(x[:,k]) for k in range(m)]
        ## Worst value
        worst = max(f)
        worstindex = np.argmax(f)
        xworst = x[:,[worstindex]]
        ## Best value
        best = min(f)
        bestindex = np.argmin(f) 
        tmp = f
        tmp[worstindex] = -np.inf
        secondworst = max(tmp)
        secondworstindex = np.argmax(tmp)
        xc = (np.sum(x,axis=1,keepdims=True) - xworst) / n
        d = xc - x[:,[worstindex]]
        xr = 2 * xc - xworst
        fxr = obj(xr) 
        if fxr < best:
          xe = 2 * xr - xc
          fxe = obj(xe)
          if fxe < fxr:
            xnew = xe
          else:
            xnew = xr 
        elif secondworst > fxr:
            xnew = xr
        elif fxr >= worst:
            xnew = 0.5 * (xworst + xc)
        else:
            xnew = 0.5 * (xr + xc)
        fxnew = obj(xnew)
        iters.append([x.copy(),xworst.copy(),xnew.copy(),xr])
        x[:,[worstindex]] = xnew
        if linalg.norm(d) < eps or it >= maxiter:
            break

    return x[:,bestindex],iters

Example 15.2, page 350

In [3]:
def f(x):
    f = 0.5 * x.item(0) * x.item(0) + 4.5 * x.item(1) * x.item(1)
    return f
In [4]:
x0 = np.array([[1, 2 , 1.1],[ 1, 1.1, 2]])
x0
(sol,iters) = nelderMead(f,x0)
sol
Out[4]:
array([-5.71073706e-06,  6.14849584e-08])

Table 15.1, page 352

In [5]:
for k in range(len(iters)):
    print("{}\t{:+E}\t{:+E}\t{:+E}\t{:+E}\t{:+E}".format(k+1,iters[k][0][0,0],iters[k][0][0,1],iters[k][0][0,2],iters[k][3].item(0),iters[k][2].item(0)))
    print("\t{:+E}\t{:+E}\t{:+E}\t{:+E}\t{:+E}".format(iters[k][0][1,0],iters[k][0][1,1],iters[k][0][1,2],iters[k][3].item(1),iters[k][2].item(1)))
    print("_________________________________________________________________________________________")
    print("\t{:+E}\t{:+E}\t{:+E}\t{:+E}\t{:+E}".format(f(iters[k][0][:,0]),f(iters[k][0][:,1]),f(iters[k][0][:,2]),f(iters[k][3]),f(iters[k][2])))
    print("_________________________________________________________________________________________")
   
    
1	+1.000000E+00	+2.000000E+00	+1.100000E+00	+1.900000E+00	+1.900000E+00
	+1.000000E+00	+1.100000E+00	+2.000000E+00	+1.000000E-01	+1.000000E-01
_________________________________________________________________________________________
	+5.000000E+00	+7.445000E+00	+1.860500E+01	+1.850000E+00	+1.850000E+00
_________________________________________________________________________________________
2	+1.000000E+00	+2.000000E+00	+1.900000E+00	+9.000000E-01	+9.000000E-01
	+1.000000E+00	+1.100000E+00	+1.000000E-01	-4.440892E-16	-4.440892E-16
_________________________________________________________________________________________
	+5.000000E+00	+7.445000E+00	+1.850000E+00	+4.050000E-01	+4.050000E-01
_________________________________________________________________________________________
3	+1.000000E+00	+9.000000E-01	+1.900000E+00	+1.800000E+00	+1.200000E+00
	+1.000000E+00	-4.440892E-16	+1.000000E-01	-9.000000E-01	+5.250000E-01
_________________________________________________________________________________________
	+5.000000E+00	+4.050000E-01	+1.850000E+00	+5.265000E+00	+1.960312E+00
_________________________________________________________________________________________
4	+1.200000E+00	+9.000000E-01	+1.900000E+00	+1.600000E+00	+1.300000E+00
	+5.250000E-01	-4.440892E-16	+1.000000E-01	-4.250000E-01	+2.875000E-01
_________________________________________________________________________________________
	+1.960312E+00	+4.050000E-01	+1.850000E+00	+2.092813E+00	+1.216953E+00
_________________________________________________________________________________________
5	+1.300000E+00	+9.000000E-01	+1.900000E+00	+3.000000E-01	+3.000000E-01
	+2.875000E-01	-4.440892E-16	+1.000000E-01	+1.875000E-01	+1.875000E-01
_________________________________________________________________________________________
	+1.216953E+00	+4.050000E-01	+1.850000E+00	+2.032031E-01	+2.032031E-01
_________________________________________________________________________________________
6	+1.300000E+00	+9.000000E-01	+3.000000E-01	-1.000000E-01	-1.000000E-01
	+2.875000E-01	-4.440892E-16	+1.875000E-01	-1.000000E-01	-1.000000E-01
_________________________________________________________________________________________
	+1.216953E+00	+4.050000E-01	+2.032031E-01	+5.000000E-02	+5.000000E-02
_________________________________________________________________________________________
7	-1.000000E-01	+9.000000E-01	+3.000000E-01	-7.000000E-01	-3.000000E-01
	-1.000000E-01	-4.440892E-16	+1.875000E-01	+8.750000E-02	+6.562500E-02
_________________________________________________________________________________________
	+5.000000E-02	+4.050000E-01	+2.032031E-01	+2.794531E-01	+6.437988E-02
_________________________________________________________________________________________
8	-1.000000E-01	-3.000000E-01	+3.000000E-01	-7.000000E-01	+5.000000E-02
	-1.000000E-01	+6.562500E-02	+1.875000E-01	-2.218750E-01	+8.515625E-02
_________________________________________________________________________________________
	+5.000000E-02	+6.437988E-02	+2.032031E-01	+4.665283E-01	+3.388214E-02
_________________________________________________________________________________________
9	-1.000000E-01	-3.000000E-01	+5.000000E-02	+2.500000E-01	+1.125000E-01
	-1.000000E-01	+6.562500E-02	+8.515625E-02	-8.046875E-02	-4.394531E-02
_________________________________________________________________________________________
	+5.000000E-02	+6.437988E-02	+3.388214E-02	+6.038849E-02	+1.501848E-02
_________________________________________________________________________________________
10	-1.000000E-01	+1.125000E-01	+5.000000E-02	+2.625000E-01	-9.375000E-03
	-1.000000E-01	-4.394531E-02	+8.515625E-02	+1.412109E-01	-3.969727E-02
_________________________________________________________________________________________
	+5.000000E-02	+1.501848E-02	+3.388214E-02	+1.241855E-01	+7.135373E-03
_________________________________________________________________________________________
11	-9.375000E-03	+1.125000E-01	+5.000000E-02	+5.312500E-02	+5.078125E-02
	-3.969727E-02	-4.394531E-02	+8.515625E-02	-1.687988E-01	+2.166748E-02
_________________________________________________________________________________________
	+7.135373E-03	+1.501848E-02	+3.388214E-02	+1.296298E-01	+3.402026E-03
_________________________________________________________________________________________
12	-9.375000E-03	+1.125000E-01	+5.078125E-02	-7.109375E-02	-7.109375E-02
	-3.969727E-02	-4.394531E-02	+2.166748E-02	+2.591553E-02	+2.591553E-02
_________________________________________________________________________________________
	+7.135373E-03	+1.501848E-02	+3.402026E-03	+5.549426E-03	+5.549426E-03
_________________________________________________________________________________________
13	-9.375000E-03	-7.109375E-02	+5.078125E-02	-1.093750E-02	-9.765625E-03
	-3.969727E-02	+2.591553E-02	+2.166748E-02	+8.728027E-02	-7.952881E-03
_________________________________________________________________________________________
	+7.135373E-03	+5.549426E-03	+3.402026E-03	+3.434012E-02	+3.323011E-04
_________________________________________________________________________________________
14	-9.765625E-03	-7.109375E-02	+5.078125E-02	+1.121094E-01	-2.529297E-02
	-7.952881E-03	+2.591553E-02	+2.166748E-02	-1.220093E-02	+1.638641E-02
_________________________________________________________________________________________
	+3.323011E-04	+5.549426E-03	+3.402026E-03	+6.954138E-03	+1.528183E-03
_________________________________________________________________________________________
15	-9.765625E-03	-2.529297E-02	+5.078125E-02	-8.583984E-02	+1.662598E-02
	-7.952881E-03	+1.638641E-02	+2.166748E-02	-1.323395E-02	+1.294212E-02
_________________________________________________________________________________________
	+3.323011E-04	+1.528183E-03	+3.402026E-03	+4.472358E-03	+8.919551E-04
_________________________________________________________________________________________
16	-9.765625E-03	-2.529297E-02	+1.662598E-02	+3.215332E-02	+1.779175E-02
	-7.952881E-03	+1.638641E-02	+1.294212E-02	-1.139717E-02	-4.451275E-03
_________________________________________________________________________________________
	+3.323011E-04	+1.528183E-03	+8.919551E-04	+1.101448E-03	+2.474355E-04
_________________________________________________________________________________________
17	-9.765625E-03	+1.779175E-02	+1.662598E-02	-8.599854E-03	+1.031952E-02
	-7.952881E-03	-4.451275E-03	+1.294212E-02	-2.534628E-02	+3.370023E-03
_________________________________________________________________________________________
	+3.323011E-04	+2.474355E-04	+8.919551E-04	+2.927931E-03	+1.043530E-04
_________________________________________________________________________________________
18	-9.765625E-03	+1.779175E-02	+1.031952E-02	+3.787689E-02	+2.145004E-03
	-7.952881E-03	-4.451275E-03	+3.370023E-03	+6.871629E-03	-4.246753E-03
_________________________________________________________________________________________
	+3.323011E-04	+2.474355E-04	+1.043530E-04	+9.298162E-04	+8.345764E-05
_________________________________________________________________________________________
19	+2.145004E-03	+1.779175E-02	+1.031952E-02	-5.327225E-03	-5.327225E-03
	-4.246753E-03	-4.451275E-03	+3.370023E-03	+3.574544E-03	+3.574544E-03
_________________________________________________________________________________________
	+8.345764E-05	+2.474355E-04	+1.043530E-04	+7.168781E-05	+7.168781E-05
_________________________________________________________________________________________
20	+2.145004E-03	-5.327225E-03	+1.031952E-02	-1.350174E-02	+4.364204E-03
	-4.246753E-03	+3.574544E-03	+3.370023E-03	-4.042232E-03	+1.516959E-03
_________________________________________________________________________________________
	+8.345764E-05	+7.168781E-05	+1.043530E-04	+1.646769E-04	+1.987838E-05
_________________________________________________________________________________________
21	+2.145004E-03	-5.327225E-03	+4.364204E-03	-3.108025E-03	+8.317471E-04
	-4.246753E-03	+3.574544E-03	+1.516959E-03	+9.338257E-03	-8.505009E-04
_________________________________________________________________________________________
	+8.345764E-05	+7.168781E-05	+1.987838E-05	+3.972436E-04	+3.600985E-06
_________________________________________________________________________________________
22	+8.317471E-04	-5.327225E-03	+4.364204E-03	+1.052318E-02	-1.364625E-03
	-8.505009E-04	+3.574544E-03	+1.516959E-03	-2.908086E-03	+1.953887E-03
_________________________________________________________________________________________
	+3.600985E-06	+7.168781E-05	+1.987838E-05	+9.342496E-05	+1.811063E-05
_________________________________________________________________________________________
23	+8.317471E-04	-1.364625E-03	+4.364204E-03	-4.897082E-03	-4.897082E-03
	-8.505009E-04	+1.953887E-03	+1.516959E-03	-4.135733E-04	-4.135733E-04
_________________________________________________________________________________________
	+3.600985E-06	+1.811063E-05	+1.987838E-05	+1.276040E-05	+1.276040E-05
_________________________________________________________________________________________
24	+8.317471E-04	-1.364625E-03	-4.897082E-03	-2.700710E-03	-1.698646E-03
	-8.505009E-04	+1.953887E-03	-4.135733E-04	-3.217961E-03	+6.609248E-04
_________________________________________________________________________________________
	+3.600985E-06	+1.811063E-05	+1.276040E-05	+5.024564E-05	+3.408396E-06
_________________________________________________________________________________________
25	+8.317471E-04	-1.698646E-03	-4.897082E-03	+4.030183E-03	+1.798367E-03
	-8.505009E-04	+6.609248E-04	-4.135733E-04	+2.239972E-04	+6.460455E-05
_________________________________________________________________________________________
	+3.600985E-06	+3.408396E-06	+1.276040E-05	+8.346974E-06	+1.635843E-06
_________________________________________________________________________________________
26	+8.317471E-04	-1.698646E-03	+1.798367E-03	-7.320262E-04	+4.408037E-04
	-8.505009E-04	+6.609248E-04	+6.460455E-05	+1.576030E-03	-2.438681E-04
_________________________________________________________________________________________
	+3.600985E-06	+3.408396E-06	+1.635843E-06	+1.144535E-05	+3.647765E-07
_________________________________________________________________________________________
27	+4.408037E-04	-1.698646E-03	+1.798367E-03	+3.937816E-03	-2.895304E-04
	-2.438681E-04	+6.609248E-04	+6.460455E-05	-8.401883E-04	+2.856465E-04
_________________________________________________________________________________________
	+3.647765E-07	+3.408396E-06	+1.635843E-06	+1.092982E-05	+4.090865E-07
_________________________________________________________________________________________
28	+4.408037E-04	-2.895304E-04	+1.798367E-03	-1.647093E-03	-7.857283E-04
	-2.438681E-04	+2.856465E-04	+6.460455E-05	-2.282620E-05	-9.685116E-07
_________________________________________________________________________________________
	+3.647765E-07	+4.090865E-07	+1.635843E-06	+1.358803E-06	+3.086887E-07
_________________________________________________________________________________________
29	+4.408037E-04	-2.895304E-04	-7.857283E-04	-5.539426E-05	-2.309963E-04
	-2.438681E-04	+2.856465E-04	-9.685116E-07	-5.304831E-04	+8.161408E-05
_________________________________________________________________________________________
	+3.647765E-07	+4.090865E-07	+3.086887E-07	+1.267890E-06	+5.665351E-08
_________________________________________________________________________________________
30	+4.408037E-04	-2.309963E-04	-7.857283E-04	-1.457528E-03	-3.377930E-05
	-2.438681E-04	+8.161408E-05	-9.685116E-07	+3.245137E-04	-1.017727E-04
_________________________________________________________________________________________
	+3.647765E-07	+5.665351E-08	+3.086887E-07	+1.536086E-06	+4.718007E-08
_________________________________________________________________________________________
31	-3.377930E-05	-2.309963E-04	-7.857283E-04	+5.209527E-04	+1.942824E-04
	-1.017727E-04	+8.161408E-05	-9.685116E-07	-1.919008E-05	-1.463469E-05
_________________________________________________________________________________________
	+4.718007E-08	+5.665351E-08	+3.086887E-07	+1.373530E-07	+1.983662E-08
_________________________________________________________________________________________
32	-3.377930E-05	-2.309963E-04	+1.942824E-04	+3.914995E-04	-7.537238E-05
	-1.017727E-04	+8.161408E-05	-1.463469E-05	-1.980214E-04	+1.170520E-05
_________________________________________________________________________________________
	+4.718007E-08	+5.665351E-08	+1.983662E-08	+2.530921E-07	+3.457051E-09
_________________________________________________________________________________________
33	-3.377930E-05	-7.537238E-05	+1.942824E-04	+1.526894E-04	+1.283786E-05
	-1.017727E-04	+1.170520E-05	-1.463469E-05	+9.884319E-05	-5.161871E-05
_________________________________________________________________________________________
	+4.718007E-08	+3.457051E-09	+1.983662E-08	+5.562191E-08	+1.207261E-08
_________________________________________________________________________________________
34	+1.283786E-05	-7.537238E-05	+1.942824E-04	-2.568170E-04	+8.150759E-05
	-5.161871E-05	+1.170520E-05	-1.463469E-05	-2.527882E-05	-1.729572E-05
_________________________________________________________________________________________
	+1.207261E-08	+3.457051E-09	+1.983662E-08	+3.585306E-08	+4.667883E-09
_________________________________________________________________________________________
35	+1.283786E-05	-7.537238E-05	+8.150759E-05	-6.702650E-06	-1.817522E-06
	-5.161871E-05	+1.170520E-05	-1.729572E-05	+4.602819E-05	+2.161646E-05
_________________________________________________________________________________________
	+1.207261E-08	+3.457051E-09	+4.667883E-09	+9.556136E-09	+2.104374E-09
_________________________________________________________________________________________
36	-1.817522E-06	-7.537238E-05	+8.150759E-05	-1.586975E-04	+2.145632E-05
	+2.161646E-05	+1.170520E-05	-1.729572E-05	+5.061739E-05	-3.174437E-07
_________________________________________________________________________________________
	+2.104374E-09	+3.457051E-09	+4.667883E-09	+2.412199E-08	+2.306403E-10
_________________________________________________________________________________________
37	-1.817522E-06	-7.537238E-05	+2.145632E-05	+9.501118E-05	-3.277649E-05
	+2.161646E-05	+1.170520E-05	-3.174437E-07	+9.593820E-06	+1.117736E-05
_________________________________________________________________________________________
	+2.104374E-09	+3.457051E-09	+2.306403E-10	+4.927748E-09	+1.099349E-09
_________________________________________________________________________________________
38	-1.817522E-06	-3.277649E-05	+2.145632E-05	-9.502647E-06	-9.502647E-06
	+2.161646E-05	+1.117736E-05	-3.174437E-07	-1.075655E-05	-1.075655E-05
_________________________________________________________________________________________
	+2.104374E-09	+1.099349E-09	+2.306403E-10	+5.658155E-10	+5.658155E-10
_________________________________________________________________________________________
39	-9.502647E-06	-3.277649E-05	+2.145632E-05	+4.473016E-05	-1.339983E-05
	-1.075655E-05	+1.117736E-05	-3.174437E-07	-2.225135E-05	+2.820179E-06
_________________________________________________________________________________________
	+5.658155E-10	+1.099349E-09	+2.306403E-10	+3.228446E-09	+1.255680E-10
_________________________________________________________________________________________
40	-9.502647E-06	-1.339983E-05	+2.145632E-05	+1.755914E-05	-2.737200E-06
	-1.075655E-05	+2.820179E-06	-3.174437E-07	+1.325929E-05	-4.752592E-06
_________________________________________________________________________________________
	+5.658155E-10	+1.255680E-10	+2.306403E-10	+9.453009E-10	+1.053882E-10
_________________________________________________________________________________________
41	-2.737200E-06	-1.339983E-05	+2.145632E-05	-3.759335E-05	+6.693904E-06
	-4.752592E-06	+2.820179E-06	-3.174437E-07	-1.614970E-06	-6.418253E-07
_________________________________________________________________________________________
	+1.053882E-10	+1.255680E-10	+2.306403E-10	+7.183665E-10	+2.425791E-11
_________________________________________________________________________________________
42	-2.737200E-06	-1.339983E-05	+6.693904E-06	+1.735653E-05	-5.710737E-06
	-4.752592E-06	+2.820179E-06	-6.418253E-07	-8.214597E-06	+6.148496E-08
_________________________________________________________________________________________
	+1.053882E-10	+1.255680E-10	+2.425791E-11	+4.542828E-10	+1.632327E-11
_________________________________________________________________________________________
43	-2.737200E-06	-5.710737E-06	+6.693904E-06	+3.720367E-06	+2.105975E-06
	-4.752592E-06	+6.148496E-08	-6.418253E-07	+4.172252E-06	+1.941041E-06
_________________________________________________________________________________________
	+1.053882E-10	+1.632327E-11	+2.425791E-11	+8.525516E-11	+1.917195E-11
_________________________________________________________________________________________

Figure 15.2 (a), page 350

In [6]:
%matplotlib inline
import matplotlib.pyplot as plt
def theFunctionToPlot(x,y):
    return 0.5 * x * x + 4.5 * y * y
xmin = -0.1
xmax = 2.1
ymin = -0.1
ymax = 2.1
xlist = np.linspace(xmin,xmax,100)
ylist = np.linspace(ymin,ymax,100)
X,Y = np.meshgrid(xlist,ylist)
Z = theFunctionToPlot(X,Y)
plt.contour(X,Y,Z,50)
iter = 0
xiter = [iters[iter][0][:,k].item(0) for k in range(3)]+[iters[iter][0][:,0].item(0)]
yiter = [iters[iter][0][:,k].item(1) for k in range(3)]+[iters[iter][0][:,0].item(1)]
xarrow = [iters[iter][1].item(0),iters[iter][2].item(0)]
yarrow = [iters[iter][1].item(1),iters[iter][2].item(1)]
plt.xlim([xmin,xmax])
plt.ylim([ymin,ymax])
plt.plot(xarrow,yarrow,linewidth=3,color='b')
plt.plot(xiter,yiter, linewidth=5, color='r',marker='o',mfc='blue')
plt.show()

Figure 15.2 (b), page 350

In [7]:
%matplotlib inline
import matplotlib.pyplot as plt
def theFunctionToPlot(x,y):
    return 0.5 * x * x + 4.5 * y * y
xmin = -0.1
xmax = 2.1
ymin = -0.1
ymax = 2.1
xlist = np.linspace(xmin,xmax,100)
ylist = np.linspace(ymin,ymax,100)
X,Y = np.meshgrid(xlist,ylist)
Z = theFunctionToPlot(X,Y)
plt.contour(X,Y,Z,50)
iter = 1
xiter = [iters[iter][0][:,k].item(0) for k in range(3)]+[iters[iter][0][:,0].item(0)]
yiter = [iters[iter][0][:,k].item(1) for k in range(3)]+[iters[iter][0][:,0].item(1)]
xarrow = [iters[iter][1].item(0),iters[iter][2].item(0)]
yarrow = [iters[iter][1].item(1),iters[iter][2].item(1)]
plt.xlim([xmin,xmax])
plt.ylim([ymin,ymax])
plt.plot(xarrow,yarrow,linewidth=3,color='b')
plt.plot(xiter,yiter, linewidth=5, color='r',marker='o',mfc='blue')
plt.show()

Figure 15.2 (c), page 350

In [8]:
%matplotlib inline
import matplotlib.pyplot as plt
def theFunctionToPlot(x,y):
    return 0.5 * x * x + 4.5 * y * y
xmin = -0.1
xmax = 2.1
ymin = -0.1
ymax = 2.1
xlist = np.linspace(xmin,xmax,100)
ylist = np.linspace(ymin,ymax,100)
X,Y = np.meshgrid(xlist,ylist)
Z = theFunctionToPlot(X,Y)
plt.contour(X,Y,Z,50)
iter = 2
xiter = [iters[iter][0][:,k].item(0) for k in range(3)]+[iters[iter][0][:,0].item(0)]
yiter = [iters[iter][0][:,k].item(1) for k in range(3)]+[iters[iter][0][:,0].item(1)]
xarrow = [iters[iter][1].item(0),iters[iter][2].item(0)]
yarrow = [iters[iter][1].item(1),iters[iter][2].item(1)]
plt.xlim([xmin,xmax])
plt.ylim([ymin,ymax])
plt.plot(xarrow,yarrow,linewidth=3,color='b')
plt.plot(xiter,yiter, linewidth=5, color='r',marker='o',mfc='blue')
plt.show()

Figure 15.2 (d), page 350

In [9]:
%matplotlib inline
import matplotlib.pyplot as plt
def theFunctionToPlot(x,y):
    return 0.5 * x * x + 4.5 * y * y
xmin = -0.1
xmax = 2.1
ymin = -0.1
ymax = 2.1
xlist = np.linspace(xmin,xmax,100)
ylist = np.linspace(ymin,ymax,100)
X,Y = np.meshgrid(xlist,ylist)
Z = theFunctionToPlot(X,Y)
plt.contour(X,Y,Z,50)
iter = 3
xiter = [iters[iter][0][:,k].item(0) for k in range(3)]+[iters[iter][0][:,0].item(0)]
yiter = [iters[iter][0][:,k].item(1) for k in range(3)]+[iters[iter][0][:,0].item(1)]
xarrow = [iters[iter][1].item(0),iters[iter][2].item(0)]
yarrow = [iters[iter][1].item(1),iters[iter][2].item(1)]
plt.xlim([xmin,xmax])
plt.ylim([ymin,ymax])
plt.plot(xarrow,yarrow,linewidth=3,color='b')
plt.plot(xiter,yiter, linewidth=5, color='r',marker='o',mfc='blue')
plt.show()

Figure 15.3 (a), page 351

In [10]:
%matplotlib inline
import matplotlib.pyplot as plt
def theFunctionToPlot(x,y):
    return 0.5 * x * x + 4.5 * y * y
xmin = -0.5
xmax = 2.1
ymin = -0.2
ymax = 2.1
xlist = np.linspace(xmin,xmax,100)
ylist = np.linspace(ymin,ymax,100)
X,Y = np.meshgrid(xlist,ylist)
Z = theFunctionToPlot(X,Y)
plt.contour(X,Y,Z,50)
for iter in range(len(iters)):
    xiter = [iters[iter][0][:,k].item(0) for k in range(3)]+[iters[iter][0][:,0].item(0)]
    yiter = [iters[iter][0][:,k].item(1) for k in range(3)]+[iters[iter][0][:,0].item(1)]
    plt.plot(xiter,yiter, linewidth=5, color='r',marker='o',mfc='blue')
plt.xlim([xmin,xmax])
plt.ylim([ymin,ymax])
plt.show()

Figure 15.3 (b), page 351

In [11]:
%matplotlib inline
import matplotlib.pyplot as plt
def theFunctionToPlot(x,y):
    return 0.5 * x * x + 4.5 * y * y
xmin = -0.2
xmax = 0.2
ymin = -0.1
ymax = 0.1
xlist = np.linspace(xmin,xmax,100)
ylist = np.linspace(ymin,ymax,100)
X,Y = np.meshgrid(xlist,ylist)
Z = theFunctionToPlot(X,Y)
plt.contour(X,Y,Z,50)
for iter in range(len(iters)):
    xiter = [iters[iter][0][:,k].item(0) for k in range(3)]+[iters[iter][0][:,0].item(0)]
    yiter = [iters[iter][0][:,k].item(1) for k in range(3)]+[iters[iter][0][:,0].item(1)]
    plt.plot(xiter,yiter, linewidth=5, color='r',marker='o',mfc='blue')
plt.xlim([xmin,xmax])
plt.ylim([ymin,ymax])
plt.show()

Example 15.3, page 352

In [12]:
def mckinnon(x):
    x1 = x.item(0)
    x2 = x.item(1)
    return (x1 <= 0) * (360 * x1 * x1 + x2 + x2 * x2) + (x1 > 0) * (6 * x1 * x1 + x2 + x2 * x2)
In [13]:
x0 = np.array([[1, (1+np.sqrt(33))/8 , 0],[ 1, (1-np.sqrt(33))/8, 0]])
x0
(sol,iters) = nelderMead(mckinnon,x0)
sol
Out[13]:
array([0., 0.])

Figure 15.4, page 353

In [14]:
%matplotlib inline
import matplotlib.pyplot as plt
def theFunctionToPlot(x,y):
    res = (x <= 0) * (360 * x * x + y + y * y) + (x > 0) * (6 * x * x + y + y * y)
    return res
xmin = -0.2
xmax = 1.2
ymin = -0.7
ymax = 1.1
xlist = np.linspace(xmin,xmax,100)
ylist = np.linspace(ymin,ymax,100)
X,Y = np.meshgrid(xlist,ylist)
Z = theFunctionToPlot(X,Y)
plt.contour(X,Y,Z,50)
for iter in range(len(iters)):
    xiter = [iters[iter][0][:,k].item(0) for k in range(3)]+[iters[iter][0][:,0].item(0)]
    yiter = [iters[iter][0][:,k].item(1) for k in range(3)]+[iters[iter][0][:,0].item(1)]
    plt.plot(xiter,yiter, linewidth=5, color='r',marker='o',mfc='blue')
plt.xlim([xmin,xmax])
plt.ylim([ymin,ymax])
plt.show()