Two-level value function approach to non-smooth optimistic and pessimistic bilevel programs

ABSTRACT

The authors' paper in Dempe et al. [Necessary optimality conditions in pessimistic bilevel programming. Optimization. 2014;63:505–533], was the first one to provide detailed optimality conditions for pessimistic bilevel optimization. The results there were based on the concept of the two-level optimal value function introduced and analysed in Dempe et al. [Sensitivity analysis for two-level value functions with applications to bilevel programming. SIAM J. Optim. 22 (2012), 1309–1343], for the case of optimistic bilevel programs. One of the basic assumptions in both of these papers is that the functions involved in the problems are at least continuously differentiable. Motivated by the fact that many real-world applications of optimization involve functions that are non-differentiable at some points of their domain, the main goal of the current paper is to extend the two-level value function approach by deriving new necessary optimality conditions for both optimistic and pessimistic versions in bilevel programming with non-smooth data.     

Linear bilevel multi-follower programming with independent followers

This paper considers a particular case of linear bilevel programming problems with one leader and multiple followers. In this model, the followers are independent, meaning that the objective function and the set of constraints of each follower only include the leader’s variables and his own variables. We prove that this problem can be reformulated into a linear bilevel problem with one leader and one follower by defining an adequate second level objective function and constraint region. In the second part of the paper we show that the results on the optimality of the linear bilevel problem with multiple independent followers presented in Shi et al. [The kth-best approach for linear bilevel multi-follower programming, J. Global Optim. 33, 563–578 (2005)] are based on a misconstruction of the inducible region.     

A simple Tabu Search method to solve the mixed-integer linear bilevel programming problem

Multilevel programming is characterized as mathematical programming to solve decentralized planning problems. The models partition control over decision variables among ordered levels within a hierarchical planning structure of which the linear bilevel form is a special case of a multilevel programming problem. In a system with such a hierarchical structure, the high-level decision making situations generally require inclusion of zero-one variables representing ‘yes-no’ decisions. We provide a mixed-integer linear bilevel programming formulation in which zero-one decision variables are controlled by a high-level decision maker and real-value decision variables are controlled by a low-level decision maker. An algorithm based on the short term memory component of Tabu Search, called Simple Tabu Search, is developed to solve the problem, and two supplementary procedures are proposed that provide variations of the algorithm. Computational results disclose that our approach is effective in terms of both solution quality and efficiency.     

Finding an efficient solution to linear bilevel programming problem: An effective approach

Multilevel programming is developed to solve the decentralized problem in which decision makers (DMs) are often arranged within a hierarchical administrative structure. The linear bilevel programming (BLP) problem, i.e., a special case of multilevel programming problems with a two level structure, is a set of nested linear optimization problems over polyhedral set of constraints. Two DMs are located at the different hierarchical levels, both controlling one set of decision variables independently, with different and perhaps conflicting objective functions. One of the interesting features of the linear BLP problem is that its solution may not be Paretooptimal. There may exist a feasible solution where one or both levels may increase their objective values without decreasing the objective value of any level. The result from such a system may be economically inadmissible. If the decision makers of the two levels are willing to find an efficient compromise solution, we propose a solution procedure which can generate effcient solutions, without finding the optimal solution in advance. When the near-optimal solution of the BLP problem is used as the reference point for finding the efficient solution, the result can be easily found during the decision process.     

二(双)层规划综述

二(双)层规划是研究二层决策的递阶优化问题.其理论、方法和应用在过去的30多年取得了很大的发展.本文对二层规划问题的基本概念、性质和算法作了综述,并且对下层规划问题的解不唯一的情况也作了介绍,最后还给出了几种常见的二层规划模型.     

一类特殊线性双层规划的对偶规划

本文首先给出值型线性双层规划的等价形式 ,然后讨论了非增的值型线性双层规划的 Johri一般对偶规划 ,并且说明了其对偶间隙等于零 ,最后说明了它们最优解的关系     

An interval approach based on expectation optimization for fuzzy random bilevel linear programming problems

This paper considers a class of bilevel linear programming problems in which the coefficients of both objective functions are fuzzy random variables. The main idea of this paper is to introduce the Pareto optimal solution in a multi-objective bilevel programming problem as a solution for a fuzzy random bilevel programming problem. To this end, a stochastic interval bilevel linear programming problem is first introduced in terms of α-cuts of fuzzy random variables. On the basis of an order relation of interval numbers and the expectation optimization model, the stochastic interval bilevel linear programming problem can be transformed into a multi-objective bilevel programming problem which is solved by means of weighted linear combination technique. In order to compare different optimal solutions depending on different cuts, two criterions are given to provide the preferable optimal solutions for the upper and lower level decision makers respectively. Finally, a production planning problem is given to demonstrate the feasibility of the proposed approach.     

