I need to write a matlab m file that takes the following function of $x=(x_{1},x_{2},\cdots, x_{2n})$, and for $n=10$, $n=100$, $n=500$, $$f(x) = \frac{1}{2}\sum_{i=1}^{2n}i(x_{i})^{2}-\sum_{i=1}^{2n}x_{i}+\sum_{i=2}^{2n}\left[\frac{1}{4}\left(x_{i}+x_{i-1} \right)^{2} +\left(x_{i}-x_{i-1}\right)^{2}\right]+\left(x_{2n}-x_{1} \right)^{2} $$ calculates the gradient, and each component $H_{ij}=\frac{\partial^{2}f}{\partial x_{i} \partial x_{j}}$ of the Hessian matrix.
Now, the course that I am doing this for is NOT a course on Matlab (its a nonlinear optimization course). In fact, they take for granted that we all are extremely proficient in Matlab and are comfortable programming to this sophisticated of a degree, which I am not.
Therefore, I am asking, based on the code that I have done thus far, which I am including in a grapic, how do I write the code to
- Calculate the gradients, based on the number inputted into the function by the user, and put all the components into a function of the form $g = [\cdots; \cdots; \cdots]$ with $m$ components.
- Calculate the Hessian components, also based on the number inputted into the function by the user. EDIT: I think I might have come up with suitable code for this. Please see my screenshot and tell me if it looks okay. (Still have no idea how to do this for the gradient though)
I am assuming I would need to set up some kind of dynamic vector for each of these things to be inputted into, and I have absolutely no idea how to do this. So, any assistance with which you could provide me would be greatly beneficial.
Thank you for your time and patience.
Best Answer
Your current solution is based on symbolic math. There are two ways to move forward.
The first is to have continue with symbolic math and use automated differentiation. That will not be the fastest solution, because for $n=500$ you have roughly half a million elements in the Hessian you need to compute.
The second is to observe that your function is quadratic in $x$, and can be written as $0.5 x^TAx + b^Tx + c$. After computing $A$ and $b$, the gradient can be computed efficiently as $Ax+b$, and the Hessian is $A$.
Your objective function is: $$f(x) = \frac{1}{2}\sum_{i=1}^{2n}i(x_{i})^{2}-\sum_{i=1}^{2n}x_{i}+\sum_{i=2}^{2n}\left[\frac{1}{4}\left(x_{i}+x_{i-1} \right)^{2} +\left(x_{i}-x_{i-1}\right)^{2}\right]+\left(x_{2n}-x_{1} \right)^{2}. $$ The easiest way to set up your code is to initialize $A$ and $b$ to a matrix or vector with all zeros:
and to go through the terms of $f$ and update $A$ and $b$. For example, the first term affects the diagonal of $A$:
You should be able to figure out the code for the other terms. Note that you should compute $A$ and $b$ only once, not repeatedly in each iteration.