A Bilinear Algorithm for Optimizing a Linear Function over the Efficient Set of a Multiple Objective Linear Programming Problem

The problem Q of optimizing a linear function over the efficient set of a multiple objective linear program serves several useful purposes in multiple criteria decision making. However, Q is in itself a difficult global optimization problem, whose local optima, frequently large in number, need not be globally optimal. Indeed, this is due to the fact that the feasible region of Q is, in general, a nonconvex set. In this paper we present a monotonically increasing algorithm that finds an exact, globally-optimal solution for Q. Our approach does not require any hypothesis on the boundedness of neither the efficient set EP nor the optimal objective value. The proposed algorithm relies on a simplified disjoint bilinear program that can be solved through the use of well-known specifically designed methods within nonconvex optimization. The algorithm has been implemented in C and preliminary numerical results are reported.     

证券数增加情形下证券组合有效边缘特征灵敏度分析

本文较为详细地讨论了当证券市场不存在无风险收益证券且允许卖空时证券数的增加对 M-V证券组合有效边缘及其特征的影响 ,给出了有效边缘、渐近线斜率、全局最小方差证券组合及其协方差、最小方差证券组合的投资权数等的变化模式     

Exponential Transformation in Convexifying a Noninferior Frontier and Exponential Generating Method

The convexification of a noninferior frontier can be achieved in an appropriate equivalent objective space for general nonconvex multiobjective optimization problems. Specifically, this paper proves that taking the exponentials of the objective functions can act as a convexification scheme. This convexification scheme further leads to the exponential generating method that guarantees the identification of the entire set of noninferior solutions.     

Convexification of a Noninferior Frontier

In a recent paper by Li (Ref. 1), a scheme was proposed to convexify an efficient frontier for a vector optimization problem by rescaling each component of the vector objective functions by its p-power. For sufficiently large p, it was shown that the transformed efficient frontier is cone-convex; hence, the usual linear scalarization (or supporting hyperplane) method can be used to find the efficient solutions. An outstanding question remains: What is the minimum value of p such that the efficient frontier can be convexified? In this note, we answer the above question by deriving some theoretical lower bounds for p.

     

Optimizing a linear function over an efficient set

The problem (P) of optimizing a linear functiond ^T x over the efficient set for a multiple-objective linear program (M) is difficult because the efficient set is typically nonconvex. Given the objective function directiond and the set of domination directionsD, ifd ^T 0 for all nonzero D, then a technique for finding an optimal solution of (P) is presented in Section 2. Otherwise, given a current efficient point , if there is no adjacent efficient edge yielding an increase ind ^T x, then a cutting plane is used to obtain a multiple-objective linear program ( ) with a reduced feasible set and an efficient set . To find a better efficient point, we solve the problem (I_i) of maximizingc _i ^T x over the reduced feasible set in ( ) sequentially fori. If there is a that is an optimal solution of (I_i) for somei and , then we can choosex ⁱ as a current efficient point. Pivoting on the reduced feasible set allows us to find a better efficient point or to show that the current efficient point is optimal for (P). Two algorithms for solving (P) in a finite sequence of pivots are presented along with a numerical example.The authors would like to thank an anonymous referee, H. P. Benson, and P. L. Yu for numerous helpful comments on this paper.     

双层线性分式规划求顶点的算法

基于双层线性分式规划的性质,讨论了上层不带约束的双层线性分式规划模型,给出了求其所有顶点的算法.此算法为进一步进行双层线性分式规划的灵敏度分析打下了坚实的基础,通过例子对算法进行了检验,并利用结果进行了灵敏度分析.     

Necessary conditions for nonlinear suboptimization over the weakly-efficient set

The optimization problem of a nonlinear real function over the weakly-efficient set associated to a nonlinear multi-objective program is examined. Necessary first-order conditions for a suboptimal solution are proposed, assuming the convexity of the multi-objective program. Estimations of the optimal value are established and an algorithm for finding suboptimal solutions is proposed. The optimal value is approximated to any prescribed degree of accuracy using a weakly-efficient suboptimal solution.This work was done while the author was preparing his Ph.D. Thesis at the University of Melbourne, Australia. The author is thankful to Dr. B. D. Craven for his suggestions and helpful discussions and to Professor W. Stadler and the anonymous referees for their helpful comments and corrections.     

基于不确定性期望效用模型的投资优化

针对资产的收益的分布不确切知道,并且所获得的矩信息也不是准确值的问题,提出了最大化最坏情形期望效用的鲁棒性方法.引入了凹凸类效用函数来度量模型不确定情形下投资者的效用,用一个不确定性结构来刻画资产收益的所有可能的分布和收益的矩信息,通过把具有不确定性结构的鲁棒性模型转化成参数二次规划问题,得到了最优投资策略、有效前沿和均衡价格的解析表示.方法为采用保守策略并且厌恶不确定性的投资者提供了一种有效的投资决策方案.     

A Unified Monotonic Approach to Generalized Linear Fractional Programming

We present an efficient unified method for solving a wide class of generalized linear fractional programming problems. This class includes such problems as: optimizing (minimizing or maximizing) a pointwise maximum or pointwise minimum of a finite number of ratios of linear functions, optimizing a sum or product of such ratios, etc. – over a polytope. Our approach is based on the recently developed theory of monotonic optimization.     

