Name this optimum-within-convex-hull algorithm: State is a convex combination of hull vertices; Nonnegativity ensured by reparameterization

Question

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?

Answer 1

I don't know of any name for this.

There are several algorithms, e.g. Newton trust region methods, that have convergence guarantees for convex optimization problems with linear inequality constraints. When $f$ is convex, you know that $d^2f$ is symmetric and positive-definite, which means you can use specialized linear solvers like conjugate gradient or Cholesky. Finally, you can get an approximation for how much you expect the objective to decrease with one more iteration of Newton's method by calculating the Newton decrement $\langle d^2f(x_k)\cdot v_k, v_k\rangle$ where $x_k$ and $v_k$ are the current guess and search direction. Compute the Newton decrement can help you come up with sensible convergence criteria. The re-parameterization approach you're describing turns a convex problem into a non-convex one -- just because $f$ is convex doesn't mean that $f(Vu^2)$ is -- and you lose all of these nice properties. So you'll need to work harder to be sure that an iterative algorithm will converge.

Another issue you're likely to encounter is that this re-parameterization turns a problem with a unique solution -- assuming $f$ and $K$ are convex -- into one with multiple solutions. For example, consider minimizing $\|x\|^2$ over a regular hexagon, the (unique) solution of which is the origin. But there are multiple ways to write this solution as a convex combination of the hexagon vertices.

Inequality constraints are annoying and hard to deal with but turning a convex problem into a non-convex one may be making your life even harder.