# A Solving Algorithm for Nonlinear Bilevel Programing Problems Based on Human Evolutionary Model
## 2 The Basic Concepts of Bilevel Programing Problem  
After the notion of multi-level programs was first proposed by [PERSON] and [PERSON] [35] in 1977, [PERSON] and [PERSON] [36], [PERSON] and [PERSON] [37; 38], [PERSON] et al. [3; 39] developed the mathematic model for multi-level programs and bilevel programs. In this paper, we consider the bilevel programming problem formulated as follows.  
\[\min_{\mathbf{x}} F(\mathbf{x},\mathbf{y})\] \[(\mathrm{BLPP}) s.t.\;\;g(\mathbf{x},\mathbf{y})\leq 0,\]  
where \(y\) is the solution of the following problem:  
\[\min_{\mathbf{y}} f(\mathbf{x},\mathbf{y})\] \[s.t.\;\;h(\mathbf{x},\mathbf{y})\leq 0,\]  
where \(\mathbf{x}\in R^{n_{x}},\mathbf{y}\in R^{n_{y}}\) are decision variables of the upper and lower program problem for the bilevel program, respectively. \(F,f:R^{n_{x}+n_{y}}\to R\) are the objective functions of the upper and lower level decision-makers, respectively. \(\mathbf{g}:R^{n_{x}+n_{y}}\to R^{n_{u}},\mathbf{h}:R^{n_{x}+n_{y}}\to R^{n_{l}}\) are the constraint functions of the upper and lower level problems, respectively.  
According to the existing researches, the basic definitions of BLPP are provided as follows [8].  
1. Constraint region of the BLPP: \(\Omega=\{(\mathbf{x},\mathbf{y})|\mathbf{g}(\mathbf{x},\mathbf{y})\leq 0, \mathbf{h}(\mathbf{x},\mathbf{y})\leq 0\}\);
2. Projection of constraint region onto the upper level decision space: \(\Omega(\mathbf{X})=\{\mathbf{x}\in R^{n_{x}}|\exists\;\mathbf{y}\in R^{n_{y}},(\mathbf{x},\mathbf{y})\in\Omega\}\); According to the decision variables given by the upper maker, i.e., \(\mathbf{x}\in\Omega(\mathbf{X})\), the constraint region of the lower level problem is formulated as follows: \(\Omega(\mathbf{X})=\{\mathbf{y}|h(\mathbf{x},\mathbf{y})\leq 0\}\)
3. For each fixed \(\mathbf{x}\in\Omega(\mathbf{X})\), the lower level decision-maker's rational reaction set: \(M(\mathbf{x})=[\mathbf{y}]\mathbf{y}\in argmin[f(\mathbf{x},\mathbf{y}), \mathbf{y}\in\Omega(\mathbf{X})]\);
4. Inducible region of BLPP: \(IR=\{(\mathbf{x},\mathbf{y})\big{|}(\mathbf{x},\mathbf{y})\in\Omega,\mathbf{y }\in M(\mathbf{x})\}\).  
The inducible region is the feasible set of the BLPP, but it is non-convex. What is more, if the upper level constraints involve the lower level decision variables, it may be non-connected [5]. In order to guarantee the existence of the optimal solutions to BLPP, some assumptions are given as follows:  
**Hypothesis 1**. \(\Omega\) _and \(\Omega(\mathbf{X})\) are a non-empty bounded compact set._  
_For each fixed \(\mathbf{x}\in\Omega(\mathbf{X})\), even though IR is non-empty, there are no optimal solution for the upper problem in case of the existence of the non-unique lower solutions. Therefore, in order to avoid this, the following further assumption is provided._  
**Hypothesis 2**. _For fixed \(\mathbf{x}\in\Omega(\mathbf{X})\), there only exists a unique solution to the lower problem denoted by \(\mathbf{y}(\mathbf{x})\)._  
_That is to say, the bilevel program problem can be denoted as: \(min[F(\mathbf{x},\mathbf{y})\big{|}(\mathbf{x},\mathbf{y})\in IR]\), where \(F(\mathbf{x},\mathbf{y})\) is the objective function value of the point \((\mathbf{x},\mathbf{y})\)._  
_Ultimately, the feasible solutions and the optimal solutions to the problem are defined as follows [8]._  
**Definition 1**. _If \((\mathbf{x},\mathbf{y})\in IR\), \((\mathbf{x},\mathbf{y})\) is the feasible solution to the problem._  
**Definition 2**. _If \((\mathbf{x}^{\star},\mathbf{y}^{\star})\in IR\) and \(F(\mathbf{x}^{\star},\mathbf{y}^{\star})\leq F(\mathbf{x},\mathbf{y})\;, \forall(\mathbf{x},\mathbf{y})\in IR\), \((\mathbf{x}^{\star},\mathbf{y}^{\star})\) is the optimal solution._