摘要
非线性共轭梯度法是求解大规模最优化问题深受欢迎的一类算法,也是倍受学者们关注的一类算法.非线性共轭梯度法的研究近年来又有了许多新的进展.本文进一步研究求解无约束最优化问题的非线性共轭梯度法.结合共轭梯度法和投影梯度法,提出一种求解线性等式约束优化问题的共轭梯度型方法,并将该方法应用于投资组合问题.本文还进一步研究鲁棒最优投资组合问题.
在第2章,基于Li和Fukushima的修正割线条件,我们提出两种修正Hestenes-Stiefel (HS)型共轭梯度法.两种方法的一个共同性质是算法能产生充分下降方向.不需要采用截断策略和目标函数为凸的假设,我们证明两种方法在标准Armijio线搜索下全局收敛.而且,在较弱的条件下,证明两种方法具有R-阶线性收敛速率.另外,我们给出一种适用的初始步长选取方式,并讨论初始步长在标准Armijio线搜索下的可接受性.数值试验表明该方法有很好的数值效果,可以和CG-DESCENT共轭梯度法相媲美.
在第3章,我们将Rosen梯度投影法和修正的Fletcher-Reeves(FR)共轭梯度法相结合,提出一种求解带线性等式约束优化问题的共轭梯度型算法.该算法产生的搜索方向是可行下降方向.在较弱条件下,当采用Armijio线搜索时,该算法具有全局收敛性.我们还证明,当用于求解线性等式约束下二次函数极小值问题时,若采用精确线性搜索,则该算法具有有限终止性.最后,我们研究该算法在Markowitz均值-方差投资组合模型中的应用,数值试验表明该算法较Rosen梯度投影法更有效.
在第4章,我们研究鲁棒均值下半绝对偏差投资组合模型.假定资产收益的期望属于矩形和椭球不确定集,分别给出矩形不确定集下和椭球不确定集下鲁棒均值下半绝对偏差投资组合优化模型,其中前者可转化为线性规划(LP)问题,后者可转化为二阶锥规划(SOCP)问题.采用上海交易市场上证50的实际交易数据对所提出的模型进行实证分析,结果表明鲁棒均值下半绝对偏差投资组合优化模型能够获得具有更好财富增长率的投资策略,及更稳定的回报.
Conine(?)Tamarkin以及Andrew和Chen指出金融资产的收益具有非对称的性质,尤其是保险和信用风险资产.已有的鲁棒条件风险模型基本是基于矩形或椭球等对称的不确定集,因此用矩形或椭球等对称的不确定集刻画资产信息的偏差,是导致鲁棒模型过于保守的可能原因之一.在第5章,基于Chen等的鲁棒优化技术,假定投资组合收益的均值属于非对称仿射不确定集,我们提出一种计算上可解的鲁棒条件风险投资组合模型.新方法的突出优点是鲁棒模型保持原问题的计算复杂度,即鲁棒模型仍然是一个线性规划问题,而且该鲁棒模型考虑了资产回报的非对称性.通过模拟数据和市场数据的数值试验,表明新鲁棒优化模型的有效性.
条件风险价值(CVaR)因其是一致性风险度量和数学上的凸性,是目前最重要的风险度量方法.然而,近期的研究表明抽样样本的误差对条件价值风险(CVaR)的实际应用产生很大的影响,其原因是条件风险价值(CVaR)的计算依赖于小部分大损失的样本.在第6章,我们提出一种考虑抽样样本的误差的Worst-Case条件价值风险(称之为AWCVaR)我们证明AWCVaR是一个一致性风险度量,并且其鲁棒对应形式仍然是一个线性规划问题.实证分析表明AWCVaR较CVaR更有效.
Nonlinear conjugate gradient methods form a class of welcome methods forsolving large-scale unconstrained optimization problem. In recent years, there hasbeen much new progress in nonlinear conjugate gradient methods. This thesisfurther studies nonlinear conjugate gradient methods. Combined with the con-jugate gradient method and projection gradient method, we propose a conjugategradient-type method for solving linear equality constrained optimization prob-lem, and apply it to portfolio problem. Finally we further study robust optimalportfolio problem.
In Chapter2, based on the modified secant equation by Li and Fukushima,we propose two modified Hestenes-Stiefel (HS) conjugate gradient methods. Acommon nice property of the proposed methods is that they can generate sufcientdescent directions without any line search. Under mild conditions, we show that themethods with Armijio line search are globally convergent. Moreover, the R-linearconvergence rate of the modified HS methods is established. Preliminary numericalresults show that the proposed methods are promising, and are competitive withthe well-known CG-DESCENT method.
In Chapter3, combining the idea of the modified Fletcher-Reeves conjugategradient method and the Rosen gradient projection method, we propose a conju-gate gradient-type method for linear equality constrained optimization problem.Search direction generated by the method is a feasible descent direction. Con-sequently the generated iterates are feasible points, moreover, the sequence offunction is decreasing. Under mild conditions, we show that the method withArmijio line search is globally convergent. Moreover, when the method with exactline search is used to solve a linear equality constrained quadratic programming,it will terminate at the solution of the problem within finite iterations We applythe proposed method to Markowitz mean-variance portfolio optimization problem.Numerical results show that the method is more efective than the Rosen gradientprojection method.
In Chapter4, we study robust mean semi-absolute deviation models for port-folio optimization. We consider the case where the return of assets belongs to abox uncertainty set or ellipsoidal uncertainty set. We derive robust counterpartsfor both portfolio optimization. The first model is a Linear programming (LP) andthe last one is a second-order cone programming (SOCP), both can be computed efciently. The empirical analysis and comparisons from the real market data indi-cate that the robust models can obtain a portfolio strategy with the better wealthgrowth rate and more stable return.
Andrew and Chen, Conine and Tamarkin found that the asymmetries in thedata reject the null hypothesis of multivariate normal distributions. Exiting robustCVaR method is under the box uncertainty set or the ellipsoidal uncertainty setwhich are symmetric. This may be overly conservative for capturing the deviationsof the asymmetric asset returns. In Chapter5, based on the robust optimizationtechniques by Chen et al, we study robust CVaR method in which the mean re-turn of the portfolio belongs a non-symmetric afne uncertainty set. We derive acomputationally tractable robust optimization method for minimizing the CVaRof a portfolio. A remarkable characteristic of the new method is that the robustoptimization model reserves the complexity of original portfolio optimization prob-lem, i.e., the robust counterpart problem is still a linear programming problem.Moreover, it takes into consideration asymmetries in the distributions of returns.We present some numerical experiments with simulated and real market data toillustrate the behavior of the robust optimization model.
Conditional value-at-risk (CVaR) has become the most popular risk measuredue to its coherence property and tractability. However, recent study has indicatedthat optimal solutions to the CVaR minimization are highly susceptible to estima-tion error of the risk measure because the estimate depends on only a small portionof sampled scenarios. In Chapter6, considering the error of samples in conditionalvalue-at-risk (CVaR), we propose a Worst-Case CVaR risk (called AWCVaR). Weshow that the AWCVaR is a coherent risk measure, and the robust problem is stilla linear programming problem. The empirical analysis shows that AWCVaR ismore efective than the conditional value-at-risk (CVaR).
引文
[1]袁亚湘,孙文瑜.最优化理论与方法.北京：科学出版社,2001
[2]李董辉,童小娇,万中.数值最优化.北京：科学出版社,2005
[3]李董辉,童小娇.数值最优化理论与算法.北京：科学出版社,2010
[4]Fleteher R, Reeves C. Function minimization by conjugate gradients. computer Journal,1964,7:149-154
[5]Hestenes M R, Stiefel E L. Methods of conjugate gradient for sovling linear systems. Journal of Research of the National Bureau of Standards,1952,6(49):409-436
[6]Polak B, Ribiere G. Note surla convergence des methodes de directions conjuguees. Pev. Francaise Infomat Recherche Operatonelle,3e Annee.1969,16:35-43
[7]Polyak B T. The conjugate gradient method in extreme problems, USSR Compu-tational Mathematics and Mathematical Physics,1969,9:94-112
[8]Fletcher R. Prauctic Methods of Optimization, V61I:uncontrained Optimiza-tion. John Wiley&Sons, New York,1987
[9]Liu Y, Storey c. Efficient generalized conjugate gradient algorithms (Pan1):Theory Journal of Optimization Theory and Applications,1991,69:129-137
[10]Dai Y, Yuan Y. A nonlinear conjugate gradient with a strong global convergence properties. SIAM Journal on Optimization,2000,10:177-182
[11]Zoutendijk G. Nonlinear Programming computational Methods. In:Integer and Nonlinear Programming. North-Holland, Amsterdam,1970,37-86
[12]Al-Baali M. Descent property and global convergence of the Fletcher-Reeves method with inexact line search. IMA Journal of Numerical Analysis,1985,5:121-124
[13]Liu G H, Han J Y, Yin H X. Global convergence of the Fletcher-Reeves algo-rithm with an inexact line search. Applied Mathematics. A Journal of Chinese Universities,1995,10(1):75-82.
[14]Dai Y H, Yuan Y. Convergence properties of the Fletcher-Reeves method. IMA Journal of Numerical Analysis,1996,16:155-164
[15]Powell M J D. Restart procedures of the conjugate gradient method. Mathematical Programming,1977,2:241-254
[16]Yuan Y. Analysis on the conjugate gradient method. Optimization Methods and Software,1993,2:19-29
[17]Gilbert J C, Nocedal J. Global convergence properties of conjugate gradient meth-ods for optimization. SIAM Journal on Optimization,1992,2:21-42
[18]Grippo L, Lucidi S. A globally convergent version of the Polak-Ribiere gradient method. Mathematical Programming,1997,78:375-391
[19]戴志锋,陈兰平.一种混合的HS-DY共轭梯度法,计算数学,2005,27(4)：429-436
[20]Dai Y H, Liao L Z. New conjugacy conditions and related nonlinear conjugate gradient methods. Applied Mathematic and Optimizatin,2001,43(1):87-101
[21]Yabe H, Takano M. Global convergence properties of nonlinear conjugate gradient methods with modified secant condition. Computation Optimization and Applica-tion,2004,28(2):203-225
[22]Li G Y, Tang C M, Wei Z X. New conjugacy condition and related new conjugate gradient methods for unconstrained optimization. Journal of Computational and Applied Mathematies,2007,202:523-539
[23]Hager W W, Zhang H. A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM Journal on Optimization,2005,16:170-192
[24]Yuan G L. Modified nonlinear conjugate gradient methods with sufficient descent property for large-scale optimization problems. Optimization Letters,2009,3:11-21
[25]Dai Z F, Tian B S. Global convergence of some modified PRP nonlinear conjugate gradient methods. Optimization Letters,2011,5:615-630
[26]Zhang L, Zhou W J, Li D H. A descent modified Polak-Ribiere-Polyak conjugate gradient method and its global convergence. IMA Journal of Numerical Analysis,2006,26:629-640
[27]Zhang L, Zhou W J, Li D H. Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search. Numerische Mathematik,2006,104:561-572
[28]Zhang L, Zhou W J, Li D H. Some descent three-term conjugate gradient methods and their global convergence, Optimization Methods and Softwere,2007,22:697-711
[29]Cheng W Y. A two-term PRP-based descent method. Numerical Functional Anal-ysis and Optimization,2007,28:1217-1230
[30]Broyden C G, Dennis J E, More, J. J. On the local and superlinear convergence of quasi-Newton methods. Journal of Institute of Mathematics and Applications,1973,12:223-246
[31] Byrd R H, Noeedal J, Yuan Y. Globale onvergence of a class of quasi-Newtonmethods on convex problems. SIAM Journal on Numerieal Analysis,1987,24:1171-1189
[32] Byrd R H, Noeedal J. A tool for the analysis of quasi-Newton methods withapplieation to uneonstrained minimization. SIAM Journal on Numerieal Analysis,1989,26:727-739
[33] Li D H, Fkushima M. A modified BFGS method and its global convergence innoneonvex minimization. Journal of Computational and Applied Mathematies,2001,129:15-35
[34] Li D H，Fkushima M. On the global convergence of the BFGS methods for noncon-vex unconstrained optimization Problems. SIAM Journal on Optimization,2001,11:1054-164
[35] Dai Y H. Convergence properties of the BFGS algorithm. SIAM Journal on Opti-mization,2002,13:693-701
[36] Shi Z J, Shen J. Convergence of the Polak-Ribi′ere-Polyak conjugate gradientmethod. Nonlinear Analysis,2007,66:1428-1441
[37] Andrei N. An unconstrained optimization test functions collection. Advanced Mod-eling and Optimization,2008,10:147-161
[38] Dolan E D, Mor′e J J. Benchmarking optimization software with performance pro-files. Mathematical Programming,2002,91:201-213
[39] Karmarkar N K. A new polynomial-time algorithm for linear programming. Com-binatorica,1984,4:373-395
[40] Roos C, Terlaky T, Vial J-Ph. Theory and Algorithms for Linear Optimization.An Interior-Point Approach. Chichester: John Wiley&Sons,1997
[41] Dai Y H, Fletcher R. Projected Barzilai-Borwein methods for largescale box-constrained quadratic programming. Numerische Mathematik,2005,100:21-47
[42] Hager W W, Zhang H. A new active set algorithm for box constrained optimiza-tion. SIAM Journal on Optimization,2006,17(2):526-557
[43] Peng J, Roos C, Terlaky T. A new class of polynomial primal-dual interior-pointmethods for second-order cone optimization based on self-regular proximities.SIAM Journal on Optimization,2002,13(1):179-203
[44] Tsuchiya T. A convergence analysis of the scaling-invariant primal-dual path-following algaorithms for second-order cone programing. Optimization Methodsand Software,1999,11(12):141-182
[45] Bellman R, Fan K. On systems of linear inequalities in Hermitian matrix vari-ables. In: Convexity, proceedings of symposia in Pure Mathematics. AmericanMathematical Society, Providence, RI,1963,7:1-11
[46]Coleman T F, Verma A. A preconditioned conjugate gradient approach to lin-ear equality constrained minimization. Technical report, Department of Computer Sciences, Cornell University, Ithaca, New York, USA, July1998
[47]Gould N I M, Hribar M E, Nocedal J. On the solution of equality constrained quadratic programming problems arising in optimization, SIAM Journal on Scien-tific Computing,2001,23:1376-1395
[48]Rosen J B. The gradient projection method for nonlinear programming, part Ⅰ, linear constraints. SIAM Journal on Applied Mathematics,1960,8(1):182-217
[49]Rosen J B. The gradient projection method for nonlinear programming, part Ⅱ, nonlinear constraints. SIAM Journal on Applied Mathematics,1960,9(4):514-532
[50]Du D Z, Zhang X S. Global convergence of Rosen's gradient projection method. Mathematical Programming,1989,44:357-366
[51]陈广军.一个解带线性或非线性约束最优化问题的梯度投影算法.计算数学,1987,49：356-364
[52]赖炎连,高自友,贺国平.非线性最优化的广义梯度投影法.中国科学,A辑,1992,9：916-924
[53]Goldfarb D, Lapidus L. Conjugate gradient method for nonlinear programming problems with linear constraints. Industral&Engineering Chemistry Fundamen-tals,1968,7:142-151
[54]Goldfarb D. Extension of Davidson's variable metric method to maximization un-der linear inequality and equality constraints. SIAM Journal on Applied Mathe-matics,1969,17:739-764
[55]Nesterov Y, Nemirovski A. Conic formulation of convex programming problem and duality. Optimization Methods and Software,1992,1:95-115
[56]Nesterov Y, Nemirovski A. Interior point Polynomial Algorithms in convex pro-gramming. Philadelphia, USA:SIAM,1994
[57]Alizadch F. Interior point methods in semidefite programming with applications to combinatorial optimization. SIAM Journal on Optimization,1995,5:13-51
[58]Toh K C, Tutuncii R H, Todd M J. SDPT3-A Matlab software for semidefite quadratic linear programming. www.math.nus.edu.sg/mattohkc/sdpt3.html,1996
[59]Sturm J F. Using SEDUMI1.02, a MATLAB toolbox for optimization over sym-metric cones. Optimization Methods and Software,1999,11(1):625-653
[60]Soyster A L. Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations Research,1973,21:1154-1157
[61]Ben-Tal A, Nemirovski A. Robust convex optimization. Mathematics of Operations Research,1998,23(4):769-805
[62]Ben-Tal A, Nemirovski A. Robust solutions to uncertain linear Programs. Opera-tions Research Letters,1999,25(1):1-13
[63]Ben-Tal A, Nemirovski A. Robust solutions of linear Programming Problems con-taminated with uncertain data. Mathematical Programming,2000,88(3):411-424
[64]EI Ghaoui L, Oustry F, Lebret H. Robust solutions to least-square Problems with uncertain data matrices. SIAM Journal on Matrix Analysis and Applications,1997,18(10):1035-1064
[65]EI Ghaoui L, Oustry F, Lebret H. Robust solutions to uncertain semidefinite Programs. SIAM Journal on Optimization,1998,9(1):35-52
[66]Bertsimas D, Sim M. Tractable approximations to robust conic optimization prob-lems. Mathematical Programming,2006,107:5-36
[67]Chen X, Sim M, Sun P. A robust optimization perspective on stochastic program-ming. Operations Research,2007,55(6):1058-1077
[68]Markowitz H. Portfolio Selection. The Journal of Finance,1952,7:77-91
[69]Markowitz H M. Portfolio Selection:Efficient diversification of investment. New York:John Wiley&Sons,1959
[70]Sharp W F. A simplified model for portfolio selction analysis. Management Science,1963,9:277-293
[71]Ross S A. The arbitrage theory of capital asset pricing. Journal of Economic The-ory,1976,13:341-360
[72]Konno H, Yamazaki H. Mean-absolute deviation portfolio optimization model and its applications to Tokyo stock market. Management Science,1991,37:519-531
[73]Speranza M G. Linear programming models for portfolio optimization. Finance,1993,14:107-123
[74]Speranza M G. A heuristic algorithm for a portfolio optimization model applied to the Milan stock market. Computers&Operations Research,2004,223(5):433-441
[75]朱书尚,李端,周迅宇,汪寿阳.论投资组合与金融优化-对理论研究和实践的分析与反思.管理科学学报,2004,7(6)：1-12
[76]赵贞玉,欧阳令南.基于M-Semi A. D组合投资模型及对上海股市实证研究.中国管理科学,2004,12(1)：20-23
[77]张鹏,张忠桢,岳超源.限制性卖空的均值-半绝对偏差投资组合模型及其旋转算法研究.中国管理科学,2006,14(2)：7-11
[78]Jorion P. Value at Risk:The New Benchmark for Managing Financial Risk. McGraw-Hill, New York.2000
[79] Artzner F, Delbaen J M. Eber and D. Heath, Coherence measures of risk. Mathe-matical Finance,1999,9:203-228
[80] Rockafellar R T, Uryasev S. Optimization of conditional value-at-risk. Journal ofRisk,2000,2:21-41
[81] Rockafellar R T, Uryasev S. Conditional value-at-risk for general loss distributions.Journal of Banking and Finance,2002,26(7):1443-1471
[82] Ogryczak W, Ruszczynski A. Dual stochastic dominance and related mean-riskmodels. SIAM Journal on Optimization,2002,13:60-78
[83] Black F, Litterman R. Global portfolio optimization. Journal of Financial Ana-lysts,1992,48:28-43
[84] Chopra V K, Ziemba W T. The efect of errors in means, variance and covarianceson optimal portfolio choice. Journal Portfolio Management,1993,19:6-11
[85] Lobo M S, Boyd S. The worst-case risk of a portfolio, Technical Report,http://faculty.fuqua.duke.edu/sim mlobo/bio/researchfiles/rsk-bnd.pdf,2000
[86] Tu¨tu¨ncu¨ R H, Koenig M. Robust asset allocation. Annals of Operations Research,2004,132:157-187
[87] Goldfarb D, Iyengar G. Robust portfolio selection problems. Mathematics of Op-erations Research,2003,28:1-38
[88] Pinara M C, Tutuncu R H. Robust profit opportunities in risky financial portfolios.Operations Research Letters,2005,33:331-340
[89] El Ghaoui L, Oks M, Oustry F. Worst-Case Value-at-Risk and Robust PortfolioOptimization: A Conic Programming Approach. Operations Research,2003,51:543-556
[90] Zhu S S, Fukushima M. Worst-Case Conditional Value-at-Risk with application torobust portfolio management. Operations Research,2009,57:1155-1168
[91] Huang D S, Zhu S S, Fabozzi F J, Fukushima M. Portfolio selection with uncertainexit time: a robust CVaR approach. Journal of Economic Dynamics&Control,2008,32(2):594-623
[92] Quaranta A G, Zafaroni A. Robust optimization of conditional value at risk andportfolio selection. Journal of Banking and Finance,2008,32:2046-2056
[93] Fabozzi F J, Kolm P N, Pachamanova D, Focardi S M. Robust portfolio optimiza-tion and management. Hoboken: Wiley,2007
[94] Fabozzi F J, Huang D S, Zhou G F. Robust portfolios: contributions from opera-tions research and finance. Annals of Operations Research,2010,176:191-220
[95]安晓敏,罗桂美.椭球不确定集下的投资组合鲁棒优化模型.湖南大学学报,2010,37：89-92
Conine T E, Tamarkin M J. On diversification given asymmetry in returns. Journal of Finance,1981,36:1143-1155
[97]Andrew A, Chen J. Asymmetric Correlations of Equity Portfolios. Journal of Fi-nancial Economics,2002,63(3):443-494
[98]Topaloglou N, Vladimirou H, Zenios S A. CVaR models with selective hedging for international asset allocation. Journal of Banking and Finance,2002,26:1535-1561
[99]Zhu S S, Ji X D, Li D. Robust Downside Risk Minimization via Set-valued Sce-nario Approach, Working paper, Department of Management Science, School of Management, Fudan University,2011
[100]Costa O L V, Paiva A C. Robust portfolio selection using linear-matrix inequalities. Journal of Economic Dynamics and Control,2002,26(6):889-909
[101]高莹,黄小原.具有vaR约束的跟踪误差投资组合鲁棒优化模型.中国管理科学,2007,15(1)：1-5
[102]高金窑,李仲飞.模型不确定性条件下的Robust投资组合有效前沿与CAPM.中国管理科学,2010,18(6)：1-8
[103]凌爱凡,吕江林.具有联合椭圆不确定集与概率约束的鲁棒投资组合选择.控制与决策,2011,26(4)：558-564
[104]Moon Y M, Yao T. A robust mean absolute deviation model for portfolio opti-mization. Computers Operations Research,2011,38:1251-1258
[105]Zymler S, Rustem B, Kuhn D. Robust portfolio optimization with derivative insur-ance guarantees. European Journal of Operational Research,2011,210:410-424
[106]Fonseca R, Wiesemann W, Rustem B. Robust international portfolio management. Computational Management Science,2012,9(1):31-62
[107]Natarajan K, Pachamanova D, Sim M. Constructing risk measure from uncertainty sets. Operations Research,2009,57(5):1129-1141
[108]Bertsimas D, Brown D B. Constructing uncertainty sets for robust linear opti-mization. Operations Research,2009,57(6):1483-1495
[109]Jagannathan R, Ma T. Risk reduction in large portfolios:why imposing the wrong constraints helps. Journal of Finance,2003,4:1651-1683
[110]Ledoit O, Wolf M. Improved estimation of the covariance matrix of stock returns with an application to portfolio selection. Journal of Empirical Finance,2003,10:603-621
[111] DeMiguel V, Garlappi L, Uppal R. Optimal versus naive diversification: how inef-ficient is the1/N portfolio strategy. Review of Financial Studies,2009,22:1915-1953
[112] Gotoh J Y, Takeda A. On the role of norm constraints in portfolio selection.Computational Management Science,2011,8:323-353
[113] Fama E. Foundations of Finance. Basic Books, New York,1976
[114] Dufee G. The long-run behavior of firms stock returns: Evidence and interpreta-tions. Working paper, Haas School of Business, University of California at Berkeley,Berkeley, CA,2002
[115] Sch¨onbucher P. Factor models for portfolio credit risk. Working paper, Universityof Bonn, Germany. http://www.gloriamundi.org,2000
[116] Lim A E B, Shanthikumar J G, Vahn G Y. Conditional value-at-risk in portfoliooptimization: Coherent but fragile. Operations Research Letters,2011,39:163-171