Sofiane Tanji
November 4, 2024
In this blog post, we introduce and motivate the bundle level method as first proposed in [1].
We want to minimize a closed, proper, convex function \(f : \mathbf{R}^d \rightarrow \mathbf{R}\) over a nonempty, closed, convex set \(\mathcal{X} \subseteq \text{int dom } f\).
We equip \(\mathcal{X}\) with an arbitrary norm \(\|\cdot\|\) and we denote \(\|\cdot\|_*\) its conjugate.
We assume that \(f\) is bounded from below: \(\forall x \in \mathcal{X}, f(x) \geq f_{min}\).
We assume access to a first-order oracle. Specifically, at any query point \(x \in \mathbf{R}^d\), returns \((f(x), g(x))\) where \(g(x) \in \partial f(x)\) is an arbitrary subgradient.
We assume \(f\) to be \(L\)-Lipschitz with respect to \(\|\cdot\|\).
We are going to write some code:
using LinearAlgebra
a = [1, 2, 3, 3, 4, 5, 2, 2]
@show dot(a, a)
println(dot(a, a))[1] Claude Lemaréchal, Arkadii Nemirovskii & Yurii Nesterov (1995). New variants of bundle methods. Mathematical Programming 69 (1995) 111-147