Continuous-time mean variance portfolio with transaction costs: a proximal approach involving time penalization

This paper proposes a new continuous-time optimization solution that enables the computation of the portfolio problem (based on the utility option pricing and the shortfall risk minimization). We first propose a dynamical stock price process, and then, we transform the solution to a continuous-time discrete-state Markov decision processes. The market behavior is characterized by considering arbitrage-free and assessing transaction costs. To solve the problem, we present a proximal optimization approach, which considers time penalization in the transaction costs and the utility. In order to include the restrictions of the market, as well as those that imposed by the continuous-time space, we employ the Lagrange multipliers approach. As a result, we obtain two different equations: one for computing the portfolio strategies and the other for computing the Lagrange multipliers. Each equation in the portfolio is an optimization problem, for which the necessary condition of a maximum/minimum is solved employing the gradient method approach. At each step of the iterative proximal method, the functional increases and finally converges to a final portfolio. We show the convergence of the method. A numerical example showing the effectiveness of the proposed approach is also developed and presented.     

Quadratic programming algorithms for large-scale model predictive control

Quadratic programming (QP) methods are an important element in the application of model predictive control (MPC). As larger and more challenging MPC applications are considered, more attention needs to be focused on the construction and tailoring of efficient QP algorithms. In this study, we tailor and apply a new QP method, called QPSchur, to large MPC applications, such as cross directional control problems in paper machines. Written in C++, QPSchur is an object oriented implementation of a novel dual space, Schur complement algorithm. We compare this approach to three widely applied QP algorithms and show that QPSchur is significantly more efficient (up to two orders of magnitude) than the other algorithms. In addition, detailed simulations are considered that demonstrate the importance of the flexible, object oriented construction of QPSchur, along with additional features for constraint handling, warm starts and partial solution.     

Large scale portfolio optimization with piecewise linear transaction costs

We consider the fundamental problem of computing an optimal portfolio based on a quadratic mean-variance model for the objective function and a given polyhedral representation of the constraints. The main departure from the classical quadratic programming formulation is the inclusion in the objective function of piecewise linear, separable functions representing the transaction costs. We handle the non-smoothness in the objective function by using spline approximations. The problem is first solved approximately using a primal-dual interior-point method applied to the smoothed problem. Then, we crossover to an active set method applied to the original non-smooth problem to attain a high accuracy solution. Our numerical tests show that we can solve large scale problems efficiently and accurately.     

基于改进粒子群算法的投资组合选择模型

研究了在实际投资决策中存在交易成本(税收和交易费用)和投资数量约束下的投资组合选择问题,并进一步设计了一种求解该问题的改进粒子群算法.最后,给出了一个数值例子,说明该模型和方法的有效性.     

A novel approach to multiparametric quadratic programming

Multiparametric (mp) programming pre-computes optimal solutions offline which are functions of parameters whose values become apparent online. This makes it particularly well suited for applications that need a rapid solution of online optimization problems. In this work, we propose a novel approach to multiparametric programming problems based on an enumeration of active sets and use it to obtain a parametric solution for a convex quadratic program (QP). To avoid the combinatorial explosion of the enumeration procedure, an active set pruning criterion is presented that makes the enumeration implicit. The method guarantees that all regions of the partition are critical regions without any artificial cuts, and further that no region of the parameter space is left unexplored.     

The quadratic programming problem with fuzzy relation inequality constraints

The quadratic programming has been widely applied to solve real world problems. The quadratic functions are often applied in the inventory management, portfolio selection, engineering design, molecular study, and economics, etc. Fuzzy relation inequalities (FRI) are important elements of fuzzy mathematics, and they have recently been widely applied in the fuzzy comprehensive evaluation and cybernetics. In view of the importance of quadratic functions and FRI, we present a fuzzy relation quadratic programming model with a quadratic objective function subject to the max-product fuzzy relation inequality constraints. Some sufficient conditions are presented to determine its optimal solution in terms of the maximum solution or the minimal solutions of its feasible domain. Also, some simplification operations have been given to accelerate the resolution of the problem by removing the components having no effect on the solution process. The simplified problem can be converted into a traditional quadratic programming problem. An algorithm is also proposed to solve it. Finally, some numerical examples are given to illustrate the steps of the algorithm.     

Sharpe-ratio pricing and hedging of contingent claims in incomplete markets by convex programming

We analyze the problem of pricing and hedging contingent claims in a financial market described by a multi-period, discrete-time, finite-state scenario tree using an arbitrage-adjusted Sharpe-ratio criterion. We show that the writer’s and buyer’s pricing problems are formulated as conic convex optimization problems which allow to pass to dual problems over martingale measures and yield tighter pricing intervals compared to the interval induced by the usual no-arbitrage price bounds. An extension allowing proportional transaction costs is also given. Numerical experiments using S&P 500 options are given to demonstrate the practical applicability of the pricing scheme.     

有交易费的未定权益无套利套期保值定价

针对多种股票参与交易的市场,利用折算函数衡量总资产,给出了有交易费市场情形下的套利机会定义和基本性质,进而利用辅助鞅方法和凸分析方法,得到了套期保值策略的无套利性质和未定权益的套期保值定价公式.     

求解一类特殊的双层规划问题的遗传算法

主要研究上层函数及其约束函数不要求具有凸性和可微性,下层是关于下层决策变量是凸二次规划的双层规划模型,通过Karush-Kuhn-Tucher 条件转化为一个单层规划,利用下层是正定二次规划,将下层的决策变量表示为关于 Lagrangian乘子的表达式,从而降低了搜索空间的维数,设计了遗传算法,并通过数值实验表明该遗传算非常有效。     

基于SQP局部搜索的蝙蝠优化算法

