New optimization algorithms for large-scale isotonic regression in L2-norm
2007 (English)In: EUROPT-OMS Conference on Optimization,2007, University of Hradec Kralove, Czech Republic: Guadeamus , 2007, 44-44 p.Conference paper (Other academic)
regression problem (IR) has numerous important applications in
statistics, operations research, biology, image and signal
and other areas. IR in L2-norm is a minimization problem in which
objective function is the squared Euclidean distance from a given
to a convex set defined by monotonicity constraints of the form:
component of the decision vector is less or equal to its j-th
component. Unfortunately, the conventional optimization methods are
unable to solve IR problems originating from large data sets.
The existing IR algorithms, such as the minimum lower sets
Brunk, the min-max algorithm by Lee, the network flow algorithm by
Maxwell & Muchstadt and the IBCR algorithm by Block et al. are
find exact solution to IR problem for at most a few thousands of
variables. The IBCR algorithm, which proved to be the most
them, is not robust enough. An alternative approach is related to
solving IR problem approximately. Following this approach, Burdakov
al. developed an algorithm, called GPAV, whose block refinement
GPAVR, is able to solve IR problems with a very high accuracy in a
shorter time than the exact algorithms. Apart from this, GPAVR is a
very robust algorithm, and it allows us to solve IR problems with
hundred thousands of variables.
In this talk, we introduce new exact IR algorithms, which can be
as active set methods. They use the approximate solution produced
the GPAVR algorithm as a starting point. We present results of our
numerical experiments demonstrating the high efficiency of the new
algorithms, especially for very large-scale problems, and their
robustness. They are able to solve the problems which all existing
exact IR algorithms fail to solve.
Place, publisher, year, edition, pages
University of Hradec Kralove, Czech Republic: Guadeamus , 2007. 44-44 p.
quadratic programming, isotonic regression, large-scale optimization, active-set methods
IdentifiersURN: urn:nbn:se:liu:diva-40342Local ID: 53033OAI: oai:DiVA.org:liu-40342DiVA: diva2:261191