Controlled Optimization of Quadratic Functions in $R^n$

Jean-Jacques Godeme

► To cite this version:

Jean-Jacques Godeme. Controlled Optimization of Quadratic Functions in $R^n$. 2025. hal-04986655v3

HAL Id: hal-04986655

https://hal.science/hal-04986655v3

Preprint submitted on 19 Aug 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Controlled Optimization of Quadratic Functions in $\mathbb{R}^n$

Jean-Jacques Godeme¹

Inria Côte d'Azur & Université Côte d'Azur, CNRS, LJAD, France.

e-mail:jeanjacquesgodeme@gmail.fr.

In honor to the 90th Birthday of Professor emiritus R. Tyrrell Rockafellar for all his contributions to mathematics and his role as an inspiration to younger generations.

**Abstract.** In this work, we introduce and study the controllability of the trajectories of a linear dynamical system, which can be used to solve the minimization of a quadratic function in finite dimension. We named this dynamical system the controlled quadratic gradient flow. Finally, we introduce what we call the controlled quadratic gradient descent and the controlled proximity operator which are respectively the Euler explicit and implicit discretization of the controlled gradient flow.

**Keywords:** Quadratic optimization, controlled gradient flow, compressed sensing, etc...

# 1 Introduction

## 1.1 Problem statement & Motivations

In this paper, we consider the following quadratic optimization problem

$$ \min_{x \in \mathbb{R}^n} f(x) = \frac{1}{2} \langle x, Ax \rangle + \langle b, x \rangle + c, \quad (P) $$

where (P) obey to the following assumptions

### Assumptions 1.

- $\mathbb{R}$ is the set of real vectors, $n, m$ are positive integers,

- $A \in \mathbb{R}^{n \times n}$ is a symmetric, positive semidefinite, $b \in \mathbb{R}^n$ a vector.

(P) is the one of the most famous approach to solve problems arising in many fields like operational research, inverse problems, machine learning and automatic differentiation and has applications in many real life problems such as X-ray crystallography and light scattering. For instance, the least-square formulation of the compressed sensing can be written as:

$$ \min_{x \in \mathbb{R}^n} \frac{1}{2} \|Bx - y\|^2 = \frac{1}{2} \langle x, B^\top Bx \rangle + \langle -B^\top y, x \rangle + \|y\|^2. \quad (1.1) $$

where we want to recover the signal $\bar{x} \in \mathbb{R}^n$ from the measurements vector $y = B\bar{x}$. In such case, one can identify that $A = B^\top B, b = -B^\top y$ and $c = \|y\|^2$. The set of critical points of (P) is given by

$$ \text{crit}(f) = \{x \in \mathbb{R}^n \text{ s.t. } Ax + b = 0\}, $$

it is a set of linear equations.
## 1.2 Prior work and Contributions

### Optimization

Optimization is an important of mathematics with many applications in real-world systems, see for instance the encyclopedia of optimization [8]. To optimize $f$ and then solve (P), the basic and intuitive idea is to make a search for the optimal value using the value function $f$. One can see this has a “Rollercoaster approach”, it consists in finding the minimum by using only $f$. It means checking all the value of $f$ to find the minimum. This method is easy to implement on simple or very basic function but for more sophisticated function, it is easy to see that it is an NP-hard problem. In view to improve the seek, one can use more information on $f$ such as first-order derivatives. The pioneered work of Cauchy [1], based on following the negative of the gradient and is called the *gradient-flow*. Before Cauchy, we have the work in Latin by Newton [16] in 1760, for finding the zeros of a function $f$ and can be applied to the gradient of $f$, yielding to Newton methods. The convergence of the Newton methods has been studied in works such as [10, 20]. Concerning the gradient flow, it convergence has been intensively studied by [23, 22, 11, 5, 2]. Let us now turn our attention to the gradient flow of this problem, we have

$$ \dot{x}(t) = -Ax(t) - b. \qquad (\text{grad-flow}) $$

This equation ensure to find an element of the critical points of $f$. It has been shown for convex function, for instance by Brézis, Bruck and Haddad, that the trajectories weakly converges to the set of $\operatorname{argmin}(f)$. Other works try to solve the optimization problem using several approach such as inertial scheme: Polyak methods in [17, 18], Nesterov methods [15], the heavy ball [3, 4] with appropriate convergences.

### Control theory

At this step, our main inspiration comes from control theory [7, 19, 25, 9]. Roughly speaking, control theory answers the question of whether it is possible or not to control the trajectories of a dynamical system between two known states. Our goal is to control the trajectories of the quadratic gradient flow by acting on this system with another “function” $u$ commonly called *control*. Why control theory in optimization? because the gradient flow only allow to move in the direction of the gradient, our main purpose here is to act independently on the system to ensure that the system converges by allowing different kind of direction on the gradient flow system. We call our new approach *controlled optimization*. One can also observe that every other methods such as the set of inertial methods are actually some kind of control over the gradient flow with an appropriate choice of direction (control) over the system. To the best of our knowledge the closest approach to ours is this paper [21] where the author proposed a model of reinforcement learning where we have an objective function subject to a constraint which is a controlled dynamical system. The two approaches are completely different because we impose the control directly on the gradient-flow dynamics.

