liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A Comparison of Feasible Direction Methods for the Stochastic Transportation Problem
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.ORCID-id: 0000-0003-2094-7376
Mathematical Sciences, Chalmers University of Technology and Göteborg University, Gothenburg, Sweden.
Linköpings universitet, Institutionen för teknik och naturvetenskap. Linköpings universitet, Tekniska högskolan.ORCID-id: 0000-0001-6405-5914
2010 (Engelska)Ingår i: Computational optimization and applications, ISSN 0926-6003, E-ISSN 1573-2894, Vol. 46, nr 3, s. 451-466Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

The feasible direction method of Frank and Wolfe has been claimed to be efficient for solving the stochastic transportation problem. While this is true for very moderate accuracy requirements, substantially more efficient algorithms are otherwise diagonalized Newton and conjugate Frank–Wolfe algorithms, which we describe and evaluate. Like the Frank–Wolfe algorithm, these two algorithms take advantage of the structure of the stochastic transportation problem. We also introduce a Frank–Wolfe type algorithm with multi-dimensional search; this search procedure exploits the Cartesian product structure of the problem. Numerical results for two classic test problem sets are given. The three new methods that are considered are shown to be superior to the Frank–Wolfe method, and also to an earlier suggested heuristic acceleration of the Frank–Wolfe method.

Ort, förlag, år, upplaga, sidor
2010. Vol. 46, nr 3, s. 451-466
Nyckelord [en]
Stochastic transportation problem, Frank–Wolfe method, Descent methods, Cartesian product sets
Nationell ämneskategori
Matematik
Identifikatorer
URN: urn:nbn:se:liu:diva-14440DOI: 10.1007/s10589-008-9199-0ISI: 000278736100004OAI: oai:DiVA.org:liu-14440DiVA, id: diva2:23507
Tillgänglig från: 2007-04-27 Skapad: 2007-04-27 Senast uppdaterad: 2017-12-13
Ingår i avhandling
1. Feasible Direction Methods for Constrained Nonlinear Optimization: Suggestions for Improvements
Öppna denna publikation i ny flik eller fönster >>Feasible Direction Methods for Constrained Nonlinear Optimization: Suggestions for Improvements
2007 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

This thesis concerns the development of novel feasible direction type algorithms for constrained nonlinear optimization. The new algorithms are based upon enhancements of the search direction determination and the line search steps.

The Frank-Wolfe method is popular for solving certain structured linearly constrained nonlinear problems, although its rate of convergence is often poor. We develop improved Frank--Wolfe type algorithms based on conjugate directions. In the conjugate direction Frank-Wolfe method a line search is performed along a direction which is conjugate to the previous one with respect to the Hessian matrix of the objective. A further refinement of this method is derived by applying conjugation with respect to the last two directions, instead of only the last one.

The new methods are applied to the single-class user traffic equilibrium problem, the multi-class user traffic equilibrium problem under social marginal cost pricing, and the stochastic transportation problem. In a limited set of computational tests the algorithms turn out to be quite efficient. Additionally, a feasible direction method with multi-dimensional search for the stochastic transportation problem is developed.

We also derive a novel sequential linear programming algorithm for general constrained nonlinear optimization problems, with the intention of being able to attack problems with large numbers of variables and constraints. The algorithm is based on inner approximations of both the primal and the dual spaces, which yields a method combining column and constraint generation in the primal space.

Ort, förlag, år, upplaga, sidor
Matematiska institutionen, 2007. s. 29
Serie
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1095
Nyckelord
constrained nonlinear optimization, feasible direction methods, conjugate directions, traffic equilibrium problem, sequential linear programming algorithm, stochastic transportation problem
Nationell ämneskategori
Beräkningsmatematik
Identifikatorer
urn:nbn:se:liu:diva-8811 (URN)978-91-85715-11-4 (ISBN)
Disputation
2007-05-25, Alan Turing, Hus E, Campus Valla, Linköping University, Linköping, 10:15 (Engelska)
Opponent
Handledare
Anmärkning
The articles are note published due to copyright rextrictions.Tillgänglig från: 2007-04-27 Skapad: 2007-04-27 Senast uppdaterad: 2015-01-14

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextLink to Ph.D. thesis

Personposter BETA

Daneva (Mitradjieva), MariaLarsson, TorbjörnRydergren, Clas

Sök vidare i DiVA

Av författaren/redaktören
Daneva (Mitradjieva), MariaLarsson, TorbjörnRydergren, Clas
Av organisationen
OptimeringsläraTekniska högskolanInstitutionen för teknik och naturvetenskap
I samma tidskrift
Computational optimization and applications
Matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 597 träffar
RefereraExporteraLänk till posten
Permanent länk

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