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

Direct link
Methods for Network Optimization and Parallel Derivative-free Optimization
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
2014 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

This thesis is divided into two parts that each is concerned with a specific problem.

The problem under consideration in the first part is to find suitable graph representations, abstractions, cost measures and algorithms for calculating placements of unmanned aerial vehicles (UAVs) such that they can keep one or several static targets under constant surveillance. Each target is kept under surveillance by a surveillance UAV, which transmits information, typically real time video, to a relay UAV. The role of the relay UAV is to retransmit the information to another relay UAV, which retransmits it again to yet another UAV. This chain of retransmission continues until the information eventually reaches an operator at a base station.

When there is a single target, then all Pareto-optimal solutions, i.e. all relevant compromises between quality and the number of UAVs required, can be found using an efficient new algorithm. If there are several targets, the problem becomes a variant of the Steiner tree problem and to solve this problem we adapt an existing algorithm to find an initial tree. Once it is found, we can further improve it using a new algorithm presentedin this thesis.

The second problem is optimization of time-consuming problems where the objective function is seen as a black box, where the input parameters are sent and a function valueis returned. This has the important implication that no gradient or Hessian information is available. Such problems are common when simulators are used to perform advanced calculations such as crash test simulations of cars, dynamic multibody simulations etc. It is common that a single function evaluation takes several hours.

Algorithms for solving such problems can be broadly divided into direct search algorithms and model building algorithms. The first kind evaluates the objective function directly, whereas the second kind builds a model of the objective function, which is then optimized in order to find a new point where it is believed that objective function has agood value. Then the objective function is evaluated in that point.

Since the objective function is very time-consuming, it is common to focus on minimizing the number of function evaluations. However, this completely disregards the possibility to perform calculations in parallel and to exploit this we investigate different ways parallelization can be used in model-building algorithms. Some of the ways to do this is to use several starting points, generate several new points in each iteration, new ways of predicting a point’s value and more.

We have implemented the parallel extensions in one of the state of the art algorithms for derivative-free optimization and report results from testing on synthetic benchmarksas well as from solving real industrial problems.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2014. , 319 p.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1580
Keyword [en]
Derivative-free, parallelization, Steiner tree, constrained shortest path, unmanned aerial vehicles
National Category
Other Mathematics
URN: urn:nbn:se:liu:diva-104110DOI: 10.3384/diss.diva-104110ISBN: 978-91-7519-388-5 (print)OAI: diva2:695431
Public defence
2014-03-20, BL32, B-huset, ingång 23, Campus Valla, Linköpings Universitet, Linköping, 10:15 (English)
Available from: 2014-02-24 Created: 2014-02-07 Last updated: 2014-02-24Bibliographically approved

Open Access in DiVA

Methods for Network Optimization and Parallel Derivative-free Optimization(11842 kB)582 downloads
File information
File name FULLTEXT02.pdfFile size 11842 kBChecksum SHA-512
Type fulltextMimetype application/pdf
omslag(570 kB)8 downloads
File information
File name COVER01.pdfFile size 570 kBChecksum SHA-512
Type coverMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Olsson, Per-Magnus
By organisation
Optimization The Institute of Technology
Other Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 582 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

Altmetric score

Total: 445 hits
ReferencesLink to record
Permanent link

Direct link