New optimization methods for isotonic regression in L1 norm
2007 (English)In: EUROPT-OMS Conference on Optimization,2007, University of Hradec Kralove, Czech Republic: Guadeamus , 2007, 133-133 p.Conference paper (Other academic)
regression problem (IR) has numerous important
applications in statistics, operations research, biology, image and
signal processing and other areas. IR is a minimization problem
the objective function defined by the distance from a given point
convex set defined by monotonicity constraints of the form: i-th
component of the decision vector is less or equal to its j-th
component. The distance in IR is usually associated with the Lp
whereas the norms L1 and L2 are of the highest practical interest.
conventional optimization methods are unable to solve large-scale
problems originating from large data sets.
Historically, the major efforts were focused on IR problem in the
norm. Exact algorithms such as the minimum lower sets algorithm by
Brunk, the min-max algorithm by Lee, the network flow algorithm by
Maxwell & Muchstadt and the IBCR algorithm by Block et al. were
developed. Among them the IBCR algorithm has been proved to be the
numerically efficient, but it is not robust enough. An alternative
approach is related to solving IR problem approximately. Following
approach, Burdakov et al. developed GPAV algorithm whose block
refinement extension, GPAVR, is able to solve IR problem with high
accuracy in a far shorter time than the exact algorithms. Apart
this, GPAVR is a very robust algorithm.
Unfortunately, for the norm L1 there are no algorithms which are as
efficient as those in L2 norm. In our talk, we introduce new
algorithms, GPAVR1 and IBCR1. They are extensions of the algorithms
GPAV and IBCR to L1 norm. We present also results of numerical
experiments, which demonstrate the high efficiency of the new
algorithms, especially for very large-scale
Place, publisher, year, edition, pages
University of Hradec Kralove, Czech Republic: Guadeamus , 2007. 133-133 p.
quadratic programming, linear programming, isotonic regression, large-scale optimization
IdentifiersURN: urn:nbn:se:liu:diva-40343Local ID: 53034OAI: oai:DiVA.org:liu-40343DiVA: diva2:261192