Using Efficient Anchoring Points for Generating Search Directions in Interior Multiobjective Linear Programming

This paper modifies the affine-scaling primal algorithm to multiobjective linear programming (MOLP) problems. The modification is based on generating search directions in the form of projected gradients augmented by search directions pointing toward what we refer to as anchoring points. These anchoring points are located on the boundary of the feasible region and, together with the current, interior, iterate, define a cone in which we make the next step towards a solution of the MOLP problem. These anchoring points can be generated in more than one way. In this paper we present an approach that generates efficient anchoring points where the choice of termination solution available to the decision maker at each iteration consists of a set of efficient solutions. This set of efficient solutions is being updated during the iterative process so that only the most preferred solutions are retained for future considerations. Current MOLP algorithms are simplex-based and make their progress toward the optimal solution by following an exterior trajectory along the vertices of the constraints polytope. Since the proposed algorithm makes its progress through the interior of the constraints polytope, there is no need for vertex information and, therefore, the search for an acceptable solution may prove less sensitive to problem size. We refer to the resulting class of MOLP algorithms that are based on the affine-scaling primal algorithm as affine-scaling interior multiobjective linear programming (ASIMOLP) algorithms.     

An Interior Multiple Objective Primal-dual Linear Programming Algorithm Using Efficient Anchoring Points

We present an interior Multiple Objective Linear Programming (MOLP) algorithm based on the path-following primal-dual algorithm. In contrast to the simplex algorithm, which generates a solution path on the exterior of the constraints polytope by following its vertices, the path-following primal-dual algorithm moves through the interior of the polytope. Interior algorithms lend themselves to modifications capable of addressing MOLP problems in a way that is quite different from current solution approaches. In addition, moving through the interior of the polytope results in a solution approach that is less sensitive to problem size than simplex-based MOLP algorithms. The modification of the interior single-objective algorithm to MOLP problems, as presented here, is accomplished by combining the step direction vectors generated by applying the single-objective algorithm to each of the cost vectors into a combined direction vector along which we step from the current iterate to the next iterate.     

齐次多目标规划问题的KKT点

通过构造原问题的辅助问题,得到多目标规划问题的一些性质.并且给出目标函数是齐次函数的多目标优化问题KKT点的一个等价性质.     

On Sensitivity in Linear Multiobjective Programming

In this paper, we prove that, if the data of a linear multiobjectiveprogramming problem are smooth functions of a parameter, then in theparameter space there is an open dense subset where the efficient solutionset of the problem can be locally represented as a union of some faces whosevertices and directions are smooth functions of the parameter.     

Pointwise Efficiency in Multiobjective Stochastic Linear Programming

In most of the approaches to the Multiobjective Stochastic Linear Programming problem that have been proposed in the literature, the notion of quality of a solution is not adequately defined. We reconsider this problem from a decision point of view, in contexts where either the decision maker's preference structure cannot be described by a utility function, or where this structure is expressed by an unknown non-decreasing utility function and the probability distribution of the random parameters is unknown. We define a fundamental set of ‘pointwise admissible’ solutions, as well as several subsets of particular interest. We discuss the relevance of these various pointwise efficient sets, their interrelations, and their practical identification.     

A Semidefinite Programming approach for solving Multiobjective Linear Programming

Several algorithms are available in the literature for finding the entire set of Pareto-optimal solutions of Multiobjective Linear Programmes (MOLPs). However, all of them are based on active-set methods (simplex-like approaches). We present a different method, based on a transformation of any MOLP into a unique lifted Semidefinite Program (SDP), the solutions of which encode the entire set of Pareto-optimal extreme point solutions of any MOLP. This SDP problem can be solved, among other algorithms, by interior point methods; thus unlike an active set-method, our method provides a new approach to find the set of Pareto-optimal solutions of MOLP.     

Primal-Dual Simplex Method for Multiobjective Linear Programming

