Convex Parametric Programming in Abstract Spaces

This article studies stability and optimality for convex parametric programming models in abstract spaces. Necessary conditions for continuity of the feasible set mapping are given in complete metric spaces. This continuity is characterized for models in which the space of decision variables is reflexive Banach space. The main result on optimality characterizes locally optimal parameters relative to stable perturbations of the parameter. The result is stated in terms of the existence of a saddle-point for a Lagrangian that uses a finite Borel measure. It does not hold for unstable perturbations even if the model is finite dimensional. The results are applicable to various formulations of control and optimal control problems.     

Solving a multiobjective possibilistic problem through compromise programming

Real decision problems usually consider several objectives that have parameters which are often given by the decision maker in an imprecise way. It is possible to handle these kinds of problems through multiple criteria models in terms of possibility theory.Here we propose a method for solving these kinds of models through a fuzzy compromise programming approach.To formulate a fuzzy compromise programming problem from a possibilistic multiobjective linear programming problem the fuzzy ideal solution concept is introduced. This concept is based on soft preference and indifference relationships and on canonical representation of fuzzy numbers by means of their α-cuts. The accuracy between the ideal solution and the objective values is evaluated handling the fuzzy parameters through their expected intervals and a definition of discrepancy between intervals is introduced in our analysis.     

On the Stability of the Feasible Set in Linear Optimization

This paper deals with the stability of two families of linear optimization problems, each one formed by the dual problems to the members of the other family. We characterize the problems of these families that are stable in the sense that they remain consistent (inconsistent) under sufficiently small arbitrary perturbations of all the data. This characterization is established in terms of the lower semicontinuity property of the feasible set mapping and the boundedness of the optimal set of the corresponding coupled problem. Other continuity properties of the feasible set mapping are also derived. This stability theory extends some well-known theorems of Williams and Robinson on the stability of ordinary linear programming problems to linear optimization problems with infinitely many variables or constraints.     

A note on second-order stochastic dominance constraints induced by mixed-integer linear recourse

We introduce stochastic integer programs with second-order dominance constraints induced by mixed-integer linear recourse. Closedness of the constraint set mapping with respect to perturbations of the underlying probability measure is derived. For discrete probability measures, large-scale, block-structured, mixed- integer linear programming equivalents to the dominance constrained stochastic programs are identified. For these models, a decomposition algorithm is proposed and tested with instances from power optimization.     

On Implicit Active Constraints in Linear Semi-Infinite Programs with Unbounded Coefficients

The concept of implicit active constraints at a given point provides useful local information about the solution set of linear semi-infinite systems and about the optimal set in linear semi-infinite programming provided the set of gradient vectors of the constraints is bounded, commonly under the additional assumption that there exists some strong Slater point. This paper shows that the mentioned global boundedness condition can be replaced by a weaker local condition (LUB) based on locally active constraints (active in a ball of small radius whose center is some nominal point), providing geometric information about the solution set and Karush-Kuhn-Tucker type conditions for the optimal solution to be strongly unique. The maintaining of the latter property under sufficiently small perturbations of all the data is also analyzed, giving a characterization of its stability with respect to these perturbations in terms of the strong Slater condition, the so-called Extended-Nürnberger condition, and the LUB condition.     

A Proof of the Necessity of Linear Independence Condition and Strong Second-Order Sufficient Optimality Condition for Lipschitzian Stability in Nonlinear Programming

For a nonlinear programming problem with a canonical perturbations, we give an elementary proof of the following result: If the Karush–Kuhn–Tucker map is locally single-valued and Lipschitz continuous, then the linear independence condition for the gradients of the active constraints and the strong second-order sufficient optimality condition hold.     

Quantitative stability analysis for vector problems of 0–1 programming

We consider multiple objective 0–1 programming problems in the situation where parameters of objective functions and linear constraints are exposed to independent perturbations. We study quantitative characteristics of stability (stability radii) of problem solutions. An approach to deriving formulae and estimations of stability radii is presented. This approach is applied to stability analysis of the linear 0–1 programming problem and problems with two types of nonlinear objective functions: linear absolute value and quadratic.     

