均值-VaR模型的一种新解法：鞍点近似、遗传算法

以均值度量收益,方差度量风险的均值.方差模型,广泛应用于资产组合优化.随着对金融风险度量方法研究的不断深入,VaR作为一种简便、易于理解的风险度量方法,在金融企业中得到日益广泛的应用.本文用VaR代替均值-方差模型中的方差,构建了均值-VaR模型应用干投资组合优化.均值-VaR模型是非线性规划,仅当VaR满足凸性和可微性的前提下,满足库恩-塔克条件的解才是全局最优解.本文在CreditRisk+框架下,提出一个在不允许卖空条件下,不需对VaR的性质做出前提假定的新解法:将鞍点近似法用于计算VaR,在资产头寸与VaR之间建立起函数关系,采用遗传算法寻找模型的近似最优解.并用一个债券组合说明该方法的有效性。     

经典一维装箱问题近似算法的研究进展

自20世纪70年代开始,随着计算复杂性理论的建立,近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象,装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强,广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外,装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天,对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型,简述若干经典Fit算法的发展历程,分析基于线性规划松弛的近似方案的主要思路,总结当前的研究现状并对未来的研究提供一些参考建议。     

经典一维装箱问题近似算法的研究进展

自20世纪70年代开始,随着计算复杂性理论的建立,近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象,装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强,广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外,装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天,对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型,简述若干经典Fit算法的发展历程,分析基于线性规划松弛的近似方案的主要思路,总结当前的研究现状并对未来的研究提供一些参考建议。     

带约束条件集值优化问题近似Henig有效解集的连通性

研究了带约束条件集值优化问题近似Henig有效解集的连通性.在实局部凸Hausdorff空间中,讨论了可行域为弧连通紧的,目标函数为C-弧连通的条件下,带约束条件集值优化问题近似Henig有效解集的存在性和连通性.并给出了带约束条件集值优化问题近似Henig有效解集的连通性定理.     

一类凸优化的混合下降算法

邻近点算法(PPA)是一类求解凸优化问题的经典算法, 但往往需要精确求解隐式子问题,于是近似邻近点算法(APPA)在满足一定的近似规则下非精确求解PPA的子问题, 降低了求解难度. 本文利用近似规则的历史信息和随机数扩张预测校正步产生了两个方向, 通过随机数组合两个方向获得了一类凸优化的混合下降算法.在近似规则满足的情况下, 给出了混合下降算法的收敛性证明. 一系列的数值试验表明了混合下降算法的有效性和效率性.     

变分不等式的极大熵函数方法

利用极大熵函数方法将不等式组及变分不等式的求解问题转化为近似可微优化问题,给出了不等式组及变分不等式问题近似解的可微优化方法,得到了不等式组和变分不等式问题的解集合的示性函数.     

锥-次预不变凸集值优化问题近似解的最优性条件[英文]

本文讨论相依上图导数形式下广义锥-预不变集值优化近似解的最优性条件问题. 首先, 引入锥-次预不变凸集值映射的概念, 并举例说明次类广义锥-凸性是锥-预不变凸性的推广. 其次, 得到了锥-次预不变凸集值映射的两个有用性质. 最后, 在锥-次预不变凸性条件下, 分别建立了集值优化问题强近似极小元和弱近似有效元的充分最优性条件.     

锥-次预不变凸集值优化问题近似解的最优性条件(英文)

本文讨论相依上图导数形式下广义锥-预不变集值优化近似解的最优性条件问题.首先,引入锥-次预不变凸集值映射的概念,并举例说明次类广义锥-凸性是锥-预不变凸性的推广.其次,得到锥-次预不变凸集值映射的两个有用性质.最后,在锥-次预不变凸性条件下,分别建立集值优化问题强近似极小元和弱近似有效元的充分最优性条件.     

一类KdV非线性Schr(o)dinger组合微分方程组时间周期解的存在性

本文研究了一类KdV非线性Schr(o)dinger组合微分方程组时间周期解的问题,首先利用Galerkin方法构造近似时间周期解序列,然后利用先验估计和Leray-Schauder不动点原理,证明近似时间周期解序列的收敛性,从而得到该问题时间周期解的存在性.     

均值-方差-近似偏度投资组合模型和实证分析

