{"id":693,"date":"2025-08-08T12:37:10","date_gmt":"2025-08-08T12:37:10","guid":{"rendered":"http:\/\/quentin-duchemin.alwaysdata.net\/wiki\/?p=693"},"modified":"2025-08-08T12:37:10","modified_gmt":"2025-08-08T12:37:10","slug":"connections-between-optimization-methods","status":"publish","type":"post","link":"https:\/\/quentin-duchemin.alwaysdata.net\/wiki\/index.php\/2025\/08\/08\/connections-between-optimization-methods\/","title":{"rendered":"Connections between optimization methods"},"content":{"rendered":"\n

<\/p>\n\n\n\n

In this post, I will start by presenting some famous optimization algorithms. In a second step, I will give some interesting connections between them, allowing the reader to get a better understanding of the field.<\/p>\n\n\n\n

I. Greedy methods<\/h2>\n\n\n\n

<\/p>\n\n\n\n

II. Primal methods<\/h2>\n\n\n\n
  1. Gradient descent<\/strong><\/li><\/ol>\n\n\n\n

    In this section, we consider a function \"f : \mathbb R^d \to \mathbb R\", that is differentiable and convex, and we tackle the problem:

      <\/span>   <\/span>\"\[ \min_{x \in \mathbb R^d}f(x).\]\"<\/p> The gradient descent is a simple algorithm to reach a minimizer of \"f\". Suppose we are
    provided with an initial point \"x_0 \in \mathbb R^d\". Then the gradient descent algorithm is:

      <\/span>   <\/span>\"\[ x_{k+1}:= x_k - \gamma_k \nabla f(x_k),\]\"<\/p>where \"\gamma_k\" is a step size to be tuned. The interpretation of the gradient descent method is minimizing a local quadratic approximation
    of \"f\":

      <\/span>   <\/span>\"\[ f(x) \approx f(x_k)+\nabla f(x_k) ^{\top}( x-x_k) + \frac{1}{2\gamma_k} \|x-x_k\|^2_2.\]\"<\/p>
    where \"\gamma_k\" is unknown a priori. However, there are several manners to choose the step size \"\gamma_k\". The first one is to consider it constant. In this case, we require \"f\" to be gradient Lipschitz in order to ensure convergence. Another way to choose the step size is to perform an adaptive and local computation, called a line search. One example is the so-called backtracking line search<\/em>, also know as Armijo\u2019s rule.<\/p>\n\n\n\n

    Drawbacks<\/strong><\/td>Advantages<\/strong><\/td><\/tr>
    Often slow<\/td>Each iteration has small cost<\/td><\/tr>
    \"f\" needs to be differentiable<\/td>It is a first order method<\/td><\/tr><\/tbody><\/table>
    Gradient descent: pro and cons.<\/figcaption><\/figure>\n\n\n\n