On degeneracy and collapsing in the construction of the set of objective values in a multiple objective linear program

In this paper an algorithm is developed to generate all nondominated extreme points and edges of the set of objective values of a multiple objective linear program. The approach uses simplex tableaux but avoids generating unnecessary extreme points or bases of extreme points. The procedure is based on, and improves, an algorithm Dauer and Liu developed for this problem. Essential to this approach is the work of Gal and Kruse on the neighborhood problem of determining all extreme points of a convex polytope that are adjacent to a given (degenerate) extreme point of the set. The algorithm will incorporate Gal's degeneracy graph approach to the neighborhood problem with Dauer's objective space analysis of multiple objective linear programs.     

Cone convexity,cone extreme points,and nondominated solutions in decision problems with multiobjectives

Although there is no universally accepted solution concept for decision problems with multiple noncommensurable objectives, one would agree that agood solution must not be dominated by the other feasible alternatives. Here, we propose a structure of domination over the objective space and explore the geometry of the set of all nondominated solutions. Two methods for locating the set of all nondominated solutions through ordinary mathematical programming are introduced. In order to achieve our main results, we have introduced the new concepts of cone convexity and cone extreme point, and we have explored their main properties. Some relevant results on polar cones and polyhedral cones are also derived. Throughout the paper, we also pay attention to an important special case of nondominated solutions, that is, Pareto-optimal solutions. The geometry of the set of all Pareto solutions and methods for locating it are also studied. At the end, we provide an example to show how we can locate the set of all nondominated solutions through a derived decomposition theorem.     

Necessary and sufficient conditions for local and global nondominated solutions in decision problems with multi-objectives

In this paper, the decision problem with multi-objectives is considered, and the nondominated solutions associated with a polyhedral domination cone are discussed. The necessary and sufficient conditions for the solutions are given in the decision space rather than the objective space. The similarity of the solution conditions obtained in this article to the Kuhn-Tucker condition of a convex programming problem is examined. As an application of the solution condition, an algorithm to locate the set of all nondominated solutions is shown for the linear multi-objective decision problem.The author would like to thank the reviewer for his helpful comments.     

Nondominated Equilibrium Solutions of a Multiobjective Two-Person Nonzero-Sum Game and Corresponding Mathematical Programming Problem

With reference to a multiobjective two-person nonzero-sum game, we define nondominated equilibrium solutions and provide a necessary and sufficient condition for a pair of mixed strategies to be a nondominated equilibrium solution. Using the necessary and sufficient condition, we formulate a mathematical programming problem yielding nondominated equilibrium solutions. We give a numerical example and demonstrate that nondominated equilibrium solutions can be obtained by solving the formulated mathematical programming problem.     

Generalization of domination structures and nondominated solutions in multicriteria decision making

The concepts of domination structures and nondominated solutions are important in tackling multicriteria decision problems. We relax Yu's requirement that the domination structure at each point of the criteria space be a convex cone (Ref. 1) and give results concerning the set of nondominated solutions for the case where the domination structure at each point is a convex set. A practical necessity for such a generalization is discussed. We also present conditions under which a locally nondominated solution is also a globally nondominated solution.     

An approximation algorithm for convex multi-objective programming problems

In multi-objective convex optimization it is necessary to compute an infinite set of nondominated points. We propose a method for approximating the nondominated set of a multi-objective nonlinear programming problem, where the objective functions and the feasible set are convex. This method is an extension of Benson’s outer approximation algorithm for multi-objective linear programming problems. We prove that this method provides a set of weakly ε-nondominated points. For the case that the objectives and constraints are differentiable, we describe an efficient way to carry out the main step of the algorithm, the construction of a hyperplane separating an exterior point from the feasible set in objective space. We provide examples that show that this cannot always be done in the same way in the case of non-differentiable objectives or constraints.     

Strongly extreme points in Banach spaces

In this paper some properties of a special type of boundary point of convex sets in Banach spaces are studied. Specifically, a strongly extreme point x of a convex set S is a point of S such that for each real number r>0, segments of length 2r and centered x are not uniformly closer to S than some positive number d(x,r). Results are obtained comparing the notion of strongly extreme point to other known types of special boundary points of convex sets. Using the notion of strongly extreme point, a convexity condition is defined on the norm of the space under consideration, and this convexity condition makes possible a unified treatment of some previously studied convexity conditions. In addition, a sufficient condition is given on the norm of a separable conjugate space for every extreme point of the unit ball to be strongly extreme.     

