**ABSTRACT**

In this research, the aim of the study is to present a method to solve a class of inverse optimal value problem with linear constraints by using a nonlinear gradient neural network. Firstly, based on optimal theory, solving the inverse optimal value problem is changed as solving a nonlinear bilevel program problem equivalently. Then a nonlinear gradient neural network model for solving the nonlinear bilevel programming is presented. By employing Lyapunov function approach, the proposed neural network is analyzed to be globally Lyapunov stable and capable of generating approximal optimal solution to the nonlinear bilevel programming problem. Finally, numerical examples are provided to verify the feasibility and the efficiency of the proposed method in this study.

PDF Abstract XML References Citation

**Received:**September 01, 2011;

**Accepted:**December 28, 2011;

**Published:**February 28, 2012

####
**How to cite this article**

*Information Technology Journal, 11: 713-718.*

**DOI:**10.3923/itj.2012.713.718

**URL:**https://scialert.net/abstract/?doi=itj.2012.713.718

**INTRODUCTION**

In the recent years, the inverse optimal value problems have received extensive attention from a lot of scholars (Tarantola, 1987; Burton and Toint, 1994; Zhang * et al*., 1995, 1996; Sokkalingam* et al*., 1999; Zhang and Liu, 1996, 1999; Yang* et al*., 1997; Zhang and Cai, 1998; Ahuja and Orlin, 2000, 2001, 2002; Heuberger, 2004; Ahmed and Guan, 2005; Lv *et al*., 2008a; 2010a). Let min p (x, c), xεX, be an optimization problem where, X is the feasible region and c is an parameter vector representing costs, capacities, weights, returns, etc. The general optimization problem (also called forward optimization) is to find an x*εX such that the objective p (x, c) is optimal at x*. The inverse optimization problem can be described as follows. Assume that it has been known that an and a vector c which is an estimate to the parameter values of the problem. We are interested in finding out whether there exist acceptable values of the parameter vector c, denoted by which make optimal to problem min . If the answer is positive, find the vector that differs from the vector c as little as possible.

Burton and Toint (1994) first investigated an inverse shortest paths problem. Since, then, many different inverse optimization problems (discrete or continuous) have been considered. Zhang *et al*. (1996) addressed inverse shortest paths problems with l_{1} norm for p paths using a column generation method. Zhang * et al*. (1996) and Sokkalingam *et al*. (1999) worked on inverse minimum spanning tree problems.

Zhang and Liu (1996, 1999) studied inverse linear programming problems. Worked on inverse maximum flow and minimum cut problems done by Yang *et al*. (1997) Zhang and Cai (1998). Ahuja and Orlin (2000, 2001, 2002) also developed a general approach to inverse linear programming problems and discussed applications to some special cases. Heuberger (2004) gave a survey on inverse combinatorial optimization problems, methods and results. Ahmed and Guan (2005) proved that the inverse optimal value problem is NP-hard and on the basis of some assumptions, got the optimal solutions of the inverse optimal value problem by solving a series of linear and bilinear programming problems. By using the penalty method, Lv *et al*. (2008b, 2010a) gave an existence theorem of solutions of the inverse optimal value problem and propose some numerical algorithms.

It should be noted that in the existing literature, almost all results is to focus mainly on the study of the classical numerical algorithm for the inverse optimal value problem. However, in lots of engineering applications many optimization problems need to be solved in real time. It is obvious that the classical methods cannot render real-time solutions to these optimization problems, especially large-scale problems. Compared with classical optimization approaches, the appearance of neural computing approach satisfies the demand of real-time optimal solutions. The main advantage of **neural network** approach to optimization is that the nature of the dynamic solution procedure is inherently parallel and distributed. Therefore, the **neural network** approach can solve optimization problems in running time at the orders of magnitude much faster than the most popular optimization algorithms executed on general purpose digital computers. Recently, there have been some works to focus on solving varied optimization problems in engineering by using neural networks, the reader may consult (Lv *et al*., 2010b; Gao, 2004; Xia and Wang, 1998; Chen *et al*., 2002; Wu *et al*., 2010; Al-Bastaki, 2006; Dempe, 2002; Lijia *et al*., 2011; Yedjour *et al*., 2011; Salazar *et al*., 2010; Arafa *et al*., 2011; Niknafs and Parsa, 2011; Lotfi and Benyettou, 2011; Liu *et al*., 2012) and the references therein. To the best of the authors’ knowledge, solving the inverse optimal value problems by **neural networks** has not been investigated to date which inspirits us to carry out the present study.

