连续型动态规划的新算法研究

提出了求解一维连续型动态规划问题的自创算法----离散近似迭代法,并结合双收敛方法求解多维连续型动态规划问题. 该算法的基本思路为：在给定其它状态向
量序列的基础上,每次对一个状态变量序列进行离散近似迭代,并找出该状态变量的最优序列,直到所有状态向量序列都检查完.当模型为非凸非凹动态规划时,
证明了该算法的收敛性.当模型为凸动态规划时,证明了该算法的线性收敛性. 最后,以一个具体算例验证了该模型和算法的有效性.     

均值—动态VaR多阶段投资组合优化研究

将动态风险度量方法运用到多阶段投资组合中,提出了具有交易成本和交易量限制的均值—动态VaR多阶段投资组合模型,并运用自创算法——离散近似迭代法求解.方法的基本思路为:首先,将模型中的连续型状态变量离散化,并将上述模型转化多阶段赋权有向图,然后,运用极大代数求出起点至终点的最长路程,即获得模型的一个可行解;最后,以该可行解为基础,继续迭代直到前后两个可行解非常接近.证明了该方法的收敛性,并以一个具体的算例,验证了该算法可以较快地计算出不同终期财富所对应的最优投资策略.     

多阶段均值-半绝对偏差模糊投资组合优化研究

考虑交易成本和交易量限制,提出投资组合的收益率的隶属函数为梯形的多阶段均值-半绝对偏差可能性投资组合模型,并用自创算法——离散近似迭代法求解.其基本思路为:将连续型状态变量离散化,根据网络图的构造方法将上述模型转化多阶段赋权有向图;运用极大代数求出起点至终点的最长路程,即获得模型的一个可行解;以该可行解为基础,继续迭代直到前后两个可行解非常接近.文章还证明了该方法的线性收敛.最后,文章以一个具体的算例验证了该算法的有效性.     

多阶段M-SV投资组合优化的离散近似迭代法研究

文章提出了离散近似迭代法,用该方法求解具有交易成本和交易量限制的多阶段均值一半方差(M-sV)投资组合模型.离散近似迭代方法的基本思路为:首先,将连续型状态变量离散化,根据网络图的构造方法将上述模型转化多阶段赋权有向图;其次,运用嘉量原理求出起点至终点的最长路程,即获得模型的一个可行解;最后,以该可行解为基础,继续迭代直到前后两个可行解非常接近.文章还证明了该方法的收敛性和复杂性.     

基于离散近似迭代法的多阶段M-V投资组合优化

提出了离散近似迭代方法,并用该方法求解具有交易成本和交易量限制的多阶段均值-方差(M-V)投资组合模型.离散近似迭代方法的基本思路为:首先,将连续型状态变量离散化,根据网络图的构造方法将上述模型转化多阶段赋权有向图;其次,运用嘉量原理求出起点至终点的最长路程,即获得模型的一个可行解;最后,以该可行解为基础,继续迭代直到前后两个可行解非常接近.还证明了该方法的收敛性和复杂性.     

离散变量结构优化设计的组合算法*

本文首先给出了离散变量优化设计局部最优解的定义,然后提出了一种综合的组合算法.该算法采用分级优化的方法,第一级优化首先采用计算效率很高且经过随机抽样性能实验表明性能较高的启发式算法─—相对差商法,求解离散变量结构优化设计问题近似最优解 X ;第二级采用组合算法,在 X 的离散邻集内建立离散变量结构优化设计问题的(-1,0.1)规划模型,再进一步将其化为(0,1)规划模型,应用定界组合算法或相对差商法求解该(0,1)规划模型,求得局部最优解.解决了采用启发式算法无法判断近似最优解是否为局部最优解这一长期未得到解决的问题,提高了计算精度,同时,由于相对差商法的高效率与高精度,以上综合的组合算法的计算效率也还是较高的.     

非线性背包问题的动态规划目标水平割算法

提出了求解非线性背包问题的一个动态规划目标水平割算法.通过引入替代约束公式将多约束问题转化为单个替代约束问题,由此结合目标水平割给出了一个收敛的动态规划算法,在解的过程中逐步消除对偶间隙,并确保在有限次迭代步内找到原问题的最优解.数值试验表明该方法的有效性.     

两端固定资源连续分配问题的区间根式解算法证明

对两端固定资源连续分配问题,动态规划解法过程复杂.针对目标函数及约束条件均为线性函数的此类问题,给出一个根式解的算法证明,将针对点的根式解的算法推广到区间的根式解,使该根式解的算法真正具有实用性.     

具有实际约束的多阶段M-V投资组合时间一致性策略研究

从动态规划的角度分析,方差算子的不可分离性导致标准的多阶段均值-方差模型的最优投资策略不满足时间一致性。文章采用条件期望映射的方法,构建了一个具有交易成本、借贷约束和阈值约束的多阶段M-V投资组合模型。由于考虑了交易成本,该模型是一个具有路径依赖性的动态优化问题。为了获得其时间一致性投资策略,文章将该问题近似地转化为连续性动态规划模型,证明最优解的近似度,并运用离散迭代算法求解。最后,使用上海证券交易所的部分历史数据验证了模型和算法的有效性。     

