Difference between revisions of "Optimization with absolute values"

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
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 .