Difference between revisions of "Optimization with absolute values"

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
Line 6: Line 6:
 
==Numerical Example==
 
==Numerical Example==
  
<math>\min{|x_1| + 2|x_2| + |x_3|} </math>
+
<math>\min{|x_1| + 2|x_2| + |x_3|} </math><BR>
 
+
<math>\min |x_1| + 2|x_2| + |x_3| </math>
 
<math>  \begin{align}
 
<math>  \begin{align}
 
\ s.t. x_1 + x_2 - x_3 \le 10 \\
 
\ s.t. x_1 + x_2 - x_3 \le 10 \\
Line 34: Line 34:
  
 
<math>  \begin{align}
 
<math>  \begin{align}
\ s.t. x_1 + x_2 - x_3 \le 10 \\
+
\s.t. x_1 + x_2 - x_3 \le 10 \\
 
x_1 - 3x_2 + 2x_3= 12
 
x_1 - 3x_2 + 2x_3= 12
 
\end{align}</math>
 
\end{align}</math>
 
<math> x_1 - 3x_2 + 2x_3 = 12</math>
 
  
 
<math> -U_1 \le x_1 \le U_1 </math>
 
<math> -U_1 \le x_1 \le U_1 </math>

Revision as of 16:47, 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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \s.t. x_1 + x_2 - x_3 \le 10 \\ x_1 - 3x_2 + 2x_3= 12 \end{align}}

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