Piecewise Continuous Linear Functions Regarding Insurance Rates Data

Piecewise Linear Approximation Author: John Marsiglio ChE 345 Spring 2015 Steward: Dajun Yue, Fengqi You

1 Piecewise Linear Approximation
- 1.1 Limitation
2 Formulations
- 2.1 SOS1
- 2.2 SOS2
  - 2.2.1 Example of Using Special Ordered Sets: Determining the Cost of Constructing a New Building
- 2.3 Discrete Case
3 Algorithms Based on Piecewise Linear Approximations
- 3.1 Branch and Refine
- 3.2 Single Pass Piecewise Linear Approximation Algorithm
- 3.3 Piecewise Linear Approximations for Accuracy
- 3.4 Approximating Planar Curves
4 Example Applications
- 4.1 Supply Chain Models
- 4.2 Network Flow Problems
- 4.3 Network Loading Problems
- 4.4 Facility Location Problem
- 4.5 Appointment Scheduling
5 MATLAB Functions
- 5.1 FPLOT FUNCTION
6 Conclusion
7 References

Piecewise Linear Approximation

Approximating a function to a simpler one is an indispensable tool. A piecewise approximation plays many important roles in many area of mathematics and engineering. A piecewise linear approximation is one method of constructing a function $g{(x)}$ that fits a nonlinear objective function $f{(x)}$ by adding extra binary variables, continuous variables, and constraints to reformulate the original problem. The specific goal is to approximate a single valued function of one variable in terms of a sequence of linear segments. For the function $f(x)$ , defined on the interval [a,b], a piecewise linear approximation will approximate a function $g(x)$ over the same interval. $g(x)$ is to be made up of a sequence of linear segments. Then g(x) is in the form $g(x)=c+dx$ for every x in [a,b].[11] A commonly known example of a piecewise function is $f(x) = |x|$ where $|x| = \begin{cases} x, & \mbox{if } x \ge 0 \\ -x, & \mbox{if } x < 0. \end{cases}$

The above piecewise function itself could be used as a piecewise linear approximation of the nonlinear function $g{(x)} = x^2$ as shown below.

The purpose of doing a piecewise linear approximation is that the new linearity will allow the previously nonlinear problem to be solved by linear programming methods, which are much easier to employ than their nonlinear counterparts. [1]

Limitation

Creating a piecewise linear approximation creates its own optimization problem. Obviously the best piecewise linear approximation would use an infinite number of linear pieces to fit the curve. This however becomes simply the original nonlinear problem. So the new optimization problem becomes generating the most accurate approximation with the fewest number of linear segments.

Optimal search algorithm as presented by A. Imamoto and B. Tang (2008) [10]

There are several commercial solvers in GAMS such as CONOPT and MINOS that are able to solve this problem.[2] Recently a methodology to solve this optimization problem has been proposed for both convex and concave objective functions. The objective of this methodology, shown here, is to minimize the maximum absolute error over the range. This is also known as the minimax solution.

An example optimal piecewise linear approximation to a polynomial curve. This was done by sampling the curve at three intermediate points and constructing linear interpolations between them. [3]

Formulations

SOS1

SOS1, or a special ordered set of type 1 is a set of variables where no more than one set member may be non-zero, and positive in the feasible solution. All SOS1's are mutually exclusive arranged in order of increasing size. For example, one value would have to be somehow chosen from the set of increasing values. [16]

SOS2

SOS2, or special ordered sets of type 2, are very similar to SOS1 except instead of one variable in the set of increasing order being non-zero and positive, two can be. The constraint here is that the two non-zero and positive variables must be consecutive within the set order.[16]

Example of Using Special Ordered Sets: Determining the Cost of Constructing a New Building

A new building is to be constructed. It may be 1, 2, 3, 4, or 5 stories tall. The cost of constructing these buildings are x₁, x₂, x₃, x₄, and x₅ respectively. These variables may be written with a constraint in a function that denotes the available number of stories that could be built, or z = x₁ + x₂ + x₃ + x₄ + x₅. An assumption that can be made is that there is a fractional solution of x₁ = 0.1 and x₅ = 0.9, so then 0.1*1 + 0.9*5 = 4.6 is the weighted average of stories that will be built. To solve the set must be split between the two variables on either side of the weighted average, or in this case x₁, x₂, x₃, and x₄ are placed in one set and x₅ is in another. Now the problem must be branched such that in one branch x₁, x₂, x₃, and x₄ are set to 0 and x₅ is set to one, and in the other branch x₅ is set to 0, which results in an infeasible solution. So for the building to be built the added constraint x₁ + x₂ + x₃ + x₄ + x₅ = 1 is required. This new constraint is a special ordered set of type 1.

Discrete Case

For a discrete set of data the equation can be used: [9]

$p_{lk}(x) = \frac{x-x_{k+1}}{x_k-x_{k+1}}f(x) + \frac{x-x_{k}}{x_{k+1}-x_{k}}f(x)$

where $x_k$ and $x_{k+1}$ are consecutive data points

Consider the following set of data points along the cosine function:

k	(x_k , f(x)_k)
$0$	$(0,1)$
$1$	$(\pi/3, 0.5)$
$2$	$(2\pi/3,-0.5)$
$3$	$(\pi,-1)$

Using the above formula, the piecewise approximation of the data is found to be

$f(x) = \begin{cases} -0.477x+1 & \ x \in\ [0, \pi/3] \\ -0.955x+0.5 & \ x \in\ [\pi/3,2\pi/3] \\ -0.477x+1.5 & \ x \in\ [2\pi/3,1] \\ \end{cases}$ .

Algorithms Based on Piecewise Linear Approximations

There are a number of useful algorithms that use piecewise linear approximations to solve complicated problems for optimal solutions.

Branch and Refine

The branch and refine algorithm is based on the piecewise linear approximation. It is an efficient way to solve a problem for the global optimum. It uses piecewise linear approximations to provide global lower bounds for the MINLP. From there the feasible solutions provide the upper bounds of the MINLP. As the number of iterations increase, the number of pieces will increase, moving forward to the global solution.[12]

Single Pass Piecewise Linear Approximation Algorithm

The algorithm developed by F.Gritzali and G. Papakonstantinou finds different portions of a formulated waveform function and identifies some of the points as peaks. The points identified as peaks are where the derivative of the waveform is equal to zero. The algorithm works by starting at a peak point and developing the piecewise linear approximation to the waveform such that all points of the waveform has the same difference from the piecewise approximation, and peak points are represented in the piecewise curve. This sort of algorithm is useful in real time applications where peak points are important such as an EKG readout. [13]

Piecewise Linear Approximations for Accuracy

Hiroaki Nishikawa devised an algorithm to find local and global asymptotic L₂ error estimates to piecewise linear continuous approximations such that the desired error to the curve could be achieved. This was done through a local error analysis that then used leading terms to approximate. This is followed by numerical tests to check the error is around L₂. [14]

Approximating Planar Curves

The piecewise linear approximation is not just limited to 2-D cases, but can be used to fit multidimensional curves and planes. Williams developed an early efficient algorithm to fit planar curves by economizing the number of line vectors necessary. The approximation methods he used fit straight line sequences to the plane are based on geometrical review of the plane's curvature followed by "numerically stable and geometrically concise" computations. [15]

Example Applications

Supply Chain Models

Most supply chain models are simplified by assuming a constant average price of all costs and revenues in the system. This model however, ignores the real world fact that there are often discounts for buying large quantities of items. Using the real world non constant pricing, the concave functions in the resulting model can simply be estimated by piecewise linearization techniques and then convert the to a mixed 0-1 programming problem. From there finding the global minimum or maximum is easy. [4]

Network Flow Problems

A good example of a network flow problem is to minimize the costs in a routing problem consisting of many goods going between different locations. To do so the economies of scale in the arc flow costs are approximated by piecewise linear functions. Doing so enables the global minimum to be found in with a composite algorithm that generates good lower bounds and heuristic solutions. [5]

Network Loading Problems

Piecewise linear approximations are also important in solving common network loading problems. For example when the posynomial geometric programming problem is considered first the posynomial terms must be made convex. Once this is the case, piecewise linear functions can then be used to approximate the decision variables that were generated. [6]

Facility Location Problem

Commonly in the standard facility location problem there are "staircase" costs. This means that costs are fixed at multiple different levels. This makes the problem a mixed integer problem, which can be difficult to solve. Employing a piecewise linear approximation, by introducing a few integer variables, the problem may be solved in less time. [7]

Appointment Scheduling

Appointment scheduling can also be optimized by employing piecewise linear approximations. When considering the problem of optimizing a processor so that the time spent waiting is minimized, piecewise linear approximations can be used for the polynomial cost functions such that the problem can be easier solved. [8]

MATLAB Functions

FPLOT FUNCTION

Mathworks MATLAB has the built-in function FPLOT that is capable of selecting the input points that will minimize error between piecewise linear approximation of a continuous function. FPLOT(FUN,LIMS) uses the specifications set by the string, or .M file, FUN and the x-axis limits LIMS = [XMIN XMAX], or the x and y-axis limits LIMS = [XMIN XMAX YMIN YMAX]. An example of a FUN string, or FUN(x) would be cos(x), such that a row vector is returned for each element of the input vector x. For example if FUN(x) is defined as $f(x) g(x) h(x)$ , the input $[x y]$ should return This code produces the following table:

FPLOT also allows the minimum error tolerance, the minimum number of points, and with some parameters to be included in the plot.

Conclusion

Piecewise linear approximations are clearly indispensable to the field of optimization. Their simplicity and nontrivial status make them an indispensable tool for any mathematician or engineering student.

References

[1] Applied Mathematical Programming by Bradley, Hax, and Magnanti (Addison-Wesley, 1977) http://web.mit.edu/15.053/www/AppliedMathematicalProgramming.pdf

[2] Ahmadi, H., Martí, J. R., & Moshref, A. (2013, July). Piecewise linear approximation of generators cost functions using max-affine functions. InPower and Energy Society General Meeting (PES), 2013 IEEE (pp. 1-5). IEEE. http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6672353&tag=1

[3] Robert, R. V. (1996). Linear programming: Foundations and extensions. http://link.springer.com/book/10.1007/978-0-387-74388-2

[4] Tsai, J. F. (2007). An optimization approach for supply chain management models with quantity discount policy. European Journal of Operational Research, 177(2), 982-994. http://www.sciencedirect.com/science/article/pii/S037722170600035X

[5] Balakrishnan, A. and Graves, S. C. (1989), A composite algorithm for a concave-cost network flow problem. Networks, 19: 175–202. doi: 10.1002/net.3230190202 http://onlinelibrary.wiley.com/doi/10.1002/net.3230190202/abstract;jsessionid=65363B425D9FCFD678883702675D5B06.f03t01

[6] Tsai, J. F., & Lin, M. H. (2011). An efficient global approach for posynomial geometric programming problems. INFORMS Journal on Computing, 23(3), 483-492. http://pubsonline.informs.org/doi/abs/10.1287/ijoc.1100.0403

[7] Holmberg, K. (1994). Solving the staircase cost facility location problem with decomposition and piecewise linearization. European Journal of Operational Research, 75(1), 41-61. http://www.sciencedirect.com/science/article/pii/0377221794901848

[8] Ho-Yin Mak, Ying Rong, Jiawei Zhang. (2014) Appointment Scheduling with Limited Distributional Information. Management Science 61:2, 316-334. http://pubsonline.informs.org/doi/abs/10.1287/mnsc.2013.1881

[9] Theodore, J. (1969). RIVLIN: An Introduction to the Approximation of Functions.

[10] Imamoto, A., & Tang, B. (2008, October). Optimal piecewise linear approximation of convex functions. In Proceedings of the world congress on engineering and computer science (pp. 1191-1194). Citeseer.

[11] Cameron, S. H. (1966). Piece-wise linear approximations (No. CSTN-106). IIT RESEARCH INST CHICAGO IL COMPUTER SCIENCES DIV.

[12]Gong, J., & You, F. (2014). Global optimization for sustainable design and synthesis of algae processing network for CO2 mitigation and biofuel production using life cycle optimization. AIChE Journal, 60(9), 3195-3210. http://onlinelibrary.wiley.com/doi/10.1002/aic.14504/abstract

[13] Gritzali, F., & Papakonstantinou, G. (1983). A fast piecewise linear approximation algorithm. Signal Processing, 5(3), 221-227. http://ac.els-cdn.com/0165168483900701/1-s2.0-0165168483900701-main.pdf?_tid=9a28a0aa-0cb3-11e5-84fb-00000aacb361&acdnat=1433640303_d972a16da509b4da8be1fe9b9aa08666

[14] Nishikawa, H. (1998). Accurate Piecewise Linear Continuous Approximations to One-Dimensional Curves: Error Estimates and Algorithms.

[15] Williams, C. M. (1978). An efficient algorithm for the piecewise linear approximation of planar curves. Computer Graphics and Image Processing, 8(2), 286-293.

[16] J.A. Tomlin, "Special Ordered Sets and an Application to Gas Supply Operations Planning", Ketron Management Science, Inc., Mountain View, CA 94040-1266, USA

nivisonplebadve.blogspot.com

Source: https://optimization.mccormick.northwestern.edu/index.php/Piecewise_linear_approximation