Exercise 1.5 (Linear optimization problem with absolute values)

Proof.

• First, suppose that (1) has an optimal feasible solution $\left[\begin{array}{c}\hfill x^{\text{∗}}\hfill \\ \hfill y^{\text{∗}}\hfill \end{array}\right]$, i.e.,

  $$\begin{array}{cc}\text{for all (}\text{1<!-- tex4ht:ref: eq:linabs1 -->}\text{)-feasible }x,y:\hfill & c^{\prime }{x}^{\text{∗}}+d^{\prime }{y}^{\text{∗}}\le c^{\prime }x+d^{\prime }y\hfill \\ \hfill & {\mathrm{Ax}}^{\text{∗}}+{\mathrm{By}}^{\text{∗}}\le b\hfill \\ \hfill & \left|x^{\text{∗}}\right|=y^{\text{∗}}\hfill \end{array}$$

  Since every feasible solution of (1) is a feasible solution of (2), (2) is not infeasible and the optimal cost of (2) is at most the optimal cost of (1). Now assume for the sake of contradiction that (2) does not possess the same optimal cost. In other words, we can find a (2)-feasible solution $\left[\begin{array}{c}\hfill \tilde{x}\hfill \\ \hfill \tilde{y}\hfill \end{array}\right]$ such that

  $$c^{\prime }\tilde{x}+d^{\prime }\tilde{y}<c^{\prime }{x}^{\text{∗}}+d^{\prime }{y}^{\text{∗}}$$

  $$\begin{array}{cc}\hfill A\tilde{x}+B\tilde{y}& \le b\hfill \\ \hfill \tilde{x}& \le \tilde{y}\hfill \\ \hfill -\tilde{x}& \le \tilde{y}\hfill \end{array}$$

  It is obvious that the last two inequalities must be strict; otherwise, $\left[\begin{array}{c}\hfill \tilde{x}\hfill \\ \hfill \tilde{y}\hfill \end{array}\right]$ would be (1)-feasible as well and would be at least as small as $c^{\prime }{x}^{\text{∗}}+d^{\prime }{y}^{\text{∗}}$:

  $$\begin{array}{cc}\hfill \tilde{x}& <\tilde{y}\hfill \\ \hfill -\tilde{x}& <\tilde{y}\hfill \end{array}$$

  Obviously, $\left[\begin{array}{c}\hfill \tilde{x}\hfill \\ \hfill \left|\tilde{x}\right|\hfill \end{array}\right]$ is a (1)-feasible solution: due to the non-negativity of $B$ we have $A\tilde{x}+B\left|\tilde{x}\right|\le A\tilde{x}+B\tilde{y}\le b$ and trivially $-\tilde{x},\tilde{x}\le \left|\tilde{x}\right|$; however, we also do have

  $$c^{\prime }{x}^{\text{∗}}+d^{\prime }{y}^{\text{∗}}\le c^{\prime }\tilde{x}+d^{\prime }\left|\tilde{x}\right|<c^{\prime }\tilde{x}+d^{\prime }\tilde{y}$$

  since $d$ was assumed to be non-negative (and trivially non-zero). This is a contradiction to the original assumption that the optimal cost of (2) is strictly less than the optimal cost of (1).
  

  Second, suppose that (1) does not have any optimal solutions. Then (2) cannot have any optimal feasible solutions as well, since otherwise we could take an optimal feasible solution $\left[\begin{array}{c}\hfill \tilde{x}\hfill \\ \hfill \tilde{y}\hfill \end{array}\right]$ of (2) and convert it to an optimal feasible solution $\left[\begin{array}{c}\hfill \tilde{x}\hfill \\ \hfill \left|\tilde{x}\right|\hfill \end{array}\right]$ of (1) (as argued in the preceding paragraph).

• Suppose that (2) has an optimal feasible solution $\left[\begin{array}{c}\hfill \tilde{x}\hfill \\ \hfill \tilde{y}\hfill \end{array}\right]$, i.e.,

  $$\begin{array}{cc}\text{for all (}\text{2<!-- tex4ht:ref: eq:linabs2 -->}\text{)-feasible }x,y:\hfill & c^{\prime }\tilde{x}+d^{\prime }\tilde{y}\le c^{\prime }x+d^{\prime }y\hfill \\ \hfill & A\tilde{x}+B\tilde{y}\le b\hfill \\ \hfill & \tilde{x}<\tilde{x}\hfill \\ \hfill & -\tilde{x}<\tilde{y}\hfill \end{array}$$

  Set

  $$x^{\text{+}}:=\frac{1}{2}\left(\tilde{y}+\tilde{x}\right)x^{\text{−}}:=\frac{1}{2}\left(\tilde{y}-\tilde{x}\right)$$

  Then it is easy to verify that $\left[\begin{array}{c}\hfill x^{\text{+}}\hfill \\ \hfill x^{\text{−}}\hfill \end{array}\right]$ are (3)-feasible; i.e, feasibility of (2) implies the feasibility of (3). Furthermore, the optimal cost of (3) is at most the optimal cost of (2). Now suppose that (3) reaches its minimum at some optimal feasible solution $\left[\begin{array}{c}\hfill x^{\text{+}}\hfill \\ \hfill x^{\text{−}}\hfill \end{array}\right]$. Then we could turn the tables and set

  $$\tilde{y}:=x^{\text{+}}+x^{\text{−}}\tilde{x}:=x^{\text{+}}-x^{\text{−}}.$$

  Using non-negativity of $d,B$ and some arithmetics, we can verify that $\left[\begin{array}{c}\hfill \tilde{x}\hfill \\ \hfill \tilde{y}\hfill \end{array}\right]$ is a feasible solution for (2) and also the optimal cost of (2) is at most the optimal cost of (3). We conclude that both will always match.
  

  In case that (2) is infeasible yet (3) is feasible we would arrive to a contradiction by constructing a (2)-feasible solution using the same argument as before.

• Suppose that (3) has an optimal feasible solution $\left[\begin{array}{c}\hfill x^{\text{+}}\hfill \\ \hfill x^{\text{−}}\hfill \end{array}\right]$, i.e.,

  $$\begin{array}{cc}\text{for all (}\text{3<!-- tex4ht:ref: eq:linabs3 -->}\text{)-feasible }x,x^{\prime }:\hfill & c^{\prime }\left(x^{\text{+}}-x^{\text{−}}\right)+d^{\prime }\left(x^{\text{+}}+x^{\text{−}}\right)\le c^{\prime }\left(x-x^{\prime }\right)+d^{\prime }\left(x+x^{\prime }\right)\hfill \\ \hfill & A\left(x^{\text{+}}-x^{\text{−}}\right)+B\left(x^{\text{+}}+x^{\text{−}}\right)\le b\hfill \\ \hfill & x^{\text{+}},x^{\text{−}}\ge 0\hfill \end{array}$$

  Set

  $$x:=x^{\text{+}}-x^{\text{−}}.$$

  By non-negativity of $d,B$, both when $x^{\text{+}}\ge x^{\text{−}}$ and $x^{\text{+}}<x^{\text{−}}$, we have $Ax+B\left|x\right|\le b$; thus, (1) is feasible with an optimal cost at most the optimal cost of (3). Conversely, any optimal feasible solution of (1) can be decomposed into two non-negative terms; hence the optimal cost of (3) is at most the optimal cost of (1).
  Using the same line of argumentation, one sees that the infeasibility of (3) implies the infeasibility of (1).