# How to minimize an absolute value in the objective of an LP?

I want to solve the following optimization problem

$$\begin{array}{ll} \text{minimize} & | c^\top x |\\ \text{subject to} & A x \leq b\end{array}$$

Without the absolute value, this a standard form for linear programs. Can such a problem be transformed to an ordinary linear program?

Alternatively, by observing that $$|c \cdot x|= \max \{c^T x, -c^T x\}$$,

$$\min_x |c\cdot x| \text{ subject to } Ax \le b$$

can be rewritten as

$$\min_x \max \{c^T x, -c^T x\} \text{ subject to } Ax \le b$$

which is equivalent to

$$\min_{x, z} z$$

subject to

$$z \ge c^Tx$$

$$z \ge -c^Tx$$

$$Ax \le b$$

which is a linear program.

This works because at the optimal value, $$z$$ will take one of the value of $$c^Tx$$ or $$-c^Tx$$, it takes the value that is bigger.

• Great to see you on OR.SE :) Jun 1, 2019 at 14:49
• Nice answer. This is a lot more elegant than my approach. Jun 2, 2019 at 10:22

This is possible by introducing 2 new variables, $$t_1,t_2$$, and adding a few constraints:

\begin{align} \min t_1+t_2 \quad \text{s.t.} \quad t_1-t_2 &= c\cdot x\\ t_1&\geq 0 \\ t_2&\geq 0 \\ Ax&\leq b \end{align}

Why does this work? The main idea is that an optimal solution must set at least one of $$t_1,t_2$$ to $$0$$. First suppose $$c\cdot x \leq 0$$. This means $$0\leq t_1\leq t_2$$, so the minimum of $$t_1+t_2$$ is attained by setting $$t_1=0$$ and $$t_2=-c\cdot x$$ and so $$t_1+t_2 = -c\cdot x = |c\cdot x|$$. Otherwise, $$c\cdot x>0$$ and so $$0\leq t_2 < t_1$$, so the minimum of $$t_1+t_2$$ is attained by setting $$t_2=0$$ and $$t_1=c\cdot x$$ and so $$t_1+t_2 =c\cdot x =|c\cdot x|$$.

Note that this does not work for maximization problems. Replacing min by max makes the program above unbounded (suppose there is a feasible solution with $$t_1=a$$ and $$t_2=b$$. Then there is a feasible solution with $$t_1=a+C$$ and $$t_2=b+C$$ for any $$C\geq 0$$).

I'm not aware of any similar formulation for LP problems, but this is solvable in ILP problems by maximizing $$T$$ under the disjunctive constraint $$T= c\cdot x \vee T= -c\cdot x$$. (disjunctive constraints can be modeled with a binary decision variable)

I would like to suggest a different angle using the epigraphical relaxation of the absolute value. In particular,

$$|z| = \min_{|z|\leq t}t = \min_{-t \leq z \leq t}t$$

Using this observation, the optimization problem:

$$\operatorname*{Minimize}_{x, Ax \leq b} |c^\top x|$$

is equivalent to

$$\operatorname*{Minimize}_{x, Ax \leq b} \min_{-t \leq c^\top x \leq t}t,$$

that is

$$\operatorname*{Minimize}_{x,t \,{}:{}\, Ax \leq b,\ -t \leq c^\top x \leq t} t,$$

which is an LP.

• While your derivation is a bit different, it seems that this program pretty much the same as in this answer. (the only difference I see is that you have the constraint $-t\leq c^\top x$ instead of $t\geq -c^\top x$, but these constraints are of course equivalent.) Jun 2, 2019 at 10:18
• @Discretelizard you're right, the result is the same. It's just a different approach. Jun 2, 2019 at 14:38