1

I want to find the smallest vector $\vec p$ such that some constraints are satisfied, so something like:

$$\hat p = \underset{\vec p}{\arg \min} \; |\vec p| \\ s.t. \; F(x_i, \vec p) \leq \epsilon_i \; \forall i $$

Is there a general approach for solving such a problem?

My idea is to pre-allocate $\vec p$ to be very large and then minimize the number of nonzero entries like so:

$$\hat p = \underset{\vec p}{\arg \min} \; \sum_j^{|\vec p|} (p_j \neq 0) \\ s.t. \; F(x_i, \vec p) \leq \epsilon_i \; \forall i $$

Is this the right idea?

rhombidodecahedron
  • 1,532

1 Answers1

4

It sounds like you want to minimize the $L_0$ norm of $p$ subject to your constraints. That would lead to an intractable problem though, so what people do instead is minimize the $L_1$ norm of $p$. This is a very popular heuristic that encourages $p$ to be sparse.

$L_1$ norm minimization (to promote sparsity) has been a very active topic in optimization and applied math. It's discussed in Boyd and Vandenberghe, for example.

littleO
  • 51,938