When optimizing a function, we often start by first bracketing an interval containing a local minimum. We then successively reduce the interval to converge to the local minimum.
import numpy as np
# function definition - single dimension
def f(x):
#return x**4 - 14*x**3 + 60*x**2 - 70*x
return x**2 + 4 * np.cos(x)
'''Function to find the range in the function which contains the minimum value of the function
Satisfying the condition f(x1)>f(x0)<f(x2)'''
def initial_bracket(x,fac,eps):
i = 1
x0, f_x0 = x, f(x)
x1 = x0 + (fac*i)*eps
f_x1 = f(x1)
if f_x0 < f_x1 : #''' We reverse the bracket direction, if this condition is true in the initial initiation'''
j = i*2
x0 = x1
eps = -eps
x1 = x0 + (fac*j)*eps
i = i*2
x2 = x1 + (fac*i) * eps
f_x2 = f(x2)
if (f_x1 > f_x2): #''' Check for f(x2) > f(x1)'''
while (f_x1 > f_x2): #''' Finding the point in the function which is greater than f(x2) such that f(x1)>f(x2)<f(x3).
# Our required bracket'''
x0, x1 = x1, x2
f_x0, f_x1 = f(x1), f(x2)
i = i*2
x2 = x2 + (fac*i) * eps
f_x2 = f(x2)
#print(i,x0,x1,x2,f_x0,f_x1,f_x2)
return [x0,x2]
else:
return [x0,x2]
# function call for one-dimensional intial bracket method
x = 0
eps = 0.01
fac = 2
initial_bracket(x,fac,eps)
[0.6200000000000001, 2.54]
Q. Consider using a gradient algorithm to minimize the function: $f(x) = \frac{1}{2} x^T \begin{bmatrix} 2& 1\\ 1&2 \end{bmatrix}x$ With the initial guess $x^{(0)} = [0.8,-0.25]^T$
(1) To initialize the line search, apply the bracketing procedure along the line starting at $x^{(0)}$ in the direction of the negative gradient. Use $\epsilon = 0.075$
# function definition - R^2 dimension
def fun(x):
a = np.array([[2,1],[1,2]])
return 0.5 * np.dot(x.T,np.dot(x.T,a).T)
# function to return the grdient of the function
def grad_f(x):
a = np.array([[2,1],[1,2]])
return - np.dot(a,x)
'''Function to find the range in the function which contains the minimum value of the function
Satisfying the condition f(x1)>f(x0)<f(x2)
def initial_bracket_multidimensional(x,d,eps):
i = 1
x0, f_x0 = x, fun(x)
x1 = x0 + (i*eps)*fac
f_x1 = fun(x1)
print("Initial values","fac:",fac,"x0:",x0,"x1:",x1,"f(x0):",f_x0,"f(x1):",f_x1)
if f_x0 < f_x1 :
j = i*2
x0 = x1
eps = -eps
x1 = x0 + (j*eps)*d
i = i*2
x2 = x0 + (i*eps)*d
f_x2 = fun(x2)
print("x0, x1, x2 ","x0:",x0,"f(x0):",f_x0,"x1:",x1,"f(x1):",f_x1,"x2:",x2,"f(x2):",f_x2)
if (f_x1 > f_x2): #Check for f(x2) > f(x1)
while (f_x1 > f_x2): Finding the point in the function which is greater than f(x2) such that f(x1)>f(x2)<f(x3).
# Our required bracket
i = i*2
x2 = x0 + (i*eps)*d
f_x2 = fun(x2)
print("x0, x1, x2 ","x0:",x0,"f(x0):",f_x0,"x1:",x1,"f(x1):",f_x1,"x2:",x2,"f(x2):",f_x2)
return [x1,x2]
else:
return [x0,x2]'''
# function call for one-dimensional intial bracket method
x = np.array([0.8,-0.25]) # Initial values of x
eps = 0.075
d = grad_f(x) # passing the gradient direction
initial_bracket_multidimensional(x,fac,eps)
Initial values fac: [-1.35 -0.3 ] x0: [ 0.8 -0.25] x1: [ 0.69875 -0.2725 ] f(x0): 0.5025000000000001 f(x1): 0.37209843750000005 x0, x1, x2 x0: [ 0.8 -0.25] f(x0): 0.5025000000000001 x1: [ 0.69875 -0.2725 ] f(x1): 0.37209843750000005 x2: [ 0.5975 -0.295 ] f(x2): 0.26776875 x0, x1, x2 x0: [ 0.8 -0.25] f(x0): 0.5025000000000001 x1: [ 0.69875 -0.2725 ] f(x1): 0.37209843750000005 x2: [ 0.395 -0.34 ] f(x2): 0.13732500000000003 x0, x1, x2 x0: [ 0.8 -0.25] f(x0): 0.5025000000000001 x1: [ 0.69875 -0.2725 ] f(x1): 0.37209843750000005 x2: [-0.01 -0.43] f(x2): 0.18930000000000005 x0, x1, x2 x0: [ 0.8 -0.25] f(x0): 0.5025000000000001 x1: [ 0.69875 -0.2725 ] f(x1): 0.37209843750000005 x2: [-0.82 -0.61] f(x2): 1.5447000000000002
[array([ 0.69875, -0.2725 ]), array([-0.82, -0.61])]