# Difference between revisions of "Optimization with absolute values"

Jump to navigation
Jump to search

Line 2: | Line 2: | ||

Steward: Fengqi You | Steward: Fengqi You | ||

+ | |||

+ | |||

+ | ==Numerical Example== | ||

+ | |||

+ | <math>\ Min |x_1| + 2|x_2| + |x_3| </math><br> | ||

+ | <math>\ s.t. x_1 + x_2 - x_3 \le 10</math> | ||

+ | |||

+ | <math> x_1 - 3x_2 + 2x_3= 12</math> | ||

+ | |||

+ | We replace the absolute value quantities with a single variable: | ||

+ | |||

+ | <math>|x_1| = U_1 </math> | ||

+ | |||

+ | <math>|x_2| = U_2</math> | ||

+ | |||

+ | <math>|x_3| = U_3</math> | ||

+ | |||

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

+ | |||

+ | <math> -U_1 \le x_1 \le U_1 </math> | ||

+ | |||

+ | <math> -U_2 \le x_2 \le U_2 </math> | ||

+ | |||

+ | <math> -U_3 \le x_3 \le U_3 </math> | ||

+ | |||

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

+ | |||

+ | <math>\ Min U_1 + 2U_2 + U_3 </math><br> | ||

+ | |||

+ | <math>\ s.t. x_1 + x_2 - x_3 \le 10</math> | ||

+ | |||

+ | <math> x_1 - 3x_2 + 2x_3 = 12</math> | ||

+ | |||

+ | <math> -U_1 \le x_1 \le U_1 </math> | ||

+ | |||

+ | <math> -U_2 \le x_2 \le U_2 </math> | ||

+ | |||

+ | <math> -U_3 \le x_3 \le U_3 </math> | ||

+ | |||

+ | The optimum value for the objective function is <math>6</math>, which occurs when <math>x_1 = 0 </math> and <math>x_2 = 0 </math> and <math>x_3 = 6 </math>. |

## Revision as of 16:29, 20 November 2020

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

Steward: Fengqi You

## Numerical Example

We replace the absolute value quantities with a single variable:

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

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

The optimum value for the objective function is , which occurs when and and .