0
$\begingroup$

I have some optimization problem involving sum of absolute values constraint, such as $\sum_{i=1}^{M}|x_i| \le N$. I've read some posting in the past and found some solutions, especially in this one Minimize sum of absolute value with linear constraint

However, my question is I don't fully understand the intuition behind the first reformulation. To make things simple, assuming I only have 3 $x$'s. Then the constraint becomes $|x_1| + |x_2| + |x_3| \le 10$. Then the reformulation becomes $\sum_{i=1}^{M}y_i \le 10$ and \begin{align} y_1 &\ge x_1 \\ y_1 &\ge -x_1 \\ y_2 &\ge x_2 \\ y_2 &\ge -x_2 \\ y_3 &\ge x_3 \\ y_3 &\ge -x_3 \end{align}

But intuitively, how do we show the reformulation is equivalent? I've gone as far as changing the group of $y_i$'s to \begin{align} -y_1 &\le x_1\le y_1 \\ -y_2 &\le x_2\le y_2 \\ -y_3 &\le x_3\le y_3 \end{align} Then I'm not sure how to proceed...

Thanks

$\endgroup$

2 Answers 2

1
$\begingroup$

Your question says "I have some optimization problem involving sum of absolute values constraint". The question you have linked to has an objective function involving the sum of absolute values (with a linear constraint). The reformulation given in the accepted answer does not apply directly to your problem (and is unlikely to be helpful except in special cases).

Letting $f$ denote your objective function, your problem is

$$\min_x f(x)\qquad \text{subject to}\qquad \sum_{i=1}^M|x_i|\leq N $$

The problem in the question minimize sum of absolute value with linear constraint is

$$\min_x \sum_{i=1}^M|x_i|\qquad \text{subject to}\qquad Ax=b.$$

In your problem, making a substitution $y_i=|x_i|$ will not be helpful unless your objective function has a special form. In particular you want $f$ to involve either terms of the form $g(x_i)$ where $g(x_i)=g(|x_i|)$. For example, if $f(x)=|x_2|e^{|x_1|}$, then you can rewrite the problem

$$\min_x -x_1^2e^{|x_2|}\qquad \text{subject to}\qquad |x_1|+|x_2|\leq 10$$

as

$$\min_y -y_1^2e^{y_2}\qquad \text{subject to}\qquad y_1+y_2\leq 10$$

The solutions to the second problem is $y=(0,10)$ and so the solutions to the first problem are $(0,10)$ and $(0,-10)$.

$\endgroup$
0
$\begingroup$
  1. Suppose that $|x_1|+|x_2|+|x_3|\leq 10$. Put $y_i = |x_i|$. Then $y_i \geq \pm x_i$ and $y_1+y_2+y_3 \leq 10$.

  2. Suppose now that $y_i \geq \pm x_i$, and $y_1+y_2+y_3 \leq 10$. Then $|x_i|=\max\{ x_i, -x_i \} \leq y_i$. Therefore, $|x_1|+|x_2|+|x_3|\leq y_1+y_2+y_3 \leq 10$.

Together, 1+2 show that the projection of the feasible set expressed in terms of the variables $(x,y)$ onto the first block-coordinate (i.e., $x$) is the same as the feasible set of the original problem. Therefore they are equivalent in this sense.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.