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>\min{|x_1| + 2|x_2| + |x_3|} </math> | ||
<math> | <math> \begin{align} | ||
\ s.t. x_1 + x_2 - x_3 \le 10 \\ | |||
x_1 - 3x_2 + 2x_3= 12 | |||
\end{align}</math> | |||
We replace the absolute value quantities with a single variable: | We replace the absolute value quantities with a single variable: | ||
| Line 29: | Line 31: | ||
The problem has now been reformulated as a linear programming problem that can be solved normally: | 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 | <math>\min{ U_1 + 2U_2 + U_3} </math> | ||
<math>\ | <math> \begin{align} | ||
\ s.t. x_1 + x_2 - x_3 \le 10 \\ | |||
x_1 - 3x_2 + 2x_3= 12 | |||
\end{align}</math> | |||
<math> x_1 - 3x_2 + 2x_3 = 12</math> | <math> x_1 - 3x_2 + 2x_3 = 12</math> | ||
Revision as of 16:44, 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 x_1 - 3x_2 + 2x_3 = 12}
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 } .