## 1.3 Outline of the paper

In Section 3, we develop our main theory of controlled-optimization, where we study the controllability of the gradient-flow for minimizing a quadratic function then we
discretize the corresponding system using an Euler explicit scheme and we find the quadratic gradient descent for solving the minimization of quadratic function. In Section 3.5, we focus on properly define the controlled Moreau's proximity operator. In Section 4, we apply our controlled gradient descent to solve an example compressed sensing problem for Gaussian measurements.

## 2 Notations and preliminaries

**Vectors and matrices** We denote $\langle \cdot, \cdot \rangle$ a scalar product on $\mathbb{R}^n$ and $\|\cdot\|$ the corresponding norm. $B(x, r)$ is the corresponding ball of radius $r$ centered at $x$ and $S^{n-1}$ is the corresponding unit sphere. Moreover, $\|\cdot\|_p, p \in [1, \infty]$ stands for the $l_p$ norm. We denote by $\Gamma_0(\mathbb{R}^n)$ the class of proper lsc convex function on $\mathbb{R}^n$. Given a matrix $M \in \mathbb{R}^{m \times n}$, $M^\top$ is its transpose.

**Functions** A function $f: \mathbb{R}^n \to \bar{\mathbb{R}} = \mathbb{R} \cup \{+\infty\}$ is closed (or lower semicontinuous, lsc) if its epigraph is closed. The effective domain of $f$ is $\text{dom}(f) = \{x \in \mathbb{R}^n : f(x) < +\infty\}$ and $f$ is proper if $\text{dom}(f) \neq \emptyset$ as is the case when it is finite-valued.

The Legendre-Fenchel conjugate of $f$ is $f^*(z) = \sup_{x \in \mathbb{R}^n} \langle z, x \rangle - f(x)$.

We will need to properly define the exponential of a matrix or a linear operator over $\mathbb{R}^n$

$$e^A \stackrel{\text{def}}{=} \sum_{k=0}^{\infty} \frac{A^k}{k!}, \quad \text{where} \quad A^k = \underbrace{A \times A \times \dots \times A}_{k \text{ times}}, \qquad (2.1)$$

Let us define for any $\alpha \in \mathbb{R}^n$ and $x \in \mathbb{R}$ we define the following polynomials

$$P_{\alpha}(x) = \alpha_{0} + \alpha_{1}x + \dots + \alpha_{n}x^{n}.$$

**Theorem 1 (Hamilton-Cayley).** For any $A \in \mathbb{R}^{n \times n}$ be a linear operator then their exists $a \in \mathbb{R}^{n+1}$ such that

$$P_a(A) = 0.$$

## 3 Controlled Optimization

We consider in this work (grad-flow) on which we act with an additive control. We have

$$\dot{x}(t) = -Ax(t) - b + Bu(t), \qquad (3.1)$$

where $B \in \mathbb{R}^{n \times m}$ with $m \le n$ and $u$ is the control taking values in $\mathbb{R}^m$. Let us simplify the notations, we get

$$\dot{x} = -Ax + Bu - b. \qquad (3.2)$$

(3.2) is also known in the control theory literature as the time invariant linear control system. Let $T_0$ and $T_1$ be two real numbers such that $T_0 < T_1$. We want to study the following controlled system

$$\begin{cases} \dot{x}(t) = -Ax + Bu - b \\ x(T_0) = x_0 \in \mathbb{R}^n, u \in L^\infty((T_0, T_1); \mathbb{R}^m). \end{cases} \qquad (\text{cq-Gf})$$
## 3.1 Existence of solution

Let us consider the system (cq-Gf), we have the following existence result.

**Proposition 1 (Existence result).** For any $x_0 \in \mathbb{R}^n$, one has that the solution to (cq-Gf) is unique.

*Proof.* Let $x(t)$ and $y(t)$ two different curves generated by the controlled gradient flow starting at the same point $x_0 \in \mathbb{R}^n$, we consider the following distance

$$g(t) = \frac{1}{2} \|x(t) - y(t)\|^2,$$

therefore

$$ \begin{aligned} g'(t) &= \langle \dot{x}(t) - \dot{y}(t), x(t) - y(t) \rangle \\ &= \langle -Ax(t) - b + Bu(t) + Ay(t) + b - Bu(t), x(t) - y(t) \rangle \\ &= - \langle Ax(t) + b - Ay(t) - b, x(t) - y(t) \rangle \geq 0. \end{aligned} $$

This implies that $g'(t) \leq 0$ thus $g$ is a decreasing function of $t$ thus

$$\forall t > 0, \quad g(t) \leq g(0) = 0.$$

## 3.2 Controllability of the gradient flow for quadratic functions

Let us properly define when a system is called “controllable” in finite dimension.

**Definition 1.**

- (Controllability) Let us consider the system (cq-Gf), we say that (cq-Gf) is controllable from $x_0 \in \mathbb{R}^n$ in time $T > 0$ if their exist $\tilde{T} \in [T_0, T_1]$ such that $T = \tilde{T} - T_0$ and one can reach from the initial point $x(T_0) = x_0$ any point of the space by acting on the system with a control $u \in L^\infty((T_0, T_1); \mathbb{R}^m)$.