Numerical treatment of an asset price model with non-stochastic uncertainty

In contrast to stochastic differential equation models used for the calculation of the term structure of interest rates, we develop an approach based on linear dynamical systems under non-stochastic uncertainty with perturbations. The uncertainty is described in terms of known feasible sets of varying parameters. Observations are used in order to estimate these parameters by minimizing the maximum of the absolute value of measurement errors, which leads to a linear or nonlinear semi-infinite programming problem. A regularized logarithmic barrier method for solving (ill-posed) convex semi-infinite programming problems is suggested. In this method a multi-step proximal regularization is coupled with an adaptive discretization strategy in the framework of an interior point approach. A special deleting rule permits one to use only a part of the constraints of the discretized problems. Convergence of the method and its stability with respect to data perturbations in the cone of convexC ¹-functions are studied. On the basis of the solutions of the semi-infinite programming problems a technical trading system for future contracts of the German DAX is suggested and developed. Supported by the Stiftung Rheinland/Pfalz für Innovation, No. 8312-386261/307.     

数据包络分析SBM超效率模型无可行解问题的两阶段求解法

数据包络分析是一种得到广泛应用的基于线性规划的非参数技术效率分析方法,其超效率模型是将被评价DMU从参照集中排除从而使求解得出的效率值可能大于1.超效率模型在文献中用于对有效的DMU进行排序、探测异常值、敏感性和稳定性分析、分析生产率变化的Malmquist模型、二人博弈模型等.超效率模型存在的一个缺陷是在规模收益可变的假设下会出现无可行解的问题.提出了一种基于两阶段求解的SBM超效率模型,并保持了与传统SBM超效率模型的兼容性:在传统的投入(产出)导向SBM超效率模型有可行解时,两阶段法获得的结果与之相同;在传统的投入(产出)导向SBM超效率模型无可行解时,两阶段超效率模型可以得出最接近投入(产出)导向定义的可行解.算例采用实际数据对方法进行了验证.     

On a necessary condition for stability in perturbed linear and convex programming

We show that a necessary condition for stable perturbations in linear and convex programming is valid on an arbitrary region of stability. Using point-to-set mappings, two new regions of stability are identified.Contribution of this author is part of his M.Sc. thesis in Applied Mathematics at McGill University.     

Perturbation and robust stability of autonomous singular linear matrix difference equations

In the perturbation theory of linear matrix difference equations, it is well known that the theory of finite and infinite elementary divisors of regular matrix pencils is complicated by the fact that arbitrarily small perturbations of the pencil can cause them to disappear. In this paper, the perturbation theory of complex Weierstrass canonical form for regular matrix pencils is investigated. By using matrix pencil theory and the Weierstrass canonical form of the pencil we obtain bounds for the finite elementary divisors of a perturbed pencil. Moreover we study robust stability of a class of linear matrix difference equations (of first and higher order) whose coefficients are square constant matrices.     

Regularity modulus of arbitrarily perturbed linear inequality systems

We aim to quantify the stability of systems of (possibly infinitely many) linear inequalities under arbitrary perturbations of the data. Our focus is on the Aubin property (also called pseudo-Lipschitz) of the solution set mapping, or, equivalently, on the metric regularity of its inverse mapping. The main goal is to determine the regularity modulus of the latter mapping exclusively in terms of the system's data. In our context, both, the right- and the left-hand side of the system are subject to possible perturbations. This fact entails notable differences with respect to previous developments in the framework of linear systems with perturbations of the right-hand side. In these previous studies, the feasible set mapping is sublinear (which is not our current case) and the well-known Radius Theorem constitutes a useful tool for determining the modulus. In our current setting we do not have an explicit expression for the radius of metric regularity, and we have to tackle the modulus directly. As an application we approach, under appropriate assumptions, the regularity modulus for a semi-infinite system associated with the Lagrangian dual of an ordinary nonlinear programming problem.     

On computational methods for solutions of multiobjective linear production programming games

