2
$\begingroup$

I was wondering if there is a simple or known way to minimize the number of unique elements in a decision variable (vector). Note that I'm not asking for minimization of nonzero elements (rank constraint). In particular I'm searching for a penalization (soft constraint) or hard constraint in the form $$f(x) <= n_{max} $$ where f() is what I'm searching for, x is the decision vector and n_max is the maximum number of unique elements that x is allowed to have.

EDIT: I am not trying to minimize the number of unique elements in a vector " per se", which of course is trivial. The question is related to minimizing the unique element in a vector of decision variables that is the solution to another optimization problem. Eg: $$argmin_{x} g(x) $$ s.t. $$x \in \mathbb{X} $$ $$\sum(unique(x))<n_{max }$$ Thank you for your time, Lorenzo

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ Please re-write your question to make it more clear. "Minimization of the number of unique elements in a vector" is trivial (set all elements equal to the same value), which, obviously, is not what you are looking for. Similar comment for the constraint form you are considering since any trivial function such as $f(x)=0$ is valid. $\endgroup$ – Stelios Feb 28 '17 at 15:45
  • 1
    $\begingroup$ Also, are the $x$ integers? If they are real numbers, then there cannot be a stable solution. $\endgroup$ – Wolfgang Bangerth Mar 1 '17 at 1:55
  • $\begingroup$ Have a look at the edited question, thanks very much for your time. Lorenzo $\endgroup$ – Lorenzo Mar 1 '17 at 14:08
3
$\begingroup$

Inspired by the well-known approach of employing a regularization (penalty) term $\gamma ||\mathbf{x}||_1$ as a means of relaxing the requirement of minimum non-zero elements of vector $\mathbf{x}$ (e.g., see here), you could try using a regularization of the from $$ \gamma ||\mathbf{x} - c\mathbf{1}||_1, $$ where $\mathbf{1}$ is the all-ones vector and $c\in \mathbb{R}$ (assuming the domain is the set of real-valued vectors). You would then solve the resulting problem with respect to both $\mathbf{x}$ and $c$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $\ell_1$ norm is def the way to go. Seems like total variation would work as well. $\endgroup$ – Richard Zhang Mar 2 '17 at 18:44

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.