18
$\begingroup$

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?


$\endgroup$
19
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Great to see you on OR.SE :) $\endgroup$ – TheSimpliFire Jun 1 '19 at 14:49
  • $\begingroup$ Nice answer. This is a lot more elegant than my approach. $\endgroup$ – Discrete lizard Jun 2 '19 at 10:22
9
$\begingroup$

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)

| improve this answer | |
$\endgroup$
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 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$ – Discrete lizard Jun 2 '19 at 10:18
  • 1
    $\begingroup$ @Discretelizard you're right, the result is the same. It's just a different approach. $\endgroup$ – Pantelis Sopasakis Jun 2 '19 at 14:38

Your Answer

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

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