基于鲁棒二阶随机占优的投资组合优化模型研究

本文主要考虑一类经典的含有二阶随机占优约束的投资组合优化问题,其目标为最大化期望收益,同时利用二阶随机占优约束度量风险,满足期望收益二阶随机占优预定的参考目标收益。与传统的二阶随机占优投资组合优化模型不同,本文考虑不确定的投资收益率,并未知其精确的概率分布,但属于某一不确定集合,建立鲁棒二阶随机占优投资组合优化模型,借助鲁棒优化理论,推导出对应的鲁棒等价问题。最后,采用S&P 500股票市场的实际数据,对模型进行不同训练样本规模和不确定集合下的最优投资组合的权重、样本内和样本外不确定参数对期望收益的影响的分析。结果表明,投资收益率在最新的历史数据规模下得出的投资策略,能够获得较高的样本外期望收益,对未来投资更具参考意义。在保证样本内解的最优性的同时,也能取得较高的样本外期望收益和随机占优约束被满足的可行性。     

Robustness to uncertain optimization using scalarization techniques and relations to multiobjective optimization

In this paper, we propose two kinds of robustness concepts by virtue of the scalarization techniques (Benson’s method and elastic constraint method) in multiobjective optimization, which can be characterized as special cases of a general non-linear scalarizing approach. Moreover, we introduce both constrained and unconstrained multiobjective optimization problems and discuss their relations to scalar robust optimization problems. Particularly, optimal solutions of scalar robust optimization problems are weakly efficient solutions for the unconstrained multiobjective optimization problem, and these solutions are efficient under uniqueness assumptions. Two examples are employed to illustrate those results. Finally, the connections between robustness concepts and risk measures in investment decision problems are also revealed.     

Minmax robustness for multi-objective optimization problems

In real-world applications of optimization, optimal solutions are often of limited value, because disturbances of or changes to input data may diminish the quality of an optimal solution or even render it infeasible. One way to deal with uncertain input data is robust optimization, the aim of which is to find solutions which remain feasible and of good quality for all possible scenarios, i.e., realizations of the uncertain data. For single objective optimization, several definitions of robustness have been thoroughly analyzed and robust optimization methods have been developed. In this paper, we extend the concept of minmax robustness (Ben-Tal, Ghaoui, & Nemirovski, 2009) to multi-objective optimization and call this extension robust efficiency for uncertain multi-objective optimization problems. We use ingredients from robust (single objective) and (deterministic) multi-objective optimization to gain insight into the new area of robust multi-objective optimization. We analyze the new concept and discuss how robust solutions of multi-objective optimization problems may be computed. To this end, we use techniques from both robust (single objective) and (deterministic) multi-objective optimization. The new concepts are illustrated with some linear and quadratic programming instances.     

Robust optimization for multiple responses using response surface methodology

Typically in the analysis of industrial data for product/process optimization, there are many response variables that are under investigation at the same time. Robustness is also an important concept in industrial optimization. Here, robustness means that the responses are not sensitive to the small changes of the input variables. However, most of the recent work in industrial optimization has not dealt with robustness, and most practitioners follow up optimization calculations without consideration for robustness. This paper presents a strategy for dealing with robustness and optimization simultaneously for multiple responses. In this paper, we propose a robustness desirability function distinguished from the optimization desirability function and also propose an overall desirability function approach, which makes balance between robustness and optimization for multiple response problems. Simplex search method is used to search for the most robust optimal point in the feasible operating region. Finally, the proposed strategy is illustrated with an example from the literature. Copyright © 2009 John Wiley & Sons, Ltd.     

A robust optimization approach to closed-loop supply chain network design under uncertainty

The concern about significant changes in the business environment (such as customer demands and transportation costs) has spurred an interest in designing scalable and robust supply chains. This paper proposes a robust optimization model for handling the inherent uncertainty of input data in a closed-loop supply chain network design problem. First, a deterministic mixed-integer linear programming model is developed for designing a closed-loop supply chain network. Then, the robust counterpart of the proposed mixed-integer linear programming model is presented by using the recent extensions in robust optimization theory. Finally, to assess the robustness of the solutions obtained by the novel robust optimization model, they are compared to those generated by the deterministic mixed-integer linear programming model in a number of realizations under different test problems.     

New models for the robust shortest path problem: complexity, resolution and generalization