针对基本蝙蝠算法存在寻优精度不高,后期收敛速度较慢和易陷入局部最优等问题,提出一种基于序贯二次规划（Sequential Quadratic Programming,SQP）的蝙蝠优化算法。该算法应用佳点集理论构造初始种群,增强了初始种群的遍历性;为避免算法陷入早熟收敛,引入柯西变异算子对种群中精英个体进行变异操作,增加种群多样性;在迭代后期,对最优个体进行SQP局部搜索,提高蝙蝠算法的局部深度搜索能力,保证个体在靠近全局最优值时能够寻优到全局最优解,加快种群进化速度。通过仿真实验结果证明,改进后的蝙蝠算法性能优越,具有良好的寻优精度和收敛速度。     

机器人路径规划的多目标二次优化方法

基于多目标进化算法的机器人路径规划问题存在求解速度慢的不足,为提高求解效率,提出了一种多目标二次优化方法(MOQO)。在MOQO方法中首先引入二次优化的思想,通过离线的全局优化为在线的局部优化提供一个次优的初始解集,以更有效利用全局优化过程的先验信息和进化信息,从而加速后期的局部优化操作;其次,在MOQO方法中还提出了一种改进的多目标进化算法PPMOEA,以进一步提高优化求解的实时性能。最终的机器人路径规划仿真实验测试了MOQO方法对进化求解操作的加速效果,证明了方法的有效性和可行性。     

基于二次粒子群算法的投资组合优化

投资组合优化问题是一个复杂的组合优化问题,属于NP难问题,传统算法很难解决这一问题。将二次粒子群算法应用到投资组合优化问题中,并采用参数的自适应变化。数值模拟表明该算法在投资组合优化问题中能避免陷入局部最优,加快达到全局最优的收敛速度,并在一定意义下优于标准粒子群算法。     

一种自适应程序设计方法

当前的程序设计都是人工设计执行流程,这种方法具有被动性、机械性、缺乏灵活性等缺点。提出一种基于强化学习的程序设计机制,并实现了相应的算法。根据环境情况和问题要求让计算机自主选择执行流程,通过学习使结果达到最优,同时能实现分层调用。采用这种方法,程序执行可以自主决策,较好地实现了自适应,减少了对设计者的依赖。结果显示,这种方法能取得较好的运行效率。     

一类特殊凸二次双层规划的算法

根据值型凸二次双层规划的Johri对偶理论,讨论一类特殊双层规划——上层仅含一个不等式约束的非减值型线性．凸二次双层规划的办法,通过把对其Johri对偶规划的求解转化为对有限个凸二次规划的求解,给出求解该类双层规划的一种多项式时间算法。     

基于VC++和FORTRAN混合编程的优化系统设计

用VC＋＋和FORTRAN语言混合编程的方法进行优化系统的设计,不但可以方便地进行优化算法的设计和友好的人机界面设计,还能够实现并行地进行软件系统的开发,可以有效地缩短程序设计时间.对外壳函数调用FORTRAN生成的可执行文件时系统出现的异步执行问题和“黑屏”问题提出了解决办法,最后给出了优化系统的设计实例,验证了该方法的可行性和有效性.     

Using quadratic programming to solve high multiplicity scheduling problems on parallel machines

We introduce and analyze several models of schedulingn different types (groups) of jobs onm parallel machines, where in each group all jobs are identical. Our main goal is to exhibit the usefulness of quadratic programming approaches to solve these classes of high multiplicity scheduling problems, with the total weighted completion time as the minimization criterion. We develop polynomial algorithms for some models, and strongly polynomial algorithms for certain special cases. In particular, the model in which the weights are job independent, as well as the generally weighted model in which processing requirements are job independent, can be formulated as an integer convex separable quadratic cost flow problem, and therefore solved in polynomial time. When we specialize further, strongly polynomial bounds are achievable. Specifically, for the weighted model with job-independent processing requirements if we restrict the weights to be machine independent (while still assuming different machine speeds), anO(mn+n logn) algorithm is developed. If it is also assumed that all the machines have the same speed, the complexity of the algorithm can be improved toO(m logm+n logn). These results can be extended to related unweighted models with variable processing requirements in which all the machines are available at time zero. The research of Frieda Granot was partially supported by Natural Sciences and Engineering Research Council of Canada Grant 5-83998. The research of Jadranka Skorin-Kapov was partially supported by National Science Foundation Grant DDM-8909206.     

A Hybrid approach for integer programming combining genetic algorithms, linear programming and ordinal optimization

Hybrid methods are promising tools in integer programming, as they combine the best features of different methods in a complementary fashion. This paper presents such a framework, integrating the notions of genetic algorithm, linear programming, and ordinal optimization in an effort to shorten computation times for large and/or difficult integer programming problems. Capitalizing on the central idea of ordinal optimization and on the learning capability of genetic algorithms to quickly generate good feasible solutions, and then using linear programming to solve the problem that results from fixing the integer part of the solution, one may be able to obtain solutions that are close to optimal. Indeed ordinal optimization guarantees the quality of the solutions found. Numerical testing on a real-life complex scheduling problem demonstrates the effectiveness and efficiency of this approach.     

Linear programming based approximation algorithms for feedback set problems in bipartite tournaments

We consider the feedback vertex set and feedback arc set problems on bipartite tournaments. We improve on recent results by giving a 2-approximation algorithm for the feedback vertex set problem. We show that this result is the best that we can attain when using optimal solutions to a certain linear program as a lower bound on the optimal value. For the feedback arc set problem on bipartite tournaments, we show that a recent 4-approximation algorithm proposed by Gupta (2008) [8] is incorrect. We give an alternative 4-approximation algorithm based on an algorithm for the feedback arc set on (non-bipartite) tournaments given by van Zuylen and Williamson (2009) [14].