Two Affine Scaling Methods for Solving Optimization Problems Regularized with an L1-norm

Affine Scaling;Optimization;Computer Science

Li, Zhirong

University of Waterloo

关键词: Affine Scaling;    Optimization;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/5546/1/Li_Zhirong.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

In finance, the implied volatility surface is plotted against strike price and time to maturity.The shape of this volatility surface can be identified by fitting the model to what is actuallyobserved in the market. The metric that is used to measure the discrepancy between themodel and the market is usually defined by a mean squares of error of the model prices to themarket prices. A regularization term can be added to this error metric to make the solutionpossess some desired properties. The discrepancy that we want to minimize is usually a highlynonlinear function of a set of model parameters with the regularization term. Typicallymonotonic decreasing algorithm is adopted to solve this minimization problem. Steepestdescent or Newton type algorithms are two iterative methods but they are local, i.e., theyuse derivative information around the current iterate to find the next iterate. In order toensure convergence, line search and trust region methods are two widely used globalizationtechniques.Motivated by the simplicity of Barzilai-Borwein method and the convergence propertiesbrought by globalization techniques, we propose a new Scaled Gradient (SG) method forminimizing a differentiable function plus an L1-norm. This non-monotone iterative methodonly requires gradient information and safeguarded Barzilai-Borwein steplength is used ineach iteration. An adaptive line search with the Armijo-type condition check is performed ineach iteration to ensure convergence. Coleman, Li and Wang proposed another trust regionapproach in solving the same problem. We give a theoretical proof of the convergence oftheir algorithm. The objective of this thesis is to numerically investigate the performanceof the SG method and establish global and local convergence properties of Coleman, Li andWang’s trust region method proposed in [26]. Some future research directions are also givenat the end of this thesis.