# Optimization with absolute values

Jump to navigation Jump to search

Authors: Matthew Chan (mdc297), Yilian Yin (), Brian Amado (ba392), Peter (pmw99), Dewei Xiao (dx58) - SYSEN 5800 Fall 2020

Steward: Fengqi You

## Numerical Example

${\displaystyle \ min|x_{1}|+2|x_{2}|+|x_{3}|}$
${\displaystyle \ s.t.x_{1}+x_{2}-x_{3}\leq 10}$

${\displaystyle x_{1}-3x_{2}+2x_{3}=12}$

We replace the absolute value quantities with a single variable:

${\displaystyle |x_{1}|=U_{1}}$

${\displaystyle |x_{2}|=U_{2}}$

${\displaystyle |x_{3}|=U_{3}}$

We must introduce additional constraints to ensure we do not lose any information by doing this substitution:

${\displaystyle -U_{1}\leq x_{1}\leq U_{1}}$

${\displaystyle -U_{2}\leq x_{2}\leq U_{2}}$

${\displaystyle -U_{3}\leq x_{3}\leq U_{3}}$

The problem has now been reformulated as a linear programming problem that can be solved normally:

${\displaystyle \min U_{1}+2U_{2}+U_{3}}$

${\displaystyle \ s.t.x_{1}+x_{2}-x_{3}\leq 10}$

${\displaystyle x_{1}-3x_{2}+2x_{3}=12}$

${\displaystyle -U_{1}\leq x_{1}\leq U_{1}}$

${\displaystyle -U_{2}\leq x_{2}\leq U_{2}}$

${\displaystyle -U_{3}\leq x_{3}\leq U_{3}}$

The optimum value for the objective function is ${\displaystyle 6}$, which occurs when ${\displaystyle x_{1}=0}$ and ${\displaystyle x_{2}=0}$ and ${\displaystyle x_{3}=6}$.