We develop a primal-dual simplex algorithm for multicriteria linear programming. It is based on the scalarization theorem of Pareto optimal solutions of multicriteria linear programs and the single objective primal-dual simplex algorithm. We illustrate the algorithm by an example, present some numerical results, give some further details on special cases and point out future research. The paper was written during a visit of the first author to the University of Sevilla financed by a grant of the Andalusian Consejería de Educación. The research of the first author was partially supported by University of Auckland Grant 3602178/9275. The research of the second and third authors was partially financed by Spanish Grants BFM2001-2378, BFM2001-4028, MTM2004-0909 and HA2003-0121. We thank Anthony Przybylski for the implementation and making his results available. We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper.     

A Solution Concept for Fuzzy Multiobjective Programming Problems Based on Convex Cones

A solution concept for fuzzy multiobjective programming problems based on ordering cones (convex cones) is proposed in this paper. The notions of ordering cones and partial orderings on a vector space are essentially equivalent. Therefore, the optimality notions in a real vector space can be elicited naturally by invoking a concept similar to that of the Pareto-optimal solution in vector optimization problems. We introduce a corresponding multiobjective programming problem and a weighting problem of the original fuzzy multiobjective programming problem using linear functionals so that the optimal solution of its corresponding weighting problem is also the Pareto-optimal solution of the original fuzzy multiobjective programming problem.     

多目标线性生产规划的模糊联盟对策

研究多目标生产规划的模糊联盟对策的求解问题,提出了求解多目标模糊联盟对策的Shapley值方法.通过建立多目标线性生产规划的模糊联盟对策模型,提出了多目标对策转化为多个单目标对策的权重分析法.结合多目标线性生产规划问题的实例,给出不同权重系数下局中人合作的利益分配策略.     

Stackelberg Solutions to Multiobjective Two-Level Linear Programming Problems

In this paper, we consider a multiobjective two-level linear programming problem in which the decision maker at each level has multiple-objective functions conflicting with each other. The decision maker at the upper level must take account of multiple or infinite rational responses of the decision maker at the lower level in the problem. We examine three kinds of situations based on anticipation of the decision maker at the upper level: optimistic anticipation, pessimistic anticipation, and anticipation arising from the past behavior of the decision maker at the lower level. Mathematical programming problems for obtaining the Stackelberg solutions based on the three kinds of anticipation are formulated and algorithms for solving the problems are presented. Illustrative numerical examples are provided to understand the geometrical properties of the solutions and demonstrate the feasibility of the proposed methods.     

An Interior Point Method for Linear Programming

In this paper we present an interior point method which solves a linear programming problem by using an affine transformation. We prove under certain assumptions that the algorithm converges to an optimal solution even if the dual problem is degenerate as long as the prime is bounded, or to a ray direction if the optimal value of the objective function is unbounded.     

不确定信息多目标线性优化的鲁棒方法

研究不确定信息的多目标线性优化问题,其数据不能精确给出但是属于一个给定的集合.首先,采用鲁棒方法把该问题转化为一个确定的多目标优化问题.然后,给出此问题解存在的充分条件.最后,通过实例验证了用鲁棒方法解决不确定信息的多目标线性优化问题的有效性.     

应用模糊目标规划方法求解多目标线性分式规划问题

针对多目标分式线性规划问题,提出利用上(下)界表示目标期望水平及允许上(下)限,且利用一阶泰勒公式逼近隶属函数,将多目标分式规划转化为线性规划问题,并用单纯形法求解,通过实验算例说明了所提出的方法的有效性.     

Outcome Space Partition of the Weight Set in Multiobjective Linear Programming

Approaches for generating the set of efficient extreme points of the decision set of a multiple-objective linear program (P) that are based upon decompositions of the weight set W⁰ suffer from one of two special drawbacks. Either the required computations are redundant, or not all of the efficient extreme point set is found. This article shows that the weight set for problem (P) can be decomposed into a partition based upon the outcome set Y of the problem, where the elements of the partition are in one-to-one correspondence with the efficient extreme points of Y. As a result, the drawbacks of the decompositions of W⁰ based upon the decision set of problem (P) disappear. The article explains also how this new partition offers the potential to construct algorithms for solving large-scale applications of problem (P) in the outcome space, rather than in the decision space.     

