Applied Mathematics
Vol.05 No.20(2014), Article ID:51587,6 pages
10.4236/am.2014.520305

The best piecewise linearization of nonlinear functions

Department of Applied Mathematics, School of Mathematical Sciences, Ferdowsi University of Mashhad, International Campus, Mashhad, Iran

Email: *mm.mazarei@pgstp.ir   Received 11 August 2014; revised 12 September 2014; accepted 8 October 2014

ABSTRACT

In this paper, we propose a method for finding the best piecewise linearization of nonlinear functions. For this aim, we try to obtain the best approximation of a nonlinear function as a piecewise linear function. Our method is based on an optimization problem. The optimal solution of this optimization problem is the best piecewise linear approximation of nonlinear function. Finally, we examine our method to some examples.

Keywords:

Nonlinear systems, Piecewise linearization, Optimization problem, Linear programming 1. Introduction

The linearization of nonlinear systems is an efficient tool for finding approximate solutions and treatment analysis of these systems, especially in application  - . Some researchers have used some methods based on the optimization problem  . But in many applications for nonlinear and nonsmooth functions, we are faced to some problems. In fact, piecewise linearization is a more efficient tool for finding approximate solutions. Some researchers have used piecewise linearization in applications   . Also, some researchers have used piecewise linearization to solve ODEs and PDEs  .

First, we consider a nonlinear function. Let be a nonlinear function. We suppose that varies in a subset of as and this subset is compact. Our aim is to approximate the

nonlinear function by a piecewise linear function as follows: (1)

where is th subset in partitioning of as . As we know, this partitioning has bel-

low properties:

1) 2) Also, is a characteristic function on such that: (2)

Now, let . As we know is a Hilbert space of with the follow-

ing inner product:

(3)

and

(4)

Definition 1. We define be the set of all of the form (1).

Definition 2. If is a nonlinear function and, we define as follows:

(5)

Theorem. The subset is dens on.

Proof. Suppose that be a nonlinear function that.

Definition 3. We call the best piecewise linear approximation of if for any

we have

.

In fact, by above definition is optimal solution of the following optimization problem:

(6)

Obviously, because, the optimization problem has optimal solution.

2. Approach

At first, we consider a nonlinear function. Secondly, we explain this approach for a nonlinear function. Then, we explain this approach for a nonlinear function.

1) Let to consider the bellow optimization problem

where, is a nonlinear function and. As we know can be replaced by.

Now, we decompose interval to subintervals (See Figure 1).

Since, , we have

Figure 1. Partitioning to subintervals.

(7)

Our objective function is a functional. Now, we reduce this functional to a summation as follows:

(8)

So, the optimization problem (8) is as follows:

(9)

But, the optimization problem (9) is a nonlinear programming problem. We reduce this problem to a linear programming problem by relation such that. So, our optimization problem will be as follows:

(10)

2) Second, we consider a nonlinear function. So, we have the optimization problem as follows:

(11)

where is the ith partition in partitioning of and. Also we can replace by. As, we explained in 1) the optimization problem (11) will be reduced to a linear programming problem as follows:

(12)

where and are numbers of subintervals on axises and, respectively (See Figure 2).

3) Third, we consider a nonlinear function. So, we have the optimization problem as fol-

Figure 2. Partitioning to subintervals.

lows:

(13)

As, we explained in sections 1) and 2) this optimization problem will be reduced to a linear programming problem as follows:

(14)

where are numbers of subintervals on axises respectively.

3. Examples

In this section, we show efficiency of our approach by several examples. Also, we define the root mean squared error by follow relation:

(15)

Example 1. We consider nonlinear nonsmooth function on interval.

As we explained in section 1), the linear programming corresponding to this function is as follows:

(16)

The optimal solution of linear programming problem (16) is the best piecewise linearization of the function on. We let and, respectively (See Figure 3, Figure 4). In this example, we have for. As we can see the approximate piecewise linearization of this function is high accurate.

Example 2. We consider nonlinear function on interval. We have obtained the piecewise approximation of this nonlinear function using two other methods. These methods are Splines Piecewise Approximation (SPA) and Mixture of Polynomials (MOP). Then we have compared these with our method.

As we explained in section 1), the linear programming corresponding to this function is as follows:

(17)

Figure 3. The figure of piecewise function approximation of nonlinear function for.

Figure 4. The figure of piecewise function approximation of nonlinear function for.

The optimal solution of linear programming problem (17) is the best piecewise linearization of the function on. We let (See Figure 5). In this example, we have while for Splines Piecewise Approximation and. As we can see the approxi- mate piecewise linearization of this function using our method is more accurate in compared with two other methods.

Example 3. We consider nonlinear non smooth function on.

As we explained in section 2), the linear programming corresponding to this function is as follows:

(18)

The optimal solution of linear programming problem (18) is the best piecewise linearization of the function

on. We let and (See Figure 6, Figure 7). In this example,

Figure 5. The figure of piecewise function approximation of nonlinear function for.

Figure 6. The figure of piecewise function approximation of nonlinear function for.

Figure 7. The figure of piecewise function approximation of nonlinear function for.

we have and, respectively. As we can see the approximate piecewise linearization of this function is high accurate.

4. Conclusion

Our method for piecewise linearization of nonlinear functions is extensible to by the function. As we can see, this approximation is high accurate in comparison of other methods and this method is very simple for achieving this optimal solution. Also, this piecewise linearization form of nonlinear functions is useful for many applications, especially for nonlinear nonsmooth optimization, nonlinear differential equations, fuzzy ODE and PDE differential equations and so on.

References

1. Aranda-Bricaire, E., Kotta, U. and Moog, C. (1996) Linearization of Discrete-Time Systems. SIAM Journal on Control and Optimization, 34, 1999-2023. http://dx.doi.org/10.1137/S0363012994267315
2. Jouan, P. (2003) Immersion of Nonlinear Systems into Linear Systems Modulo Output Injection. SIAM Journal on Control and Optimization, 41, 1756-1778. http://dx.doi.org/10.1137/S0363012901391706
3. Sladeček, L. (2003) Exact Linearization of Stochastic Dynamical Systems by State Space Coordinate Transformation and Feedback Ig-Linearization. Applied Mathematics E-Notes, 3, 99-106.
4. Vahidian Kamyad, A., Hashemi Mehne, H. and Hashemi Borzabadi, A. (2005) The Best Linear Approximation for Nonlinear Systems. Applied Mathematics and Computation, 167, 1041-1061. http://dx.doi.org/10.1016/j.amc.2004.08.002
5. Herdem, S. and Koksal, M. (2002) A Fast Algorithm to Compute Steady-State Solution of Nonlinear Circuits by Piecewise Linearization. Computers and Electrical Engineering, 28, 91-101.
6. Gunnerud, V., Foss, B.A., Mckinnon, K.I.M. and Nygreen, B. (2012) Oil Production Optimization Solved by Piecewise Linearization in a Branch and Price Framework. Computers and Operations Research, 39, 2469-2477. http://dx.doi.org/10.1016/j.cor.2011.12.013
7. Ramos, J.I. and Garcia-Lopez, C.M. (1997) Nonstandard Finite Difference Equations for ODEs and 1-D PDEs Based on Piecewise Linearization. Applied Mathematics and Computations, 86, 11-36.

NOTES

*Corresponding author.