{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"conjugate_gradient.ipynb","provenance":[],"collapsed_sections":[],"authorship_tag":"ABX9TyMk0o0z3TupAh+07KjYmaxP"},"kernelspec":{"name":"python3","display_name":"Python 3"},"language_info":{"name":"python"}},"cells":[{"cell_type":"markdown","metadata":{"id":"tLjoDv4W1g8N"},"source":["# 1. Conjugate Gradient Method to solve a quadratic function\n","\n","Q. Consider the quadratic function \n","$f(x_1,x_2,x_3) = \\frac{3}{2}x_1^2+2x_2^2+\\frac{3}{2}x_3^2+x_1x_3+2x_2x_3-3x_1-x_3$\n","We find the minimizer using the conjugate gradient algorithm, using the starting point $x^{(0)}=[0,0,0].$\\\n","We can represent f as \\\n","\\begin{align} \n"," f(x) = \\frac{1}{2}x^TQx -x^Tb\n","\\end{align}\n","where \n","\\begin{align} \n","Q =\\begin{pmatrix}\n","3 & 0 & 1 \\\\\n","0 & 4 & 2 \\\\\n","1 & 2& 3\n","\\end{pmatrix}\n","\\end{align}\n","\\begin{align} \n","b = \\begin{pmatrix}\n","3 \\\\\n","0 \\\\\n","1 \n","\\end{pmatrix}\n","\\end{align}\n"]},{"cell_type":"code","metadata":{"id":"MvDkrmUefDX9","executionInfo":{"status":"ok","timestamp":1624444267175,"user_tz":-120,"elapsed":273,"user":{"displayName":"Nasreen Ahmed","photoUrl":"","userId":"04649825647281041989"}}},"source":["import numpy as np\n","# function to return the gradient of the quadratic function\n","def g_f(x):\n","\n"," return np.array([3*x[0]+x[2]-3,4*x[1]+2*x[2], x[0]+2*x[1]+3*x[2]-1])"],"execution_count":111,"outputs":[]},{"cell_type":"code","metadata":{"id":"7ga0Awj04Wbr","executionInfo":{"status":"ok","timestamp":1624444268517,"user_tz":-120,"elapsed":8,"user":{"displayName":"Nasreen Ahmed","photoUrl":"","userId":"04649825647281041989"}}},"source":["# The function conjugate gradient : for finding the minimum value for quadratic function.\n","def conjugate_gradient(x,Q,eps):\n","\n"," i = 0\n"," lst_x = []\n"," lst_g = []\n"," sum_g = [] \n"," g = g_f(x) # getting the gradient\n"," lst_x.append(x) \n"," lst_g.append(g)\n"," sum_g.append(abs(np.sum(g)))\n"," \n"," d = -g # specifying the direction of descent\n"," \n"," while abs(np.sum(g)) > eps: # specifing exit instance from the executing of the loop\n"," \n"," i +=1 # specifying a counter to keep a count on the number of executions.\n","\n"," alpha = - np.divide(np.dot(g,d),np.dot(d,np.dot(Q,d))) # calculating the step size.\n"," x = x + alpha*d #calculating the next value of x\n"," lst_x.append(x) \n","\n"," g = g_f(x) \n"," lst_g.append(g) \n"," beta = np.divide(np.dot(g,np.dot(Q,d)),np.dot(d,np.dot(Q,d))) # calculating beta, to calculate the Q-conjugate descent direction\n"," d = -g + beta*d \n"," sum_g.append(abs(np.sum(g)))\n","\n","\n"," return x,lst_x,lst_g,i,sum_g"],"execution_count":112,"outputs":[]},{"cell_type":"code","metadata":{"id":"XYsYm0Xp6n8d","executionInfo":{"status":"ok","timestamp":1624444270903,"user_tz":-120,"elapsed":286,"user":{"displayName":"Nasreen Ahmed","photoUrl":"","userId":"04649825647281041989"}}},"source":["# Initializing values of x, Q and function call \n","\n","x = np.array([0,0,0])\n","Q = np.array([[3,0,1],[0,4,2],[1,2,3]])\n","x,lst,lst_g,i,sum_g = conjugate_gradient(x,Q,eps=1e-4)"],"execution_count":113,"outputs":[]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/","height":175},"id":"YV6zAQ1f8cJt","executionInfo":{"status":"ok","timestamp":1624444272771,"user_tz":-120,"elapsed":45,"user":{"displayName":"Nasreen Ahmed","photoUrl":"","userId":"04649825647281041989"}},"outputId":"ca045dc6-9276-4154-e635-cb9d2567b163"},"source":["# Presenting the iterations in readable format.\n","import pandas as pd\n","lst = np.array(lst)\n","lst_g = np.array(lst_g)\n","g = lst_g.reshape(i+1,len(x))\n","x = lst.reshape(i+1,len(x))\n","df = np.concatenate((x,g),axis=1)\n","df = pd.DataFrame(df,columns=['x1','x2','x3','g1','g2','g3'])\n","df"],"execution_count":114,"outputs":[{"output_type":"execute_result","data":{"text/html":["
| \n"," | x1 | \n","x2 | \n","x3 | \n","g1 | \n","g2 | \n","g3 | \n","
|---|---|---|---|---|---|---|
| 0 | \n","0.000000 | \n","0.000000e+00 | \n","0.000000e+00 | \n","-3.000000e+00 | \n","0.000000e+00 | \n","-1.000000e+00 | \n","
| 1 | \n","0.833333 | \n","0.000000e+00 | \n","2.777778e-01 | \n","-2.222222e-01 | \n","5.555556e-01 | \n","6.666667e-01 | \n","
| 2 | \n","0.934579 | \n","-1.214953e-01 | \n","1.495327e-01 | \n","-4.672897e-02 | \n","-1.869159e-01 | \n","1.401869e-01 | \n","
| 3 | \n","1.000000 | \n","-1.110223e-16 | \n","2.775558e-17 | \n","-4.440892e-16 | \n","-3.885781e-16 | \n","-2.220446e-16 | \n","