Minimization of absolute value functional with unity constraint

Question

I am interested in the problem of minimizing the functional $$ J(k_1,\dots,k_p) = \sum_{j=1}^p|a_j - k_j|, $$ where the $a_j$ are constants, over all real $p$-vectors $k = [k_1,\dots,k_p]^{tr}$ and subject to the constraint $$ \sum_{j=1}^p k_j = 1. $$ The only meaningful values for the differences $|a_j-k_j|$ are positive, but without the absolute value the problem fails to be convex.

Any advice?

Answer 1

With or without absolute value problem is convex .

But without Absolut value, problem might be unbounded = $- \infty$.

when you have absolute value this problem is equivalent to the following LP

$$ \min \sum_{j}\epsilon_j ~ ~st ~~ \sum_{j=1}^p k_j = 1, ~~ |a_j - k_j| \leq \epsilon_j ~ ~j=1,2..,n $$

P.S : Note that the constraint $ |a_j - k_j| \leq \epsilon_j$ is linear since it is same as $ -\epsilon_j \leq a_j - k_j \leq \epsilon_j$, So you can solve problem effectively using Simplex method

Answer 2

Let's impose the constraint that $k_j \leq a_j$ as otherwise the solution is not of practical interest to OP.

Hence $a_j-k_j \geq 0$

The objective values become $\min \sum_{j=1}^p (a_j-k_j)$ which remains convex as linear functions are convex.

The problem is equivalent to

$$\max \sum_{j=1}^p k_j$$

subject to $$k_j \leq a_j, \forall j \in \{ 1, \ldots, p \}$$

$$\sum_{j=1}^p k_j=1$$

Notice that any feasible point is an optimal point since the objective value is evaluated to $1$ for any feasible point.

Using the additional information that $a_j \geq 0$, we can implement a greedy algorithm.

Find the smallest $q$ such that $\sum_{j=1}^q a_j \geq 1$.

Let $k_j = a_j$ for $j \in \{ 1, \ldots, q-1\}$

and $k_q=1-\sum_{j=1}^{q-1}a_j$

and $k_j=0$ for $j \in \{q+1, \ldots, p\}$.

Notice that the solution is not unique. I am just proposing an algorithm to generate one feasible point. For example, you can reorder the index to generate another point.

Intuitively, the solution is like I have $j$ debts, each amount is $a_j$, I am going to pay as much as possible using my $\$1 $, just do not overpay. As long as I do not overpay and I used up $\sum_{j=1}^p k_j =1$, the solution is optimal.