一个新的非线性整数规划问题的单参数填充函数算法

非线性整数规划问题是一类复杂的优化问题,填充函数算法是求解整数规划问题的一类有效方法.构造一个新的单参数填充函数,分析并证明了其填充性质;然后,基于该填充函数并结合离散最速下降法提出了一种新的填充函数算法;最后,采用新算法对6个测试函数进行数值实验,结果表明该算法具有良好的计算效果,是有效可行的.     

Output feedback stabilization for a class of nonlinear time-evolution systems

A variety of problems in nonlinear time-evolution systems such as communication networks, computer networks, manufacturing, traffic management, etc., can be modelled as min–max-plus systems in which operations of min, max and addition appear simultaneously. Systems with only maximum (or minimum) constraints can be modelled as max-plus system and handled by max-plus algebra which changes the original nonlinear system in the traditional sense into linear system in this framework. Min-max-plus systems are extensions of max-plus systems and nonlinear even in the max-plus algebra view. Output feedback stabilization for min–max-plus systems with min–max-plus inputs and max-plus outputs is considered in this paper. Max-plus projection representation for the closed-loop system with min–max-plus output feedback is introduced and the formula to calculate the cycle time is presented. Stabilization of reachable systems with at least one observable state and a further result for reachable and observable systems are worked out, during which max-plus output feedbacks are used to stabilize the systems. The method based on the max-plus algebra is constructive in nature.     

A property of the defining equations for the Lie algebra in the group classification problem for wave equations

We solve the group classification problem for nonlinear hyperbolic systems of differential equations. The admissible continuous group of transformations has the Lie algebra of dimension less than 5. This main statement follows from the principal property of the defining equations of the admissible Lie algebra: the commutator of two solutions is a solution. Using equivalence transformations we classify nonlinear systems in accordance with the well-known Lie algebra structures of dimension 3 and 4.     

A generalized eigenmode algorithm for reducible regular matrices over the max-plus algebra with applications to the Metro-bus public transport system in Mexico city

In this paper, an algorithm for computing a generalized eigenmode of reducible regular matrices over the max-plus algebra is applied to the Metro-bus public transport system in Mexico city. A timed event Petri net model is constructed from the data table that characterizes the transport system. A max-plus recurrence equation, with a reducible and regular matrix, is associated with the transport system timed event Petri net. Next, given the reducible and regular matrix, the problem consists of giving an algorithm which will tell us how to compute its generalized eigenmode over the max plus algebra. The solution to the problem is achieved by studying some type of recurrence equations. In fact, by transforming the reducible regular matrix into its normal form, and considering a very specific recurrence equation, an explicit mathematical characterization is obtained, upon which the algorithm is constructed. The generalized eigenmode obtained sets a timetable for the transport system.     

Min-Max Spaces and Complexity Reduction in Min-Max Expansions

Idempotent methods have been found to be extremely helpful in the numerical solution of certain classes of nonlinear control problems. In those methods, one uses the fact that the value function lies in the space of semiconvex functions (in the case of maximizing controllers), and approximates this value using a truncated max-plus basis expansion. In some classes, the value function is actually convex, and then one specifically approximates with suprema (i.e., max-plus sums) of affine functions. Note that the space of convex functions is a max-plus linear space, or moduloid. In extending those concepts to game problems, one finds a different function space, and different algebra, to be appropriate. Here we consider functions which may be represented using infima (i.e., min-max sums) of max-plus affine functions. It is natural to refer to the class of functions so represented as the min-max linear space (or moduloid) of max-plus hypo-convex functions. We examine this space, the associated notion of duality and min-max basis expansions. In using these methods for solution of control problems, and now games, a critical step is complexity-reduction. In particular, one needs to find reduced-complexity expansions which approximate the function as well as possible. We obtain a solution to this complexity-reduction problem in the case of min-max expansions.     

Max-Plus Algebra and Mathematical Fear in Dynamic Optimization

Max-plus algebra, cost measures, and mathematical fear have proved useful tools in dynamic optimization. Indeed, the first two have even become a central tool in some fields of investigation such as discrete event systems. We first recall the fundamentals of max-plus algebra with simple examples of max-plus linear models, and simple consequences of that remark. We then introduce cost measures, the natural equivalent of probability measures in the max-plus algebra, and their fundamental properties, including the definition of the mathematical fear (the equivalent of the mathematical expectation), induced measures and conditioning. Finally, we concentrate on those aspects that are put in use in dynamical optimization and state a separation theorem which was first derived using these tools.     

极大加可约矩阵的谱与周期时间向量的关系

提出了极大加代数上可约矩阵特征值的缺失值及冗余值的概念,得到了相应的定理;对特征值与周期时间向量分量之间的关系作了深入的研究.