LiU Electronic Press
Download:
File size:
11842 kb
Format:
application/pdf
Author:
Olsson, Per-Magnus (Linköping University, Department of Mathematics, Optimization ) (Linköping University, The Institute of Technology)
Title:
Methods for Network Optimization and Parallel Derivative-free Optimization
Department:
Linköping University, Department of Mathematics, Optimization
Linköping University, The Institute of Technology
Publication type:
Doctoral thesis, monograph (Other academic)
Language:
English
Place of publ.: Linköping Publisher: Linköping University Electronic Press
Pages:
319
Series:
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524; 1580
Year of publ.:
2014
URI:
urn:nbn:se:liu:diva-104110
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-104110
ISBN:
978-91-7519-388-5 (print)
Subject category:
Other Mathematics
Keywords(en) :
Derivative-free, parallelization, Steiner tree, constrained shortest path, unmanned aerial vehicles
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.

Public defence:
2014-03-20, BL32, B-huset, ingång 23, Campus Valla, Linköpings Universitet, Linköping, 10:15 (English)
Degree:
Doctor of Philosophy (PhD)
Supervisor:
Holmberg, Kaj, Professor (Linköping University, Department of Mathematics, Optimization ) (Linköping University, The Institute of Technology)
Opponent:
Migdalas, Athanasios, Professor (Luleå tekniska universitet)
Available from:
2014-02-24
Created:
2014-02-07
Last updated:
2014-02-24
Statistics:
247 hits
FILE INFORMATION
File size:
11842 kb
Mimetype:
application/pdf
Type:
fulltext
Statistics:
336 hits
File size:
570 kb
Mimetype:
application/pdf
Type:
cover
Statistics:
5 hits