0
$\begingroup$

I'm working on the following problem and am unsure if I'm doing it right:

Let $y = (y_1,y_2,....,y_N)^T$ be an $N$- vector of non-negative real numbers. Consider the following problem:

$$min_{x \in \mathbb{R^N}} \sum_{i=1}^N |x_i - y_i| + a*\sum_{i=1}^{N-1}|x_{i+1} - x_i|$$ with $x \ge 0$ and $a > 0$.

Bring this problem into the Standard Form, i.e:

$min_{x \in \mathbb{R^n}} c^T*x $ with $Ax=b$ and $x \ge 0$.

I proved earlier that for any real number $x \in \mathbb{R}$ holds:

$|x| = inf_{(y_1,y_2) \in \mathbb{R^2}} \ y_1 + y_2 \ $ such that $x = y_1 - y_2 , \ y_1 \ge 0 , \ y_2 \ge 0$

With that in mind we can rewrite the above problem to:

$$min_{x \in \mathbb{R^N}} \sum_{i=1}^N |x_i - y_i| + a*\sum_{i=1}^{N-1}|x_{i+1} - x_i|$$

$$= min_{x \in \mathbb{R^N}}\sum_{i=1}^N inf_{x_i+y_i \ = \ x_i-y_i } \ x_i + y_i \ \ + \ \ a*\sum_{i=1}^{N-1} inf_{x_{i+1}+x_i \ = \ x_{i+1}-x_i} \ x_{i+1} + x_i $$

$$= min_{x \in \mathbb{R^N}}\sum_{i=1}^N x_i + y_i \ \ + \ \ a*\sum_{i=1}^{N-1} x_{i+1} + x_i $$ such that $x_{i+1}+x_i \ = \ x_{i+1}-x_i$ and $x_i+y_i \ = \ x_i-y_i$

$$= min_{x \in \mathbb{R^N}}\sum_{i=1}^N (a+1)*x_i + y_i $$ such that $x_{i+1}+x_i \ = \ x_{i+1}-x_i$ and $x_i+y_i \ = \ x_i-y_i$

$\endgroup$
  • 1
    $\begingroup$ your first step is already incorrect, where is the $x=y_1-y_2$ constraint that you had in your $|x|$ reformulation? $\endgroup$ – LinAlg Apr 26 '18 at 19:24
  • $\begingroup$ OK, I correceted my post, but I still don't see what can further be done here. Could you give me some hints? $\endgroup$ – 3nondatur Apr 26 '18 at 20:10
  • 1
    $\begingroup$ You have to use new variables, you cannot reuse $y_i$. $\endgroup$ – LinAlg Apr 26 '18 at 20:39
  • $\begingroup$ Do you mean I could use a vector $ z = (x,y)$ such that $z_i + z_{2N+1} = z_i - z_{2N+1}$ ? But this can't be expressed in the form $A*z =b$ can it? $\endgroup$ – 3nondatur Apr 26 '18 at 21:59
  • 1
    $\begingroup$ You need to replace $|x_i-y_i|$ with $z_i + z_{N+i}$ and add $z_i + z_{N+i} = x_i-y_i$, $z \geq 0$. This is linear and therefore can be expressed as $Ax=b$. $\endgroup$ – LinAlg Apr 27 '18 at 1:40

Your Answer

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

Browse other questions tagged or ask your own question.