Optimality and Duality Results for Bilevel Programming Problem Using Convexifactors

The paper is devoted to the applications of convexifactors to bilevel programming problem. Here we have defined ∂ ^∗-convex, ∂ ^∗-pseudoconvex and ∂ ^∗-quasiconvex bifunctions in terms of convexifactors on the lines of Dutta and Chandra (Optimization 53:77–94, 2004) and Li and Zhang (J. Opt. Theory Appl. 131:429–452, 2006). We derive sufficient optimality conditions for the bilevel programming problem by using these functions, and we establish various duality results by associating the given problem with two dual problems, namely Wolfe type dual and Mond–Weir type dual.     

Bilevel invex equilibrium problems with applications

In this paper, bilevel invex equilibrium problems of Hartman-Stampacchia type and Minty type [resp., in short, (HSBEP) and (MBEP)] are firstly introduced in finite Euclidean spaces. The relationships between (HSBEP) and (MBEP) are presented under some suitable conditions. By using fixed point technique, the nonemptiness and compactness of solution sets to (HSBEP) and (MBEP) are established under the invexity, respectively. As applications, we investigate the existence of solution and the behavior of solution set to the bilevel pseudomonotone variational inequalities of [Anh et al. J Glob Optim 2012, doi:10.1007/s10898-012-9870-y] and the solvability of minimization problem with variational inequality constraint.     

An improved solution to the replenishment policy for the EMQ model with rework and multiple shipments

Recently, Chiu et al. (2012) [1] present an alternative optimization procedure to derive the optimal replenishment lot size for an economic manufacturing quantity (EMQ) model with rework and multiple shipments. This inventory model was proposed by Chiu et al. (2011) [2]. Both papers do not consider the determining of the number of shipments. This paper determines both the optimal replenishment lot size and the optimal number of shipments jointly. The solution of this paper is better than the solutions of Chiu et al.  and .     

Links Between Linear Bilevel and Mixed 0–1 Programming Problems

We study links between the linear bilevel and linear mixed 0–1 programming problems. A new reformulation of the linear mixed 0–1 programming problem into a linear bilevel programming one, which does not require the introduction of a large finite constant, is presented. We show that solving a linear mixed 0–1 problem by a classical branch-and-bound algorithm is equivalent in a strong sense to solving its bilevel reformulation by a bilevel branch-and-bound algorithm. The mixed 0–1 algorithm is embedded in the bilevel algorithm through the aforementioned reformulation; i.e., when applied to any mixed 0–1 instance and its bilevel reformulation, they generate sequences of subproblems which are identical via the reformulation.     

Generic well-posedness of minimization problems with mixed continuous constraints

In this paper we study mathematical programming problems with mixed constraints in a Banach space and show that most of the problems (in the Baire category sense) are well-posed. Our result is a generalization of a result of Ioffe et al. [SIAM J. Optim. 12 (2001) 461–478] obtained for finite-dimensional Banach spaces.     

Higher-order Mond-Weir converse duality in multiobjective programming involving cones

In this work,we established a converse duality theorem for higher-order Mond-Weir type multiobjective programming involving cones.This flls some gap in recently work of Kim et al.[Kim D S,Kang H S,Lee Y J,et al.Higher order duality in multiobjective programming with cone constraints.Optimization,2010,59:29–43].     

Two-Stage Approach for Quantitative Policy Analysis Using Bilevel Programming

Quantitative policy analysis problems with hierarchical decision-making can be modeled as bilevel mathematical programming problems. In general, the solution of these models is very difficult; however, special cases exist in which an optimal solution can be obtained by ordinary mathematical programming techniques. In this paper, a two-stage approach for the formulation, construction, solution, and usage of bilevel policy problem is presented. An outline of an example for analyzing Israel's public expenditure policy is also given.     

An optimal solution to a three echelon supply chain network with multi-product and multi-period

Recently, Kadadevaramath et al. (2012) [1] presented a mathematical model for optimizing a three echelon supply chain network. Their model is an integer linear programming (ILP) model. In order to solve it, they developed five algorithms; four of them are based on a particle swarm optimization (PSO) method and the other is a genetic algorithm (GA). In this paper, we develop a more general mathematical model that contains the model developed by Kadadevaramath et al. (2012) [1]. Furthermore, we show that all instances proved in Kadadevaramath et al. (2012) [1] can easily be solved optimally by any integer linear programming solver.     