Motivated by the above discussion, in the present paper, a new nonlinear **neural networks** for solving the inverse optimal value problem with linear constraints is presented. Firstly, the inverse value problem with linear constraints is transformed into the corresponding nonlinear bilevel programming problem; Secondly, a nonlinear **neural network** model for solving the bilevel programming is developed. The equilibrium point of the proposed **neural network** is equivalent to the solution of the inverse optimal value problem. Thirdly, a new sufficient condition to ensure the global stability for the proposed **neural network** is given, by the use of the Lyapunov function method. Finally, numerical examples are provided to show the effectiveness of the proposed approach.

**PROBLEM STATEMENT AND PRELIMINARIES**

Consider the following linear program problem:

(1) |

where, c, xεR^{n}, AεR^{pxn}, bεR^{p}. Given a set C⊆R^{n} and a real number z*. Arguing as in Tarantola (1987), the inverse optimal value problem corresponding to Eq. 1 is to find cεC such that the optimal objective value Q(c) of the linear programming Eq. 1 is close to z*. It is obvious that the inverse optimal value problem can be written as:

(2) |

where, f(c) = |Q(c)-z*|, |. | denotes the Euclidean norm of R.

Combining Eq. 1 and 2, the inverse optimal value problem corresponding the linear program can be described as follows:

(3) |

The model Eq. 3 is a class of the bilever program problem with the optimal value of the lower level problem feeding back to the upper level. (UP) is called the upper level problem and (LP) is called the lower level problem.

Throughout, the rest of this study, the following assumptions are made:

• | H1: The set of cost vectors C is nonempty, C = {c: Dc = d}, D⊆R^{mxn}, dεR^{m} |

• | H2: The feasible region {x: Ax≤b, x≥0} is nonempty bound |

Without losing generality, replacing f(c) = |Q(c)-z*| with f^{2}(c) = (Q(c)-z*)^{2}, then the bilever program problem Eq. 3 can be rewritten as:

(4) |

For fixed cεC, by using the Kuhn-Tucker optimality conditions to replace (LP), the problem Eq. 4 can be changed equivalently as the following program problem:

(5) |

where, uεR^{p}, vεR^{n} are row vectors. It is obvious that the problem (Eq. 5) is a convex program problem.

From the above discussion, it is easy to see that the inverse optimal value problem corresponding to the linear program (Eq. 1) is equivalent to a special class of the convex program (Eq. 5). Hence, solving the inverse optimal value problem corresponding to the linear program (Eq. 1) can be changed as solving the convex program (Eq. 5).

In order to obtain the main results of this study, the following definitions and lemmas are introduced.

**Definition 1:** The Fish-Burmeiste function is Φ: R^{2}→R defined by and the perturbed Fish-Burmeister function is Φ: R^{3}→R defined by .

The Fish-Burmeister function Φ(a,b) has the property: Φ(a,b) = ⇔ a≥0, b≥0, ab = 0. Its perturbed variant satisfies Φ(a,b,ε) if and only if:

for ε≥0. It is easy to see that Φ(a,b) is non-differentiable at a = b = 0. However, Φ(a, b, ε) is smooth with respect to a, b for ε>0.

Let . It is obvious that Φ’(a, b, ε) has the same property with the function Φ(a, b, ε). By using Φ(a, b, ε), the problem (Eq. 5) can be approximated by:

(6) |

where, h(x) = (h_{1}(x),…, h_{p}(x))^{T} = b-Ax.

To simply the discussion, set:

then the program problem (Eq. 6) can be written as:

(7) |