In optimization, it is common to deal with uncertain and inaccurate factors which make it difficult to assign a single value to each parameter in the model. It may be more suitable to assign a set of values to each uncertain parameter. A scenario is defined as a realization of the uncertain parameters. In this context, a robust solution has to be as good as possible on a majority of scenarios and never be too bad. Such characterization admits numerous possible interpretations and therefore gives rise to various approaches of robustness. These approaches differ from each other depending on models used to represent uncertain factors, on methodology used to measure robustness, and finally on analysis and design of solution methods. In this paper, we focus on the application of a recent criterion for the shortest path problem with uncertain arc lengths. We first present two usual uncertainty models: the interval model and the discrete scenario set model. For each model, we then apply a criterion, called bw-robustness (originally proposed by B. Roy) which defines a new measure of robustness. According to each uncertainty model, we propose a formulation in terms of large scale integer linear program. Furthermore, we analyze the theoretical complexity of the resulting problems. Our computational experiments perform on a set of large scale graphs. By observing the results, we can conclude that the approved solvers, e.g. Cplex, are able to solve the mathematical models proposed which are promising for robustness analysis. In the end, we show that our formulations can be applied to the general linear program in which the objective function includes uncertain coefficients.     

A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization

We propose a polynomial-time-delay polynomial-space algorithm to enumerate all efficient extreme solutions of a multi-criteria minimum-cost spanning tree problem, while only the bi-criteria case was studied in the literature. The algorithm is based on the reverse search framework due to Avis and Fukuda. We also show that the same technique can be applied to the multi-criteria version of the minimum-cost basis problem in a (possibly degenerated) submodular system. As an ultimate generalization, we propose an algorithm to enumerate all efficient extreme solutions of a multi-criteria linear program. When the given linear program has no degeneracy, the algorithm runs in polynomial-time delay and polynomial space. To best of our knowledge, they are the first polynomial-time delay and polynomial-space algorithms for the problems.     

A cooperative swarm intelligence algorithm for multi-objective discrete optimization with application to the knapsack problem

We propose a novel cooperative swarm intelligence algorithm to solve multi-objective discrete optimization problems (MODP). Our algorithm combines a firefly algorithm (FA) and a particle swarm optimization (PSO). Basically, we address three main points: the effect of FA and PSO cooperation on the exploration of the search space, the discretization of the two algorithms using a transfer function, and finally, the use of the epsilon dominance relation to manage the size of the external archive and to guarantee the convergence and the diversity of Pareto optimal solutions.We compared the results of our algorithm with the results of five well-known meta-heuristics on nine multi-objective knapsack problem benchmarks. The experiments show clearly the ability of our algorithm to provide a better spread of solutions with a better convergence behavior.     

Sequential Semidefinite Program for Maximum Robustness Design of Structures under Load Uncertainty

A robust structural optimization scheme as well as an optimization algorithm are presented based on the robustness function. Under the uncertainties of the external forces based on the info-gap model, the maximization of the robustness function is formulated as an optimization problem with infinitely many constraints. By using the quadratic embedding technique of uncertainty and the S-procedure, we reformulate the problem into a nonlinear semidefinite programming problem. A sequential semidefinite programming method is proposed which has a global convergent property. It is shown through numerical examples that optimum designs of various linear elastic structures can be found without difficulty.The authors are grateful to the Associate Editor and two anonymous referees for handling the paper efficiently as well as for helpful comments and suggestions.     

Local and variable neighborhood search for the <Emphasis Type="Italic">k</Emphasis>-cardinality subgraph problem

The minimum weighted k-cardinality subgraph problem consists of finding a connected subgraph of a given graph with exactly k edges whose sum of weights is minimum. For this NP-hard combinatorial problem, only constructive types of heuristics have been suggested in the literature. In this paper we propose a new heuristic based on variable neighborhood search metaheuristic rules. This procedure uses a new local search developed by us. Extensive numerical results that include graphs with up to 5,000 vertices are reported. It appears that VNS outperforms all previous methods.     

A unified approach for different concepts of robustness and stochastic programming via non-linear scalarizing functionals

Abstract

We show that many different concepts of robustness and of stochastic programming can be described as special cases of a general non-linear scalarization method by choosing the involved parameters and sets appropriately. This leads to a unifying concept which can be used to handle robust and stochastic optimization problems. Furthermore, we introduce multiple objective (deterministic) counterparts for uncertain optimization problems and discuss their relations to well-known scalar robust optimization problems by using the non-linear scalarization concept. Finally, we mention some relations between robustness and coherent risk measures.     

Restricted Robust Uniform Matroid Maximization Under Interval Uncertainty

For the problem of selecting p items with interval objective function coefficients so as to maximize total profit, we introduce the r-restricted robust deviation criterion and seek solutions that minimize the r-restricted robust deviation. This new criterion increases the modeling power of the robust deviation (minmax regret) criterion by reducing the level of conservatism of the robust solution. It is shown that r-restricted robust deviation solutions can be computed efficiently. Results of experiments and comparisons with absolute robustness, robust deviation and restricted absolute robustness criteria are reported. This work is supported by a grant from Turkish Academy of Science(TUBA).     

到达不确定呼叫中心人员配置的鲁棒优化模型

