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
A Sequential Linear Programming Algorithm with Multi-dimensional Search: Derivation and Convergence
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.ORCID iD: 0000-0003-2094-7376
Mathematical Sciences, Chalmers University of Technology and Göteborg University, Gothenburg, Sweden.
Show others and affiliations
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.

Place, publisher, year, edition, pages
2007.
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-14441OAI: oai:DiVA.org:liu-14441DiVA: diva2:23508
Available from: 2007-04-27 Created: 2007-04-27 Last updated: 2016-07-01Bibliographically approved
In thesis
1. Feasible Direction Methods for Constrained Nonlinear Optimization: Suggestions for Improvements
Open this publication in new window or tab >>Feasible Direction Methods for Constrained Nonlinear Optimization: Suggestions for Improvements
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
constrained nonlinear optimization, feasible direction methods, conjugate directions, traffic equilibrium problem, sequential linear programming algorithm, stochastic transportation problem
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-8811 (URN)978-91-85715-11-4 (ISBN)
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

Open Access in DiVA

No full text

Other links

Link to Ph.D. thesis

Authority records BETA

Daneva (Mitradjieva), MariaGöthe-Lundgren, MaudLarsson, TorbjörnRydergren, Clas

Search in DiVA

By author/editor
Daneva (Mitradjieva), MariaGöthe-Lundgren, MaudLarsson, TorbjörnRydergren, Clas
By organisation
Optimization The Institute of TechnologyDepartment of Science and Technology
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 652 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