Difference between revisions of "Optimization with absolute values"

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
(Added initial draft for Method section and Reference section.)
Line 3: Line 3:
 
Steward: Fengqi You
 
Steward: Fengqi You
  
 +
== Method ==
 +
 +
=== Defining Absolute Values ===
 +
An absolute value of a real number can be described as its distance away from zero, or the non-negative magnitude of the number. Thus,
 +
 +
<math>|x| = \begin{cases} -x, & \text{if }x < 0 \\ x, & \text{if }x \ge 0 \end{cases}  </math>
 +
 +
Absolute values can exist in optimization problems in two primary instances: in constraints and in the objective function.
 +
 +
=== Absolute Values in Constraints ===
 +
Within linear equations, linear constraints can exist in several forms.
 +
 +
The first form exists as <math>|X| = 0  </math>, where <math display="inline">X </math> is a linear combination of variables.
 +
 +
In this case, the only solution is if <math>|X| = 0 </math>, simplifying the constraint to <math>X = 0  </math>. Note that this solution also occurs if the constraint is in the form <math>|X| <= 0  </math> due to the same conclusion (only solution <math>X = 0  </math>).
 +
 +
 +
Second form a linear constraint can exist in is <math>|X| \le C </math> where <math display="inline">X </math> remains a linear combination of variables and constant <math display="inline">C > 0 </math>.
 +
 +
In this case, we can describe an equivalent feasible solution by splitting the inequality into
 +
 +
<math>X \le C </math>
 +
 +
<math>-X \le C </math>
 +
 +
We can understand this visually as the solution <math display="inline">X </math> must lie between <math display="inline">-C
 +
</math> and <math display="inline">C </math>, as shown below:
 +
[[File:Number Line X Less Than C.png|none|thumb]]
 +
 +
 +
The last case for linear constraints is when <math>|X| \ge C </math>.
 +
 +
Visually, the solution space is the complement of the second solution above, resulting in the following representation:
 +
[[File:Number Line for X Greater Than C.png|none|thumb]]
 +
 +
 +
In expression form, the solutions can be written as:
 +
 +
<math>X \ge C </math>
 +
 +
<math>-X \ge C </math>
 +
 +
As seen visually, the feasible region has a gap and thus non-convex. The expressions also make it impossible for both to simultaneously hold true. This means that it is not possible to transform constraints in this form to linear equations. An approach to reach a solution for this particular case exists in the form of [[Mixed-Integer Linear Programming]], where only one of the equations above is “active”.
 +
 +
=== Absolute Values in Objective Functions ===
 +
WIP
  
 
==Numerical Example==
 
==Numerical Example==
Line 45: Line 91:
  
 
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>.
 
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>.
 +
 +
== References ==
 +
To be formatted:
 +
 +
# http://lpsolve.sourceforge.net/5.1/absolute.htm
 +
# https://ocw.mit.edu/courses/sloan-school-of-management/15-053-optimization-methods-in-management-science-spring-2013/tutorials/MIT15_053S13_tut04.pdf

Revision as of 05:54, 21 November 2020

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

Steward: Fengqi You

Method

Defining Absolute Values

An absolute value of a real number can be described as its distance away from zero, or the non-negative magnitude of the number. Thus,

Absolute values can exist in optimization problems in two primary instances: in constraints and in the objective function.

Absolute Values in Constraints

Within linear equations, linear constraints can exist in several forms.

The first form exists as , where is a linear combination of variables.

In this case, the only solution is if , simplifying the constraint to . Note that this solution also occurs if the constraint is in the form due to the same conclusion (only solution ).


Second form a linear constraint can exist in is where remains a linear combination of variables and constant .

In this case, we can describe an equivalent feasible solution by splitting the inequality into

We can understand this visually as the solution must lie between and , as shown below:

Number Line X Less Than C.png


The last case for linear constraints is when .

Visually, the solution space is the complement of the second solution above, resulting in the following representation:

Number Line for X Greater Than C.png


In expression form, the solutions can be written as:

As seen visually, the feasible region has a gap and thus non-convex. The expressions also make it impossible for both to simultaneously hold true. This means that it is not possible to transform constraints in this form to linear equations. An approach to reach a solution for this particular case exists in the form of Mixed-Integer Linear Programming, where only one of the equations above is “active”.

Absolute Values in Objective Functions

WIP

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 .

References

To be formatted:

  1. http://lpsolve.sourceforge.net/5.1/absolute.htm
  2. https://ocw.mit.edu/courses/sloan-school-of-management/15-053-optimization-methods-in-management-science-spring-2013/tutorials/MIT15_053S13_tut04.pdf