**Definition 2:** Let {y^{ε}} be a feasible point of the program problem (Eq. 7). y is said to a regular point if the gradients ∇H_{1}(y),…, ∇H_{p+2n+m}(y) are linearly independent.

By using theorem in Dempe (2002) the following lemma can be obtained.

**Lemma 1:** Let {y^{ε}} be a sequence of solution of the program problem (Eq. 7). Suppose that the sequence {y^{ε}} converges to some for ε→0^{+}. If is a regular point, then is a Bouligand stationary solution for problem (Eq. 4).

**NEURAL NETWORK MODEL FOR THE PROGRAM PROBLEM**

**Neural network model: **Define the Lagrange function of the program problem (Eq. 7) as L (y, λ) = F (y)+λH (y), where, λεR^{p+2n+m} is referred as the Lagrange multiplier. Based on the well-known Saddle point theorem, we have.

**Theorem 1:** If there exists (y*, λ*), such that Δ_{y}L(y*,λ) = 0, H(y*) hold. Then, y* is an optimal solution of the program problem (Eq. 7).

By Theorem 1, the energy function of the program problem (Eq. 7) can be constructed as:

in the following, a **neural network** model is proposed which is said to be the gradient network, for solving the problem (7), whose dynamical equation is described as follows:

(8) |

That is:

According to Theorem 1, it is easy to obtain.

**Theorem 2:** (y*,λ*) is an equilibrium point of the **neural network** (Eq. 8) if and only if y* is an optimal solution of the program problem (Eq. 7).

**Proof:** Firstly, if (y*,λ*) is an equilibrium point of the **neural network** (Eq. 8), that means:

By theorem 1, we have that y* is an optimal solution of program problem (Eq. 7).

Conversely, if y* is an optimal solution of program problem (Eq. 7), from K-T condition we have that there exist λ*, such that ∇y_{L}(y*,λ*) = 0 and ∇y_{λ}(y*,λ*) = 0. i.e., ∇y_{L}(y*,λ*) = 0 and H(y*) = 0. Then, the equations -∇^{2}_{yy}L(y*,λ).∇_{y}L(y*,λ*)-H^{T}(y)∇_{y}H(y*) = 0 and -∇^{2}_{yy}L(y*,λ). -∇_{y}L(y*,λ) = 0 are existence. This means (y*,λ*) is an equilibrium point of the neural network (Eq. 8).

**Stability analysis: **Since, the program problem (Eq. 7) is a class of convex programs, there exists an unique optimal solution. Hence, by Theorem 2, the **neural network** (Eq. 8) has an equilibrium point.

**Theorem 3:** If (y*,λ*) is the equilibrium point of the **neural network** (Eq. 8), then (y*,λ*) is globally asymptotically stable.

**Proof:** Let η = (y,λ). Consider Lyapunov function:

V(η) = E(η)-E(η*) = E(η) |

It is obvious that V(η)>0, ∀η≠η* and V(η*) = 0. Calculate the derivative of V(η) along the solution η(t) of the **neural network** (Eq. 8), we have:

Based on the Lyapunov stability theory, we can obtain that η* is globally asymptotically stable.

**ILLUSTRATIVE EXAMPLES**

Here, three examples will be given to illustrate the effectiveness of the proposed approach for solving the inverse optimal value problem.

**Example 1:** Consider the following inverse optimal value problem:

(9) |

Let z* = 14. The problem (Eq. 6) corresponding to (Eq. 9) is:

(10) |

Fig. 1: | The transient behavior of the variables in Example 1 |

By using the classical fourth-order Runge-Kutta method in MATLAB to solving the **neural network** (Eq. 8), we can obtain the transient behavior of the state trajectories (x_{1},x_{2},c_{1},c_{2}) (Fig. 1). Take the initial values y = (3.5,1,3,2,0,0,0,0,0) and λ = (0,0,0,0,0,0,0,0). Let ε be 0.01, 0.001 and 0.00001, respectively, we can get the different optimal solutions of the problem (10) (Table 1). It is easy to see that optimal solution (x*_{1},x*_{2},c*_{1},c*_{2}) of the problem (10) converges to the solution (4,2,2,3) of the inverse optimal value problem (9).

