Solving sequences of related convex optimisation problems

28 Views Asked by At

I have a problem in which I need to solve a number of optimisation problems (indexed by $t$) of the form:

$$ \min_{x} f_{t}(x) \\ \text{s.t. } x \in \mathcal{C}_{t} $$

where $C_{t}$ is a compact convex set and $f_{t}$ is a real-valued convex function. Typically $f_{t+1}$ is similar to $f_{t}$ and $\mathcal{C}_{t+1}$ is similar to $\mathcal{C}_{t}$ (according to some distance metric). One I have solved problem $t$, I was hoping that I could somehow use the solution to problem $t$ to solve problem $t+1$ faster, like a kind of warm start. I assume this kind of problem has been encountered before many times, but I am struggling to find literature that investigates this problem thoroughly. Is there a generic scheme for applying this idea with theoretical guarantees? If there isn't, are there any techniques of this type that leverage specific problem structure?

For example, I may have sequence of linear programs:

$$\min_{x \in \mathbb{R}^{d}} c_{t+1}^{\top}x \\ \text{s.t. } A_{t+1}x = b_{t+1} $$

where

$$ A_{t+1} = \begin{pmatrix} A_{t} \\ a_{t+1} \end{pmatrix}, \quad c_{t+1} = c_{t} + u_{t+1}, \quad b_{t+1} = \begin{pmatrix}b_{t} \\ v_{t+1}\end{pmatrix} $$

where $A_{t} \in \mathbb{R}^{t \times d}$, $a_{t} \in \mathbb{R}^{1 \times d}$, $c_{t} \in \mathbb{R}^{d}$, $u_{t} \in \mathbb{R}^{d}$, $b_{t} \in \mathbb{R}^{t}$, $v_{t} \in \mathbb{R}$.

Do these kind of problems have a specific name?