Applications of the General Nonlinear Neural Networks in Solving the Inverse Optimal Value Problem with Linear Constraints

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₁ 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ⁿ, AεR^pxn, bεR^p. Given a set C⊆Rⁿ 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:

Without losing generality, replacing f(c) = |Q(c)-z*| with f²(c) = (Q(c)-z*)², 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ⁿ 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²→R defined by and the perturbed Fish-Burmeister function is Φ: R³→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₁(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₁(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 Δ_yL(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 -∇²_yyL(y*,λ).∇_yL(y*,λ*)-H^T(y)∇_yH(y*) = 0 and -∇²_yyL(y*,λ). -∇_yL(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:

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₁,x₂,c₁,c₂) (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*₁,x*₂,c*₁,c*₂) 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₁,x₂,c₁,c₂) (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*₁,x*₂,c*₁, c*₂) 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₁,x₂,x₃,c₁,c₂,c₃) (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.