**Example 2:** Consider the following inverse optimal value problem:

(11) |

Table 1: | The comparison of the optimal solution of example 1 and 2 |

Different optimal solution (x*_{1}, x*_{2}, c*_{1}, c*_{2}) corresponding to different ε |

Fig. 2: | The transient behavior of the variables in Example 2 |

Fig. 3: | The transient behavior of the variables in Example 3 |

Using the same method of example 1, we can obtain the transient behavior of the state trajectories (x_{1},x_{2},c_{1},c_{2}) (Fig. 2). Take the initial values y = (1,2,2,1,0,0,0,0) and λ = (0,0,0,0,0,0,0). Let ε be 0.01, 0.001 and 0.0001, respectively, we can get the different optimal solutions of the problem (11) (Table 1). It is easy to see that optimal solution (x*_{1},x*_{2},c*_{1}, c*_{2}) of the problem (11) converges to the solution (1.5,2,2,1).

**Example 3:** Consider the following inverse optimal value problem:

(12) |

Table 2: | The comparison of the optimal solution of example 3 |

Different optimal solution (x*_{1}, x*_{2}, x*_{3}, c*_{1}, c*_{2}, c*_{3}) corresponding to different ε |

Take the initial values y = (2,0,3,3,3,4,0,0,0,0,0,0) and λ = (0,0,0,0,0,0,0,0,0,0). Let ε be 0.01, 0.001 and 0.001, respectively, we can get the different optimal solutions of the problem (12) (Table 2). The transient behavior of the state trajectories (x_{1},x_{2},x_{3},c_{1},c_{2},c_{3}) (Fig. 3).

Table 2 the comparison of the optimal solution of example 3.

From the above examples we can find that the computed results converge to the different optimal solution with the decreasing of ε. It shows that the **neural network** approach is feasible to the inverse optimal value problem.

**CONCLUSION**

In this study, a **neural network** model has been developed for solving the inverse optimal value problem with linear constraints. Based on Lyapunov stability theory, the proposed **neural network** has been proved to be globally asymptotically stable and capable of generating approximal optimal solution of the inverse optimal value problem. Three examples have been given to show the effectiveness of the proposed approach. The results obtained in this paper are highly valuable in both theory and practice for solving the inverse optimal value problem.

**ACKNOWLEDGMENT**

The authors are extremely grateful to the Editor and the Reviewers for their valuable comments and suggestions which help to enrich the content and improve the presentationof this study. This study was supported by the Natural Science Foundation of Hebei Province of China (A2011203103) and the Hebei Province Education Foundation of China (2009157).

####
**REFERENCES**

- Burton, D. and P.L. Toint, 1994. On the use of an inverse shortest paths algorithm for recovering correlated costs. Math. Program., 63: 1-22.

CrossRefDirect Link - Zhang, J., Z. Ma and C. Yang, 1995. A column generation method for inverse shortest paths problems. Math. Meth. Operat. Res., 41: 347-358.

CrossRefDirect Link - Zhang, J., Z. Liu and Z. Ma, 1996. On the inverse problem of minimum spanning tree with partition constraints. Math. Meth. Operat. Res., 44: 171-188.

CrossRefDirect Link - Sokkalingam, P.T., R.K. Ahuja and J.B. Orlin, 1999. Solving inverse spanning tree problems through network ﬂow techniques. Operat. Res., 47: 291-298.

CrossRefDirect Link - Zhang, J. and Z. Liu, 1996. Calculating some inverse linear programming problems. J. Computat. Applied Math., 72: 261-273.

CrossRefDirect Link - Zhang, J. and Z. Liu, 1999. A further study on inverse linear programming problems. J. Comput. Applied Math., 106: 345-359.

CrossRefDirect Link - Yang, C., J. Zhang and Z. Ma, 1997. Inverse maximum ﬂow and minimum cut problems. Optimization, 40: 147-170.

CrossRefDirect Link - Zhang, J. and M.C. Cai, 1998. Inverse problem of minimum cuts. Math. Meth. Operat. Res., 47: 51-58.