Estimation of intrinsic processes affected by additive fractal noise

Fractal Gaussian models have been widely used to represent the singular behavior of phenomena arising in different applied fields; for example, fractional Brownian motion and fractional Gaussian noise are considered as monofractal models in subsurface hydrology and geophysical studies Mandelbrot [The Fractal Geometry of Nature, Freeman Press, San Francisco, 1982 [13]]. In this paper, we address the problem of least-squares linear estimation of an intrinsic fractal input random field from the observation of an output random field affected by fractal noise (see Angulo et al. [Estimation and filtering of fractional generalised random fields, J. Austral. Math. Soc. A 69 (2000) 1-26 [2]], Ruiz-Medina et al. [Fractional generalized random fields on bounded domains, Stochastic Anal. Appl. 21 (2003a) 465-492], Ruiz-Medina et al. [Fractional-order regularization and wavelet approximation to the inverse estimation problem for random fields, J. Multivariate Anal. 85 (2003b) 192-216]. Conditions on the fractality order of the additive noise are studied to obtain a bounded inversion of the associated Wiener-Hopf equation. A stable solution is then obtained in terms of orthogonal bases of the reproducing kernel Hilbert spaces associated with the random fields involved. Such bases are constructed from orthonormal wavelet bases (see Angulo and Ruiz-Medina [Multiresolution approximation to the stochastic inverse problem, Adv. in Appl. Probab. 31 (1999) 1039-1057], Angulo et al. [Wavelet-based orthogonal expansions of fractional generalized random fields on bounded domains, Theoret. Probab. Math. Stat. (2004), in press]). A simulation study is carried out to illustrate the influence of the fractality orders of the output random field and the fractal additive noise on the stability of the solution derived.     

A genetic algorithm for solving linear fractional bilevel problems

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterized by the existence of two optimization problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimization problem. In this paper a genetic algorithm is proposed for the class of bilevel problems in which both level objective functions are linear fractional and the common constraint region is a bounded polyhedron. The algorithm associates chromosomes with extreme points of the polyhedron and searches for a feasible solution close to the optimal solution by proposing efficient crossover and mutation procedures. The computational study shows a good performance of the algorithm, both in terms of solution quality and computational time.     

Logarithmic SUMT limits in convex programming

The limits of a class of primal and dual solution trajectories associated with the Sequential Unconstrained Minimization Technique (SUMT) are investigated for convex programming problems with non-unique optima. Logarithmic barrier terms are assumed. For linear programming problems, such limits – of both primal and dual trajectories – are strongly optimal, strictly complementary, and can be characterized as analytic centers of, loosely speaking, optimality regions. Examples are given, which show that those results do not hold in general for convex programming problems. If the latter are weakly analytic (Bank et al. [3]), primal trajectory limits can be characterized in analogy to the linear programming case and without assuming differentiability. That class of programming problems contains faithfully convex, linear, and convex quadratic programming problems as strict subsets. In the differential case, dual trajectory limits can be characterized similarly, albeit under different conditions, one of which suffices for strict complementarity. Received: November 13, 1997 / Accepted: February 17, 1999?Published online February 22, 2001     

Necessary optimality conditions of a D.C. set-valued bilevel optimization problem

In this article, we consider a bilevel vector optimization problem where objective and constraints are set valued maps. Our approach consists of using a support function [1–3,14,15,32] together with the convex separation principle for the study of necessary optimality conditions for D.C. bilevel set-valued optimization problems. We give optimality conditions in terms of the strong subdifferential of a cone-convex set-valued mapping introduced by Baier and Jahn 6 Baier, J and Jahn, J. 1999. On subdifferentials of set-valued maps. J. Optim. Theory Appl., 100: 233–240. [Crossref], [Web of Science ®] , [Google Scholar] and the weak subdifferential of a cone-convex set-valued mapping of Sawaragi and Tanino 28 Sawaragi, Y and Tanino, T. 1980. Conjugate maps and duality in multiobjective optimization. J. Optim. Theory Appl., 31: 473–499.  [Google Scholar]. The bilevel set-valued problem is transformed into a one level set-valued optimization problem using a transformation originated by Ye and Zhu 34 Ye, JJ and Zhu, DL. 1995. Optimality conditions for bilevel programming problems. Optimization, 33: 9–27. [Taylor & Francis Online] , [Google Scholar]. An example illustrating the usefulness of our result is also given.