Rosenbrock Function¶
In [6]:
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
x1 = np.linspace(-2,2,30)
x2 = np.linspace(-2,2,30)
# Creating 2-D grid of features
[X, Y] = np.meshgrid(x1,x2)
Z = (1 - X)**2 + 5*(Y - X**2)**2
plt.figure(figsize=(6,6))
plt.contour(X,Y,Z,55,cmap='hot')
plt.show()
Exact Line Search¶
In [20]:
# function to find the initial bracket of the objective function
# Have directly specified the simplified version of the function
def f(alpha,x,d):
return (1-(x[0]-alpha*d[0]))**2 + 100*((x[1]-alpha*d[1])-(x[0]-alpha*d[0])**2)**2
# derivative of the objective function
def grad_alpha(f,alpha,x,d):
h = 0.00001
return (f(alpha+h,x,d)-f(alpha,x,d))/h
In [2]:
def bracket_minimum(alpha,x,d,s,k):
a, fa = alpha, f(alpha,x,d)
b, fb = a+s , f(a+s,x,d)
if fb > fa:
a,b = b,a
fa, fb = fb,fb
s = -s
while True:
c, fc = b+s, f(b+s,x,d)
if fc > fb:
if a < c:
return [a,c]
else:
return [c,a]
a,fa,b,fb = b,fb,c,fc
s*=k
In [3]:
def bisection_root_finding(a,b,x,d,eps):
if a > b :
a,b = b,a
fa, fb = grad_alpha(f,a,x,d), grad_alpha(f,b,x,d)
if fa == 0:
b = a
return (a)
if fb == 0:
a = b
return (b)
iter = 0
while abs(b - a) > eps:
iter +=1
c = (a+b)/2
y = grad_alpha(f,c,x,d)
if y == 0:
a,b = c, c
break
if np.sign(y) < 0 :
a = c
else:
b = c
return (a+b)/2
In [4]:
def line_search(alpha,x,d):
a,b = bracket_minimum(alpha,x,d,s=0.01,k=2.0)
alpha = bisection_root_finding(a,b,x,d,eps=1e-5)
return alpha
In [7]:
alpha = 5
x = np.array([1,2])
d = np.array([0.89,-0.447])
line_search(alpha,x,d)
Out[7]:
-0.3862854003906251
Gradient Descent¶
Implementing gradient descent algorithm to get the minima of the Rosenbrock function, and also using exact line search algorithm for optimum step length in every iteration.
In [14]:
# Rosenbrock's Banana Function
def fun(x,a):
pow = a
if pow == 0:
return (1 - x[0])**2 + 100*(x[1] - x[0]**2)**2
else:
h = 0.00001
x1 = np.array([x[0]+h,x[1]])
x2 = np.array([x[0],x[1]+h])
# The gradient Vector
g = np.array([(fun(x1,0)-fun(x,0))/h,(fun(x2,0)-fun(x,0))/h])
return g
In [18]:
def gradient_descent(x_init,alpha,eps):
iter = 0
arr = []
x, f ,g = x_init,fun(x_init,0),fun(x_init,1)
arr.append(x)
d = np.array(g/np.linalg.norm(g))
if (np.linalg.norm(g)==0):
print(" The min value of the function is:",f, "for value of x:",x)
return x
else:
while abs(f) > eps:
iter+=1
alpha = line_search(alpha,x,d)
x = x - alpha*d
arr.append(x)
f, g = fun(x,0) , fun(x,1)
d = np.array(g/np.linalg.norm(g))
print(iter,":","f:",f )
return (x,arr)
In [21]:
x = np.array([1,2])
alpha = 4
p = 0.1
beta = 1e-4
eps = 1e-5
x,arr = gradient_descent(x,alpha,eps)
print("The minimum point of the Rosenbrock function:",x)
1 : f: 8.119043304158598 2 : f: 8.11753265521711 3 : f: 8.115998058843157 4 : f: 8.114488565526697 5 : f: 8.112956450012003 6 : f: 8.11145101889225 7 : f: 8.109922458443107 8 : f: 8.108420009567265 9 : f: 8.106892066910072 10 : f: 8.105390172168134 11 : f: 8.10386349136107 12 : f: 8.102363449800364 13 : f: 8.100837114216839 14 : f: 8.099336933077186 15 : f: 8.09781000225749 16 : f: 8.096309107187386 17 : f: 8.09478100321202 18 : f: 8.093278871825271 19 : f: 8.09174876762115 20 : f: 8.090244046997139 21 : f: 8.088709233384591 22 : f: 8.087200157900714 23 : f: 8.08566097489898 24 : f: 8.084146096982915 25 : f: 8.082597885624448 26 : f: 8.08107574665936 27 : f: 8.07952099223351 28 : f: 8.077989888272512 29 : f: 8.076421734865889 30 : f: 8.07488086378528 31 : f: 8.07330449247498 32 : f: 8.071751440150742 33 : f: 8.07015733361603 34 : f: 8.068586331591627 35 : f: 8.066973870375946 36 : f: 8.065386657232164 37 : f: 8.063757641733494 38 : f: 8.062150706903465 39 : f: 8.060492195412474 40 : f: 8.058858076433506 41 : f: 8.057173411499893 42 : f: 8.055510912853531 43 : f: 8.0537898954191 44 : f: 8.052095878892935 45 : f: 8.050349659123874 46 : f: 8.048628459677609 47 : f: 8.046845635387383 48 : f: 8.045088310513437 49 : f: 8.043277829618981 50 : f: 8.041490398890057 51 : f: 8.039641167660138 52 : f: 8.037814306178824 53 : f: 8.035908099688509 54 : f: 8.034031012489974 55 : f: 8.032065116083468 56 : f: 8.030122097890946 57 : f: 8.028100235223388 58 : f: 8.026100904671477 59 : f: 8.024010364680995 60 : f: 8.021945330258259 61 : f: 8.019757364722498 62 : f: 8.017599128539754 63 : f: 8.01530800518776 64 : f: 8.013035141433797 65 : f: 8.010615112687688 66 : f: 8.00821422857656 67 : f: 8.005637431906367 68 : f: 8.003087566858907 69 : f: 8.000391732017066 70 : f: 7.9977246675105205 71 : f: 7.994868940222149 72 : f: 7.992042827814876 73 : f: 7.989030609546753 74 : f: 7.986038016342447 75 : f: 7.982885149671062 76 : f: 7.979760835545059 77 : f: 7.976355144262098 78 : f: 7.972974717546768 79 : f: 7.969248477280381 80 : f: 7.965547638155797 81 : f: 7.961506844353651 82 : f: 7.957485101645995 83 : f: 7.953014908304496 84 : f: 7.9485605659047325 85 : f: 7.943513199970706 86 : f: 7.938481137885064 87 : f: 7.932874959630136 88 : f: 7.9272770045074346 89 : f: 7.921107702846879 90 : f: 7.9149420891334055 91 : f: 7.908114067770349 92 : f: 7.901291912621688 93 : f: 7.893069564356331 94 : f: 7.884842892758808 95 : f: 7.874866925370101 96 : f: 7.864851309320331 97 : f: 7.853243128573864 98 : f: 7.841572121391476 99 : f: 7.828221122305061 100 : f: 7.814774433924222 101 : f: 7.797231062614354 102 : f: 7.779473963948931 103 : f: 7.755679799839378 104 : f: 7.731424198318244 105 : f: 7.69989179348141 106 : f: 7.6674348388615705 107 : f: 7.6167956781090265 108 : f: 7.563235718447853 109 : f: 7.481750273899846 110 : f: 7.390476218015211 111 : f: 4.535391740603324 112 : f: 0.19393202790637487 113 : f: 0.19383291684870588 114 : f: 0.1937382372839816 115 : f: 0.19363325194799766 116 : f: 0.19353219848452438 117 : f: 0.19342144761362734 118 : f: 0.19331551523215323 119 : f: 0.19319549679588097 120 : f: 0.19307926845243092 121 : f: 0.19294979616968766 122 : f: 0.1928244734153004 123 : f: 0.19267413739415234 124 : f: 0.19252848366730257 125 : f: 0.1923614337207022 126 : f: 0.19219836645443714 127 : f: 0.19198533717498958 128 : f: 0.19177895912784806 129 : f: 0.19148512995446842 130 : f: 0.19119686867216587 131 : f: 0.19078579969794124 132 : f: 0.19038267603053624 133 : f: 0.18971493239404186 134 : f: 0.1890566215481348 135 : f: 0.18742840367924293 136 : f: 0.18582629029903291 137 : f: 0.1824563852815737 138 : f: 0.17918554084707064 139 : f: 0.16820508370178314 140 : f: 0.15864471603571104 141 : f: 0.03431786320562987 142 : f: 0.029028922674081373 143 : f: 0.027312955635161236 144 : f: 0.025568002271696904 145 : f: 0.02422723995052189 146 : f: 0.022874835584942934 147 : f: 0.020940870604284283 148 : f: 0.01896138158585194 149 : f: 0.016104014563753353 150 : f: 0.013020421226664927 151 : f: 0.003871577549615624 152 : f: 0.0022846958887193514 153 : f: 0.0022656407534571224 154 : f: 0.002246326295100813 155 : f: 0.0022314500906596593 156 : f: 0.002216324079228483 157 : f: 0.0021985842713716517 158 : f: 0.002180412794600282 159 : f: 0.002139000943215715 160 : f: 0.002097378026600463 161 : f: 0.002065096085179421 162 : f: 0.002032640569767348 163 : f: 0.0019290117225821545 164 : f: 0.001827736154492573 165 : f: 0.000926124348242947 166 : f: 0.000539363861394565 167 : f: 0.000537728343578827 168 : f: 0.0005359838878439256 169 : f: 0.0005338476378012616 170 : f: 0.0005316245425471141 171 : f: 0.0005281484482579812 172 : f: 0.000524435937711603 173 : f: 0.000518072618623222 174 : f: 0.0005114965069666944 175 : f: 0.0005034451852091847 176 : f: 0.0004951095986187585 177 : f: 0.000491271656445071 178 : f: 0.00048736863554444066 179 : f: 5.926191315320089e-07 The minimum point of the Rosenbrock function: [1.00022091 1.00036812]
In [22]:
# Plot of the successive points of 'x' as we progress in the direction of the steepest descent.
x1 = np.linspace(-2,3,500)
x2 = np.linspace(0,4,500)
arr = pd.DataFrame(arr)
# Creating 2-D grid of features
[X, Y] = np.meshgrid(x1,x2)
Z = (1 - X)**2 + 5*(Y - X**2)**2
a,b = arr[0],arr[1]
plt.figure(figsize=(8,7))
plt.scatter(a,b)
plt.contour(X,Y,Z,90)
plt.plot(a,b,color='#bcbd22')
plt.show()