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

Direct link
Methods for Network Optimization and Parallel Derivative-free Optimization
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, pages
Linköping: Linköping University Electronic Press, 2014. 319 p.
Series
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
Identifiers
urn:nbn:se:liu:diva-104110 (URN)10.3384/diss.diva-104110 (DOI)978-91-7519-388-5 (print) (ISBN)oai:DiVA.org:liu-104110 (OAI)diva2:695431 (DiVA)
Public defence
2014-03-20, BL32, B-huset, ingång 23, Campus Valla, Linköpings Universitet, Linköping, 10:15 (English)
Opponent
Supervisors
Available from2014-02-24 Created:2014-02-07 Last updated:2014-02-24Bibliographically approved

Open Access in DiVA

fulltext(11842 kB)349 downloads
File information
File name FULLTEXT02.pdfFile size 11842 kBChecksum SHA-512
a78f99d56feec8750bf05f0d05141e1cdc691a1a16b9c472744a6ac34c71edc1ef6743778074c64b0ec6aee56f311dee65c01a2b38c8da4ca70cd8e3382c6f51
Type fulltextMimetype application/pdf
cover(570 kB)6 downloads
File information
File name COVER01.pdfFile size 570 kBChecksum SHA-512
0fd194b6d79cbd0c9c4640268e22d06f440058d1a917abf54676af35c33854ba3ad12e9b7e2809efdbf7340b9703894e73b523ba7457d32ec99a785f56b59a08
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: 349 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: 258 hits
ReferencesLink to record
Permanent link

Direct link