In this paper we consider a production model in which multiple decision makers pool resources to produce finished goods. Such a production model, which is assumed to be linear, can be formulated as a multiobjective linear programming problem. It is shown that a multi-commodity game arises from the multiobjective linear production programming problem with multiple decision makers and such a game is referred to as a multiobjective linear production programming game. The characteristic sets in the game can be obtained by finding the set of all the Pareto extreme points of the multiobjective programming problem. It is proven that the core of the game is not empty, and points in the core are computed by using the duality theory of multiobjective linear programming problems. Moreover, the least core and the nucleolus of the game are examined. Finally, we consider a situation that decision makers first optimize their multiobjective linear production programming problem and then they examine allocation of profits and/or costs. Computational methods are developed and illustrative numerical examples are given.     

UTA-poly and UTA-splines: Additive value functions with polynomial marginals

Additive utility function models are widely used in multiple criteria decision analysis. In such models, a numerical value is associated to each alternative involved in the decision problem. It is computed by aggregating the scores of the alternative on the different criteria of the decision problem. The score of an alternative is determined by a marginal value function that evolves monotonically as a function of the performance of the alternative on this criterion. Determining the shape of the marginals is not easy for a decision maker. It is easier for him/her to make statements such as “alternative a is preferred to b”. In order to help the decision maker, UTA disaggregation procedures use linear programming to approximate the marginals by piecewise linear functions based only on such statements. In this paper, we propose to infer polynomials and splines instead of piecewise linear functions for the marginals. In this aim, we use semidefinite programming instead of linear programming. We illustrate this new elicitation method and present some experimental results.     

Developments in linear and integer programming

In this review we describe recent developments in linear and integer (linear) programming. For over 50 years Operational Research practitioners have made use of linear optimisation models to aid decision making and over this period the size of problems that can be solved has increased dramatically, the time required to solve problems has decreased substantially and the flexibility of modelling and solving systems has increased steadily. Large models are no longer confined to large computers, and the flexibility of optimisation systems embedded in other decision support tools has made on-line decision making using linear programming a reality (and using integer programming a possibility). The review focuses on recent developments in algorithms, software and applications and investigates some connections between linear optimisation and other technologies.     

Further Analysis of an Outcome Set-Based Algorithm for Multiple-Objective Linear Programming

Various difficulties have been encountered in using decision set-based vector maximization methods to solve a multiple-objective linear programming problem (MOLP). Motivated by these difficulties, Benson recently developed a finite, outer-approximation algorithm for generating the set of all efficient extreme points in the outcome set, rather than in the decision set, of problem (MOLP). In this article, we show that the Benson algorithm also generates the set of all weakly efficient points in the outcome set of problem (MOLP). As a result, the usefulness of the algorithm as a decision aid in multiple objective linear programming is further enhanced.     

Stackelberg solutions for fuzzy random two-level linear programming through probability maximization with possibility

This paper considers Stackelberg solutions for decision making problems in hierarchical organizations under fuzzy random environments. Taking into account vagueness of judgments of decision makers, fuzzy goals are introduced into the formulated fuzzy random two-level linear programming problems. On the basis of the possibility and necessity measures that each objective function fulfills the corresponding fuzzy goal, together with the introduction of probability maximization criterion in stochastic programming, we propose new two-level fuzzy random decision making models which maximize the probabilities that the degrees of possibility and necessity are greater than or equal to certain values. Through the proposed models, it is shown that the original two-level linear programming problems with fuzzy random variables can be transformed into deterministic two-level linear fractional programming problems. For the transformed problems, extended concepts of Stackelberg solutions are defined and computational methods are also presented. A numerical example is provided to illustrate the proposed methods.     

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.     

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.     

Primal-dual stability in continuous linear optimization

Any linear (ordinary or semi-infinite) optimization problem, and also its dual problem, can be classified as either inconsistent or bounded or unbounded, giving rise to nine duality states, three of them being precluded by the weak duality theorem. The remaining six duality states are possible in linear semi-infinite programming whereas two of them are precluded in linear programming as a consequence of the existence theorem and the non-homogeneous Farkas Lemma. This paper characterizes the linear programs and the continuous linear semi-infinite programs whose duality state is preserved by sufficiently small perturbations of all the data. Moreover, it shows that almost all linear programs satisfy this stability property.