Return to search

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

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 actually
observed in the market. The metric that is used to measure the discrepancy between the
model and the market is usually defined by a mean squares of error of the model prices to the
market prices. A regularization term can be added to this error metric to make the solution
possess some desired properties. The discrepancy that we want to minimize is usually a highly
nonlinear function of a set of model parameters with the regularization term. Typically
monotonic decreasing algorithm is adopted to solve this minimization problem. Steepest
descent or Newton type algorithms are two iterative methods but they are local, i.e., they
use derivative information around the current iterate to find the next iterate. In order to
ensure convergence, line search and trust region methods are two widely used globalization
techniques.
Motivated by the simplicity of Barzilai-Borwein method and the convergence properties
brought by globalization techniques, we propose a new Scaled Gradient (SG) method for
minimizing a differentiable function plus an L1-norm. This non-monotone iterative method
only requires gradient information and safeguarded Barzilai-Borwein steplength is used in
each iteration. An adaptive line search with the Armijo-type condition check is performed in
each iteration to ensure convergence. Coleman, Li and Wang proposed another trust region
approach in solving the same problem. We give a theoretical proof of the convergence of
their algorithm. The objective of this thesis is to numerically investigate the performance
of the SG method and establish global and local convergence properties of Coleman, Li and
Wang’s trust region method proposed in [26]. Some future research directions are also given
at the end of this thesis.

Identiferoai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/5546
Date January 2010
CreatorsLi, Zhirong
Source SetsUniversity of Waterloo Electronic Theses Repository
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation

Page generated in 0.0017 seconds