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?


3 Answers 3


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.

  • 5
    $\begingroup$ Great to see you on OR.SE :) $\endgroup$
    – TheSimpliFire
    Commented Jun 1, 2019 at 14:49
  • $\begingroup$ Nice answer. This is a lot more elegant than my approach. $\endgroup$ Commented 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.

  • 1
    $\begingroup$ 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.) $\endgroup$ Commented Jun 2, 2019 at 10:18
  • 1
    $\begingroup$ @Discretelizard you're right, the result is the same. It's just a different approach. $\endgroup$ Commented Jun 2, 2019 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.