liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Feasible Direction Methods for Constrained Nonlinear Optimization: Suggestions for Improvements
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
2007 (English)Doctoral thesis, comprehensive summary (Other academic)
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.

Place, publisher, year, edition, pages
Matematiska institutionen , 2007. , 29 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1095
Keyword [en]
constrained nonlinear optimization, feasible direction methods, conjugate directions, traffic equilibrium problem, sequential linear programming algorithm, stochastic transportation problem
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-8811ISBN: 978-91-85715-11-4 (print)OAI: oai:DiVA.org:liu-8811DiVA: diva2:23509
Public defence
2007-05-25, Alan Turing, Hus E, Campus Valla, Linköping University, Linköping, 10:15 (English)
Opponent
Supervisors
Note
The articles are note published due to copyright rextrictions.Available from: 2007-04-27 Created: 2007-04-27 Last updated: 2015-01-14
List of papers
1. The Stiff is Moving - Conjugate Direction Frank -Wolfe Methods with Applications to Traffic Assignment
Open this publication in new window or tab >>The Stiff is Moving - Conjugate Direction Frank -Wolfe Methods with Applications to Traffic Assignment
2013 (English)In: Transportation Science, ISSN 0041-1655, E-ISSN 1526-5447, Vol. 47, no 2, 280-293 p.Article in journal (Refereed) Published
Abstract [en]

We present versions of the Frank-Wolfe method for linearly constrained convex programs, in which consecutive search directions are made conjugate. Preliminary computational studies in a MATLAB environment applying pure Frank-Wolfe, conjugate direction Frank-Wolfe (CFW), bi-conjugate Frank-Wolfe (BFW), and "partanized" Frank-Wolfe methods to some classical Traffic Assignment Problems show that CFW and BFW compare favorably to the other methods. This spurred a more detailed study, comparing our methods to an origin-based algorithm. This study indicates that our methods are competitive for accuracy requirements ensuring link flow stability. We also show that CFW is globally convergent. We further point at independent studies by other researchers that show that our methods compare favorably with recent bush-based and gradient projection algorithms on computers with several cores

National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-14437 (URN)10.1287/trsc.1120.0409 (DOI)000318852300010 ()
Available from: 2007-04-27 Created: 2007-04-27 Last updated: 2017-12-13
2. Multi-Class User Equilibria under Social Marginal Cost Pricing
Open this publication in new window or tab >>Multi-Class User Equilibria under Social Marginal Cost Pricing
2002 (English)In: Operations Research 2002, 2002, 174-179 p.Conference paper, Published paper (Other academic)
Abstract [en]

In the congested cities of today, congestion pricing is a tempting alternative. With a single user class, already Beckmann et al. showed that ``system optimal'' traffic flows can be achieved by social marginal cost (SMC) pricing where users have to pay for the delays the incur on others. However different user classes can have widly differing time values. Hence, when introducing tolls, one should consider multi-class user equilibria, where the classes have different time values. In the single class case, the equilibrium conditions can be viewn as optimality conditions of an equivalent optimization problem. In the multi-class case, however, netter claims that this is not possible. We show that, depending on the formulation, the multi-class SMC-pricing equilibrium problem (with different time values) can be stated either as an asymmetric or as a symmetric equilibrium problem. In the latter case, the corresponding optimization problems is in general non-convex. For this non-convex problem, we devise descent methods of Frank-Wolfe type. We apply the methods and study a synthetic case based on Sioux Falls.

National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-14438 (URN)978-3-540-00387-8 (ISBN)
Available from: 2007-04-27 Created: 2007-04-27 Last updated: 2009-05-11
3. A Conjugate Direction Frank-Wolfe Method for Nonconvex Problems
Open this publication in new window or tab >>A Conjugate Direction Frank-Wolfe Method for Nonconvex Problems
2003 (English)Report (Refereed)
Abstract [en]

In this paper we propose an algorithm for solving problems with nonconvex objective function and linear constraints. We extend the previously suggested Conjugate direction Frank–Wolfe algorithm to nonconvex problems. We apply our method to multi-class user equilibria under social marginal cost pricing. Results of numerical experiments on Sioux Falls and Winnipeg are reported.

Series
LiTH-MAT-R, ISSN 0348-2960 ; 2003:09
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-14439 (URN)
Available from: 2007-04-27 Created: 2007-04-27 Last updated: 2016-07-01Bibliographically approved
4. A Comparison of Feasible Direction Methods for the Stochastic Transportation Problem
Open this publication in new window or tab >>A Comparison of Feasible Direction Methods for the Stochastic Transportation Problem
2010 (English)In: Computational optimization and applications, ISSN 0926-6003, E-ISSN 1573-2894, Vol. 46, no 3, 451-466 p.Article in journal (Refereed) 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.

Keyword
Stochastic transportation problem, Frank–Wolfe method, Descent methods, Cartesian product sets
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-14440 (URN)10.1007/s10589-008-9199-0 (DOI)000278736100004 ()
Available from: 2007-04-27 Created: 2007-04-27 Last updated: 2017-12-13
5. A Sequential Linear Programming Algorithm with Multi-dimensional Search: Derivation and Convergence
Open this publication in new window or tab >>A Sequential Linear Programming Algorithm with Multi-dimensional Search: Derivation and Convergence
Show others...
2007 (English)Article in journal (Other academic) Submitted
Abstract [en]

We present a sequential linear programming, SLP, algorithm in which the traditional line-search step is replaced by a multi-dimensional search. The algorithm is based on inner approximations of both the primal and dual spaces, which yields a method which in the primal space combines column and constraint generation. The algorithm does not use a merit function, and the linear programming subproblem of the algorithm differs from the one obtained in traditional methods of this type, in the respect that linearized constraints are taken into account only implicitly in a Lagrangiandual fashion. Convergence to a point that satisfies the Karush-Kuhn-Tucker conditions is established. We apply the new method to a selection of the Hoch-Schittkowski’s nonlinear test problems and report a preliminary computational study in a Matlab environment. Since the proposed algorithmcombines column and constraint generation, it should be advantageous with large numbers of variables and constraints.

National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-14441 (URN)
Available from: 2007-04-27 Created: 2007-04-27 Last updated: 2016-07-01Bibliographically approved

Open Access in DiVA

fulltext(303 kB)16179 downloads
File information
File name FULLTEXT01.pdfFile size 303 kBChecksum MD5
c828fbe56ab5b2d9158fb881f51d40bfff3bfa70df81be5e61d3e455210f45e4307a37f6
Type fulltextMimetype application/pdf
popular summary(9 kB)128 downloads
File information
File name POPULARSUMMARY01.pdfFile size 9 kBChecksum MD5
b9b7b6b324aa77f1fad3c18be2c317a7e9995ba3a6681010388ab00fa60a9e64b10311d4
Type popularsummaryMimetype application/pdf

Authority records BETA

Mitradjieva-Daneva, Maria

Search in DiVA

By author/editor
Mitradjieva-Daneva, Maria
By organisation
Optimization The Institute of Technology
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 16179 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 5565 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf