1
$\begingroup$

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?
$\endgroup$
5
  • $\begingroup$ You state that the constraint set is the convex hull (which, by definition, includes its interior). But your algorithm only appears to search the boundary of the convex hull. You then talk about ' "finding x that maximizes f,", but the original problem statement is to minimize f (subject to constraint). If you actually want to maximize f, there would be a global optimum at an extreme of the convex hull, i.e., a vertex, because it would be minimizing a concave function over a compact convex constraint region. Maybe there are typos you need to fix? $\endgroup$ Aug 22 at 14:33
  • $\begingroup$ As far as I can tell the interior is permitted. The $\alpha$ are barycentric coordinates, so they can specify points inside the convex hull. The reparameterization to $u$ shouldn't change this. The max/min thing was just a typo, might be fixed now. Thanks! ~m $\endgroup$
    – MRule
    Aug 22 at 14:46
  • $\begingroup$ Doesn't $\sum_i u_i^2 = 1$ preclude points in the interior of the convex hull, which would require $\sum_i u_i^2 \le 1$ instead, and therefore is cutting off a portion of the feasible region, which therefore could result in a suboptimal solution? $\endgroup$ Aug 22 at 15:37
  • $\begingroup$ My intuition is this: Consider a triangle, with three points. The coordinate α=(⅓,⅓,⅓) is valid (L1 norm is 1). It is also the barycenter, and inside the triangle (if not degenerate). I think the missing intuition (which maybe reveals why this naïve approach is not great) is that if you have K vertices, you optimize in a degenerate K-dimensional space. You need at least K+1 vertices for a K-dimesional simplex, but you can also have K»D+1. Now, there are multiple convex combinations (I think) that map to the same point x ∈ R^D. $\endgroup$
    – MRule
    Aug 24 at 7:45
  • $\begingroup$ I suppose whether the interior is accessible depends on whether you view this as an optimization in the convex combination weights α, or in the original coordinate x. $\endgroup$
    – MRule
    Aug 24 at 7:46

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.