Optimization with absolute values: Difference between revisions
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> | ||
<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> |
Revision as of 16:48, 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
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min{|x_1| + 2|x_2| + |x_3|} }
Failed to parse (SVG (MathML can be enabled via browser plugin): 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}}
We replace the absolute value quantities with a single variable:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |x_1| = U_1 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |x_2| = U_2}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |x_3| = U_3}
We must introduce additional constraints to ensure we do not lose any information by doing this substitution:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -U_1 \le x_1 \le U_1 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -U_2 \le x_2 \le U_2 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -U_3 \le x_3 \le U_3 }
The problem has now been reformulated as a linear programming problem that can be solved normally:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min{ U_1 + 2U_2 + U_3} }
Failed to parse (SVG (MathML can be enabled via browser plugin): 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}}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -U_1 \le x_1 \le U_1 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -U_2 \le x_2 \le U_2 }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -U_3 \le x_3 \le U_3 }
The optimum value for the objective function is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 6} , which occurs when Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1 = 0 } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_2 = 0 } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_3 = 6 } .