The optimal step gradient method

In this article, we propose an exercise that 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. We mention also we can use the convex functions to study the optimality of some models.

A problem with the optimal method of the step gradient

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$.

Subscribe our newsletter

  • Unlimited access to all
  • Paper Magazine delivery
  • Priority Support
Thank You, we'll be in touch soon.

Share article


StateMath: Your go-to blog for all things math! Explore our wide range of courses and exercises on algebra, calculus, probability, and geometry. Let's ace those math problems together!