liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
New optimization methods for isotonic regression in L1 norm
Linköpings universitet, Filosofiska fakulteten. Linköpings universitet, Institutionen för datavetenskap, Statistik.
Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.ORCID-id: 0000-0003-1836-4200
Linköpings universitet, Filosofiska fakulteten. Linköpings universitet, Institutionen för datavetenskap, Statistik.
2007 (engelsk)Inngår i: EUROPT-OMS Conference on Optimization,2007, University of Hradec Kralove, Czech Republic: Guadeamus , 2007, s. 133-133Konferansepaper, Publicerat paper (Annet vitenskapelig)
Abstract [en]

Isotonic regression problem (IR) has numerous important applications in statistics, operations research, biology, image and signal processing and other areas. IR is a minimization problem with the objective function defined by the distance from a given point to a 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 norm, whereas the norms L1 and L2 are of the highest practical interest. The conventional optimization methods are unable to solve large-scale IR problems originating from large data sets. Historically, the major efforts were focused on IR problem in the L2 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 most numerically efficient, but it is not robust enough. An alternative approach is related to solving IR problem approximately. Following this 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 from 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 problems.

sted, utgiver, år, opplag, sider
University of Hradec Kralove, Czech Republic: Guadeamus , 2007. s. 133-133
Emneord [en]
quadratic programming, linear programming, isotonic regression, large-scale optimization
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-40343Lokal ID: 53034OAI: oai:DiVA.org:liu-40343DiVA, id: diva2:261192
Tilgjengelig fra: 2009-10-10 Laget: 2009-10-10 Sist oppdatert: 2018-01-13

Open Access i DiVA

Fulltekst mangler i DiVA

Personposter BETA

Sysoev, OlegBurdakov, OlegGrimvall, Anders

Søk i DiVA

Av forfatter/redaktør
Sysoev, OlegBurdakov, OlegGrimvall, Anders
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric

urn-nbn
Totalt: 344 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf