Objective: Minimize the function $f(\boldsymbol{x}) = \sum_{k=1}^{N} ||x_k-x_{k-1}||$, for $x_0,x_1,....,x_N \in \mathbb{R}^2$ within the initial point (1,1) and final point is (3,2). It is about finding a shortest path between two points.
The sub-gradient method is required to solve it with N=10 points or any arbitrary N, but I am unable to get a correct solution, i.e., a straight line.
I have done the following steps:
Generate $N-1$ random points within a sphere of radius 50 centred at (0,0) in $\mathbb{R}^2$. These $N-1$ points together with the initial and final points are used as initial path $\boldsymbol{x}_n = \{x_{n,k} \}$ for iteration $n=0$. $x_{0,0}=a$ and $x_{0,N}=b$ in this initial path.
Compute sub-gradient at each individual point of $f(\boldsymbol{x}_{n})$. The sub-gradient of $S_n = \partial f(\boldsymbol{x_n})$ is a matrix of size $N \times 2$. Gradient of each row $S_{n,k}$ of $S_n$ is computed as $S_{n,k} = \partial f(\boldsymbol{x}_{n,k}) = \left( \frac{\partial f(\boldsymbol{x}_n)}{\partial x_{n,k,1}}, \frac{\partial f(\boldsymbol{x}_n)}{\partial x_{n,k,2}} \right) $
Sub-gradient iterations are: $x_{n+1} = {x_n} - \gamma_n S_n$, where the step $\gamma_n = \frac{a}{(b+n)||S_n||}$, where I have used $||S|| = \sqrt{ \sum_{k=1}^{N} (S_{k,0}^2+S_{k,1}^2) } $, and sub-gradient is computed as
If $ \boldsymbol{x_k} - \boldsymbol{x_{k-1}} = \boldsymbol{0}$, then sub-gradient $S$ can be any point within a sphere of unit radius in $\mathbb{R}^2$.
If $ \boldsymbol{x_k} - \boldsymbol{x_{k-1}} \neq \boldsymbol{0}$, then sub-gradient is computed by using $S_k = (S_{k,0}, S_{k,1}) = \partial f(\boldsymbol{x_k}) =\frac{\boldsymbol{x_k} - \boldsymbol{x_{k-1}}}{||\boldsymbol{x_k} - \boldsymbol{x_{k-1}}||} $
My question is if I am computing the sub-gradient and its norm ||S|| correctly? or it could be an implementation issue. For this, the link for python implementation of the project is available here
https://github.com/efarmuh/optimization/blob/main/Exercise%206_LS.ipynb
( see problem 3 in the notebook).
Problem: All points in the path are converging to initial and final points.