Consider the orthogonal distance regression $($ODR$)$ problem, which can be stated as follows. Given $N$ random observations $(x_i,Y_i)in{R}^{d+1}$ of the true underlying data $(x_i,y_i)$ which follow the relationship $y_i={}_0+{}^T{x}_i$ for $i=1,$dots,$N.$ We would like to find $(,{}_0)$ such that the total squared distance between $(x_i,Y_i)$ and $(x_i,y_i)$ is minimized, i$.$e$.,$

$(1)mi{n}_{(,{}_0),x_i}{\displaystyle \underset{i=1}{\overset{N}{}}}||x_i-x_i||{|}^2+(Y_i-{}_0-{}^T{x}_i{)}^2.|$

This is an unconstrained optimisation problem $mi{n}_{zin{R}^n}f(z),$ which can be solved by a trust$-$region algorithm described as follows.

Choose initial point $z_0,$ initial radius $r_0,$ maximum radius $r_{\text{m}\text{a}\text{x}}$ and threshold $in[0,0\mathrm{.}25).$ while $||gradf(z_k)||>lon$ do

Calculate $p_k$ by solving the following problem

$(2)mi{n}_{||p||}{r}_k{m}_k(p)=f(z_k)+$gradf$(z_k{)}^{T}p+\frac{1}{2}{p}^T{H}_f(z_k)p.$

Compute ${}_k=\frac{f(z_k)-f(z_k+p_k)}{m_k(0)-m_k(p_k)}.$

if ${}_k<mn\; id="EditorElement\_254794">0</mn><mn\; id="EditorElement\_254795">.</mn><mn\; id="EditorElement\_254796">2</mn><mn\; id="EditorElement\_254797">5</mn>$ then

$r_{k+1}=0\mathrm{.}25r_k$

else

if ${}_k>0\mathrm{.}75$ and $||p_k||=r_k$ then

else

$r_{k+1}=$min$\{2r_k,r_{\text{m}\text{a}\text{x}}\}$

$r_{k+1}=r_k$

if ${}_k>$ then

else

$z_{k+1}=z_k+p_k$

$z_{k+1}=z_k$

For this question, consider the following tasks:

a$)$ Explain the main idea behind the given algorithm how to move from $z_k$ to $x_{k+1}$ with $p_k$ and $r_k.$ In addition, what is ${}_k$ and how does it affect the update of the radius $r_k$ to $r_{k+1}?$

b$)$ Instead of solving the sub$-$problem $(2)$ exactly, one can restrict the problem by imposing the constraint $p=p_k^l$ with $0$ and $p_k^l$ is the optimal solution of the following problem

$(3)mi{n}_{||p||}{r}_k{m}_k^l(p)=f(z_k)+$gradf$(z_k{)}^{T}p.$

Write down the exact formulation of $p_k$ by solving the sub$-$problem $(2)$ with the additional constraint as discussed.