均值-方差投资组合模型作为现代投资组合理论的基础, 采用方差作为风险度量,但忽略了投资组合收益的非对称性. 而考虑收益非对称性的基于偏度的投资组合模型由于非凸和非二次性 使模型难以求解. 本文提出用上下半方差的比值近似刻画偏度, 建立了均值-方差-近似偏度(MVAS）模型,并利用该模型对中国证券市场主要股票指数进行实证分析. 实证分析结果表明, 在收益率非正态分布的市场中,考虑了收益率非对称性的投资组合模型较传统的MV和MAD模型具有更优的表现.     

The Million-Variable “March” for Stochastic Combinatorial Optimization

Combinatorial optimization problems have applications in a variety of sciences and engineering. In the presence of data uncertainty, these problems lead to stochastic combinatorial optimization problems which result in very large scale combinatorial optimization problems. In this paper, we report on the solution of some of the largest stochastic combinatorial optimization problems consisting of over a million binary variables. While the methodology is quite general, the specific application with which we conduct our experiments arises in stochastic server location problems. The main observation is that stochastic combinatorial optimization problems are comprised of loosely coupled subsystems. By taking advantage of the loosely coupled structure, we show that decomposition-coordination methods provide highly effective algorithms, and surpass the scalability of even the most efficiently implemented backtracking search algorithms.     

An asymptotical study of combinatorial optimization problems by means of statistical mechanics

The analogy between combinatorial optimization and statistical mechanics has proven to be a fruitful object of study. Simulated annealing, a metaheuristic for combinatorial optimization problems, is based on this analogy. In this paper we show how a statistical mechanics formalism can be utilized to analyze the asymptotic behavior of combinatorial optimization problems with sum objective function and provide an alternative proof for the following result: Under a certain combinatorial condition and some natural probabilistic assumptions on the coefficients of the problem, the ratio between the optimal solution and an arbitrary feasible solution tends to one almost surely, as the size of the problem tends to infinity, so that the problem of optimization becomes trivial in some sense. Whereas this result can also be proven by purely probabilistic techniques, the above approach allows one to understand why the assumed combinatorial condition is essential for such a type of asymptotic behavior.     

求解非减上模集函数最小值问题的近似算法及其性能保证

上模集函数的优化问题在组合优化问题中有广泛应用,许多组合优化问题,如设备选址问题、p-中心问题等都可化为上模集函数的优化问题.本文给出了求解非减上模集函数最小值问题的一种近似算法,并讨论了所给算法的性能保证.     

Convex Combinatorial Optimization

We introduce the convex combinatorial optimization problem, a far-reaching generalization of the standard linear combinatorial optimization problem. We show that it is strongly polynomial time solvable over any edge-guaranteed family, and discuss several applications.     

一类组合优化函数的若干研究

本文研究了一个组合优化问题.利用组合数论的理论,给出了计算优化函数的一个新方法,并确定了4≤4m≤120时优化函数g(4m,6)的准确值,以及相心的优化向量.     

An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints

In this paper, we consider combinatorial optimization problems with additional cardinality constraints. In k-cardinality combinatorial optimization problems, a cardinality constraint requires feasible solutions to contain exactly k elements of a finite set E. Problems of this type have applications in many areas, e.g. in the mining and oil industry, telecommunications, circuit layout, and location planning. We formally define the problem, mention some examples and summarize general results. We provide an annotated bibliography of combinatorial optimization problems of which versions with cardinality constraint have been considered in the literature.     

A Tutorial on the Cross-Entropy Method

The cross-entropy (CE) method is a new generic approach to combinatorial and multi-extremal optimization and rare event simulation. The purpose of this tutorial is to give a gentle introduction to the CE method. We present the CE methodology, the basic algorithm and its modifications, and discuss applications in combinatorial optimization and machine learning.     

Applying GIS and Combinatorial Optimization to Fiber Deployment Plans

A decision-support system for the Fiber Deployment Plan problem is developed for the telephone cable network design in the telecommunications industry. The system employs a Geographic Information System (GIS) and uses combinatorial optimization techniques as its components. A mathematical combinatorial optimization model is formulated for the problem and a heuristic solution procedure is developed for the model. A GIS within the ESRI Arc/INFO and ArcView environment is used to provide data needed to build the mathematical combinatorial optimization model and to furnish an interface between the users and computers in data input and in solution result display. Combinatorial optimization techniques are used in the heuristic solution procedure to find good solutions for the optimization model. The developed decision-support system has been used to real life problems and has resulted in tremendous improvements in the telephone cable network design process. The user is completely satisfied with the performance of the system.     

Extension of M-Convexity and L-Convexity to Polyhedral Convex Functions

The concepts of M-convex and L-convex functions were proposed by Murota in 1996 as two mutually conjugate classes of discrete functions over integer lattice points. M/L-convex functions are deeply connected with the well-solvability in nonlinear combinatorial optimization with integer variables. In this paper, we extend the concept of M-convexity and L-convexity to polyhedral convex functions, aiming at clarifying the well-behaved structure in well-solved nonlinear combinatorial optimization problems in real variables. The extended M/L-convexity often appears in nonlinear combinatorial optimization problems with piecewise-linear convex cost. We investigate the structure of polyhedral M-convex and L-convex functions from the dual viewpoint of analysis and combinatorics and provide some properties and characterizations. It is also shown that polyhedral M/L-convex functions have nice conjugacy relationships.     

On the relation between complexity and uncertainty

In practical problem situations data are usually inherently unreliable. A mathematical representation of uncertainty leads to stochastic optimization problems. In this paper the complexity of stochastic combinatorial optimization problems is discussed. Surprisingly, certain stochastic versions of NP-hard determinstic combinatorial problems appear to be solvable in polynomial time.