Adjacency based method for generating maximal efficient faces in multiobjective linear programming

Multiobjective linear optimization problems (MOLPs) arise when several linear objective functions have to be optimized over a convex polyhedron. In this paper, we propose a new method for generating the entire efficient set for MOLPs in the outcome space. This method is based on the concept of adjacencies between efficient extreme points. It uses a local exploration approach to generate simultaneously efficient extreme points and maximal efficient faces. We therefore define an efficient face as the combination of adjacent efficient extreme points that define its border. We propose to use an iterative simplex pivoting algorithm to find adjacent efficient extreme points. Concurrently, maximal efficient faces are generated by testing relative interior points. The proposed method is constructive such that each extreme point, while searching for incident faces, can transmit some local informations to its adjacent efficient extreme points in order to complete the faces’ construction. The performance of our method is reported and the computational results based on randomly generated MOLPs are discussed.     

Nondominated equilibrium solutions of a multiobjective two-person nonzero-sum game in extensive form and corresponding mathematical programming problem

In most of studies on multiobjective noncooperative games, games are represented in normal form and a solution concept of Pareto equilibrium solutions which is an extension of Nash equilibrium solutions has been focused on. However, for analyzing economic situations and modeling real world applications, we often see cases where the extensive form representation of games is more appropriate than the normal form representation. In this paper, in a multiobjective two-person nonzero-sum game in extensive form, we employ the sequence form of strategy representation to define a nondominated equilibrium solution which is an extension of a Pareto equilibrium solution, and provide a necessary and sufficient condition that a pair of realization plans, which are strategies of players in sequence form, is a nondominated equilibrium solution. Using the necessary and sufficient condition, we formulate a mathematical programming problem yielding nondominated equilibrium solutions. Finally, giving a numerical example, we demonstrate that nondominated equilibrium solutions can be obtained by solving the formulated mathematical programming problem.     

Characterizing the nondominated set by separable functions

We present sufficient and necessary conditions for classes of separable (additive) functions to generate the set of nondominated outcomes in multicriteria optimization problems. The basic technique consists of convexifying the set of outcomes and then applying the standard characterization of a convex set by a class of linear functions. The conditions include the case when the set of feasible alternatives is convex and the criteria are convex-transformable. We show that the sum of powers and the sum of functions of exponents can generate the nondominated set for an arbitrary set of outcomes (under compactness conditions). We also discuss monotonicity, proper nondominance, uniqueness and connectedness of solutions, and weights and trade-offs with respect to these functions.The research was done while the author was Visiting Professor at the University of Illinois at Urbana-Champaign, Illinois. The author is grateful to G. Hazen, Northwestern University, for helpful discussions.     

Extreme bosonic linear channels

The set of all channels with a fixed input and output is convex. We first give a convenient formulation of the necessary and sufficient condition for a channel to be an extreme point of this set in terms of the complementary channel, a notion of great importance in quantum information theory. This formulation is based on the general approach to extremality of completely positive maps in an operator algebra in the spirit of Arveson. We then use this formulation to prove our main result: under certain nondegeneracy conditions, environmental purity is necessary and sufficient for the extremality of a bosonic linear (quasifree) channel. It hence follows that a Gaussian channel between finite-mode bosonic systems is extreme if and only if it has minimum noise.     

A revised simplex method for linear multiple objective programs

For linear multiple-objective problems, a necessary and sufficient condition for a point to be efficient is employed in the development of a revised simplex algorithm for the enumeration of the set of efficient extreme points. Five options within this algorithm were tested on a variety of problems. Results of these tests provide indications for effective use of the algorithm.This work was partially supported by the Office of Naval Research, Contract No. N00014-67-A-0321-0003 (NR047-095).     

Variable preference modeling with ideal-symmetric convex cones

Based on the concept of general domination structures, this paper presents an approach to model variable preferences for multicriteria optimization and decision making problems. The preference assumptions for using a constant convex cone are given, and, in remedy of some immanent model limitations, a new set of assumptions is presented. The underlying preference model is derived as a variable domination structure that is defined by a collection of ideal-symmetric convex cones. Necessary and sufficient conditions for nondominance are established, and the problem of finding corresponding nondominated solutions is addressed and solved on examples.     

