The optimal step gradient method and applications

In this article, we propose an exercise which describes the optimal method of the step gradient for coercive functions on spaces of finite dimension. These specific problems are used in optimization theory and some applications in finance.

Problem: Let $f:\mathbb{R}^n\to \mathbb{R}$ be a function of class $C^1$. Suppose that there exists a real number $\alpha>0$ such that \begin{align*} \forall (u,v)\in \mathbb{R}^n\times \mathbb{R}^n,\qquad \langle \nabla f(v)-\nabla f(u),v-u\rangle \;\ge\alpha \|v-u\|^2. \end{align*}

  • Prove that \begin{align*} \forall (u,v)\in \mathbb{R}^n\times \mathbb{R}^n,\qquad f(v)\ge f(u)+ \langle\nabla f(u),v-u\rangle+\frac{\alpha}{2} \|v-u\|^2. \end{align*}
  • Deduce that $f$ admits a global minimum on $\mathbb{R}^n$, reached in a unique point that will be denoted by $a$.
  • Let $u\in \mathbb{R}^n\backslash\{a\}$. Consider the function \begin{align*}\varphi_u:\mathbb{R}\to \mathbb{R},\quad t\mapsto f(u+t\nabla f(u)). \end{align*} Prove that $\varphi_u$ admits a global minimum on $\mathbb{R},$ reached in a unique point. This allows us to define a sequence $(u_k)_{k\ge 0}$ in $\mathbb{R}^n$ such that: $u_0\in \mathbb{R}^n$ ; if $k_k=a,$ we select $u_{k+1}=a,$ if not, let $t_k$ be the unique real number such that $\varphi_{u_k}(t_k)=\min(\varphi_{u_k})$. We then set \begin{align*} u_{k+1}=u_k+t_k \nabla f(u_k). \end{align*}
  • Verify that for any $k\in\mathbb{N},$ $\nabla f(u_k)\bot \nabla f(u_{k+1})$.
  • Prove that the series $(u_{k+1}-u_k)_{k\ge 0}$; $(\nabla f(u_{k+1})-\nabla f(u_k))_{k\ge 0}$ and $(\nabla f(u_k))_{k\ge 0}$ the suites tend towards $0$. Deduce that $u_k\to a$ as $k\to\infty$.

Post a Comment

Post a Comment (0)

Previous Post Next Post

Blogroll