0
$\begingroup$

Suppose that we are in a finite-dimensional real vector space $\Bbb R^n$, and we are on a flat $F \subset \Bbb R^n$ (aka, an affine translation of a subspace of $\Bbb R^n$). We want to minimize some $\ell_p$ norm $\|\ldots\|_p$ on $F$.

This is a fairly typical unconstrained convex minimization problem. In practice, most numeric optimization routines that are commonly available can easily solve this problem fairly quickly.

It is fairly easy to visualize why these problems are easy to solve. Something like gradient descent, for instance, converges fairly quickly to the answer. All of these norms are fairly smooth except for $p=1$ and $p=\infty$, and can easily be smoothed by just minimizing $p=1+\epsilon$ to approximate $p=1$ or some large $p$ to approximate $\infty$. So they are fairly well-behaved.

My question is: do these problems fit into some subclass of convex programming that is always known to be fast? All I know is that I have not yet run into an unconstrained norm-minimization problem that has been slow, but I don't know how to place these within some subclass of convex programming that is known to be fast (like SDP, for instance).

$\endgroup$
3
$\begingroup$

If $p$ is rational and $p>=1$, then the p-norm minimization problem can be formulated as an SOCP. This is discussed (among many other places) in

Alizadeh, Farid, and Donald Goldfarb. "Second-order cone programming." Mathematical Programming 95(1):3-51, 2003.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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