- (Attainable from a set) Let $C$ be a subset of $\mathbb{R}^n$. The set that one can attain from $C$ denoted $A[C]$ is the set of all points $x(T_1)$ where $x$ is an admissible trajectory to some control $u$ and where $x(T_0) \in C$.

**Remark 1.**

- From a control theory perspective, a dynamical system is said to be *controllable* if $A[\mathbb{R}^n] = \mathbb{R}^n$. Moreover, we can also say that a dynamical system is said to be *controllable* from $C$ if $A[C] = \mathbb{R}^n$.

- From an optimization perspective, given any $C \subset \mathbb{R}^n$ we are only interested to know whether $A[C] \cap \text{Argmin}(f) \neq \emptyset$. In this case, with a good choice of control $u(\cdot)$, we can solve (cq-Gf) and we say that the system is *opt-controllable* (optimization-controllable) from the set $C$.

- If we only have that $A[C] \cap \text{crit}(f) \neq \emptyset$ we will simply say that the system is *weakly opt-controllable* from the set $C$.

- One can see that *controllability* from a point implies *opt-controllability* and the latter implies *weak opt-controllability*.
- In this work, we will be focusing only on showing the controllability of the gradient flow for solving the quadratic optimization problem.

The following result is fundamental in linear control theory. It gives a necessary and sufficient condition for controllability. It is also known as the rank condition.

**Theorem 2 (Controllability of Gradient flow).** The control quadratic Gradient flow (cq-Gf) system is controllable on $[T_0, T_1]$ if and only if we have

$$ \operatorname{span} \{(-A)^i By; y \in \mathbb{R}^m, i = 0, \dots, n-1\} = \mathbb{R}^n. \quad (\text{Pontryagin-Kalman cond}) $$

*Proof.* We report the proof to the Appendix Section A.1.

**Remark 2.**

- Theorem 2 states that under the (Pontryagin-Kalman cond), the system (cq-Gf) is controllable. Roughly speaking, the gradient flow for minimizing the function $f(x) = \frac{1}{2} \langle x, Ax \rangle + \langle b, x \rangle + c$ is controllable. Therefore, given an initial point $x(T_0) = x_0$ and a desired target $x(T_1) = x_d^* \in \operatorname{crit}(f)$ one can control gradient flow from $x_0$ to $x_d^*$. This result is quite important since it means that instead of running the gradient flow to find any element in $\operatorname{crit}(f)$, one can control the gradient flow in such a way that we can reach our desired state $x_d^*$.

- A similar condition (Pontryagin-Kalman cond) called the Kalman condition appears first in a paper by Lev. Pontryagin in 1959 and later in a joint paper by Rudolph Kalman et al. in 1963, it also known as the Kalman condition in control theory but we think the name Pontryagin-Kalman is more suitable for optimization.

- The Pontryagin-Kalman condition or controllability condition can be equivalently stated as a rank condition i.e.

$$ \operatorname{rank}(\mathcal{C}) = n \quad \text{where} \quad \mathcal{C} \stackrel{\text{def}}{=} [B | (-A)B | A^2B \cdots | (-A)^{n-1}B]. \quad (\text{Pontryagin-Kalman cond}) $$

- Although controllability of (cq-Gf) is really interesting, it is not realistic since we can not control a real-world system with any desired control typically with a control which has «high energy».

**Application to Newton's methods for solving P** Let us consider that we want to solve the same problem using the Newton's Methods and we hope to get the same kind of condition. We then consider the following equation

$$ \begin{cases} A\dot{x}(t) = -Ax(t) - b \\ x(T_0) = x_0 \in \mathbb{R}^n, \end{cases} \quad (\text{quadNM}) $$

Let us introduce an additive control, similarly to the gradient flow system, we have

$$ \begin{cases} A\dot{x}(t) = -Ax(t) - b + Bu(t) \\ x(T_0) = x_0 \in \mathbb{R}^n, u \in L^\infty((T_0, T_1); \mathbb{R}^m). \end{cases} \quad (\text{cq-quadNM}) $$
**Corollary 1 (Controllability of Newton method).** Let us consider the problem (P), the dynamic (cq-quadNM) is controllable if and only if

$$ \mathrm{rank}(B) = n. \qquad (3.3) $$

*Proof.* Let us define $z(t) \stackrel{\mathrm{def}}{=} Ax(t)$, we get that

