{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"initial-bracket.ipynb","provenance":[],"collapsed_sections":[],"authorship_tag":"ABX9TyNWD5imoNBHASQJyK+3khf3"},"kernelspec":{"name":"python3","display_name":"Python 3"},"language_info":{"name":"python"}},"cells":[{"cell_type":"markdown","metadata":{"id":"2nkHIR9BNmae"},"source":["# Finding an Initial bracket \n","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."]},{"cell_type":"code","metadata":{"id":"8fhVinjdOsKZ"},"source":["import numpy as np"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"LoibsOYtHTlE"},"source":["# function definition  - single dimension\n","def f(x):\n","  #return x**4 - 14*x**3 + 60*x**2 - 70*x\n","  return x**2 + 4 * np.cos(x)"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"gASFIEO5Wdkb"},"source":[" '''Function to find the range in the function which contains the minimum value of the function\n","    Satisfying the condition   f(x1)>f(x0)<f(x2)'''\n","\n","def initial_bracket(x,fac,eps):\n","\n","  i = 1\n","\n","  x0, f_x0 = x, f(x)\n","\n","  x1 = x0 + (fac*i)*eps \n","\n","  f_x1 = f(x1)\n","\n","  if f_x0 < f_x1 : #''' We reverse the bracket direction, if this condition is true in the initial initiation'''\n","    j = i*2 \n","    x0 = x1\n","    eps = -eps\n","    x1 = x0 + (fac*j)*eps\n","  \n","  i = i*2\n","  x2 = x1 + (fac*i) * eps\n","  f_x2 = f(x2)\n","  \n","  if (f_x1 > f_x2): #''' Check for f(x2) > f(x1)'''\n","    \n","    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).\n","                          #   Our required bracket'''\n","      x0, x1 = x1, x2\n","      f_x0, f_x1 = f(x1), f(x2)\n","      i = i*2\n","      x2 = x2 + (fac*i) * eps\n","      f_x2 = f(x2)\n","      #print(i,x0,x1,x2,f_x0,f_x1,f_x2)\n","    return [x0,x2]\n","\n","  else:\n","   \n","    return [x0,x2]"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"nyoJ1h40bnP9","executionInfo":{"status":"ok","timestamp":1622200719251,"user_tz":-120,"elapsed":425,"user":{"displayName":"Nasreen Ahmed","photoUrl":"","userId":"04649825647281041989"}},"outputId":"4bb0d206-dcef-4fa9-9c4a-c02e4c553cb4"},"source":["# function call for one-dimensional intial bracket method\n","x = 0\n","eps = 0.01\n","fac = 2\n","initial_bracket(x,fac,eps)"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[0.6200000000000001, 2.54]"]},"metadata":{"tags":[]},"execution_count":113}]},{"cell_type":"markdown","metadata":{"id":"4DIaWif-bqck"},"source":["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$\n","\n","(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$"]},{"cell_type":"code","metadata":{"id":"WItRFx0BbA9h"},"source":["# function definition - R^2 dimension\n","def fun(x):\n","\n","  a = np.array([[2,1],[1,2]])\n","  return  0.5 * np.dot(x.T,np.dot(x.T,a).T) \n"," \n","\n","# function to return the grdient of the function \n","\n","def grad_f(x):\n","\n","  a = np.array([[2,1],[1,2]])\n","  return  - np.dot(a,x)\n"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"kWnrc2TxYlGs"},"source":[" '''Function to find the range in the function which contains the minimum value of the function\n","    Satisfying the condition   f(x1)>f(x0)<f(x2)\n","\n","def initial_bracket_multidimensional(x,d,eps):\n","\n","  i = 1\n","\n","  x0, f_x0 = x, fun(x)\n","\n","  x1 = x0 + (i*eps)*fac \n","\n","  f_x1 = fun(x1)\n","\n","  print(\"Initial values\",\"fac:\",fac,\"x0:\",x0,\"x1:\",x1,\"f(x0):\",f_x0,\"f(x1):\",f_x1)\n","\n","  if f_x0 < f_x1 :  \n","    j = i*2 \n","    x0 = x1\n","    eps = -eps\n","    x1 = x0 + (j*eps)*d\n","  \n","  i = i*2\n","  x2 = x0 + (i*eps)*d\n","  f_x2 = fun(x2)\n","\n","  print(\"x0, x1, x2 \",\"x0:\",x0,\"f(x0):\",f_x0,\"x1:\",x1,\"f(x1):\",f_x1,\"x2:\",x2,\"f(x2):\",f_x2)\n","  \n","  if (f_x1 > f_x2): #Check for f(x2) > f(x1)\n","    \n","    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).\n","                          #   Our required bracket\n","      i = i*2\n","      x2 = x0 + (i*eps)*d\n","      f_x2 = fun(x2)\n","      print(\"x0, x1, x2 \",\"x0:\",x0,\"f(x0):\",f_x0,\"x1:\",x1,\"f(x1):\",f_x1,\"x2:\",x2,\"f(x2):\",f_x2)\n","    return [x1,x2]\n","\n","  else:\n","   \n","    return [x0,x2]'''"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"nAXFJ-FKr5XP","executionInfo":{"status":"ok","timestamp":1622202236393,"user_tz":-120,"elapsed":219,"user":{"displayName":"Nasreen Ahmed","photoUrl":"","userId":"04649825647281041989"}},"outputId":"d3a45cee-82e3-41fc-fda2-634c2d31bb56"},"source":["# function call for one-dimensional intial bracket method\n","\n","x = np.array([0.8,-0.25]) # Initial values of x\n","eps = 0.075\n","d = grad_f(x) # passing the gradient direction\n","initial_bracket_multidimensional(x,fac,eps)"],"execution_count":null,"outputs":[{"output_type":"stream","text":["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\n","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\n","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\n","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\n","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\n"],"name":"stdout"},{"output_type":"execute_result","data":{"text/plain":["[array([ 0.69875, -0.2725 ]), array([-0.82, -0.61])]"]},"metadata":{"tags":[]},"execution_count":126}]}]}