An Interval-Parameter Fuzzy Approach for Multiobjective Linear Programming Under Uncertainty

An interval-parameter fuzzy linear programming method (IFMOLP) is proposed in this study for multiple objective decision-making under uncertainty. As a hybrid of interval-parameter and fuzzy methodologies, the IFMOLP incorporates interval-parameter linear programming and fuzzy multiobjective programming approaches to form an integrated optimization system. The method inherits advantages of interval-parameter programming, and allows uncertainties and decision-makers’ aspirations to be effectively communicated into its programming processes and resulting solutions. Membership functions for both objectives and constraints are formulated to reflect uncertainties in different system components and their interrelationships. An interactive solution procedure has been developed based on solution approaches of the interval-parameter and fuzzy programming techniques, plus necessary measures for handling the multiobjective feature. A didactic example is provided in the paper to illustrate the detailed solution process. Possibilities of further improvements by seeking Pareto optimum and incorporating flexible preference within constraints are also discussed.     

线性约束多目标规划的非单调信赖域算法

本文对线性约束多规划问题提出了一类非单调信赖域算法 ,该方法是可行点法与信赖域技巧的结合 .在一定的条件下证明了算法的全局收敛性 .并进行了数值试验 .     

Properties of the Central Points in Linear Programming Problems

In this paper we list several useful properties of central points in linear programming problems. We study the logarithmic barrier function, the analytic center and the central path, relating the proximity measures and scaled Euclidean distances defined for the primal and primal–dual problems. We study the Newton centering steps, and show how large the short steps used in path following algorithms can actually be, and what variation can be ensured for the barrier function in each iteration of such methods. We relate the primal and primal–dual Newton centering steps and propose a primal-only path following algorithm for linear programming.     

局部凸空间上的泛函的非光滑分析及多目标规划

该文对定义于局部凸线性拓扑空间Ｘ上的泛函引入广义方向导数、广义梯度及满足Ｌｉｐｓ－ｃｈｉｔｚ条件等概念,证明了它们的几个重要性质,并举例说明这里满足Ｌｉｐｓｃｈｉｔｚ条件的概念是Ｂａ－ｎａｃｈ空间情形的严格推广．最后,作为上述结论及方法的应用,讨论定义于Ｘ的多目标数学规划,得出若干关于弱有效解的最优性条件．     

On a Commutative Class of Search Directions for Linear Programming over Symmetric Cones

The commutative class of search directions for semidefinite programming was first proposed by Monteiro and Zhang (Ref. 1). In this paper, we investigate the corresponding class of search directions for linear programming over symmetric cones, which is a class of convex optimization problems including linear programming, second-order cone programming, and semidefinite programming as special cases. Complexity results are established for short-step, semilong-step, and long-step algorithms. Then, we propose a subclass of the commutative class for which we can prove polynomial complexities of the interior-point method using semilong steps and long steps. This subclass still contains the Nesterov–Todd direction and the Helmberg–Rendl–Vanderbei–Wolkowicz/Kojima–Shindoh–Hara/Monteiro direction. An explicit formula to calculate any member of the class is also given.     

可能性与必要性测度性质及可能目标线性规划的模糊有效解关系 …

在文「１」基础上,深入研究了可能性与必要性测度的重要性质;通过反指出在一般情形下（Ａ,Ｂ至少有一个为严格模糊集合）由“ＮＡ（Ｂ）〉０”出发,得不出“πＡ（Ｂ）＝１”的结论;同时,论证了上述结论成立的条件,以此为基础,得到两种测度的相关定理。这样,便纠正了文「１」中的错误。接为研究了可能多目标规划问题中的两种解－必要有效解与可能有效解之间的关系,得到相应的关系定理。作为它的应用,我们给出三个实例。