Nondominated Nash points: application of biobjective mixed integer programming

We study the connection between biobjective mixed integer linear programming and normal form games with two players. We first investigate computing Nash equilibria of normal form games with two players using single-objective mixed integer linear programming. Then, we define the concept of efficient (Pareto optimal) Nash equilibria. This concept is precisely equivalent to the concept of efficient solutions in multi-objective optimization, where the solutions are Nash equilibria. We prove that the set of all points in the payoff (or objective) space of a normal form game with two players corresponding to the utilities of players in an efficient Nash equilibrium, the so-called nondominated Nash points, is finite. We demonstrate that biobjective mixed integer linear programming, where the utility of each player is an objective function, can be used to compute the set of nondominated Nash points. Finally, we illustrate how the nondominated Nash points can be used to determine the disagreement point of a bargaining problem.     

An algorithm for determining all extreme points of a convex polytope

An algorithm for determining all the extreme points of a convex polytope associated with a set of linear constraints, via the computation of basic feasible solutions to the constraints, is presented. The algorithm is based on the product-form revised simplex method and as such can be readily linked onto standard linear programming codes. Applications of such an algorithm are reviewed and limited computational experience given.     

The Caratheodory-Fejer extension theorem

A construction of Carathéodory and Fejér [1] produces a function which is bounded and analytic in the unit disk with specified initial coefficients. An operator generalization of the construction is now obtained for application to the invariant subspace problem. A formal proof [2] of the existence of invariant subspaces is given by the theory of square summable power series [3] in its vector formulation [4]. But the justification of the formal argument requires a determination of extreme points of a convex set [5]. A solution is now given to an extension problem for convex decompositions which arises in connection with the Carathéodory-Fejér theorem. A necessary condition for an extreme point is obtained as an application. The condition is conjectured to be sufficient.     

Continuous selector of representative measures and the space of faces of a convex compactum

A sufficient condition for the existence of a continuous selector of representative measure, concentrated at the extreme points of a convex metrizable compactum, is considered. A necessary condition for the existence of such a selector is deduced. An example is given of a convex compactum with a closed set of extreme points, for which no continuous selector exists.Translated from Matematicheskie Zametki, Vol. 22, No. 6, pp. 897–906, December, 1977.In conclusion, the author expresses deep gratitude to A. M. Vershik for the formulation of the problem and for help in the preparation of this paper.     

Bauer's maximum principle and hulls of sets

We use the Bauer maximum principle for quasiconvex, polyconvex and rank-one convex functions to derive Krein-Milman-type theorems for compact sets in . Further we show that in general the set of quasiconvex extreme points is not invariant under transposition and it is different from the set of rank-one convex extreme points. Finally, a set in with different polyconvex, quasiconvex and rank-one convex hulls is constructed. Received September 14, 1999 / Accepted January 14, 2000 /Published online July 20, 2000     

Two row mixed-integer cuts via lifting

Recently Andersen et al. [1], Borozan and Cornuéjols [6] and Cornuéjols and Margot [9] have characterized the extreme valid inequalities of a mixed integer set consisting of two equations with two free integer variables and non-negative continuous variables. These inequalities are either split cuts or intersection cuts derived using maximal lattice-free convex sets. In order to use these inequalities to obtain cuts from two rows of a general simplex tableau, one approach is to extend the system to include all possible non-negative integer variables (giving the two row mixed-integer infinite-group problem), and to develop lifting functions giving the coefficients of the integer variables in the corresponding inequalities. In this paper, we study the characteristics of these lifting functions. We show that there exists a unique lifting function that yields extreme inequalities when starting from a maximal lattice-free triangle with multiple integer points in the relative interior of one of its sides, or a maximal lattice-free triangle with integral vertices and one integer point in the relative interior of each side. In the other cases (maximal lattice-free triangles with one integer point in the relative interior of each side and non-integral vertices, and maximal lattice-free quadrilaterals), non-unique lifting functions may yield distinct extreme inequalities. For the latter family of triangles, we present sufficient conditions to yield an extreme inequality for the two row mixed-integer infinite-group problem.