针对呼叫中心实际运营中顾客到达不确定的特点,采用鲁棒离散优化方法,建立呼叫中心人员配置的鲁棒模型。利用对偶原理将鲁棒模型转换易于求解的线性鲁棒对等式,通过调节模型中的鲁棒参数来权衡鲁棒解的保守性与最优性之间的关系,计算模型中约束违背概率上限来表示鲁棒解的可靠性。通过现实呼叫中心数据算例,验证了模型的有效性,分析了不同鲁棒水平下各时间段服务人员配置规律,以及系统最小成本与违背概率之间的权衡关系。最后,对到达扰动系数进行了敏感性分析。     

A Hybrid Improvement Heuristic for the One-Dimensional Bin Packing Problem

We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several features: the use of lower bounding strategies; the generation of initial solutions by reference to the dual min-max problem; the use of load redistribution based on dominance, differencing, and unbalancing; and the inclusion of an improvement process utilizing tabu search. Encouraging results have been obtained for a very wide range of benchmark instances, illustrating the robustness of the algorithm. The hybrid improvement procedure compares favourably with all other heuristics in the literature. It improved the best known solutions for many of the benchmark instances and found the largest number of optimal solutions with respect to the other available approximate algorithms.     

On robust optimization of two-stage systems

Robust-optimization models belong to a special class of stochastic programs, where the traditional expected cost minimization objective is replaced by one that explicitly addresses cost variability. This paper explores robust optimization in the context of two-stage planning systems. We show that, under arbitrary measures for variability, the robust optimization approach might lead to suboptimal solutions to the second-stage planning problem. As a result, the variability of the second-stage costs may be underestimated, thereby defeating the intended purpose of the model. We propose sufficient conditions on the variability measure to remedy this problem. Under the proposed conditions, a robust optimization model can be efficiently solved using a variant of the L-shaped decomposition algorithm for traditional stochastic linear programs. We apply the proposed framework to standard stochastic-programming test problems and to an application that arises in auctioning excess electric power. Mathematics Subject Classification (1991):90C15, 90C33, 90B50, 90A09, 90A43Supported in part by NSF Grants DMI-0099726 and DMI-0133943     

基于不确定需求的鲁棒应急物流系统

近年来各类突发事件和灾难频发,严重威胁到人们的生命安全,给人们经济生活带来了巨大的影响.灾难发生后,应急物流系统的效率是救援展开的保证.分析了应急物流系统的特点,采用鲁棒规划建立数学模型解决了应急物资需求不确定下如何进行应急配送中心选址和配送计划的安排,使得我们的决策能够体现最优性与鲁棒性的均衡.数值实验表明,建立的模型是符合实际的,数值结果具有较好的鲁棒性.     

A Trust Region Target Value Method for Optimizing Nondifferentiable Lagrangian Duals of Linear Programs

In this paper, we design a new variable target value procedure, the trust region target value (TRTV) method, for optimizing nondifferentiable Lagrangian dual formulations of large-scale, ill-conditioned linear programming problems. Such problems typically arise in the context of Lagrangian relaxation approaches and branch-and-bound/cut algorithms for solving linear mixed-integer programs. Subgradient optimization strategies are well-suited for this purpose and are popularly used, particularly in Lagrangian relaxation contexts, because of their simplicity in computation and mild memory requirements. However, they lack robustness and can often stall while yet remote from optimality. With this motivation, we design our proposed TRTV method to retain simplicity in computations, be theoretically convergent, as well as yield an effective and robust performance in practice. Furthermore, we augment this approach with dual refinement and primal recovery procedures based on outer-linearization and trust region strategies to further improve the accuracy of the resulting solutions and to derive primal solutions as well. Our computational study reveals a highly competitive performance of the proposed TRTV algorithm among several implemented nondifferentiable optimization procedures. Moreover, the dual refinement and primal recovery procedures help further reduce the optimality gap and promote attaining a relatively greater degree of primal feasibility as compared with several alternative ergodic primal recovery schemes. Also, the proposed method displays significantly lesser computational requirement than that of a commercial linear programming solver CPLEX.This research has been supported by the National Science Foundation under Grant Number DMI-0094462.     

Strategies of node selection in search procedures for solving combinatorial optimization problems: A survey and a general formalization

Currently, most combinatorial optimization problems have to be solved, if the optimum solution is sought, using general techniques to explore the space of feasible solutions and, more specifically, through exploratory enumerative procedures in trees and search graphs. The objective of this work is to propose a survey and a general formalization of the selection strategy of the next node to explore, a feature that is common to all these optimization procedures. This research has been partially supported by TAP98-0494 project     

Robustness in stochastic programs with risk constraints

This paper is a contribution to the robustness analysis for stochastic programs whose set of feasible solutions depends on the probability distribution?P. For various reasons, probability distribution P may not be precisely specified and we study robustness of results with respect to perturbations of?P. The main tool is the contamination technique. For the optimal value, local contamination bounds are derived and applied to robustness analysis of the optimal value of a portfolio performance under risk-shaping CVaR constraints. A?new robust portfolio efficiency test with respect to the second order stochastic dominance criterion is suggested and the contamination methodology is exploited to analyze its resistance with respect to additional scenarios.