I'm looking for the "official" name(s) for a procedure for optimizing a convex loss function over a convex subset. This seems to be a default/naïve algorithm that folks come up with before learning the various barrier/penalty methods. I've seen things vaguely like this re-implemented a few times, from first principles and without citing to outside materials.
Algorithm description
(correct missing regularity conditions/details/typos as needed)
Let $f(x)$ be a convex loss function over $x \in \Omega\subset\mathbb R^N$, where $\Omega$ is a convex hull and its interior, defined by $K$ vertices $V = \{ v_1,..,v_K\}$ with each $v_i\in\mathbb R^N$. We want to find:
$$ \underset{x}{\operatorname{argmin}} f(x),\qquad x\in\Omega $$
If $x\in\Omega$, we know that it can be represented as a convex combination of the hull vertices, $x = V \alpha$, where all $\alpha_i\ge0$ and $\sum_i \alpha_i = 1$. We can enforce $\alpha_i\ge 0$ by parameterizing our problem in terms of $\alpha_i = u_i^2$, and that $\sum_i \alpha_i = 1$ with a Lagrange multiplier:
$$ \mathcal L(x,\lambda) = f[ V u^{\circ 2} ] + \tfrac\lambda 2 (\sum_i u_i^2 - 1), $$
where $\circ$ means "elementwise". Note that $\sum_i u_i^2 = \| u \|^2$ is the L2 norm of the vector $u$. The gradients in $x$ and $\lambda$ are:
$$ \nabla_x \mathcal L = \nabla_u f[\dots] + \lambda u $$
$$ \partial_\lambda \mathcal L \propto \| u \|^2 - 1 $$
This is then solved via projected gradient descent, where we enforce that $\|u\|^2=1$, i.e. that $u$ remain a unit vector $\hat u$. Numerically, this is done by normalizing $u\gets u/\|u\|$ after each step. In the limit of infinitesimal updates, the projected gradient flow would be:
$$ \dot{\hat u} \propto - (I - \hat u \hat u^\top ) \nabla_u f[\dots] $$
Thus, we are performing gradient descent with $\hat u$ on the $K-1$ sphere. This corresponds to finding $x$ that minimizes $f$, and is some convex combination $\alpha = u^{\circ 2}$ of the hull vertices $V$.
(I may have transcribed this wrong, so apologies if the above is not, in fact, an optimization algorithm)
Notes and questions:
- Key features:
- Expressing answer as convex combination of points on the boundary of $\Omega$
- Using square-root to enforce non-negativity, leading to coordinates on a sphere.
- Projected gradient descent to solve Lagrangian numerically.
- What is its name? If it is an acceptable approach, what are some sources/references to cite for it?
- Is this guaranteed to converge to a set of $\alpha$ where $x = V\alpha$ is unique and also the optimum?
- Assuming I want a gradient-like algorithm (can only make smooth/continuous changes to $x$), what's are the more correct approaches?