Solving Sum of Ratios Fractional Programs via Concave Minimization

This article presents an algorithm for globally solving a sum of ratios fractional programming problem. To solve this problem, the algorithm globally solves an equivalent concave minimization problem via a branch-and-bound search. The main work of the algorithm involves solving a sequence of convex programming problems that differ only in their objective function coefficients. Therefore, to solve efficiently these convex programming problems, an optimal solution to one problem can potentially be used to good advantage as a starting solution to the next problem.     

Branch-and-Bound Variant of an Outcome-Based Algorithm for Optimizing over the Efficient Set of a Bicriteria Linear Programming Problem

The paper presents a finite branch-and-bound variant of an outcome-based algorithm proposed by Benson and Lee for minimizing a lower-semicontinuous function over the efficient set of a bicriteria linear programming problem. Similarly to the Benson-Lee algorithm, we work primarily in the outcome space. Dissimilarly, instead of constructing a sequence of consecutive efficient edges in the outcome space, we use the idea of generating a refining sequence of partitions covering the at most two-dimensional efficient set in the outcome space. Computational experience is also presented.     

Range sets for weak efficiency in multiobjective linear programming and a parametric polytopes intersection problem

ABSTRACT

The aim of this paper is to obtain the range set for a given multiobjective linear programming problem and a weakly efficient solution. The range set is the set of all values of a parameter such that a given weakly efficient solution remains efficient when the objective coefficients vary in a given direction. The problem was originally formulated by Benson in 1985 and left to be solved. We formulate an algorithm for determining the range set, based on some hard optimization problems. Due to toughness of these optimization problems, we propose also lower and upper bound approximation techniques. In the second part, we focus on topological properties of the range set. In particular, we prove that a range set is formed by a finite union of intervals and we propose upper bounds on the number of intervals. Our approach to tackle the range set problem is via the intersection problem of parametric polytopes. Thus, our results have much wider area of applicability since the intersection (and separability) problem of convex polyhedra is important in many fields of optimization.     

中国上市建筑企业规模经济和范围经济评价——一种随机边界成本函数方法

目前对于企业规模经济和范围经济的研究大多数是在不存在X无效的假设下进行的。即认为企业始终是在它们的有效边界内的,因此对企业规模经济和范围经济的实证研究也都是X有效的前提下的。本文试图采用一种成本非有效的随机边界成本函数,建立广义超越对数成本函数模型对企业规模经济和范围经济进行评价。数据来源于深沪两市建筑业板块25家上市公司2003-2007年的年度报告。研究结果表明:我国上市建筑企业中同时存在着规模不经济和范围不经济,而不存在X无效性假设条件下的估计结果使得规模经济值被提高。     

Second-Order Efficiency Conditions and Sensitivity of Efficient Points

The paper deals with necessary and sufficient efficiency conditions of first and second order in vector differential optimization in Banach spaces. The conditions presented ensure the Fréchet sensitivity of efficient (Pareto) points for a perturbed problem. In finite dimension, weaker conditions ensure the Lipschitz sensitivity and existence of directional derivatives of perturbed efficient points.     

基于改进基线算法的线性规划灵敏度问题研究

针对基线算法由于计算方面的无记忆性而在线性规划灵敏度方面的难实现问题,提出了改进的基线算法,并分别讨论了在价值系数C、技术系数矩阵A及资源向量b等各种情况发生变化的条件下,如何采用改进的基线算法进行灵敏度分析,从而能够简便、快捷的获得新的最优解.最后通过实例进行了说明.     

使决策单元变为DEA有效的偏差和最小法

某决策单元为非 DEA有效 ( C2 R或 C2 GS2 ) ,为了将它变为 DEA有效 ,在找出其对应点附近的一些有效前沿面的基础上 ,给出了使其对应点与这些有效前沿面上的点的输入、输出的偏差和最小的方法 .     

线性规划影子价格的求解判断方法探讨

针对线性规划对偶问题最优解不唯一时,在已有文献提出的对偶最优解不唯一的充要条件定理基础上,结合线性规划灵敏度分析,提出影子价格的求解判断的简单准则及其命题,并进行证明.最后,用算例加以分析,指出该判断方法简单易行,也可作为通过计算软件求解影子价格的准确判断方法.     

有关Pareto解在DEA中的应用的探讨

对文[1]中有关DEA有效(C2R)的定理4,本文给出了在某种条件下的逆定理,以便简化DEA有效性(C2R)的判断.     

An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem

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, some researchers in recent years have suggested that outcome set-based approaches should instead be developed and used to solve problem (MOLP). In this article, we present a finite algorithm, called the Outer Approximation Algorithm, for generating the set of all efficient extreme points in the outcome set of problem (MOLP). To our knowledge, the Outer Approximation Algorithm is the first algorithm capable of generating this set. As a by-product, the algorithm also generates the weakly efficient outcome set of problem (MOLP). Because it works in the outcome set rather than in the decision set of problem (MOLP), the Outer Approximation Algorithm has several advantages over decision set-based algorithms. It is also relatively easy to implement. Preliminary computational results for a set of randomly-generated problems are reported. These results tangibly demonstrate the usefulness of using the outcome set approach of the Outer Approximation Algorithm instead of a decision set-based approach. This revised version was published online in July 2006 with corrections to the Cover Date.