CrossRefDirect Link - Ahuja, R.K. and J.B. Orlin, 2000. A faster algorithm for the inverse spanning tree problem. J. Algorithms, 34: 177-193.

Direct Link - Ahuja, R.K. and J.B. Orlin, 2002. Combinatorial algorithms for inverse network ﬂow problems. Networks, 40: 181-187.

CrossRefDirect Link - Heuberger, C., 2004. Inverse combinatorial optimization: A survey on problems, methods and results. J. Comb. Optimizat., 8: 329-361.

CrossRefDirect Link - Ahmed, S. and Y. Guan, 2005. The inverse optimal value problem. Math. Program., 102: 91-110.

CrossRefDirect Link - Lv, Y., T. Hu and Z. Wan, 2008. A penalty function method for solving inverse optimal value problem. J. Comput. Applied Math., 220: 175-180.

CrossRefDirect Link - Lv, Y., Z. Chen and Z. Wan, 2010. A penalty function method based on bilevel programming for solving inverse optimal value problems. Applied Math. Lett., 23: 170-175.

CrossRefDirect Link - Lv, Y., Z. Chen and Z. Wan, 2010. A neural network for solving a convex quadratic bilevel programming problem. J. Comput. Applied Mathe., 234: 505-511.

CrossRef - Lv, Y., T. Hu, G. Wang and Z. Wan, 2008. A neural network approach for solving nonlinear bilevel programming problem. Comput Math. Applic., 55: 2823-2829.

CrossRefDirect Link - Gao, X.B., 2004. A novel neural network for nonlinear convex programming. IEEE Trans. Neural Networks, 15: 613-621.

CrossRefDirect Link - Xia, Y. and J. Wang, 1998. A general methodology for designing globally convergent optimizatin neural networks. IEEE Trans. Neural Networks, 9: 1331-1343.

CrossRefDirect Link - Chen, K.Z., Y. Leung, K.S. Leung and X.B. Gao, 2002. A neural network for solving nonlinear programming problems. Neural Comput. Applic., 11: 103-111.

CrossRefDirect Link - Wu, H., L. He, L. Qin, T. Feng and R. Shi, 2010. Solving interval quadratic program with box set constraints in engineering by a projection neural network. Inform. Technol. J., 9: 1615-1621.

CrossRefDirect Link - Al-Bastaki, Y.A.L., 2006. GIS image compression and restoration: A neural network approach. Inform. Technol. J., 5: 88-93.

CrossRefDirect Link - Lijia, C., Z. Shengxiu, L. Xiaofeng, L. Yinan and L. Ying, 2011. Nonlinear adaptive block backstepping control using command filter and neural networks approximation. Infor. Technol. J., 10: 2284-2291.

CrossRefDirect Link - Yedjour, H., B. Meftah, D. Yedjour and A. Benyettou, 2011. Combining spiking neural network with hausdorff distance matching for object tracking. Asian J. Applied Sci., 4: 63-71.

CrossRefDirect Link - Salazar, R., U. Schmidt, C. Huber, A. Rojano and I. Lopez, 2010. Neural networks models for temperature and CO
_{2}control. Int. J. Agric. Res., 5: 191-200.

CrossRef - Arafa, M., M. Alqedra and H. An-Najjar, 2011. Neural network models for predicting shear strength of reinforced normal and high-strength concrete deep beams. J. Applied Sci., 11: 266-274.

CrossRef - Niknafs, A. and S. Parsa, 2011. A neural network approach for updating ranked association rules, based on data envelopment analysis. J. Artif. Intell., 4: 279-287.

CrossRefDirect Link - Lotfi, A. and A. Benyettou, 2011. Using probabilistic neural networks for handwritten digit recognition. J. Artif. Intell., 4: 288-294.

CrossRefDirect Link - Liu, G., S.X. Yang and Y. Chai, 2012. Less conservative delay-dependent asymptotic stability criteria for stochastic neural networks of neutral-type with distributed delay. Inform. Technol. J., 11: 233-240.

CrossRefDirect Link