$$ \left\{ \begin{array}{l} \dot{z}(t) = -z(t) - b + Bu(t) \\ z(T_0) = z_0 \in \mathbb{R}^n, u \in L^\infty((T_0, T_1); \mathbb{R}^m) \end{array} \right. \qquad (\mathrm{cq-NMd}) $$

Then, we apply Theorem 2 to have the following condition

$$ \mathrm{rank}(C_{NM}) = n \quad \text{where} \quad C_{NM} \stackrel{\mathrm{def}}{=} [B|(-1)B|B|\cdots|(-1)^{n-1}B]. $$

Therefore, $\mathrm{rank}(C_{NM}) = n$ if and only if $\mathrm{rank}(B) = n$.

*Remark 3.*

- One can see (cq-NMd) as a gradient flow in the domain of the linear operator. For instance, the Fourier Transform we have a gradient flow in the frequency domain.

- We observe that Pontryagin-Kalman condition for Newton method (3.3) only depends on the linear operator B.

- If A is invertible then the Pontryagin-Kalman condition for Newton method can be written as

$$ \mathrm{rank}(C_{NM}) = n \quad \text{where} \quad C_{NM} \stackrel{\mathrm{def}}{=} [A^{-1}B|(-1)A^{-1}B|A^{-1}B|\cdots|(-1)^{n-1}A^{-1}B], $$
indeed the Newton's methods (cq-quadNM) becomes

$$ \dot{x}(t) = -x(t) - A^{-1}b + A^{-1}Bu. \qquad (3.4) $$

We can observe that the rank condition only depends on B, since A is invertible.

**Observations on Stochastic methods** From a continuous point of view, we also observe that the Langevin Monte-Carlo equation applied to solve (P) and known has the continuous version of the Stochastic gradient descent (SGD) is given by

$$ dX_t = -(AX_t + b)dt + \sqrt{2dB_t}. $$

Let us remark that the second term can be seen has a stochastic control over the dynamical systems. We leave the study of the controllability of this equation as a perspective.

**Definition 2 (Feedback control).** Let us consider a controlled sytem (cq-Gf), we define a feedback control has a control u such that there exists a linear operator $K : \mathbb{R}^n \to \mathbb{R}^m$,

$$ u(t) \stackrel{\mathrm{def}}{=} Kx(t) = Kx_t, \qquad (3.5) $$

where $K \in \mathbb{R}^{m \times n}$ is a constant matrice. We substitute the control expression and we get the system

$$ \dot{x}(t) = -Ax(t) + Bu(t) - b = (-A + BK)x(t) - b. \qquad (3.6) $$
### 3.3 Convergence of the objective function

**Proposition 2 (Behavior of the value function).** Let us consider (cq-Gf), we set $x(t) = x_t$ and the control $u(t) = u_t$, the following holds

$$ \frac{d}{dt} f(x_t) = - \|Ax_t + b\|^2 + \langle Ax_t + b; Bu_t \rangle. \quad (3.7) $$

*Proof.* The proof can be found in Appendix A.2.

*Remark 4.*

- Under the feedback control i.e. replacing (3.5) in (3.7), we get

$$ \frac{d}{dt} f(x_t) = - \|Ax_t + b\|^2 - \|x_t\|_{A^T B K}^2 + \langle b; B K x_t \rangle \quad (3.8) $$

- This expressions explicitly show how the choice of control affects the descent behavior of $f$. Indeed, we can observe that $f$ is not only decreasing along the trajectory. The derivative of $f$ with respect to $t$ along the trajectory can be split in two parts. The first is the usual negative of the norm of the gradient which ensure that $f$ is decreasing along the trajectory and the second is a term which involve the control $u_t$. Thanks to the control term, $f$ is not only decreasing along the trajectory but also can have different behavior this allow to easily attain the pre-image of any value of the function in the space up to a good choice of control.

### 3.4 Explicit Discretization and convergence rates

The forward Euler method or the explicit discretization of (cq-Gf) yield to

$$ \forall k \in \mathbb{N}, \quad \frac{x_{k+1} - x_k}{\gamma_k} = -Ax_k - b + Bu_k \Leftrightarrow x_{k+1} = x_k - \gamma_k (Ax_k + b) + Bu_k, \quad (3.9) $$

where $x_k = x(t_k)$, $u_k = u(t_k)$ with $t_k = k\gamma_k$ and $\gamma_k$ is the stepsize of the discretization of the time interval $[T_0, T_1]$.

**Definition 3 (Controlled gradient descent).** We call the system (cq-Gd) the controlled gradient descent applied on the quadratic program (P).

$$ \forall k \in \mathbb{N}, \quad \begin{cases} x_{k+1} = x_k - \gamma_k (Ax_k + b) + Bu_k \\ x_0 \in \mathbb{R}^n, u_k \in U \subseteq \mathbb{R}^m, B \in \mathbb{R}^{n \times m}, \end{cases} \quad (\text{cq-Gd}) $$

**Proposition 3 (Convergence rates).** Let us define $\tau \stackrel{\text{def}}{=} \|A - BK\| < 1$ and consider the controlled gradient descent (cq-Gd) applied to solve the quadratic minimization (P) and $x^* \in \text{argmin}(f)$, we have the following convergence rates

$$ \|x_{k+1} - x^*\| \le (1 - \gamma_k \|A\|)^k \|x_0 - x^*\| + \|B\| \sum_{i=0}^{k} (1 - \gamma_k \|A\|)^{k-i} \|u_i - u_*\| \quad (3.10) $$

Under the Feedback control, one simply has that

$$ \|x_{k+1} - x^*\| \le (1 - \gamma_k \tau)^k \|x_0 - x^*\|, \quad \text{where} \quad \|A - BK\| = \tau. \quad (3.11) $$

*Proof.* We leave the proof in the Appendix A.3.
## 3.5 Controlled Proximity operator

**Implicit discretization on $x$ and Explicit on $u$** The backward Euler method or the implicit discretization of (cq-Gf) yield to

$$ \forall k \in \mathbb{N}, \quad \frac{x_{k+1} - x_k}{\gamma_k} = -Ax_{k+1} - b + Bu_k \Leftrightarrow x_{k+1} + \gamma_k Ax_{k+1} + b = x_k + \gamma_k Bu_k, \quad (3.12) $$

where $x_k = x(t_k)$, $u_k = u(t_k)$ with $t_k = k\gamma_k$ and $\gamma_k$ is the stepsize of the discretization of the time interval $[T_0, T_1]$. We recall that $\nabla f(x) = Ax + b$. We get the following line

$$ x_{k+1} + \gamma_k \nabla f(x_{k+1}) = x_k + \gamma_k Bu_k $$

$$ \forall k \in \mathbb{N}, \quad \left\{ \begin{array}{ll} x_{k+1} = (\mathrm{Id} + \gamma_k \{\nabla f\})^{-1} \circ \psi_{u_k}(x_k) & \text{where } \psi_{u_k}(x_k) = x_k + \gamma_k Bu_k \\ x_0 \in \mathbb{R}^n, u_k \in \mathbb{R}^m, B \in \mathbb{R}^{n \times m}, & \text{(c-resol)} \end{array} \right. $$

**Remark 5.**

- This expression (c-resol) is closely related to a controlled version of the proximity operator.

- This controlled resolvent has probably a link with the Bregman D-prox.

**Controlled Proximity operator** The Proximity operator is defined in the seminal works by Moreau in [12, 13, 14] which appear to be very useful when working with splitting methods. In this subsection, we would like to simply define a controlled version of the proximity operator.

**Definition 4.** Let us define the following mapping that we call the controlled proximity operator for any control $u \in \mathbb{R}^m$,

$$ \mathrm{c-prox}_{\gamma f}(z) = \underset{x \in \mathbb{R}^n}{\operatorname{argmin}} \left\{ f(x) + \frac{1}{2\gamma} \|x - z\|^2 - \langle Bu; x \rangle \right\}, \quad (3.13) $$

We have the following Proposition which links the resolvant and the proximity operator.

**Proposition 4 (Controlled resolvant and proximity operators).** Let us consider the controlled proximity operator defined by (3.13), we have that solving (3.13) is up to applying the controlled resolvent (c-resol).

*Proof.* We put the proof in the Appendix B.1.

## 4 Numerical experiments

We consider a classical problem which can be put in quadratic form. We solve it use the controlled gradient descent and the classical gradient descent and we compare the numerical result.
**Application to Compressive Sensing (CS)** In Compressed Sensing, we aim to solve the following minimizing

$$ \min_{x \in \mathbb{R}^n} f_{cs}(x) = \frac{1}{2m} \|Ax - y\|^2, \qquad (P) $$

here the matrix A represents different types of linear operator: Gaussian measurements, Fourier basis, Wavelet basis, or any Parseval tight frame [24]. We use the following scheme

$$ \left\{ \begin{array}{l} x_{k+1} = x_k - \gamma_k \nabla f_{cs}(x_k) + B u_k \\ x_0 \in \mathbb{R}^n, B \in \mathbb{R}^{n \times d}, u_k \in \mathbb{R}^d. \end{array} \right. $$

Here we have that $\forall x \in \mathbb{R}^n$, $\nabla f_{cs}(x) = A^\top(Ax - y)$, thus we get the following algorithms:

<caption>**Algorithm 1: Controlled gradient descent for CS**</caption>

**Parameters:** $0 < \gamma < \frac{2}{L}$;
**Initialization:** $x_0 \in \mathbb{R}^n, B \in \mathbb{R}^{n \times d}, u_0 \in \mathbb{R}^d$;
**for** $k = 0, 1, \dots$ **do**
$$ \begin{aligned} x_{k+1} &= x_k - \gamma A^\top(Ax_k - y) + B u_k \\ u_{k+1} &= \text{updatecontrol}(u_k), \end{aligned} \qquad (\text{cgd}) $$

This is the controlled gradient descent applied to the Compressed sensing problem. Let us consider that $\forall r \in \mathbb{N}, (a_r)_{r \in [m]}$ is a standard Gaussian measurement. The next result shows the Pontryagin Kalman condition for Gaussian sensing under sufficiently large number of measurements.

**Lemma 1 (Controlability condition for Gaussian sensing).** Let suppose that $A \in \mathbb{R}^{m \times n}, B \in \mathbb{R}^{n \times d}$ Gaussian sensing for $n \ge cd$ and $m \ge Cd$ where c, C are arbitrary large constant we have

$$ d \le \text{rank}(C) \le nd, \quad \text{where} \quad C \stackrel{\text{def}}{=} [B | -AB|A^2B|\cdots|(-A)^{n-1}B]. $$

*Proof.* Let us consider the Gaussian matrix B, the proof is a direct application of the rank Theorem and the following fact. Under the bound on $n \ge \frac{16}{\rho^2}d$, we have

$$ (1 - \rho) \|u\| \le \frac{1}{m} \|Bu\| \le (1 + \rho) \|u\|. \qquad (4.1) $$

This kind of bound is called the Restricted isometry property [6]. This implies by the rank Theorem that $\text{rank}(B) = d$, by using a similar type of bound for $m \ge \frac{16}{\rho^2}d$ we have that $\text{rank}(AB) = d$. We apply a similar argument recursively to finally get that $d \le \text{rank}(C) \le nd$.
## Set-up and Observations

In this simulation, we want to reconstruct a signal of size $n = 128$ from $m$ different measurements. The Lipschitz coefficient $L \approx \sqrt{m}$. We initialized our schemes using random initialization in $\mathbb{R}^n$. We compare the gradient descent (blue) with the controlled gradient descent (red) with some kind of feedback control in several case: oversampled ($m > n$), sampled ($m \approx n$) and undersampled ($m < n$) regime. In figure 1, we displayed the $l_2$-error of reconstruction of the signal: on the left in the oversampled regime and on the right in the sampled regime. In the oversampled regime both methods behaves almost the same and one can observe a linear convergence rate. When $m \approx n$, both algorithms behave differently, we can observe that the controlled gradient descent behaves better than the gradient descent. The error with the controlled gradient descent is smaller than the error reconstruction with the gradient descent. Almost the same observation can be made in the undersampled regime see Figure 2, in which case the gradient descent behaves very bad while with the controlled gradient descent one can expect to have a better reconstruction. It is not an easy task to find the proper control adapted to the problem that we want to solve. This choice is also linked with the Landscape of the objective function that we want to minimize. In compressed sensing, the landscape obviously depend on the regime.

<figure><img src="image_2.png" /><figcaption>Fig. 1: On the left, error of reconstruction of a signal in the oversampled regime, on the right side error of the reconstruction of a signal when $m \approx n$.</figcaption></figure>

## Conclusion & Perspectives

In this work, we have introduced the controlled gradient flow which is a new perspective to optimization and we have applied our result to solve the compress sensing problem which is a linear inverse problem. This work allows us to see optimization and many algorithms from another point of view. One can see several existing algorithms has control over the gradient flow. The main problem is the choice of the control which of course depend on the objective function and the choice of the direction.
<figure><img src="image_3.png" /><figcaption>Fig. 2: Error reconstruction of a signal when $m = 0.5 \times n$ (undersampled regime).</figcaption></figure>

# A Proofs for Section 3

## A.1 Proofs of Theorem 2

Let us consider the system (cq-Gf), we have

$$ \dot{x}(t) = -Ax(t) + Bu(t) + b, \quad x(T_0) = x_0, $$

where $A \in \mathbb{R}^{n \times n}$, $B \in \mathbb{R}^{n \times m}$, and $u(t) \in \mathbb{R}^m$. We put

$$ y(t) \stackrel{\text{def}}{=} Bu(t) + b \in \mathbb{R}^n. $$

Then the system becomes

$$ \left\{ \begin{array}{l} \dot{x} = -Ax(t) + y(t) \\ x(T_0) = x_0 \in \mathbb{R}^n, y \in \text{Im}(B(U)) + b \subset \mathbb{R}^n. \end{array} \right. \qquad (A.1) $$

We have made a change of variable over the control $u \in U$ to get a new control $y \in \mathbb{R}^n$. To achieve this goal, we consider the homogeneous system which is given by

$$ \left\{ \begin{array}{l} \dot{x} = -Ax(t) \\ x(T_0) = x_0 \in \mathbb{R}^n, \end{array} \right. \qquad (A.2) $$

It is simple to verify that a solution to (A.2) is given by the following expression

$$ \forall t \in [T_0, T_1], \quad \lambda(t) = e^{-A(t-T_0)}x_0. $$

where $e^{-A(t-T_0)}$ is the resolvent from a dynamical perspective and the basic of the semi-group of contraction.

Finally, the solution to the heterogeneous system is given by the following

$$ \forall t \in [T_0, T_1], \quad x(t) = e^{-A(t-T_0)}x_0 + \int_{t_0}^{t} e^{-A(s-T_0)}y(s)ds. \qquad (A.3) $$
To steer the system to a desired final state $x_d \in \mathbb{R}^n$ at time $T_1$, we require that

$$x(T_1) = x_d \iff \int_{T_0}^{T_1} e^{-A(s-T_0)} y(s) ds = x_d - e^{-A(T_1-T_0)} x_0.$$

For any $y \in \text{Im}(B(U)) + b$ implies that $y \in L^\infty([T_0, T_1], \mathbb{R}^n)$ since $B \in \mathbb{R}^{n \times m}$. Now, we define the linear operator

$$\varphi : L^\infty([T_0, T_1], \mathbb{R}^n) \to \mathbb{R}^n, \quad \varphi(y) \stackrel{\text{def}}{=} \int_{T_0}^{T_1} e^{-A(s-T_0)} y(s) ds.$$

To ensure that any desired state $x_d$ is reachable from $x_0$, the operator $\varphi$ must be surjective. We now connect this to the controllability condition. Define the controllability matrix or Pontryagin-Kalman condition

$$\mathcal{C} := [B \ | \ -AB \ | \ A^2B \ | \ \dots \ | \ (-A)^{n-1}B] \in \mathbb{R}^{n \times nm}.$$

Indeed, on one hand we have that if $\text{rank}(\mathcal{C}) < n$ the previous mapping $\varphi$ is not surjective. The fact that $\text{rank}(\mathcal{C}) < n$ means that the matrix $\mathcal{C}$ is not surjective. There exists $\alpha \in \mathbb{R}^n \setminus \{0\}$ such that $\alpha \mathcal{C} = 0$ thus

$$\alpha B = -\alpha AB = A^2 B = \dots = (-\alpha)^{n-1} A^{n-1} B = 0.$$

Now we apply the Hamilton-Cayley Theorem (1) and we have

$$(-A)^n = \sum_{j=0}^{n-1} a_j A^j$$

Using now the expression of the exponential of a matrix and similar on $b$ and we get that

$$\begin{align*}
\forall k \in \mathbb{N}, (-1)^{n-1} \alpha A^k B = 0 &\implies (-1)^{n-1} \alpha A^k y = 0 \\
&\implies \alpha e^{-(t-t_0)} y = 0 \\
&\implies \alpha \int_{t_0}^{t} e^{-A(t-T_0)} y dt = 0.
\end{align*}$$

Therefore the previous corresponding mapping is surjective. On the other hand if $\varphi$ is not surjective thus similarly it is straightforward that $\text{rank}(\mathcal{C}) < n$. Since $\varphi$ is surjective we get that (A.3) is can attain any point in $\mathbb{R}^n$ implying that the system is controllable.

## A.2 Proof of Proposition 2

By the Chain rule, we have that

$$\begin{align*}
\frac{d}{dt} f(x_t) &= \langle \nabla f(x_t); \dot{x}_t \rangle = \langle \nabla f(x_t); -\nabla f(x_t) + Bu_t \rangle, \\
&= -\|Ax_t + b\|^2 + \langle Ax_t + b; Bu_t \rangle, \\
&= -\|Ax_t + b\|^2 + \langle (Ax_t + b); Bu_t \rangle, \\
&= -\|Ax_t + b\|^2 + \langle x_t; ABu_t \rangle + \langle b; Bu_t \rangle.
\end{align*}$$
Taking $u_t = Kx_t$, one get that

$$ 
\begin{aligned}
\frac{d}{dt} f(x_t) &= - \|Ax_t + b\|^2 + \langle x_t; ABKx_t \rangle + \langle b; BKx_t \rangle, \\
&= - \|Ax_t + b\|^2 + \|x_t\|_{ABK}^2 + \langle b; BKx_t \rangle.
\end{aligned}
$$

### A.3 Proof of Proposition 3

Let consider a sequence $(x_k)_{k \in \mathbb{N}}$ generated by the controlled gradient descent and $x^*$ a solution. If the sequence $(x_k)_{k \in \mathbb{N}}$ converges toward a solution $x^*$, it means that it exists a control let call it $u_\star$ yielding to $x^*$. Therefore, we have

$$ 
\begin{aligned}
x_{k+1} - x^* &= x_k - \gamma_k Ax_k + b + Bu_k - x^* + \gamma_k Ax^* - b - Bu_\star, \\
&= (x_k - x^*) - \gamma_k (Ax_k - Ax^*) + B(u_k - u_\star),
\end{aligned}
$$

Taking now the norm and thanks to the triangular inequality we get

$$ \|x_{k+1} - x^*\| \le (1 - \gamma_k \|A\|) \|x_k - x^*\| + \|B\| \|u_k - u_\star\|, $$

Recursively and after summing, we get that

$$ \|x_{k+1} - x^*\| \le (1 - \gamma_k \|A\|)^k \|x_k - x^*\| + \|B\| \sum_{i=0}^{k-1} (1 - \gamma_k \|A\|)^{k-i} \|u_i - u_\star\|, $$

In the particular case, if we use the control $u = Kx$ one get,

$$ 
\begin{aligned}
x_{k+1} - x^* &= x_k - x^* - A(x_k - x^*) + BK(x_k - x^*) \\
&= x_k - x^* - (A - BK)(x_k - x^*)
\end{aligned}
$$

thus we get that

$$ 
\begin{aligned}
\|x_{k+1} - x^*\| &\le \|\mathrm{Id} - (A - BK)\| \|(x_k - x^*)\| \\
\implies \|x_{k+1} - x^*\| &\le \|\mathrm{Id} - (A - BK)\|^k \|(x_0 - x^*)\|
\end{aligned}
$$

where $\|\mathrm{Id} - (A - BK)\|$ is the spectral radius of the corresponding matrix. One can bound the latter and have that

$$ \|x_{k+1} - x^*\| \le (1 - \|A - BK\|)^k \|x_k - x^*\| $$

A good condition which ensure linear convergence of the sequence is $\|A - BK\| < 1$.
# B Proof for Section 3.5

## B.1 Proof of Proposition 4

Let us consider the optimization problem (3.13), $f$ is a quadratic form over $\mathbb{R}^n$ and $A$ is symmetric positive definite which implies that $f \in \Gamma_0(\mathbb{R}^n)$ moreover $\forall u \in U, x \mapsto \langle Bu; x \rangle$ is a linear form thus $f(x) - \langle Bu; x \rangle$ is continuous proper and convex over $\mathbb{R}^n$. Therefore our function is strongly convex and have a unique minimizer. For any fixed $z \in \mathbb{R}^n$, let $\{x^*\} = \text{c-prox}_f(z)$ The first-order optimality condition yields to:

$$ 
\begin{align*}
\nabla f(x^*) + (x^* - z) - Bu = 0 &\iff \nabla f(x^*) + x^* = z + Bu, \\
&\iff (\{\nabla f\} + \text{Id})x^* = z + Bu, \\
&\iff x^* = (\{\nabla f\} + \text{Id})^{-1} (z + Bu).
\end{align*}
$$
Bibliography

[1] Cauchy A. Méthode générale pour la résolution des systèmes d’équations simul-
tanées. *Comptes Rendus de l’Académie des Sciences de Paris*, 25:536–538, January
1847.

[2] H. Attouch and J. Fadili. From the ravine method to the nesterov method and vice versa: A dynamical system perspective. *SIAM Journal on Optimization*, 32(3):2074–2101, 2022.

[3] H. Attouch, X. Goudou, and P. Redont. The heavy-ball with friction method, i. the continuous dynamical system: global exploration of the local minima of a real-valued function by asymptotic analysis of a dissipative dynamical system. *Communications in Contemporary Mathematics*, 2(01):1–34, 2000.

[4] H. Attouch and J. Peypouquet. The rate of convergence of nesterov's accelerated forward-backward method is actually faster than $o(k^{-2})$. *SIAM Journal on Optimization*, 26(3):1824–1834, 2016.

[5] H. Brezis. Asymptotic behaviour of some evolution systems. In Michael G. Crandall, editor, *Nonlinear Evolution Equations*, pages 141–154. Academic Press, 1978.

[6] E.J. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. *IEEE Transactions on Information Theory*, 52(2):489–509, 2006.

[7] J.-M. Coron. *Control and Nonlinearity*. American Mathematical Society, USA, 2007.

[8] C. A. Floudas and P. M. Pardalos. Encyclopedia of optimization. (2):489–509, 2009.

[9] M. Iri, N. Tomizawa, and S. Fujishige. On the controllability and observability of a linear system with combinatorial constraints. *Journal of the Society of Instrument and Control Engineers*, 13:235–242, 1977.

[10] L. Kantorovich. On newton's method. *Trudy Mat. Inst. Steklov*, 28:104–144, 1949.

[11] S. M. Mordukhovich. *Variational Analysis and Applications*. Springer Monographs in Mathematics. Springer Cham, Berlin, Heidelberg, 2018.

[12] J.-J. Moreau. Fonctions convexes duales et points proximaux dans un espace hilbertiens. *Comptes rendus hebdomadaires des Séances de l'Académies des Sciences*, 255:2897–2899, 1962.

[13] J.-J. Moreau. Propriétés des applications “prox”. *Comptes rendus hebdomadaires des Séances de l'Académies des Sciences*, 256:1069–1071, 1962.

[14] J.-J. Moreau. Proximité et dualité dans un espace hilbertien. *Bulletin de la Société Mathématiques de France*, 93:273–299, 1965.

[15] Y. Nesterov. Lectures on convex optimization. Springer, 137:1–17, 2018.

[16] I. Newton. Philosophiae naturalis principia mathematica. *Sumptibus et Ant, Philibert*, 1760.

[17] B. T. Polyak. Gradient methods for the minimisation of functionals. *U.S.S.R. Comput. Math. and Math. Phys.*, 3(4):864–878, 1963.
[18] B. T. Polyak. Some methods of speeding up the convergence of iteration methods. U.S.S.R. Comput. Math. and Math. Phys., 4(5):1-17, 1964.

[19] N. Raissi, C. Sanogo, and M. Serhani. Differential game model for sustainability multi-fishery. *Trends in Biomathematics: Mathematical Modeling for Health, Harvesting, and Population Dynamics: Selected works presented at the BIOMAT Consortium Lectures, Morocco 2018*, pages 119-137, 2019.

[20] L. B. Rall. Convergence of the newton process to multiple solutions. *Numer. Math.*, 9:23-37, 1966.

[21] B. Recht. *A tour of reinforcement learning : the view from continuous*. arxiv:1806.09460v2, 2018.

[22] R. T. Rockafellar. *Convex Analysis*. Princeton University Press, 1970.

[23] R. T. Rockafellar and R. J. B. Wets. *Variational Analysis*, volume 317 of *Grundlehren der mathematischen Wissenschaften*. Springer Berlin Heidelberg, Berlin, Heidelberg, 1998.

[24] J.-L. Starck, F. Murtagh, and J. M. Fadili. *Sparse Image and Signal Processing*. Cambridge Press., 2015.

[25] E. Trélat. *Contrôle optimal: théorie & applications*. Mathématiques concrètes. Vuibert, 2005.