Document [original]

Numerical algorithms for the treatment

of parametric multiobjective optimization

problems and applications

Von der Fakult¨

at f¨

ur Elektrotechnik, Informatik und Mathematik

der Universit¨

at Paderborn

zur Erlangung des akademischen Grades

eines Doktor der Naturwissenschaften

– Dr. rer. nat. –

genehmigte Dissertation

von

Katrin Witting

Paderborn 2012

Datum der Einreichung: 14.12.2011

Tag der m¨

undlichen Pr¨

ufung: 22.02.2012

Gutachter: Prof. Dr. Michael Dellnitz

Universit¨

at Paderborn

Prof. Dr. Kathrin Klamroth

Bergische Universit¨

at Wuppertal

iii

Abstract

Nowadays, mathematical optimization plays an important role in many

applications. Often not only one objective is desired to be optimized but

several aims have to be considered at the same time. For example, in ma-

nufacturing not only costs should be minimized but at the same time the

product should be of high quality. The development of theoretic and al-

gorithmic principles for the mathematical description of these problems is

the concern of multiobjective optimization. In the present thesis, different

multiobjective optimization problems from mechanical engineering are stud-

ied. Motivated by the example of the operating point assignment of a linear

drive, the focus of this thesis lies on the study of parametric multiobjective

optimization problems. Firstly, a new approach is presented which allows to

solve time-dependent multiobjective optimization problems by use of nume-

rical path following algorithms. Subsequently, the computation of solutions

which change as little as possible under variations of the external parameter

is another central topic of this thesis. For the numerical approximation of

these so-called robust Pareto points, in this work two new approaches are

presented. The first approach is based on the classical calculus of variations

while the second one makes use of numerical path following methods. Finally,

geometrical properties of the solution set of non-convex, parametric multi-

objective optimization problems are studied and connections to bifurcation

theory are pointed out.

Zusammenfassung

Heutzutage spielt die mathematische Optimierung in vielen Anwendun-

gen eine wesentliche Rolle. H¨

aufig ergibt sich der Wunsch, nicht nur ein ein-

ziges Ziel sondern mehrere Ziele gleichzeitig zu optimieren. So sollten bei-

spielsweise bei der Fertigung eines Produktes nicht nur die Kosten minimiert

werden, sondern gleichzeitig sollte auch ein qualitativ hochwertiges Produkt

entstehen. Die Entwicklung von theoretischen und algorithmischen Grundla-

gen f¨

ur die mathematische Beschreibung und L¨

osung solcher Probleme bie-

tet die Mehrzieloptimierung. In der vorliegenden Arbeit werden verschiedene

Mehrzieloptimierungsprobleme aus dem ingenieurwissenschaftlichen Bereich

untersucht. Motiviert durch das Beispiel der Arbeitspunktsteuerung eines Li-

nearmotors liegt der Fokus dieser Arbeit auf der Studie parameterabh¨

angiger

Mehrzieloptimierungsprobleme. Es wird zum einen ein neuer Ansatz vorge-

stellt, der mittels Verwendung von Algorithmen zur numerischen Pfadverfol-

gung die L¨

osung zeitabh¨

angiger Mehrzieloptimierungsprobleme erlaubt. Zum

anderen ist die Bestimmung von L¨

osungen, die sich gegen¨

uber Schwankungen

eines externen Parameters m¨

oglichst wenig ver¨

andern, ein weiteres zentrales

Thema dieser Arbeit. F¨

ur die numerische Approximation dieser sogenannten

robusten Paretopunkte werden in der vorliegenden Arbeit zwei neuartige An-

s¨

atze pr¨

asentiert, die zum einen auf der Variationsrechnung und zum anderen

auf numerischer Pfadverfolgung basieren. Abschließend werden geometrische

Eigenschaften der L¨

osungsmenge nicht-konvexer, parametrischer Mehrzielop-

timierungsprobleme untersucht und Zusammenh¨

ange zur Verzweigungstheo-

rie aufgezeigt.

Acknowledgments

First of all, I wish to express my gratitude to my parents Dagmar and

Wilfried Baptist. Many, many thanks for your love, patience and support in

all aspects of my life. Just as much I would like to thank my beloved husband

Sven who acted as a loving motivator (and a perfect contact person for any

computer problems). With love I thank our son Benjamin who makes me

happy every day through his cheerful nature.

I am greatly indebted to Prof. Dr. Michael Dellnitz for giving me the

chance to write this thesis under his supervision. I thank him for suggesting

the problem and for many stimulating conversations. Very fruitful discus-

sions have also taken place with my colleagues. Many thanks to Prof. Dr.

Oliver Sch¨

utze who once introduced me to the topic of multiobjective opti-

mization and was my first contact person at the beginning. I also wish to

express my special thanks to Dr. Mirko Hessel–von Molo who seems to know

everything. Thank you, Mirko, for discussing many, many scientific (and

other) questions. Especially, two products of this type of discussion were

the construction of Examples 4.24 and 4.26, and the geometrical interpreta-

tion of Condition (4.24) on page 96. I would also like to thank Jun.-Prof.

Dr. Sina Ober-Bl¨

obaum who spent her time to explain how to formulate the

discretized Euler-Lagrange equations, and this way supported me in formu-

lating the robustness concept described in Paragraph 4.4.2. Further, I thank

my other colleagues and ex-colleagues Tanja B¨

urger, Dr. Roberto Castelli,

Dr. Alessandro Dell’Aere, Dr. Laura Di Gregorio, Helene Derksen-Riesen,

Kathrin Flaßkamp, Sebastian Hage-Packh¨

auser, Christian Horenkamp, Prof.

Dr. Oliver Junge, Marianne Kalle, Dr. Stefan Klus, Dr. Arvind Krishna-

murthy, Anna-Lena Meyer, Jun.-Prof. Dr. Kathrin Padberg-Gehle, Pier-

paolo Pergola, Michael Petry, Dr. Marcus Post, Prof. Dr. Robert Preis,

Marcel Schwalb, Stefan Sertl, Simon Sonntag, Robert Timmermann, Bianca

Thiere, Dr. Wang Fang, and Anna Zanzottera for the good colleagueship,

friendship and support in not only scientific questions.

This work was developed in the course of the Collaborative Research Cen-

ter 614 – Self-Optimizing Concepts and Structures in Mechanical Engineering

– University of Paderborn, and funded by the Deutsche Forschungsgemein-

schaft. Thus, my work in large part was interdisciplinary. I wish to thank

the Chair of Power Electronics and Electrical Drives (especially Bernd Schulz,

Tobias Schneider, Christoph Romaus, Dr.-Ing. Andreas Pottharst, Dr.-Ing.

Rongyuan Li and Dr.-Ing. Tobias Knoke), the Chair of Control Engineer-

ing and Mechatronics (especially Jens Geisler, Dr.-Ing. Oliver Oberschelp,

Henner V¨

ocking, Peter Reinold and Martin Kr¨

uger) and the Department

of System and Circuit Technology (especially Dr.-Ing. Matthias Blesken) for

their cooperation, discussions and motivation through technical applications.

I am very grateful to the student research assistents that worked within our

research project over the last years. Namely, I want to thank Albert Seifried

and Dominik Steenken. Thanks, Albert, for the execution of numerous com-

putations, for documenting existing code and for supporting me with your

knowledge about the creation of pretty Matlab figures. Thanks, Dominik, for

developing a parallelized version of our multiobjective optimization software

which speeds up most of the computations significantly, and for maintaining

the cooperation with Matthias Blesken and hereby producing many inter-

esting results within your diploma thesis (which partly are mentioned in my

thesis as well).

A special thanks goes to all my friends, primarily Michael Mair for proof-

reading the manuscript. Also, at this point I would like to thank Marc Pfetsch

who put the L

EX sources for setting his thesis into the web. It was very

helpful for me to use these settings as a basis for my own L

EX style.

Contents

1 Introduction 1

2 Theoretical Background 11

2.1 Preliminaries and Notation . . . . . . . . . . . . . . . . . . . . 11

2.2 Nonlinear Optimization . . . . . . . . . . . . . . . . . . . . . 13

2.2.1 Problem Formulation . . . . . . . . . . . . . . . . . . . 13

2.2.2 Optimality Conditions . . . . . . . . . . . . . . . . . . 14

2.3 Calculus of Variations . . . . . . . . . . . . . . . . . . . . . . 19

2.4 Parametric Optimization . . . . . . . . . . . . . . . . . . . . 25

2.4.1 Theoretical Basics for Unconstrained One-parametric

Optimization Problems . . . . . . . . . . . . . . . . . . 26

2.4.2 Numerical Path Following . . . . . . . . . . . . . . . . 28

2.5 Self-Optimization . . . . . . . . . . . . . . . . . . . . . . . . . 30

3 Multiobjective Optimization 33

3.1 Problem Formulation and Pareto Optimality . . . . . . . . . . 34

3.2 Methods for the Computation of Pareto Points . . . . . . . . 38

3.2.1 Overview ......................... 38

3.2.2 The Weighted Sums Method . . . . . . . . . . . . . . . 39

3.2.3 Set-oriented Methods . . . . . . . . . . . . . . . . . . 40

3.3 Dents in Pareto Fronts . . . . . . . . . . . . . . . . . . . . . . 42

3.4 Treatment of Multiobjective Optimization Problems in several

Technical Applications . . . . . . . . . . . . . . . . . . . . . . 45

3.4.1 The RailCab System . . . . . . . . . . . . . . . . . . . 46

3.4.2 Multiobjective Optimization of the Hybrid Energy Stor-

ageSystem ........................ 48

3.4.3 Self-optimization of the Guidance Module . . . . . . . 51

3.4.4 Multiobjective Optimization of the Linear Drive . . . . 56

4 Parametric Multiobjective Optimization 63

4.1 Problemsetting.......................... 64

4.2 Numerical Path Following and Multiobjective Optimization . . 65

4.3 Time-dependent Multiobjective Optimization Problems . . . . 66

4.3.1 Computation of Solution Paths . . . . . . . . . . . . . 67

vii

viii Contents

4.3.2 Application: Online Optimization of the Operating Point

Assignment of a Linear Motor . . . . . . . . . . . . . . 70

4.4 Robust Pareto Points . . . . . . . . . . . . . . . . . . . . . . . 75

4.4.1 Existing Robustness Definitions in Multiobjective Op-

timization......................... 76

4.4.2 New Concepts for Robustness against Variations of an

External Parameter . . . . . . . . . . . . . . . . . . . . 80

4.4.3 Application: Robust Pareto Points in the Design of

Integrated Circuits . . . . . . . . . . . . . . . . . . . . 114

4.5 Dents in Parameter-dependent Pareto Fronts . . . . . . . . . . 117

4.5.1 Properties of Dent Border Points . . . . . . . . . . . . 118

4.5.2 Examples for Parametric Multiobjective Optimization

Problems with Dents . . . . . . . . . . . . . . . . . . . 121

5 Conclusion and Outlook 129

Bibliography 135

Index 145

Contents ix

List of Acronyms

CRC collaborative research center

HES hybrid energy storage system

h. o. t. higher order terms

iff if and only if

MOP multiobjective optimization problem

NLO nonlinear optimization problem

NLO=equality-constrained nonlinear optimization problem

ParMOP parametric multiobjective optimization problem

uPOP unconstrained parametric optimization problem

uNLO unconstrained nonlinear optimization problem

VC problem of variational calculus, variational problem

VC2pvariational problem with fixed end points

VC2p-c variational problem with fixed end points with equality constraints

VCff -c variational problem with free end points with equality constraints

wlog without loss of generality

List of Symbols

identity matrix

kxk=kxk2Euclidean norm of a vector x∈Rn

<·,·>Euclidean scalar product

αweight vector

ATtranspose of the matrix A∈Rm×n

Cmm-times continuously differentiable functions

δjf(p) partial derivative of f:Rn→Rwith respect to

the j’th variable at the point p

∂f

∂xi(p) partial derivative of f:Rn→Rwith respect to

the variable xiat the point p

im Aimage of the matrix A∈Rm×n, i. e. {Ax|x∈Rn}

ker Akernel of the matrix A∈Rm×n, i. e. {x∈Rn|Ax = 0}

Ttime

t, or

(t2

1,...t2

k) respectively weight vector

Pλλ-dependent Pareto set

PFλλ-dependent Pareto front

R+Set of all positive real numbers

R+,0Set of all real numbers that are ≥0

incl ⊆Rk{x∈Rk:xd+1 =. . . =xk= 0}(canonical inclusion)

Sλλ-dependent set of substationary points

Bclosure of a set B

V⊥orthogonal complement of the vector space V

Chapter 1

Introduction

In almost any application optimization plays an important role. In a variety

of these not only one objective but several ones are desired to be optimal at

the same time. For instance, in manufacturing cost has to be minimized, but

at the same time also quality is desired to be maximal – at least to a certain

degree. The development of theory and algorithms for the determination

of solutions that are as good as possible with respect to all objectives is

the task of multiobjective optimization. Mathematically, a multiobjective

optimization problem is given as

min

x{F(x) : x∈S⊆Rn},

where Fis defined as the vector of the objective functions f1, . . . , fk,k≥2,

which each map from Rnto R, and Sdenotes the feasible region. The exam-

ple mentioned above already illustrates that the several objectives typically

contradict each other and thus do not have identical optima. Consequently,

the solution of a multiobjective optimization problem is given by the set of

optimal compromises of the objectives, the so-called Pareto set. In the case

of minimization problems the Pareto set is given by the set of solutions in

which the value of any objective function can only be decreased at the cost

of increasing another one.

To obtain solutions that lie within the Pareto set many algorithms have

been developed. There are essentially two different types: algorithms that

allow for the computation of only one or a few Pareto points, and algorithms

that approximate the entire Pareto set. In the first case often a priori in-

formation, such as a specific weighting of the objectives or some kind of

ordering, is required. Examples for those methods are the ’weighted sums

method’, the ’ε-constraint-method’ and the ’lexicographic ordering’ (see [69],

[24]). Over the last years algorithms that are able to approximate the entire

Pareto set (restricted to a moderate number kof objectives) have been devel-

oped (see e. g. [14, 85, 15, 32, 12, 112]). For the computations of Pareto sets

in the examples given in this thesis set-oriented, numerical methods which

are implemented in the software package GAIO1have been used (see [92]),

1Global Analysis of Invariant Objects, see www.math.upb.de/˜agdellnitz

2Introduction

and Section 3.2.3 for more details).

For the development of modern, innovative mechatronic systems, the con-

cept of self-optimization has been introduced (cf. [1]). A technical system

is self-optimizing whenever three steps are repeated iteratively during ope-

ration: the analyis of the current situation (Step 1), the determination of

the system’s objectives (Step 2) and the adaptation of the system’s behavior

(Step 3). Thus, self-optimization goes beyond the classical adaptive control

in which the system’s objectives are not changing during runtime. Multiob-

jective optimization plays an important role in the self-optimization process.

One possibility to realize Step 3 – for a technical system which can be de-

scribed by a mathematical model – is to choose different solutions during

operation time from a previously approximated Pareto set. One technical

application that serves as an example to demonstrate self-optimization is the

RailCab system. The RailCab is a novel linear motor driven railway sys-

tem including the latest technologies and innovative prototypes, developed

by the project RailCab (“Neue Bahntechnik Paderborn” [73]). Many subsys-

tems contained in the RailCab provide great potential for self-optimization.

In this thesis, in particular three different subsystems of the RailCab have

been studied in close collaboration with the engineers developing these sys-

tems: the hybrid energy storage system, the guidance module and the linear

drive.

The hybrid energy storage system is intended to guarantee the availability

of energy without any interruption. It consists of batteries which are well-

suited for long term storage and double layer capacitors which perfectly fit

the purpose of short term storage. The mathematical challenge is computing

an operation strategy that distributes the power flows to the respective stor-

age devices in an optimal way during a drive of the vehicle. In this thesis the

simultaneous minimization of the normalized energy losses of the hybrid en-

ergy storage system and maximization of the power reserve has been studied

as a multiobjective optimization problem in close cooperation with the Chair

of Power Electronics and Electrical Drives, University of Paderborn. Making

use of a special numerical, image set oriented predictor-corrector method for

multiobjective optimization Pareto optimal operation strategies for a given

total power profile have been approximated. In Section 3.4.2 the results of

the multiobjective optimization of the hybrid energy storage system are given

for an example of a track section of one minute.

The guidance module allows to actively control the lateral displacement of

the RailCab vehicle within the rails. Thus, the RailCab can be steered along

arbitrary reference trajectories within the maximum distance between the

flanges and the rail-heads, the so-called clearance. How to choose these refe-

rence trajectories has been considered in this thesis in close cooperation with

the Chair of Control Engineering and Mechatronics, University of Paderborn

(see Section 3.4.3). To obtain good trajectories four different objectives have

been taken into account: maximization of the passengers comfort measured

through the structure acceleration, minimization of the deviation from the

track centerline, minimization of the average energy consumption of the hy-

draulic actuators, and maximization of the steering angle reserve. As a start,

an optimal control problem of the form

min

x∈Rn,u∈RmJ(x, u)

s. t. ˙x=f(x, u)

is formulated in which the differential equation is given by a linear model for

the lateral dynamics of the RailCab vehicle, and the functional Jis vector-

valued. Linear systems ˙x=f(x, u) are differentially flat, which means that

the inputs and controls can be computed directly from the outputs. Thus,

the trajectory optimization of the guidance module can be reformulated into

a multiobjective optimization problem in which only the outputs are opti-

mized. By this approach we have shown how the work of Murray et al on

trajectory optimization for differentially flat systems (see [72, 104, 70, 31])

can be extended to the multiobjective case. In Section 3.4.3 the results of

the multiobjective optimization of the reference trajectories for an exemplary

track section are presented.

The RailCab vehicle is propelled by a doubly-fed linear drive which con-

sists of a primary motor part between the rails of the track and a secondary

part on the vehicle. The power transfer from the primary to the secondary

motor part depends on the operating point of the linear motor which is given

through the currents and frequencies in both motor parts. The operating

points are desired to maximize both the degree of efficiency of the linear

motor and the power factor. In this work, this multiobjective optimization

problem has been addressed in close cooperation with the Chair of Power

Electronics and Electrical Drives, University of Paderborn. The amount of

power that has to be transferred into the secondary motor part depends on

the maneuver the vehicle is intended to perform. Thus, the objective func-

tions depend on the planned maneuver which consists of the planned course of

velocities, thrusts and demanded powers. These dependencies can be reduced

to time-dependency, i. e. the objective functions depend on one external pa-

rameter. In a first study presented in Section 3.4.4 the approximation of

4Introduction

Pareto sets for discretized points in time has been studied. A certain new

decision heuristic has been developed in this work that allows to choose one

Pareto point from the entire Pareto set depending on the actual situation.

Here, two different parameters that are not considered in the optimization

process come into play: the temperature of the secondary motor part and the

load value of a battery which is installed at the motor to guarantee constant

power supply even if the connection to the primary motor part is disrupted.

Also, the shape of the Pareto front is taken into account in the decision

heuristic such that no points in very flat or steep regions are chosen (under

the assumption that each objective is scaled adequately). To sum up, the

decision heuristic allows an automated, situation-dependent choice of Pareto

optimal solutions during operation time, and hereby is an important element

of the self-optimization of the linear motor.

In order to generate a satisfactory approximation of operating points for

a drive of the linear motor, the computation of Pareto sets would be neces-

sary for very many discretization points in time, approximately every one or

two milliseconds. This computation cannot be realized during runtime as the

computational effort is too high. An a priori approximation of the Pareto

sets, its storage and an application of the decision heuristic during runtime

on the stored data is not preferable because arbitrarily many different ma-

neuvers have to be considered.

Motivated hereby, in this thesis a new mathematical concept has been

developed which allows the treatment of time-dependent multiobjective opti-

mization problems. This concept allows the computation of Pareto optimal

solutions over time and can in the case of the linear drive be realized during

operation time. Mathematically speaking, a one-parametric multiobjective

optimization problem has to be solved which can be formulated as

min

x{F(x, λ) : x∈Rn, λ ∈[λstart, λend]⊆R}

with F:Rn×R→Rk,F(x, λ)=(f1(x, λ), . . . , fk(x, λ)).

In the case of the linear drive, the external parameter λis given by time.

The Pareto set of a parametric multiobjective optimization problem obviously

depends on the external parameter λ. A necessary condition for Pareto opti-

mality is given by the famous Kuhn-Tucker equations (see [63]) which indicate

that in each Pareto optimal point the gradients of the objective functions are

linearly dependent. In the case of parametric multiobjective optimization

problems this system of equations also depends on the external parameter λ

and is given by

HKT(x, α, λ) =

i=1

αi∇xfi(x, λ) = 0,

where Pk

i=1 αi= 1 and αi≥0∀i= 1, . . . , k.

Solutions xwhich satisfy the Kuhn-Tucker equations are called substa-

tionary points. One of the main ideas presented in this thesis is to apply nu-

merical path following methods (cf. [22, 2, 75]) to the parameter-dependent

Kuhn-Tucker necessary condition. Numerical path following methods allow

the approximation of λ-dependent solution paths for systems of equations

with one more unknowns than equations. The solution paths are obtained

by iteratively repeating predictor and corrector steps. Starting from a known

point (x?, λ?) on the solution curve in the predictor step a point (xp, λp) with

λp=λ?+his computed, where his an adequate step size. This point serves

as an initial guess for the numerical solution of the system of equations with

a fixed value λ=λpwhich is performed in the so-called corrector step.

The Kuhn-Tucker equations do not only depend on the optimization pa-

rameter xand the external parameter λbut also on the weight vector α.

Different weight vectors lead to the computation of different substationary

points. Thus, the main challenge in applying numerical path following meth-

ods to the Kuhn-Tucker equations lies in the treatment of the weight vector

α. This vector characterizes the direction in which a solution path is“steered”

through the λ-dependent set of substationary points. Consequently, addition-

ally to the Kuhn-Tucker equations some more equations have to be derived

which fix the direction of the solution path. How to define such a direction

through additional equations depends on the application under consideration.

For time-dependent multiobjective optimization problems like in the case

of the linear drive it turns out to be a good idea to consider paths with fixed

weights over certain time periods. Here, first an initial Pareto set is approx-

imated. During operation time, a suitable point within this set is chosen

by the decision heuristic and the corresponding weight vector obtained by

solving the Kuhn-Tucker equations is set fixed. By use of classical predictor-

corrector path following methods a solution path over time is computed and

at the respective points in time the corresponding solutions are adjusted to

the motor. A recomputation of the entire Pareto set is only performed if

variables included in the decision heuristic change drastically, or if the op-

timization setup changes due to other technical reasons. Performing these

steps during operation of the linear drive the system becomes self-optimizing.

More detailed information about this application is given in Section 4.3.2.

Besides time, the parameter λcan describe the influence of any other param-

6Introduction

eter to the objective functions. Imagine for instance the design process of a

car which is desired to be optimal with respect to comfort (first objective)

and safety (second objective). On the road, the car will be caught in a cross-

fire of influences, like side wind, wet roads, or changes in temperature. The

only information one might have is that these influences can be estimated to

lie within a certain interval, probably given by the weather forecast. For the

designer of this car subsets of Pareto points are especially desirable, for which

the Pareto points or their images under Fchange as little as possible while the

parameter varies. This fictitious example already inspires the development of

special robustness concepts for parametric multiobjective optimiza-

tion problems which is the main matter of this thesis. The study of the

robustness of solutions is a relatively young area of research in multiobjective

optimization, especially in evolutionary multiobjective optimization (cf. [16],

[29] for example). Following [10], multiobjective optimization problems can

be formulated as

min

x0,x00 F(x0, x00 +ε, λ)

where x0∈Rn1are deterministic optimization variables, x00 +εdescribes

some kind of stochastic optimization variables with x00 ∈Rn2,n1+n2=

n, and λ∈Rpdenotes external parameters. Different kinds of robustness

for multiobjective optimization problems are studied in the literature (see

Section 4.4.1 for an overview). This work restricts itself to the case of one

real, external parameter λ. None of the concepts developed in the literature

includes the condition that the solutions should stay Pareto optimal w. r. t.

the perturbed parameter values for the original objective functions. In this

thesis, two new robustness concepts have been developed which measure

how much a Pareto optimal solution (or, a solution on the Pareto front)

has to change when demanding Pareto optimality within a certain interval

[λstart, λend] of the external parameter. Loosely speaking, the more robust a

Pareto point for a fixed external parameter value is the less it changes to

other Pareto points for different values of the external parameter within a

given interval. The same considerations can be transferred to the study of

robustness on Pareto fronts. In both cases, the techniques used to obtain

robust solutions are completely different from the ones used in the literature.

The first concept is based on the calculus of variations whereas in the second

concept again numerical path following methods are employed for a certain

system of equations.

More precisely, in the first concept the variational integral

min

x,α Zλend

λstart kx0(λ)k2dλ

s. t. HKT(x(λ), α(λ), λ)=0

with the boundary conditions that x(λstart) and x(λend) are solutions of the

Kuhn-Tucker equations for the respective parameter values, is studied. This

means that the length of the curve of substationary points on the parameter-

dependent solution set of the Kuhn-Tucker equations is minimized. A curve

x(λ) which solves this variational problem is called a λ-robust substationary

point w. r. t. Concept I.

For the computation of solutions of this constrained variational problem

the multiplier rule (cf. [9]) is used and the Euler-Lagrange equations are de-

rived. They are given as a system of differential algebraic equations that pro-

vide a necessary condition for optimality of the variational integral. To allow

numerical computations of λ-robust substationary points the variational inte-

gral is discretized following the lines of [68] and the discrete Euler-Lagrange

equations are derived. One ends up with a nonlinear system of equations

which can be solved with Newton’s method, for example. In Section 4.4.2

the derivation of the discrete Euler-Lagrange equations for constrained vari-

ational problems is described in detail and numerical examples are given.

A second robustness concept is developed in Section 4.4.2. In contrast to

the variational approach of the first concept, here only local information is

taken into account: solution curves are computed that stay at the same point

constantly as long as this point is feasible under the variation of the external

parameter λ. If a point on the curve is not feasible for an increased value of λ,

then the solution path consists of those points that vary as little as necessary

compared to the previously computed point. The robustness of a Pareto

point against variations of the external parameter can be measured through

the length of these paths. In order to realize the numerical approximation of

solution paths, again numerical path following methods can come into play.

In order to force the path into the direction in which the Pareto point changes

as little as possible for increasing values of λ, the Kuhn-Tucker system has

to be expanded by certain equations.

To attack this problem, first the Pareto sets for two different values λ0and

λ1of the external parameter have been considered. A constrained nonlinear

optimization problem is formulated in which the distance of any point on

the set of substationary points for λ1to the Pareto set for λ0is minimized.

By using a classical necessary condition for optimality of this problem a

system of equations is obtained that characterizes the solution on the set of

8Introduction

substationary points for λ=λ1that is located as near as possible to the

Pareto set for λ0in x-space.

When generating a path of solutions that step by step changes as little

as possible in x-space the same situation occurs repeatedly. A predictor-

corrector method is used to compute the solution path. In the predictor step

the value of λis increased by an adequate step size h. In the corrector step

the system of equations consisting of the Kuhn-Tucker equations and the

distance minimization equations mentioned above is solved for the predicted

value of λ. For the predictor-corrector method it is required that the Jacobian

matrix of the system of equations is regular. In this thesis, the structure of

the Jacobian matrix for the new system of equations has been studied. It

is proven that the Jacobian is indeed regular if a second order sufficient

condition for the underlying minimization problem is satisfied.

The new concept is illustrated for several numerical examples. Finally, in

Section 4.4.3 an application of the second robustness concept in the design

of integrated circuits is given. Here, the robustness of Pareto points with

respect to changes in temperature and supply voltage has been computed.

In Section 4.4.2 the two robustness concept developed within this thesis

are compared. To make this possible the variational problem of Concept I is

reformulated for fixed starting points on the initial Pareto set. It it shown

that the length of solution paths with respect to Concept I is less or equal to

the length of paths obtained with Concept II.

In general, the computation of paths with respect to Concept II is less

computationally costly than by use of Concept I. However, the choice of the

‘right’ concept for the study of robustness of a technical application depends

highly on the application. The first concept delivers a substationary point

which changes as little as possible over an entire interval the external param-

eter is assumed to vary in. On the contrary, by use of the second concept

solution paths are obtained that locally, from one computed point to another,

vary as little as possible.

Motivated by the fact that in the case of nonconvex objective functions

it is not possible to compute all Pareto optimal solutions by the weighted

sums method, in this thesis also the occurrence of dents in Pareto fronts has

been studied. In [13], Das and Dennis give a trigonometric argument why –

in the case of two objectives – the weighted sums method cannot be used to

compute points in the nonconvex part, as they call the subset of the Pareto

front that contains no global optima of the weighted sum of the objectives for

every weight vector. It is an interesting question to find out if a Pareto front

contains nonconvex parts. If one assumes that the Pareto front is connected,

then every nonconvex part contains a region in which the Pareto front ‘curves

inside the feasible region’. This part of the Pareto front will be called a dent.

In Section 3.3 a formal definition of a dent is given. It will be shown that

at the border of a dent (seen as a subset of the Pareto front) typically the

Hessian of the weighted sum of the objectives is singular. These points will

be called dent border points and the corresponding preimages on the Pareto

set will be called dent border preimages.

In the case of parametric multiobjective optimization problems naturally

the question comes up, how dents evolve under the variation of the external

parameter. This question is addressed in Section 4.5. Making use of results

from bifurcation theory it is proven that under certain assumptions dent

border preimages are turning points of the Kuhn-Tucker equations

Hα?

KT(x, λ) =

i=1

α?

i∇xfi(x, λ) = 0,

where α?ist the weight vector corresponding to the dent border preimage.

Several examples of parametric multiobjective optimization problems in which

the Pareto front contains dents will be given at the end of Section 4.5.

The outline of this thesis is as follows: Chapter 2 contains a brief sum-

mary of the theoretical background needed within this thesis. Here, also

the notation is introduced. Chapter 3 deals with the theoretical background

and algorithmic approaches for multiobjective optimization. In this chapter,

three different engineering applications are presented that have been consid-

ered extensively in the context of this thesis. Chapter 3 also contains the

new ideas for the computation of dents in Pareto fronts.

Chapter 4 is the central chapter of this thesis. Here, especially the two

new robustness concepts are derived and a technical application is given.

Also, the design of a new algorithm that allows to compute Pareto optimal

solutions for a linear drive during operation time is presented. Furthermore,

in Chapter 4 the study of dents in parametric multiobjective optimization

problems is addressed. The thesis concludes with a short summary of the

results and a discussion of possible future directions and applications.

Chapter 2

Theoretical Background

In this chapter the theoretical background needed for theory and applications

developed in this thesis is summed up. After a short survey on basic defini-

tions and notations this work is based on, short introductions into the math-

ematical fields nonlinear optimization, the classical calculus of variations and

parametric optimization are given. Some of the technical applications con-

sidered in this thesis are so-called self-optimizing systems. The definition of

self-optimization is given in the last section of this chapter.

2.1 Preliminaries and Notation

As differentiable maps play an important role in this work, in the following

the basic understanding of differentiability, together with the notation used in

this work, is summed up. Everything introduced in this section is elementary

and can be found in the books [52, 61] and many, many others.

Definition 2.1 (Differentiability) A map f:U→Rmis called differentiable

in a point p∈U⊆Rn, if there exists a linear map L:Rn→Rmsuch that

the residuum R(h)given through

f(p+h) = f(p) + L(h) + R(h)

satisfies the condition

lim

h→0

R(h)

khk= 0

in a certain neighborhood of 0∈Rn. The linear map Lis called the differen-

tial of fin pand is denoted by df(p).

The differential df(p) can be represented through a matrix which is called

the Jacobian (matrix) of fin p, denoted by f0(p). It is given by the matrix

of all partial derivatives of f,

f0(p) = ∂f

∂x(p) = 





∂f1

∂x1(p). . . ∂f1

∂xn(p)

∂fm

∂x1(p). . . ∂fm

∂xn(p)





,

12 Theoretical Background

where

∂fi

∂xj

(p) = lim

h→0

h·(fi(x1, . . . , xj+h, . . . , xn)−fi(x1, . . . , xn))

for h∈R\{0}.

If m= 1, i. e. the function fmaps from Rn→R, then the Jacobian

matrix reduces to one row. We denote the the transpose of this row vector

as the gradient

∇f=∇xf=





∂f

∂x1

∂f

∂xn





.

If fdepends on several variables one wants to distinguish, for example

f:Rna+nb→Rwith f(a, b) = y, then we denote the gradient with respect to

aas

∇af=





∂f

∂a1

∂f

∂ana







and the gradient with respect to bas

∇bf=





∂f

∂b1

∂f

∂bnb





.

The matrix representation of the differential of second order (which is

defined as a symmetric, bilinear map) of f:Rn→Rin a point pis given by

the Hessian matrix f00(p), which is defined as

f00(p) = ∂2f

∂x2(p) = 





∂2f

∂x1∂x1(p)··· ∂2f

∂xn∂x1(p)

∂2f

∂x1∂xn(p)··· ∂2f

∂xn∂xn(p)





.

A map γ= (γ1, . . . , γm)T:I→Rmof an interval I⊆R, i. e. a

parametrized curve in Rm, is differentiable in a point T0∈Iif and only

if each of its components is differentiable in T0,

∂γ

∂T (T0) = ˙γ(T0) = ( ˙γ1(T0),..., ˙γm(T0))T.

2.2 Nonlinear Optimization 13

2.2 Nonlinear Optimization

Optimization plays an important role in various applications in almost any

research area. In this section, optimization problems are considered whose

objective function is nonlinear and possibly subject to equality constraints.

Here, only the mathematical problem definition and some necessary and suf-

ficient conditions for optimality that will be needed in the context of this

thesis are summed up. Comprehensive introductions into the field of non-

linear optimization, both theoretically and algorithmically oriented, can be

found in numerous textbooks like [67, 57, 54, 95].

2.2.1 Problem Formulation

In general, a constrained optimization problem is given by

min

x{f(x) : x∈S⊆Rn},(NLO)

where the feasible set Sis given as

S={x∈Rn:h(x) = 0, g(x)≤0}

with h:Rn→Rm, m ≤nand g:Rn→Rqand an objective function

f:S→R. Thus, solutions x?∈Sare to be determined that satisfy

f(x?)≤f(x)∀x∈S. (2.1)

In this case, x?is called a (global) minimizer of f(in S) and f(x?) is called the

(global) minimum. If there exists a neighborhood Uof x?such that equation

2.1 is only valid for all x∈S∩U, then x?is called a local minimizer of f(in

S) and f(x?) is called the local minimum. If the inequality in equation (2.1)

is strict, i. e. f(x?)< f(x)∀x∈Sor x∈U∩Srespectively, then x?is called

astrict (global) minimizer or a strict local minimizer respectively. Minima

are said to be isolated if they are unique within a certain neighborhood.

If no constraints have to be satisfied, which means S=Rn, then the opti-

mization problem (NLO) is called unconstrained. An optimization problem

is called nonlinear if the objective function (and possibly also the constraints)

are nonlinear.

Example 2.2 Consider the nonlinear objective function f:R→R,

f(x) = −1

40x5+7

8x4−59

6x3+ 47x2−96x+ 65,

14 Theoretical Background

Figure 2.1: Example for an unconstrained and a constrained nonlinear optimization

problem

which is wanted to be minimized for x∈[0,7]. The graph of ffor x∈[0,7]

is plotted in Figure 2.1. As one can observe, the function f(x) attains its

global minimum in the point x1= 2 and a local minimum at x2= 6.

Now, the same objective function with an additional constraint is con-

sidered. The optimal solution is desired to lie in the upper semiplane of the

straight line Ggiven by G(x) = −1

2x+ 2. This means that the inequality

condition −f(x)−x+ 2 ≤0 has to be true. As one can easily see in the

right plot of Figure 2.1, in this case x2= 6 is the global minimizer.

In an analogous way, maximization problems can be defined. As it is

possible to convert any maximization problem into a minimization problem,

within this work only minimization problems are considered.

2.2.2 Optimality Conditions

Solutions of optimization problems can under certain assumptions be char-

acterized by different necessary and/or sufficient conditions, which are sum-

marized in the following.

Optimality Conditions for Unconstrained Optimization Problems

Consider the unconstrained optimization problem , given by

min

x{f(x) : x∈Rn}.(uNLO)

Theorem 2.3 (First-order necessary condition [37]) Let X⊆Rnopen and

f:X→Ra continuously differentiable function. If x?∈Xis a local

2.2 Nonlinear Optimization 15

minimum of f, then

∇f(x?)=0.

x?is called a stationary point of f.

Proof: A proof of this theorem can for example be found in [37]. 

By use of this first-order necessary condition, the problem of finding local

solutions of (uNLO) can be traced back to solving a system of nonlinear

equations. The solution set of this system of equations contains not only

local minimizers but possibly also local maximizers and saddle points (cf.

Definition 2.5).

A sufficient condition for generating local minimizers can be formulated

by taking the definiteness of the Hessian matrix of the objective function into

account. In general, a matrix A∈Rn×nis called positive or negative definite,

if xTAx > 0 or xTAx < 0, respectively, for all x∈Rnwith x6= 0. If the

evaluation of xTAx for x∈Rnleads to both positive and negative values,

then the matrix Ais called indefinite. It is well-known that a matrix Ais

positive (negative) definite if and only if all its eigenvalues, i. e. values λwith

Ax =λx for a vector x∈Rnare positive (negative). The matrix is indefinite

if and only if both eigenvalues >0 and <0 exist.

Theorem 2.4 (Second-order sufficient condition [37]) Let X⊆Rnopen and

f:X→Ra twice continuously differentiable function. If

• ∇f(x?)=0and

•the Hessian of f,f00(x?), is positive definite,

then x?is a strict local minimizer of f(on X).

Proof: For the proof of this theorem the reader is referred to [37]. 

If the Hessian matrix is indefinite, then saddle points occur.

Definition 2.5 (saddle point) A point ¯x∈Rnis called a saddle point of the

function f:Rn→Rif ∇f(¯x)=0and the Hessian f00(¯x)is indefinite.

Example 2.6 For Example 2.2 the necessary condition looks as follows:

∇f(x) = f0(x) = −1

8x4+7

2x3−59

2x2+ 94x−96 = 0.

Polynomial long division with x1= 2, x2= 6 and x3= 4 yields

f0(x) = (x−2)(x−6)(x−4)(−1

8x+ 2) = 0.

16 Theoretical Background

Thus, the stationary points are given by x1= 2, x2= 6, x3= 4 and x4=

16, which is outside the interval regarded here. One can easily check that

f00(2) = 14, f00(4) = −6 and f00(6) = 10. Thus, x1= 2 and x2= 6 are – as

already observed in Figure 2.1 – the two local minimizers. A comparison of

the objective values shows that x1= 2 is the global optimizer.

Including inequality and/or equality conditions into an optimization prob-

lem makes the necessary and sufficient conditions for optimality a bit more

complicated. A combination of gradient and constraints has to become zero

and also some regularity conditions have to be satisfied.

Optimimality Conditions for Equality-constrained Optimization Problems

In this paragraph, the equality-constrained optimization problem

min

xf(x)

subject to h(x) = 0 (NLO=)

with functions f:Rn→Rand h:Rn→Rmis studied. The following

theorem gives a necessary condition for optimality.

Theorem 2.7 (First-order necessary condition [67]) Let x?be a local mini-

mum point of fsubject to the constraints h(x)=0. Assume further that x?

is a regular point of these constraints (i. e. the gradient vectors ∇h1(x?), . . . ,

∇hm(x?)are linearly independent). Then there exist Lagrangian multipliers

(µ1, . . . , µm)T=µ∈Rmsuch that

∇f(x?)−

i=1

µi∇hi(x?) = 0.

Proof: The proof of this theorem can be found in [67], for example. 

A sufficient condition for optimality can be given by taking the second

derivative of the Lagrangian function, which is defined as

L(x) = f(x)−µTh(x),

into account, where µis the vector of Lagrangian multipliers (cf. Theorem

2.7).

2.2 Nonlinear Optimization 17

Theorem 2.8 (Second-order sufficiency condition [67]) Suppose there is a

point x?∈Rnsatisfying h(x?)=0, and a µ= (µ1, . . . , µm)T∈Rmsuch that

∇f(x?)−

i=1

µi∇hi(x?) = 0.

Suppose also that the matrix L00(x?) = f00(x?)−Pm

i=1 µih00

i(x?)is positive

definite on M={y∈Rn: (∇h1(x?)···∇hm(x?))Ty= 0}, that is, for

06=y∈Mthere holds yTL00(x?)y > 0.

Then x?is a strict local minimum of fsubject to h(x)=0.

Example 2.9 Consider a paraboloid described by the objective function

f:R2→R,

f(x1, x2) = x2

1+x2

Assume that this function has to be minimized under the constraint that the

solution lies on the intersection of the function values with a plane in R3

which is defined by

{(x1, x2, x3)|x3+x1−2 = 0}.

Figure 2.2 shows the paraboloid and the plane. The optimization problem

can be posed as

min

xf(x1, x2)

such that h(x1, x2) = x2

1+x2

2+x1−2=0.

Solving the equality condition for x1yields x{1,2}

1=±1

2p9−4x2

2−1

2. Solving

the necessary condition

∇f(x1, x2)−µ1∇h(x1, x2) = 0

⇔2x1

2x2−µ12x1+ 1

2x2= 0

(cf. Theorem 2.7) leads to

x2= 0 and x1=µ1

2(1 −µ1).

As an assumption for the sufficient condition (cf. Theorem 2.8) both condi-

tions have to be true. Solving

µ1

2(1 −µ1)=±1

2√9−4·0−1

18 Theoretical Background

-3 -2 -1 0123-5 0

-2

x3 1

2 2

=x +x2

x =-x +2

3 1

Figure 2.2: In Example 2.9 a paraboloid is desired to be minimized on a plane

leads to two possible solution points p1and p2given by

p1= (x{1}

1, x{1}

2, µ{1}

1) = (1,0,2

p2= (x{2}

1, x{2}

2, µ{2}

1) = (−2,0,4

3).

The Hessian of the Lagrangian function is given by

L00(x1, x2) = f00(x1, x2)−µ1h00(x1, x2)

=2 0

0 2−µ12 0

0 2

=2(1 −µ1) 0

0 2(1 −µ1)

Obviously, this matrix is positive definite for all µ1<1 (independently of x1

and x2) and thus also in the point p1. By use of Theorem 2.8 it follows that

the point (x{2}

1, x{2}

2) = (1,0) is a strict local minimizer.

2.3 Calculus of Variations 19

2.3 Calculus of Variations

In contrast to nonlinear optimization where the objective to be optimized

is given as a function f:Rn→R, the calculus of variations is concerned

with the optimization of a functional. The task is to find a continuously

differentiable curve γ: [λstart, λend]→Rn,γ(λ)=(γ1(λ), . . . , γn(λ))Tthat

minimizes a variational integral

J(γ) = Zλend

λstart

C(γ(λ), γ0(λ), λ) dλ(VP)

for a given sufficiently often differentiable function Cthat may depend on

the curve γ(λ), its derivative γ0(λ) = d

dλγ(λ), and on the parameter λitself.

Additionally, boundary conditions may be included.

The basics summed up in the following can be found in numerous text-

books and papers, for example [9], [41], [34] and [79]. In this thesis only

functionals depending on a one-dimensional real parameter λare considered.

Also, only integrals that depend on γ(λ) and γ0(λ) are studied within this

work – a generalization to the case that Cdepends on derivatives of higher

order of γwith respect to λcan for example be found in [9].

The main motivation for the development of the calculus of variations

was given by Johann Bernoulli in 1696 by posing the ’Brachistochrone prob-

lem’: Given two points P0and P1in a vertical plane, a curve for a moving

point Mis searched that begins in the point P0with an initial velocity v0

and ends up in the point P1in virtue of its own gravity in the shortest pos-

sible time (cf. [34]). Even much earlier, in the middle of the eighth century

before Christ, the so-called ’Dido’s Problem’ occured: Princess Dido had

to flee to the African coast and asked the local chief for a piece of land as

large as she could envelop with a cowhide. The chief agreed and Dido clev-

erly cut the cowhide into little stripes and in this way got a much larger

piece of land as the chief had in mind. Following the legend of the founda-

tion of Carthage, this coastal strip (the so-called ’Byrsa’) was the nucleus of

Carthage. Bernoulli called the mathematical problem behind it an ’isoperi-

metric problem’ (cf. [34]). The theoretical framework that allows to compute

solutions for both kinds of problems (and also several others) mainly goes

back to Leonhard Euler and Joseph Louis Lagrange.

Most of the classical problems like the two examples mentioned in the

last paragraph have in common that curves connecting two fixed end points

are to be computed. In this case, the problem can be formulated as follows:

20 Theoretical Background

min

γJ(γ) = min

γZλend

λstart

C(γ(λ), γ0(λ), λ) dλ(VC2p)

γ(λstart) = A, γ(λend) = B

with two specified vectors A, B ∈Rn.

A minimizing curve γ?for (VC2p) with γ?(λstart) = Aand γ?(λend) = B

has to satisfy the property that

J(γ?)≤ J(γ)

for all continuous curves γ: [λstart, λend]→Rnwith γ(λstart) = Aand

γ(λend) = B.

Following [79] it is assumed that these curves are at least twice continu-

ously differentiable for the following derivation of a necessary condition for

optimality of (VC2p). However, the same results can also be proven by the

weaker assumption that γ(λ) is only once continuously differentiable by the

use of the ’Lemma of Du Bois-Reymond’ (cf. e. g. [77]).

Let η(λ) = (η1(λ), . . . , ηn(λ))Tbe a twice continuously differentiable curve

with η(λstart) = η(λend) = 0 and assume that γ(λ) is a minimizing curve of

(VC2p). δγ =ηis called a variation of γ. Let ε∈Rand consider the function

v:R→Rdefined as

v(ε) = Zλend

λstart

C(γ(λ) + εη(λ), γ0(λ) + εη0(λ), λ) dλ(2.2)

Note, that in this case the variations ηiof the components γiare assumed to

be independent of each other. Because of the minimality of γ(λ) it follows

that

v(ε)≥v(0) ∀ε∈R.

Thus, vattains a minimum in the point ε= 0 and

v0(0) = 0.(2.3)

v0(0) is called the first variation of Jand is denoted by δJ.

In the following, for simplicity, whenever Coccurs the evaluation at the

point (γ1(λ), . . . , γn(λ), γ0

1(λ), . . . , γ0

n(λ), λ) is meant. Additionally, in the

following computations the partial derivative with respect to the j’th variable

is denoted by ∂j.

2.3 Calculus of Variations 21

dε(0) = Zλend

λstart n

j=1

∂jC·d (γj+εηj)

dε+

k=n+1

∂kC·d (γ0

k−n+εη0

k−n)

dε+

+∂2n+1C·dλ

dεdλε=0

=Zλend

λstart

∂

∂γ C·η+∂

∂γ0C·η0dλ= 0.(2.4)

Integration by parts of the second summand yields

Zλend

λstart

∂

∂γ0C·η0dλ=∂

∂γ0C·ηλend

λstart −Zλend

λstart

dλ∂

∂γ0C·ηdλ. (2.5)

Insertion into equation (2.4) and the condition η(λstart) = η(λend) = 0 now

leads to Zλend

λstart ∂

∂γ C−d

dλ∂

∂γ0C·ηdλ= 0.

As these equations have to be true for every arbitrary set of functions ηi,

i= 1, . . . , n, the integral becomes zero only if

∂

∂γ C−d

dλ∂

∂γ0C= 0.

The formal proof of this so-called ’Fundamental lemma of the calculus of

variations’ can for example be found in [41].

In short (and by multiplication with −1), it has been shown that

dλ∂C

∂γ0−∂C

∂γ = 0 (2.6)

is a necessary condition for optimality of (VC2p). These equations are called

the Euler-Lagrange equations.

A simple example for a variational problem is given in the following:

Example 2.10 Which is the shortest curve connecting the two points (1,1)

and (2,2) in the x1-x2-plane in R2(cf. Figure 2.3)?

22 Theoretical Background

Figure 2.3: Some possible curves connecting the points (1,1) and (2,2) in R2(on the

left) and the connecting curve of minimal length (on the right)

One way to attack this problem is to consider the variational integral

min

xZλend

λstart

2kx0(λ)k2dλ

with x(λ) = x1(λ)

x2(λ)and the boundary conditions

λstart = 0, x(0) = 1

1

λend = 1, x(1) = 2

2.

The Euler-Lagrange equations for this example are given as

dλ∂F

∂x0−∂F

∂x =d

dλx0

1(t)

2(t)−0 = x00

1(λ)

x00

2(λ)!

= 0.

A solution for this ordinary differential equation obviously is given by

x1(λ)

x2(λ)=c1λ+d1

c2λ+d2

with constants c1,2, d1,2∈R.

Application of the boundary conditions yields c1=c2= 1 and d1=d2= 1.

Thus x1(λ)

x2(λ)=λ+ 1

λ+ 1,

which – as expected – is a straight line connecting the two points.

2.3 Calculus of Variations 23

In practice, often constraints have to be satisfied by the solution of a vari-

ational problem. In this work, the case of m < n equality constraints given

by ϕ:Rn×R→Rmwith ϕ(γ(λ), λ) = (ϕ1(γ(λ), λ), . . . , ϕm(γ(λ), λ))T= 0

occurs (so-called holonomic constraints, cf. [41]). In this case, the variational

problem can be formulated as follows:

min

γJ(γ) = min

γZλend

λstart

C(γ(λ), γ0(λ), λ) dλ

subject to ϕ(γ(λ), λ) = 0 (VC2p-c)

γ(λstart) = A, γ(λend) = B

with two specified vectors A, B ∈Rn. A necessary condition for optimality

is given in the following theorem, called the multiplier rule, which goes back

to Euler and Lagrange:

Theorem 2.11 (Multiplier rule [41]) If a twice continuously differentiable

curve γis a solution of VC2p-c, then there exist functions µ1, . . . , µm, each

mapping from [λstart, λend]to R, such that γis a solution of the unconstrained

variational problem

min

γ,µ Zλend

λstart

L(γ(λ), γ0(λ), µ(λ), λ) dλ(2.7)

γ(λstart) = A, γ(λend) = B

with the Lagrangian Ldefined as

L(γ(λ), γ0(λ), µ(λ), λ) = C(γ(λ), γ0(λ), λ) +

i=1

µi(λ)·ϕi(γ(λ), λ).

By this theorem, using the same derivation as before for the Lagrangian

Lw. r. t. γand µthe Euler-Lagrange equations for fixed boundaries read as

dλ∂C

∂γ0−∂C

∂γ −µ(λ)T·∂

∂γ ϕ(γ(λ), λ)T

= 0 (2.8)

ϕ(γ(λ), λ) = 0,(2.9)

where equation (2.9) stems from taking variations with respect to µ(λ) =

(µ1, . . . , µm)T(λ).

24 Theoretical Background

So far, the curves γhave been considered only between two fixed points

Aand B. If these boundary values of the curve γare not fixed but rather

constrained by

ϕ(γ(λstart), λstart) = ϕ(γ(λend), λend) = 0,

as it will be the case in the robustness formulation presented in Chapter 4,

the Euler-Lagrange equations have to be enlarged by the so-called transver-

sality conditions. They are derived in the following way:

Since ϕ(γ(λ), λ) = 0 has to be satisfied at the boundaries for all possible

varied curves, the variations ηifor each component of γare not independent

any more. To derive conditions for admissible variations, let ε∈Rand let

the function ¯v:R→Rmbe defined as

¯v(ε) := ϕ(γ(λ) + εη(λ), λ),

where for all εonly such variations are considered for which the constraints

are satisfied at the boundaries, i. e. ¯v(ε) = 0 for all εwith λ=λstart and

λ=λend. Therefore, also the derivative w. r. t. εhas to be zero what for

ε= 0 results in

0 = ¯v0(0) = d

dεϕ(γ(λ) + εη(λ), λ)ε=0 =∂

∂γ ϕ(γ(λ), λ)·η(λ)

for λ=λstart and λ=λend. This directly imposes conditions for the variations

η(λ) at the boundaries as thus a variation η(λ) is feasible if and only if

η(λ)∈ker ∂

∂γ ϕ(γ(λ), λ)for λ=λstart and λ=λend.(2.10)

Furthermore, from integration by parts (cp. Equation (2.5)), the condition

∂

∂γ0C·ηλend

λstart

= 0

has to be satisfied, which means that

∂

∂γ0C⊥ηfor λ=λstart and λ=λend

for all feasible variations η(λ). Together with Equation (2.10) this results in

∂

∂γ0C⊥ker ∂

∂γ ϕfor λ=λstart and λ=λend.(2.11)

2.4 Parametric Optimization 25

Equation (2.11) says that at the boundaries the partial derivative of C

w. r. t. γ0has to be transversal to the tangent space of the hyperplane which

is implicitly defined by ϕ(γ(λstart), λstart) = 0 and ϕ(γ(λend), λend) = 0, re-

spectively. Together, Equations (2.8)-(2.9) and (2.11) form a boundary value

problem that has to be solved numerically.

2.4 Parametric Optimization

Optimization problems whose solutions may change under the influence of

some external parameters are called parametric optimization problems. Para-

meter-dependencies occur in many applications. For example, optimization

problems may depend on temperature, wind velocity or other physical values.

Also time-dependent optimization problems are very important, especially in

engineering.

Furthermore, the development of methods for parametric optimization prob-

lems can be very helpful for finding solutions of complicated nonlinear opti-

mization problems: In this case one tries to reduce the solution of the original

optimization problem to another optimization problem whose solution is al-

ready known or easy to compute. These two problems then are combined

with the help of a parameter λ∈R. Denote the original objective function

by f(x) and the objective function of the already solved problem by g(x).

Then the parameter-dependent problem minx(1 −λ)·g(x) + λ·f(x) has to

be solved, varying λfrom 0 to 1. Thus one starts with the already known

solution for gand ends up with the desired minimum of f. Approaches of

this kind are commonly known as homotopy methods.

In the literature, parametric optimization is also adressed as parametric

programming. There are various publications on this topic like for example

[44, 5, 46, 60, 2] and [102].

In this work only one-parametric, unconstrained optimization problems

are considered. This means that the objective function depends on an ad-

ditional parameter λ∈R. Additionally, it is assumed that the objective

function is at least twice continuously differentiable. In the following two

sections, some theoretical basics are summed up and a short introduction

into numerical path following methods that allow to compute solutions of

parametric optimization problems is given.

26 Theoretical Background

2.4.1 Theoretical Basics for Unconstrained One-parametric Optimization

Problems

Consider a twice continuously differentiable function f:Rn×Λ→Rwith

Λ=[λstart, λend]⊂R. In an unconstrained parametric optimization problem

a solution curve x(λ) of

min

x{f(x, λ) : x∈Rn}(uPOP)

is to be found for λ∈Λ. It is assumed that the initial solution x(λstart) is

known or can be computed easily.

As the solution curve x(λ) has to be optimal in each point λ∈Λ, a

necessary condition for the optimality of x(λ) is given by

H(x, λ) = ∂

∂xf(x, λ) = 0 ∀λ∈Λ

(cf. Theorem 2.3). Here, His a nonlinear system of equations with nequa-

tions and n+ 1 (or, in the multi-parametric case n+p) variables. The

existence of solutions to this kind of problems within a neighborhood of an

already known solution is guaranteed by the implicit function theorem given

as follows:

Theorem 2.12 (Implicit Function Theorem [52, 27]) Let H:Rn×Rp→Rn

be a k-times continuously differentiable mapping. Suppose that the point

(¯x, ¯y)∈Rn×Rpsatisfies H(¯x, ¯y)=0and that the Jacobian with respect to

x,∂F

∂x (¯x, ¯y), is regular.

Then there exists a neighborhood of ¯y,U(¯y)⊆Rpand a unique, k-times

continuously differentiable function c:U(¯y)→Rnwith

H(c(y), y)=0for all y∈U(¯y)

and c(¯y) = ¯x. In this case, the function cis said to be implicitly defined by

the equation H(c(y), y)=0.

Proof: A proof of this theorem is for example given in [52]. 

Applying the implicit function theorem to the necessary condition that

∂

∂x f(x, λ) = 0 ∀λ∈Λ, the following theorem results directly:

Theorem 2.13 (Sensitivity analysis for an unconstrained parametric opti-

mization problem [27]) Let f(x, λ),f:Rn×Rp→Rbe a twice continuously

differentiable function in x. Let λ?∈Rp. Assume that x?is a strict local

2.4 Parametric Optimization 27

minimizer of the unconstrained optimization problem minxf(x, λ?), i. e. x?

satisfies the second order sufficient condition (see Theorem 2.4). Let ∂f

∂x (x, λ)

be once continuously differentiable w. r. t. λwithin a neighborhood of (x?, λ?).

Then, for λnear λ?, there exists a unique, once continuously differentiable

curve x(λ)with x(λ?) = x?which satisfies the second-order sufficient condi-

tion for f(x, λ). Hence, x(λ)is an isolated, locally unique local minimum of

f(x, λ).

Remark 2.14 In [27] also a more general formulation of Theorem 2.13 is

given that guarantees the local existence of solutions to parametric opti-

mization problems with equality and inequality constraints.

Example 2.15 Consider the objective function f:R×R→R

f(x, λ) = λ(x−2λ)2+ (1 −λ)(−(x−2λ)2)+4λ

Let the parameter λbe varied from 0 to 1. By f(x, 0) a parabola that attains

its maximum at x= 0 (apex (0,0)) is described. Due to the variation of λ

towards λ= 1 the parabola changes into another parabola that attains its

minimum at x= 2 (apex (2,4)). To compute a solution curve x(λ) for

λ∈[0,1] the necessary condition

∂

∂xf(x, λ) = 0 (2.12)

⇔(x−2λ)(4λ−2) = 0 (2.13)

is to be studied. One can observe that the change from a maximum to a

minimum occurs at λ= 0.5. In this point the Hessian of fgiven by

∂2f

∂x2(x, λ) = 4λ−2

becomes singular (here = 0). Thus, for λ= 0.5 the sufficient condition

of second order is not satisfied and Theorem 2.13 does not guarantee the

existence of a solution. As one can easily see, zeros of (2.12) are given by

x(λ)=2λ. For λ∈]0.5,1] the Hessian is positive definite (here >0) and

thus the unique existence of a minimal solution of (2.12) is guaranteed by

Theorem 2.13. For λ∈[0,0.5[ the Hessian is negative definite (here simply

<0) which means that fattains a maximum. Both theorems 2.4 and 2.13

can also be formulated for maximization problems in the same way. It would

result that x(λ) = 2λis a unique maximal solution in this interval. In Figure

2.4 the graph of fis plotted for different values of λ. In the same plot, the

path of λ-dependent solutions of Equation (2.12) is visualized (black line).

28 Theoretical Background

Figure 2.4: The graph of the function fdefined in Example 2.15 for different values of

the parameter λ

Remark 2.16 The main theoretical challenge occurs when singularities oc-

cur and the implicit function theorem cannot be applied. In [44] necessary

conditions for constrained parametric optimization problems are studied and,

for the one-parametric case, the generic singularities are described. Numeri-

cal path following methods (see next section) are used to compute curves of

local minimizers.

2.4.2 Numerical Path Following

The computation of solutions of parametric optimization problems can be

reduced to the solution of parameter-dependent systems of equations as de-

scribed in the last section. This kind of equations can be solved by numerical

path following methods (also called continuation methods) as developed in

[2, 22] and [75] for example. Following the lines of [2], this section contains

a short outline how numerical path following methods work in principle.

Consider a smooth function H:RN×R→RNwhose set of zeros is to

be found. This means, a system of equations of the form

H(y, λ) = 0 (2.14)

has to be solved, where y∈D⊆RN,Dopen. The purpose of a numerical

path following method is to generate a series of points (yi, λi)i= 0,1,2, . . .

that satisfies H(y, λ) = 0.

2.4 Parametric Optimization 29

Let u0= (y0, λ0) be a solution of (2.14), i. e. H(u0) = 0. Suppose that the

Jacobian H0(u0) has full rank. In this case the solution set H−1(0) can locally

be parametrized by one parameter sin the neighbourhood of u0. Thus, one

obtains a solution curve c(s) with

c(0) = u0and H(c(s)) = 0.

Differentiating this last equality we obtain

H0(c(s))c0(s) = 0.

Therefore c0(s) spans the one-dimensional kernel of H0(c(s)). By choosing s

to be the arclength it follows that kc0(s)k= 1.

Moreover one can show that c(s) is the solution of the initial value problem

˙u=t(H0(u))

u(0) = u0.(2.15)

Here t(A) denotes for a matrix A∈RN×(N+1) with rank(A) = Nthe unique

vector tsatisfying the following conditions:

At = 0,ktk= 1 and det A

tT>0.

The last condition allows us to fix the orientation of the tangent vector.

A numerical path following method generates a series of points in the

following way: Let u0be an initial point satisfying H(u0) = 0. Then ui+1 is

generated inductively in two steps, a predictor and a corrector step (cf. also

Figure 2.5):

Predictor Step: Solve (2.15) numerically, e.g. by the explicit Euler method:

vi+1 =ui+h·t(H0(ui)),

where h > 0 is a certain steplength.

Corrector Step: Here one uses the fact that c(s) solves H(c(s)) = 0.

Define wi+1 to be that point on the curve cwhich is nearest to vi+1, i.e. one

has to solve

min{kvi+1 −wk:H(w)=0}.

The solution of this problem – this is typically determined by Newton’s

method – defines the new point ui+1.

30 Theoretical Background

Figure 2.5: Illustration of possible predictor and corrector steps in numerical path fol-

lowing methods

Remark 2.17 The assumption that the Jacobian has full rank induces that

possible branch points of solution curves cannot be computed. For the study

of problems with singular Jacobians and also an analysis of the step size

control for different possible predictors the reader is referred to [2].

Remark 2.18 There are several software packages available which contain

codes for numerical path following. A very popular one is AUTO20001(see

[23]). In fact, this is also the software we used for part of the computations

within the numerical examples presented in Chapter 4, Section 4.3.

2.5 Self-Optimization

For the development of modern, innovative mechatronic systems, the con-

cept of self-optimization has been introduced2over the last few years. This

concept is formulated in [1] as follows:

“Self-optimization describes the ability of a technical system to endoge-

nously adapt its objective regarding changing influences and thus an au-

tonomous adaption of the system’s behavior in accordance with the objectives.

The behavior adaption may be implemented by changing the parameters or

the structure of the system. Thus, self-optimization goes considerably beyond

the familiar rule-based and adaptive control strategies; self-optimization fa-

cilitates systems with inherent ‘intelligence’ that are able to take action and

react autonomously and flexibly to changing operating conditions.”

Self-optimization can be described as a process that consists of the fol-

1AUTO2000 is a software package developed by E. Doedel et al. that allows the contin-

uation and bifurcation analysis of ordinary differential equations and parameter-dependent

systems of equations.

2by the project CRC 614, see www.sfb614.de

2.5 Self-Optimization 31

lowing three steps (cf. also [1]):

Step 1: Analysis of the current situation

Step 2: Determination of the system’s objectives

Step 3: Adaptation of the system’s behavior

More precisely, in the first step the state of the system and observations of

the environment are analyzed. It is evaluated, whether the current objectives

of the system are appropriate for the current situation. If this is not the case,

the new objectives are determined in the second step. This can be performed

through the selection of an alternative from a given finite set of possible

objectives, through an adaptation of the current objectives by changing the

priorities, or even through the generation of new objectives independently

of the existing ones. The resulting objective adaptation leads directly to the

third step, in which the behavior adaptation is performed such that the new

objectives are optimized.

For further information about self-optimizing systems, the reader is re-

ferred to [33, 1, 19]. In Chapters 3 and 4 several applications will be described

for which the concept of self-optimization has been realized.

Chapter 3

Multiobjective Optimization

In industry and business a variety of applications occur, where several objec-

tive functions are desired to be optimized at the same time. For instance, in

manufactoring cost has to be minimized, but at the same time also quality

is wanted to be maximal. This example already illustrates that the several

objectives typically contradict each other and therefore do not have identical

optima. Thus, a set of optimal compromises has to be determined. This

set is called the Pareto optimal set or just Pareto set, named after the Ital-

ian engineer, sociologist and economist Vilfredo Pareto (1848 - 1923). In his

‘Manual of Political Economy’ [76], Pareto developed a theory which includes

the study of tastes of men and the value of goods for individuals. He coined

the term of ophelimity, which is the pleasure that certain quantities of a thing

afford an individual. In this way, Pareto optimality means that members of

a collectivity enjoy maximal ophelimity in a certain position. This especially

means that in a Pareto optimum no individuum can increase its ophelimity

without decreasing the ophelimity of another individuum.

The mathematical field of multiobjective optimization deals – besides the

theoretical study of such problems – with the computation of Pareto optimal

solutions.

In this chapter, first of all a formal definition of Pareto optimality and a

necessary condition are given. After that, geometrical properties of Pareto

sets are reflected and a summary of the most important methods for solving

multiobjective optimization problems with continuous variables and objec-

tive functions is given. Among these are set-oriented methods which have

been applied to several multiobjective optimization problems in engineering

applications also described in this chapter.

Having generated the entire Pareto set for a given multiobjective opti-

mization problem, often a decision which solution to choose for the under-

lying technical system has to be made. This leads to the topic of Decision

Making on which will be reported in direct connection to the applications

considered in the last section of this chapter.

34 Multiobjective Optimization

3.1 Problem Formulation and Pareto Optimality

A (constrained) multiobjective optimization problem (MOP) is given by

min

x{F(x) : x∈S⊆Rn},(MOP)

where Fis defined as the vector of the objective functions f1, . . . , fk,k≥2,

which each map from Rnto R, i. e.

F:Rn→Rk, F(x)=(f1(x), . . . , fk(x)).

The feasible set Sis given as

S={x∈Rn:h(x) = 0, g(x)≤0}

with equality constraints h:Rn→Rm, m ≤nand inequality constraints

g:Rn→Rq. The MOP is called unconstrained MOP, if S=Rn. In all

the following considerations it is assumed that F= (f1, . . . , fk) consists of at

least continuous objective functions.

It has to be explained what is meant by ’min’ in the problem (MOP), as

a vector-valued function has to be minimized. The following definition which

introduces an appropriate partial order on Rkallows comparisons of vectors

(cf. [20]).

Definition 3.1 Let u, v be two vectors in Rk. Then the vector uis less than

vif

ui< vifor all i∈ {1, . . . , k},

denoted by u <pv. In an analogous way, the relation ≤pis defined. The

vector uis said to dominate the vector vif

u≤pvand ui< vifor at least one i∈ {1, . . . , k}.

Using the relation ≤pit can now be defined what is meant by a solution

of (MOP).

Definition 3.2 A point x?∈Rnis called globally Pareto optimal for (MOP)

(or a global Pareto point of (MOP)) if there exists no x∈S⊆Rnwith

F(x)≤pF(x?)and fj(x)< fj(x?)for at least one j∈ {1, . . . , k}.

If this property is only valid inside a neighborhood U(x?)⊂S⊆Rn, then x?

is called locally Pareto optimal (or a local Pareto point).

The set of all Pareto points is the Pareto set. Following [3], the set of the

function values of all Pareto points is called the Pareto front.

3.1 Problem Formulation and Pareto Optimality 35

In the literature, one can find several different names for Pareto optimal

solutions. Examples are ’efficient solutions’ [97, 25], ’noninferior solutions’

[3], ’nondominated points’ [59], ’vector minimum points’ [6], and ’admissible

points’ [45]. Especially the image of a Pareto optimal solution often is de-

noted as an efficient point.

An equivalent definition of Pareto optimality that is graphically more

intuitive, as illustrated in Figure 3.1, can be found e. g. in [25]:

Definition 3.3 A point x?is Pareto optimal, if there exists no

F(x)∈F(S)\{F(x?)}such that

F(x)∈F(x?)−Rk

+,0.

Figure 3.1: Pareto points only intersect in the point F(x?) with the region F(x?)−Rk

+,0

In the literature, many definitions related to Pareto optimality are con-

sidered. For example an expansion of the Pareto optimal set to the set that

evolves from omitting the condition that fj(x)< fj(x?) for at least one

j∈ {1, . . . , k}(cf. Definition 3.2) is denoted as the weakly Pareto optimal set

(cf. [69]). On the contrary, the properly Pareto optimal set is a restriction of

the Pareto set to the subset which does not contain points with unbounded

trade-offs, i. e. unbounded ratios of change, between the objectives. The main

idea is that only those points are properly Pareto optimal for which a decrease

of one objective value is only possible at the expense of some reasonable in-

crements in the other objective values. There are several definitions which

36 Multiobjective Optimization

reflect this intuitive idea (cf. [69]). One definition was given by Geoffrin in

1968:

Definition 3.4 (Geoffrin, 1968 [40]) A point x?∈Sis called properly Pareto

optimal if it is Pareto optimal and if, additionally, there exists some M∈R

such that for each objective function fiand each x∈Swith fi(x)< fi(x?)

there is at least one fjsuch that

fj(x?)< fj(x)and fi(x?)−fi(x)

fj(x)−fj(x?)≤M.

In this definition, only the existence of the number Mis required. As for

the decision maker Pareto points with a predefined bound for the trade-offs

may be interesting, this definition has been modified in such a way that the

value Mis set explicitly:

Definition 3.5 (Shukla, Dutta, Deb, 2005 [93]) Given a positive number

M > 0a point x?∈Sis called M-properly Pareto optimal if it is Pareto

optimal and if for all iand x∈Ssatisfying fi(x)< fi(x?), there exists at

least one index jsuch that

fj(x?)< fj(x)and fi(x?)−fi(x)

fj(x)−fj(x?)≤M.

For two objectives (i. e. k= 2) this definition means that any secant on

the Pareto front has a slope between −Mand −1

Example 3.6 Consider the following (very simple) multiobjective optimiza-

tion problem with two objectives f1and f2and one variable x∈R:

min

x∈RF(x) = (f1(x), f2(x))

with f1(x) = (x−1)2

and f2(x) = (x+ 1)2

Obviously, the Pareto set is given by all points x?∈[−1,1]. All points except

the individual optima of f1and f2are properly Pareto optimal. Setting the

value Mgiven in Definition 3.5 to 2, the set of M-properly Pareto optimal

points reduces to the inverval [−1

3,1

3]. Figure 3.2 illustrates this example.

The following classical result which goes back to Kuhn and Tucker [63]

provides a necessary condition for Pareto optimality. The version of the

theorem written down here can be found in [53], which itself is a reformulated

version of the one given in [43].

3.1 Problem Formulation and Pareto Optimality 37

Figure 3.2: Pareto front and its restriction to 2-proper Pareto points for Example 3.6

Theorem 3.7 (Kuhn and Tucker, 1951 [63]) Let x?be a Pareto optimal

solution of (MOP). It is assumed that ∇hi(x?), i = 1, . . . , m and ∇gj(x?)for

j∈ {J:gJ(x?) = 0}(the active constraints) are linearly independent. Then

there exist vectors α∈Rkwith αi≥0for i= 1, . . . , k and Pk

i=1 αi= 1,

γ∈Rmand δ∈Rqwith δj≥0for j= 1, . . . , q such that

i=1

αi∇fi(x?) +

j=1

γj∇hj(x?) +

l=1

δl∇gl(x?) = 0

δj·gj(x?) = 0,∀j= 1, . . . , q.

(3.1)

Following [69], points x?∈Rnthat satisfy the Kuhn-Tucker condition

(3.1) are called substationary points. Given a Pareto point x?the vector of

multipliers αis called the weight vector corresponding to x?.

Obviously the condition in the Kuhn-Tucker theorem is not sufficient for

Pareto optimality in general. In the case of convex1objective functions,

convex inequality constraints and affine2equality constraints, it is proven

that for α > 0 the Kuhn-Tucker conditions are also sufficient [43]. However,

numerical methods often make use of this criterion.

1A function f:Rn→Ris convex, if f(λx + (1 −λ)y)≤λf(x) + (1 −λ)f(y) for all

x, y ∈Rn, 0 ≤λ≤1, see e. g. [106].

2A function f:Rn→Ris affine, if f(λx + (1 −λ)y) = λf(x) + (1 −λ)f(y) for all

x, y ∈Rn, 0 ≤λ≤1, see e. g. [106].

38 Multiobjective Optimization

3.2 Methods for the Computation of Pareto Points

In this section, first of all a short overview on methods for the computation of

Pareto optima is given. Then the ‘weighted sums method’ and some recently

developed set-oriented techniques for the computation of the entire Pareto

set will be explained in more detail, as they play an important role in parts

of this thesis.

3.2.1 Overview

There are many different approaches for solving multiobjective optimization

problems (cf. [69, 3] for example). They range from methods for the compu-

tation of single Pareto optimal points to interactive methods to methods for

the approximation of the entire global Pareto set.

In the case of the computation of one single Pareto optimum, often a

priori information, e. g. a special weighting of the objective functions or an

ordering of the objectives is required. Examples for methods of this kind are

•the ‘weighted sums method’ [36, 111] (which is described in more detail

in Section 3.2.2),

•the ‘ε-constraint method’ [48], in which part of the objective functions

are treated as constraints, which have to be greater than or equal to

some values εjspecified in advance,

•different types of reference point methods, in which a distance of some

desired reference point to the Pareto front is minimized.

Over the last few years, many algorithms for the computation of the en-

tire Pareto set have been developed. Examples are the ‘Normal Boundary

Intersection’ [14], which especially works well in convex problems, a stochas-

tically motivated algorithm [85] and a technique based on numerical path

following [53].

A broad class of algorithms for the computation of entire global Pareto

sets is based on evolutionary algorithms. The books of Deb [15, 62], and

Coello Coello [12] give an overview on multiobjective evolutionary algorithms

(MOEAs).

The use of set-oriented techniques is a different approach, which is very

well-suited for multiobjective optimization (cf. [92]). Here, on the one hand

the permanent subdivision and selection in parameter space allows the nu-

merical approximation of Pareto sets (so-called subdivision techniques). On

the other hand, based on given solutions, algorithms which recover the Pareto

3.2 Methods for the Computation of Pareto Points 39

set or Pareto front by evaluating points in the neighborhood, have been de-

veloped (so-called recovering techniques). The subdivision and recovering

techniques will be explained in detail in 3.2.3. These methods have been

used for the computation of Pareto sets in the applications described in this

work.

3.2.2 The Weighted Sums Method

The weighted sums method, also called the ‘weighting method’, goes back to

Gass and Saaty [36] and Zadeh [111]. It is a very popular approach which

makes use of the intuitive idea of converting the multiobjective optimization

problem into a single objective one. For this, the objective functions are

summed up, each multiplied with an individual weight. More precisely, k

weights αiare chosen such that αi≥0 for i= 1, . . . , k and Pk

i=1 αi= 1 and

the problem

min

xgα(x)

s. t. x∈S⊆Rn,(3.2)

with gα(x) = Pk

i=1 αifi(x) is considered.

Varying the weights αi, different Pareto points can be obtained by solving

(3.2) – in the case of convex objective functions even all Pareto points can

be computed in this way. The reason for this is that the shape of the Pareto

front is also convex in such a situation. Moreover, the optimization of the

weighted sums results in different points on the Pareto front for different

weight vectors.

In contrast to this, for nonconvex objective functions the Pareto front can

contain nonconvex parts as illustrated in Figure 3.3 on the right. Here, the

nonconvex part is defined to be a subset of the Pareto front that contains no

global optima of the weighted sum of the objectives for every weight vector.

Pareto points, which are mapped into the nonconvex part of the Pareto front,

can have the same weight vector as other Pareto points whose weighted sum

has a smaller value (cf. Figure 3.4), as they are only local minima or saddle

points of gα(x). In [13], Das and Dennis give a trigonometric argument, why

– in the case of two objectives – the weighted sums method cannot be used

to compute points in the nonconvex part.

It is an interesting question to find out if a Pareto front contains non-

convex parts. If one assumes that the Pareto front is connected, then any

nonconvex part contains a region in which the Pareto front ‘curves inside

the image of the feasible region’. This part of the Pareto front will be called

40 Multiobjective Optimization

Figure 3.3: Typical shape of a Pareto front for a convex problem (left figure) and possible

shape in a nonconvex problem (right figure)

a ‘dent’. In Section 3.3 the formal definition of a dent is given and an ap-

proach which allows the numerical computation of dents in Pareto fronts is

presented.

Figure 3.4: Schematic illustration of the weighted sums approach

3.2.3 Set-oriented Methods

For the computation of the entire Pareto set, recently some set-oriented

methods have been developed (cf. [20, 87, 88, 90], and, for an overview,

[92]), which can be categorized into two main classes: the subdivision and

the recovering techniques. The subdivision techniques are of global nature

and can even deal with multiobjective optimization problems in which no

3.2 Methods for the Computation of Pareto Points 41

analytical derivatives are available. The drawback is that the number of op-

timization variables which can be treated efficiently is restricted to moderate

dimensions. The recovering techniques are of local nature but also work well

for higher-dimensional problems (especially in the case of smooth objective

functions).

The principal approach of the subdivision techniques can be characterized

as follows: Based on a covering of the feasible parameter space (a box), the

Pareto set is approximated numerically through a successive refinement and

selection of boxes in parameter space. Figure 3.5 visualizes this approach.

Figure 3.5: Approximation of the Pareto set for the MOP“minxF= (f1, f2)T:R2→R2”

with f1(x1, x2) = (x1−1)2+ (x2−1)4and f2(x1, x2) = (x1+ 1)2+ (x2+ 1)2using

the subdivision techniques with 10 (on the left) or 16 (on the right) subdivision steps

respectively

After subdividing the boxes into two smaller boxes in each subdivision

step, test points are generated in each box. One or a few steps of a descent

direction for the MOP are applied to each test point and only those boxes are

kept in which at least one of the iterated points has stayed. Many different

methods for the choice of test points and descent directions have been imple-

mented. More details about the algorithms, which are implemented in the

software tool GAIO3, and a proof of convergence can be found in [20, 88, 90]

and [87].

If one or a few Pareto optima are already known, then the recovering

techniques (cf. [87, 89]) allow the computation of the entire, connected com-

ponents of the Pareto set that contain these starting points. For this, little

boxes around the starting points are defined, and other Pareto optimal points

are generated by studying neighboring boxes. Here, one uses the fact that

– under certain smoothness and regularity assumptions – Pareto sets are lo-

cally (k−1)-dimensional manifolds (cf. [53]). Thus, it is guaranteed that

3Global Analysis of Invariant Objects, see www.math.upb.de/∼agdellnitz

42 Multiobjective Optimization

in the neighborhood of Pareto optima other Pareto optimal points can be

found. To decide which neighboring boxes may contain Pareto optima, test

points are generated and iterated in the same way as in the above described

subdivision techniques. Figure 3.6 visualizes the principal functioning of the

recovering techniques.

Figure 3.6: Principal functioning of the recovering techniques, here using test points for

the generation of new Pareto points in neighboring boxes (the black curve illustrates the

unknown Pareto set) [96]

For high-dimensional problems (i. e. MOPs with many optimization vari-

ables), a special image set oriented recovering algorithm has been developed

in [18]. For a given initial, Pareto optimal solution a box on the Pareto front

is generated around the image of this solution. Step by step, all neighboring

boxes are inserted that contain points on the Pareto front. The insertion of

boxes is based on the idea to create vectors of desired values for the objec-

tives, so-called targets T, in the neighborhood of the given boxes. Then the

following distance minimization problem is solved:

min

xkF(x)−Tk.

Using this algorithm, the entire Pareto set can be covered for unconstrained

multiobjective optimization problems with convex objective functions, as –

under certain smoothness assumptions – Pareto sets are parts of (k−1)-

dimensional manifolds [53] and, in the convex case, they are connected and

the map from the Pareto set to the Pareto front is bijective [69]. In Figure

3.7, a schematic representation of the image set oriented recovering technique

is given.

3.3 Dents in Pareto Fronts

In Figure 3.3 it has already been illustrated that the Pareto front may curve

inside the image of the feasible region in the case of nonconvex objective func-

tions. As already mentioned in Section 3.2.2 Pareto points whose images lie

in such a dent cannot be computed by using the weighted sums method. The

3.3 Dents in Pareto Fronts 43

f1f1f1

f2f2

Figure 3.7: Principal functioning of the image set oriented recovering technique (the

black curve is the unknown Pareto front)

reason is that two or more Pareto points satisfy the Kuhn-Tucker equations

with the same weight vector αwhile the weighted sum Pk

i=1 αifi(x) is not

minimal for all these solutions. The following definition gives a mathematical

description of a dent.

Definition 3.8 (Dent point, Dent preimage) Let P⊆Sbe the Pareto set

of a multiobjective optimization problem minx∈SF(x)with F:Rn→Rk,

F(x) = (f1(x), . . . , fk(x))Tand fiat least twice continuously differentiable

∀i= 1, . . . , k. Let

gα(x) =

i=1

αifi(x),

gα:Rn→R, and αi∈[0,1],Pk

i=1 αi= 1.

A point x?∈Pis called a dent preimage if it is a saddle point of gα. The

corresponding point y?=F(x?)on the Pareto front is called a dent point.

Definition 3.9 (Dent, dent border, complete dent) Let P⊆Sbe the Pareto

set of an at least twice continuously differentiable multiobjective optimization

problem minx∈SF:Rn→Rkand let PF =F(P)be the Pareto front. Let

y?∈PF be a dent point. Then, the connected component of dent points

which includes y?is called a dent corresponding to y?, denoted by Dy?:

Dy?={y∈PF|∃δ≥0and ∃c: [0, δ]→PF, c continuous, with c(0) = y?,

c(δ) = y, and c(s)is a dent point ∀s∈[0, δ]}.

A dent Dy?is called complete, if

∂PF ∩Dy?=∅,

where ∂PF is the boundary of the Pareto front PF as a subset of ∂F(S)

(with the induced topology from Rk).

44 Multiobjective Optimization

The boundary ∂Dy?of a complete dent Dy?(seen as a subset of PF) is

called dent border and a boundary point yb∈∂Dy?is called a dent border

point. A point xb∈Pwith F(xb) = ybis called a dent border preimage of

yb.

Remark 3.10 In [53] dents have been studied from a differential geometric

point of view. In this book it has been shown that – under certain geometrical

assumptions on the multiobjective optimization problem – saddle points of

gαoccur if and only if the corresponding point on the Pareto front has at

least one negative principal curvature.

In [53] it has already been considered what happens during the transition

from a minimizer x1of gα1to a saddle point x2of gα2on a connected Pareto

front i. e. during the transition of non-dent preimages to dent preimages (α1

and α2denote the weight vectors corresponding to x1and x2, respectively):

Assume that the non-dent preimage x1can be connected to the dent preim-

age x2by a continuous curve γ: [0,1] →P⊆Swith γ(τ) = (x(τ), α(τ)),

γ(0) = (x1, α1) and γ(1) = (x2, α2). To each curve point γ(τ) the n-tuple

of eigenvalues of ∂2

∂x2gα(x), denoted by (e1(τ), . . . , en(τ))T, is assigned, where

αagain is the corresponding weight vector to x. This leads to another con-

tinuous curve ˜γ:τ7→ (e1(τ), . . . , en(τ))Tcorresponding to γ. As x1is a

minimizer of gα1, ˜γ(0) >0. In the saddle point x2of gα2, there exists an

index i∈ {1, . . . , n}such that ei(1) <0. Because of the continuity of ˜γthere

must exist ¯τ∈[0,1] with ei(¯τ) = 0.

To sum up, in dent border points a zero-eigenvalue of the Hessian of gα

occurs.

Definition 3.11 (Simple dent border point/preimage) Let P⊆Sbe the

Pareto set of an at least twice continuously differentiable multiobjective opti-

mization problem F:Rn→Rkand let PF =F(P)be the Pareto front. Let

b∈PF be a dent border point and let x?

b∈Pbe a dent border preimage of

Then, y?

bis called a simple dent border point if the zero eigenvalue of

the Hessian g00

α(x?

b)is simple. In this case, x?

bis called a simple dent border

preimage.

Example 3.12 (Computation of dents)

Consider the two objectives

f1(x, λ) = 1

2(p1+(x1+x2)2+p1+(x1−x2)2+x1−x2) + λ·e−(x1−x2)2

f2(x, λ) = 1

2(p1+(x1+x2)2+p1+(x1−x2)2−x1+x2) + λ·e−(x1−x2)2

3.4 Treatment of Multiobjective Optimization Problems in several

Technical Applications 45

with a fixed value λ= 0.6 and x= (x1, x2). Then, the Pareto set can be

approximated e. g. by use of the set-oriented techniques described in Section

3.2.3.

Figure 3.8: Pareto front and dent points (black) for Example 3.12

The algorithm returns a set of boxes that covers the Pareto set. Within

these boxes, a number of test points is evaluated, the best of which are

in the following considered as the Pareto set. By solving the Kuhn-Tucker

equations of F= (f1, f2) for each of these points, the corresponding weight

vectors α∈Rkcan be computed. Then, the eigenvalues of the Hessians of

the weighted sums of the objectives are determined. All points x, in which

both eigenvalues >0 and eigenvalues <0 exist, are dent preimages. The

Pareto front and the resulting dent points for this example are visualized in

Figure 3.8.

3.4 Treatment of Multiobjective Optimization Problems in sev-

eral Technical Applications

In close cooperation with engineers working within the CRC 614 ”Self-optimi-

zing systems and structures in mechanical engineering” 4we have considered

several technical applications in which multiple objectives occur that are de-

sired to be optimized at the same time. The applications presented in this

4www.sfb614.de

46 Multiobjective Optimization

work are subsystems of the RailCab vehicle which is a novel linear motor

driven railway system including the latest technologies and innovative pro-

totypes, developed by the project RailCab (“Neue Bahntechnik Paderborn”,

cf. [73]). In particular, we have considered a hybrid energy storage system,

the guidance module and the doubly-fed linear drive. The new aspect of our

study of these applications is the numerical approximation of entire Pareto

sets. Based on the resulting global picture on the solution set, the engineers

were now able to choose suitable Pareto optimal solutions. In the case of the

linear drive we even developed a situation-dependent heuristic which allows

the automatic choice of suitable Pareto optimal solutions during operation

time. In the case of the guidance module certain reference trajectories are de-

sired to be optimized with respect to several objectives. This would directly

lead to an optimal control problem with multiple objectives. As the guidance

module is modeled as a differentially flat system, we were able to reformu-

late the optimal control problem into a nonlinear multiobjective optimization

problem. This type of reformulation has been introduced by Murray et al

(cf. [72, 104, 70, 31]) for the case of one single objective function. In this

work it is shown that the same idea works for the multiobjective case.

In the following, first a short introduction into the functionality of the

RailCab system is given. Afterwards, more detailed information about the

three subsystems considered in this work and our new results for the multi-

objective optimization of these subsystems are presented.

3.4.1 The RailCab System

The RailCab system is a novel rail-bound personal rapid transit (PRP), de-

veloped by the project RailCab (“Neue Bahntechnik Paderborn”) [73].

The idea is that the RailCab system acts like a “taxi cab on rails” which

on the one hand saves energy by using common track sections in a convoy

and on the other hand is very comfortable for the passengers, as the desired

destination is directly approached. In particular, thus it is not necessary to

change trains and the timetable is not relevant. The concept is also very

well-suited for light cargo transport.

RailCab vehicles travel autonomously and independently of other vehicles

on the common, existing rails, equipped with additional motor elements of

the linear drive between the rails and novel passive switches, which allow

the RailCabs to steer actively into the desired direction. The steering is

performed by the so-called guidance module for the front and rear axle. This

module can actively control the lateral displacement of the RailCab vehicle

on the rails. Within the clearance between the flanges and the rail-heads, the

3.4 Treatment of Multiobjective Optimization Problems in several

Technical Applications 47

Figure 3.9: Picture of the RailCab test vehicles (source: Collaborative Research Center

614 (SFB614))

RailCab vehicle can be moved freely. This is a big advantage over traditional

railway systems, in which an uncontrolled periodic movement and at higher

speed even a striking of the rail-heads against the flanges occurs.

The RailCab is propelled by a doubly-fed linear drive that consists of a

primary motor part between the rails of the track and a secondary part on

the vehicle. Energy is transferred from the track to the vehicle by use of a

magnetic field and the thrust is generated on the secondary motor part (see

e. g. [110, 80]).

In order to guarantee the availability of energy without any interruption

the RailCab is equipped with an onboard energy storage. At present, the

energy storage consists of batteries. In the future, a hybrid energy storage

system consisting of batteries and double layer capacitors will be installed. So

far, a test plant for the new hybrid energy storage system has been built at the

Chair of Power Electronics and Electrical Drives, University of Paderborn,

Germany.

Furthermore, the RailCab vehicle contains an active suspension module

which gives the vehicle the possibility to improve the passenger comfort [51].

Within the RailCab project, two RailCab vehicles and a test track in

the scale of 1:2.5 have been built next to the campus of the University of

Paderborn. Figure 3.9 shows a picture of the test vehicles. The test track

is an oval of about 530 m track length which contains an artificial hill with

an altitude difference of about 2.5 m and gradients up to 5.3% and a novel

passive switch. More detailed information about the RailCab system can for

48 Multiobjective Optimization

example be found in [1].

3.4.2 Multiobjective Optimization of the Hybrid Energy Storage System5

The hybrid energy storage system (HES) contains two different types of en-

ergy storages: batteries and double layer capacitors (DLC). Batteries are

well-suited for long term storage as they have a high energy density. The

drawback is that batteries have a poor power density and a small number of

full load cycles. On the contrary, double layer capacitors perfectly fit for short

term storage as they can be cycled many times without degradation and offer

a high power densitiy but only a low energy density. By the combination of

the two energy storages the individual advantages are utilized.

Figure 3.10 shows a picture of the test rig for the hybrid energy storage

system that has been built at the Chair of Power Electronics and Electrical

Drives, University of Paderborn, Germany.

From the mathematical point of view, the challenge in this application is

to find an operation strategy that distributes the power flows to the respective

storage devices in an optimal way during a drive of the vehicle. Here, several

aims come into play. In the study described in [83] two objectives are con-

sidered: the minimization of the normalized energy losses elosses of the HES

and the maximization of the power reserve (expressed by the minimization

of the function pres).

To facilitate the calculation of the operating strategy the planned drive

of the vehicle is divided into several sections of one to five minutes. A mul-

tiobjective optimization with respect to the above-mentioned objectives is

executed for each of these sections. For technical reasons, the sum of the

powers of both energy storages and the losses is equal to the total on-board

power of the vehicle which is given as a profile for the planned drive. Thus,

only the battery current has to be optimized over time. The resulting pro-

files of the battery power, the state of charge of the battery, the DLC power

and the state of charge of the DLC can be computed directly from the opti-

mized profile for the battery current. The optimization variables stem from a

discretization of values for the battery current over time. The discretization

points are chosen at those points in time where either the total power changes

significantly or a certain energy has been produced. The final trajectory is

set together by piecewise constant values of the battery currents.

In Figure 3.11 one possible profile for the total power of the HES is given.

In this profile, the total power changes drastically at six different points in

5in cooperation with the Chair of Power Electronics and Electrical Drives, University

of Paderborn, Germany, cf. [66, 83]

3.4 Treatment of Multiobjective Optimization Problems in several

Technical Applications 49

Figure 3.10: Photograph of the test rig of the hybrid energy storage system [83]

time T0,··· , T5(cf. Figure 3.11). The values of the battery current at these

points in time are optimized with respect to the minimization of elosses and

pres. The battery and the DLC are supposed to have a medium state of

charge at the beginning (T=T0= 0) in this example. Figure 3.12 shows an

approximation of the Pareto front. It has been computed by use of a special

image set oriented predictor-corrector method for the generation of Pareto

points. This algorithm uses basic ideas of the image set oriented method and

has been especially tailored to multiobjective optimization problems with two

objectives in which no analytic derivatives of the objectives are computable

and evenly spread solutions on the Pareto front are desired (cf. [83] for

more details). Each point within this Pareto front is related to an optimized

operating strategy. The three marked points (cf. Figure 3.12) have been

chosen to demonstrate the results. The corresponding trajectories of the

battery current are plotted in Figure 3.13. Figure 3.14 gives the resulting

states of charge of both the battery and the DLC. One can observe that in

Point 1, where the energy losses are minimal, the values of the battery current

are near zero and the state of charge of the battery is almost constant. As

50 Multiobjective Optimization

Figure 3.11: Profile of the total on-board power of the hybrid energy storage system for

a section of one minute

Figure 3.12: Approximation of the Pareto front for the HES assuming the total power

profile given in Figure 3.11

Figure 3.13: Resulting trajectories of the battery current IBat based on the total power

profile given in Figure 3.11

3.4 Treatment of Multiobjective Optimization Problems in several

Technical Applications 51

Figure 3.14: Results for the state of charge of the battery (on the left) and the state of

charge of the DLC (on the right) based on the total power profile given in Figure 3.11

a consequence, the state of charge of the DLC fluctuates much more in this

point. On the contrary, in Point 3 in which pres is minimal and thus the

power reserve is maximal, the state of charge of the battery changes more

significantly and the state of charge of the DLC is varied only within a small

range around the medium value SOCmed. Point 2 is one example for an

optimal compromise.

3.4.3 Self-optimization of the Guidance Module6

As mentioned above, the guidance module allows to actively control the la-

teral displacement of the RailCab vehicle in the rails. Within a given clear-

ance, the RailCab can be moved freely. This is very important, because track

laying does not result in ideally straight rails and flange strikes, i. e. bumpings

of the rail-heads against the flanges, have to be avoided because they cause

noise as well as wear on the wheels and rails. Figure 3.15 shows a typical rail

and a sketch of the clearance, which is the maximum distance between the

flanges and the rail-heads.

Within the clearance, the RailCab can be steered along arbitrary reference

trajectories. The challenge was to compute (Pareto-) optimal trajectories

that meet several aims:

1. minimize the deviation of the vehicle from the track centerline, i. e.

maximize “safety”

2. maximize the passenger comfort

3. minimize the average energy consumption of the hydraulic actuators

6in cooperation with the Chair of Control Engineering and Mechatronics, University of

Paderborn, Germany, cf. [38, 39]

52 Multiobjective Optimization

Figure 3.15: Photograph of a rail (on the left) and sketch of the clearance (on the right)

[38]

4. maximize the steering angle reserve

Based on a linear model of fourth order for the lateral dynamics of the

RailCab vehicle (see e. g. [38] for more details), an optimal control prob-

lem with the above mentioned objectives is formulated. In this model, the

controlled outputs are (differentially) flat, i. e. the inputs and states can be

represented as a function of these flat outputs and a finite number of their

derivatives w. r. t. time (cf. [31]).

Definition 3.13 ((Differential) Flatness [31, 72]) A system

˙x=f(x, u)

with states x∈Rnand controls u∈Rmis called differentially flat or just flat

if there exists a fictitious output y∈Rmwith

y=h(x, u, ˙u, ¨u, . . . , u(p))

such that

x=α(y, ˙y, ¨y, . . . , y(q))

u=β(y, ˙y, ¨y, . . . , y(q)).

(3.3)

Here, h, α and βdenote real-analytic functions7and p, q ∈N.yis called a

flat output.

7Functions that locally can be developed into a Taylor series are called real-analytic

functions (see e. g. [61]).

3.4 Treatment of Multiobjective Optimization Problems in several

Technical Applications 53

Differentially flat system can especially be utilized in trajectory optimiza-

tion (cf. [104]). The big advantage is that in this case the trajectories can be

optimized in the space of the outputs yand afterwards, the corresponding

inputs and states can be computed.

Thus, an optimal control problem of the form

min

x∈Rn,u∈RmJ(x, u) (3.4)

s. t. ˙x=f(x, u)

with a flat system ˙x=f(x, u) can be transformed into an optimization

problem of the form

min

y∈Rmf(y),(3.5)

where ydenotes the flat output (cf. e. g. [104, 78] and [70]).

This concept can be easily extended to the case of several objectives as

required in the trajectory optimization of the guidance module. Then, the

optimal control problem is transformed into a conventional multiobjective

optimization problem of the form

min

y∈RmF(y),(3.6)

where Fmaps from Rmto Rkand ydenotes the flat output.

In the case of the guidance module, it is assumed that the measured

position of the rails (the track centerline), is known a priori. The desired

reference trajectories of length shfor both the front and the rear axle are

approximated by piecewise polynomials, so-called splines. Many different

types of splines can be found in the literature – most common are cubic

splines and B-splines. In [70] B-splines have been used for the trajectory

optimization. In the case of the optimization of the guidance module, the

use of B-splines has no additional benefits and thus cubic splines which have

a more intuitive parametrization have been applied. Using cubic splines,

the trajectory is described by a finite number npof parameters yj, which

are interpolation values at given knot points xj(track positions) and which

have to be optimized. Additional boundary conditions are defined for the

cubic spline that keep the transition between two sequenced trajectory parts

continuously differentiable. The computational advantage that might arise

from using B-splines is negliblible in the scenario considered here, as only

25 collocation points have to be evaluated. A detailed description of cubic

splines can be found in [82]. More details about the special setting of the

spline for the application considered (choice of knot points etc.) are given in

[39].

54 Multiobjective Optimization

For the computation of Pareto optimal trajectories, the image set oriented

recovering algorithm described in Section 3.2.3 has been used. The fact that

the RailCab has to stay within the clearance leads to a hard constraint in

the multiobjective optimization problem given by

|y−ytr|< rcl,

where rcl is half the clearance, ytr the track centerline positioned in the middle

of the clearance and ythe current position of the axle center. This constraint

can be easily included by setting the center of the initial boxes (defined in

preimage space) to ytr and the radius to ytr +rcl in each knot point.

In a first study described in [38] the trajectories of the guidance module

have been optimized with respect to the first three objectives given on page

51. The exact formulas for these objectives are given in [38]. Figure 3.16

shows an approximation of the Pareto front. To each point within this Pareto

front corresponds a Pareto optimal trajectory on which the RailCab vehicle

can be steered.

Figure 3.17 gives two projections of the Pareto front. In this plot it

becomes clear that energy and comfort are correlated. An improvement of

safety causes a deterioration in both comfort and energy. This is due to the

fact that a smooth, comfortable trajectory also requires less steering and thus

less energy consumption of the hydraulic actuators.

Two points within the Pareto front have been chosen (marked by a circle

and a square) to demonstrate the results. The circle is an example for a more

safe trajectory and the square for a more comfortable one. In Figure 3.18

the corresponding trajectories and the trajectories which stem from single

objective optimizations for each of the three objectives are given. (Here,

only the optimized interpolation values at the knot points, connected with

lines, are plotted.) The black line is the (shifted) track centerline and the

gray lines describe the clearance around it.

One can observe that the trajectory which is more safe (line with cir-

cles) stays close to the centerline whereas the more comfortable trajectory

(line with squares) “cuts the corners” and is smoother. As expected, the en-

ergy optimal (dashed) and comfort optimal (dash-dot) trajectories lie close

together.

In [39] the fourth objective mentioned on page 51, the steering angle re-

serve, has been additionally considered. The exact formula for this objective

is given in [39]. Figure 3.19 shows two projections of the three-dimensional

Pareto front which has also been approximated by the image set oriented

recovering algorithm.

3.4 Treatment of Multiobjective Optimization Problems in several

Technical Applications 55

Figure 3.16: Numerically approximated Pareto front for the multiobjective optimization

of the guidance module

The guidance module becomes a self-optimizing system by continuously

running through the following three steps (cf. Section 2.5):

Step 1: Analysis of the current situation:

The values of the velocity and power allocation of the RailCab vehicle

and control errors are measured. Track irregularities have been esti-

mated offline in advance and are selected from a database.

Step 2: Determination of the system’s objectives:

The Pareto set has a priori been approximated offline by use of the

image set oriented recovering algorithm described in Section 3.2.3. To

save disk space, only the points of the Pareto front and the weights that

would lead to the same Pareto point when optimizing a weighted sum

of the objectives are stored in a database (the objectives are convex).

Within this set, a point that fits for the current situation is chosen

56 Multiobjective Optimization

Figure 3.17: Two projections of the Pareto front for the multiobjective optimization of

the guidance module

by requiring that the power allocation is adequate and the number of

flange strikes is minimal.

Step 3: Adaptation of the system’s behavior:

During runtime, the trajectory is optimized with respect to the weighted

sum of the objectives using the weight determined in Step 2. Thus, the

Pareto optimal trajectory can be reconstructed during runtime by using

for example the methodology described in [104].

3.4.4 Multiobjective Optimization of the Linear Drive8

As mentioned above, the RailCab contains a doubly-fed linear drive that

consists of a primary motor part between the rails and a secondary motor

part on the vehicle. If both components of the motor are energized, then a

magnetic traveling wave emerges in the motor. This magnetic field generates

the thrust (cf. [49]). Figure 3.20 visualizes the working principle of the

doubly-fed linear drive.

During operation time, power is transferred from the primary to the sec-

ondary motor part. The absolute value of this transferred power depends on

the operating point of the linear motor given through the currents and fre-

quencies in both motor parts. In [50] a mathematical model of the doubly-fed

8in cooperation with the Chair of Power Electronics and Electrical Drives, University

of Paderborn, Germany, cf. [81, 108, 86]

3.4 Treatment of Multiobjective Optimization Problems in several

Technical Applications 57

Figure 3.18: Examples of Pareto optimal trajectories for the RailCab vehicle

Figure 3.19: Two projections of the approximated Paretofront for the guidance module

with four objectives

linear drive has been developed. For a given target position of the RailCab,

the reference values of the current position x?

Mand the speed v?

Mare assigned

by a jerk limited profile generator. This generated profile is also called a ma-

neuver. The reference thrust F?

Mis determined as well as the demanded

electrical power P?

Bthat has to be transferred into the vehicle. Taking into

account these two values and the measured speed vMof the RailCab, refer-

ence values for the currents and the frequencies of both motor parts can be

determined by the operating point assignment.

The operating point is desired to meet two objectives at the same time (cf.

58 Multiobjective Optimization

vehicle 2 vehicle 1

relative motion

stator segment

DC power supply module

three-phase

system

common stator field

secondary field

Figure 3.20: Working principle of the doubly-fed linear drive [49]

[81]). On the one hand, the degree of efficiency ηLM has to be maximized and

on the other hand the power factor ηSN that takes the ratio of real output

power to the apparent power of the linear motor into account, has to be

maximized, too. This leads to the multiobjective optimization problem

min

xf1(x)

f2(x)= min

iSd −ηLM(iSd)

−ηSN(iSd)

in which the current iSd ∈Ris the optimization variable. These objectives

are both convex.

By use of set-oriented multiobjective optimization techniques (see Section

3.2.3), an approximation of the Pareto optimal operating points was obtained.

This optimization is performed for discretized values of the maneuver and

for each point in time a Pareto set has been computed. One of the resulting

Pareto fronts is plotted in Figure 3.23 on the left.

In more detail, here a simulated drive of the RailCab around the test

track has been considered (cf. [81]). Figure 3.21 shows the velocity profile

for the RailCab. Additionally, in this figure assumed values for the state of

charge of the battery and the temperature of the secondary motor part are

plotted. Based on these values, the decision which point within the Pareto

set, i. e. which value for the current iSd is adjusted to the motor, is made.

More precisely, a so-called decision heuristic that realized the choice of

one Pareto point has been developed. The first step of this decision heuristic

is based on the following technical properties:

3.4 Treatment of Multiobjective Optimization Problems in several

Technical Applications 59

Figure 3.21: Profiles of the velocity of the RailCab, the state of charge of the battery

and the temperature of the primary motor part which form the basis for the optimization

•If the temperature in the secondary motor part rises, then an optimiza-

tion of the power factor should be preferred.

•If the energy storage of the RailCab is discharging and the state of

charge of the battery is low, then the optimization of the degree of

efficiency becomes more important (the reason is that in this case the

reactive power oscillation between the secondary motor part and the

battery, the so-called flicker-effect, generates an extra load to the bat-

tery).

•If the battery is being charged, then only the temperature θaffects the

choice of the Pareto point.

These properties are put into formulas in such a way that the upper point

on the Pareto front, which corresponds to the maximum with respect to

ηSN, is chosen, if the state of charge and the temperature are high and the

lower point on the Pareto front, which corresponds to the maximum of ηLM,

is chosen if both the load value and the temperature are low. In between,

points are chosen by a linear interpolation between the individual optima

depending on the load and temperature values.

Figure 3.22 depicts how the decision heuristic works in this specific exam-

ple in more detail: First, the extremal points PP1(the minimum of f2) and

PP2(the minimum of f1) of the Pareto set are determined. For this specific

linear motor scenario, PP1is selected if the state of charge is at least 90%

and the temperature is at least 80◦C. Conversely, PP2is selected if the state

of charge is at most 20% and the temperature is at most 20◦C. In the case

of parameter values between these extremal points a Pareto point is chosen

by using linear interpolation.

Consider for example the state of charge. Let qcur be the current state of

charge, qmin = 0.2 the lowest possible value for qcur and qrange = 0.7 the

60 Multiobjective Optimization

Figure 3.22: Working principle of the first step of the decision heuristic for the operating

point assignment of a doubly-fed linear motor [86]

greatest amount by which qcur can vary. Then qscale and Tqare defined as

qscale =qcur −qmin

qrange

and

Sq=qscale ·PP2+ (1 −qscale)·PP1.

The procedure for Sθworks analogously with θmin = 20◦C and θmax = 80◦

C. Since the temperature and the state of charge can vary independently,

linear interpolation only works for each parameter individually. The optimal

Pareto point PP from the Pareto front with respect to the decision variables

is chosen by minimizing the following formula

w·(Sq−PP) + (1 −w)·(Tθ−PP)

with some weight w∈[0,1] which in this application has been set to 0.5.

After this decision based on external parameters, the decision heuristic

always contains a second step in which the curvature of the Pareto front in

the chosen point is studied. If the Pareto front is “flat” or “steep” around the

chosen point, then a slight movement to another point on the Pareto point

causes great benefits in one objective and only little losses in the other one.

Thus, in this second step, the tangent to the Pareto front is approximated

numerically, and the solution is possibly moved to another point on the Pareto

front in which the tangent has a (predefined) minimal or maximal slope M.

Using the definition of M-properly Pareto optimal points (see Definition 3.5

on page 36) one can say that in the second step that M-proper Pareto point

3.4 Treatment of Multiobjective Optimization Problems in several

Technical Applications 61

is chosen whose objective value is as near as possible to the objective value

of the point determined in the first step. In Figure 3.23 on the right this

second step is visualized.

Figure 3.23: Results of the multiobjective optimization for the linear drive: On the left,

the Pareto front corresponding to t= 20sis plotted. In the right plot, the black box from

the left is zoomed in more detail and a sketch of the working principle of the decision

heuristic is given.

The values for the charging state of the battery and the temperature

of the secondary motor part are not consistent with measured values which

change very slowly over time. To demonstrate the working principle of the

decision heuristic, here values that change considerably have been chosen.

Figure 3.24 shows the results of the multiobjective optimization for a

round trip of the RailCab on the test track with the given profiles of velocity

(and also some given profiles of the force and power), states of charge of the

battery and temperatures of the secondary motor part. In the left plot, the

maximum possible values of ηLM and ηSN which result from a single objective

optimization are drawn over time. As the objectives are conflicting, it is

not possible that both values are reached at the same time. The dashed

lines are the values of ηSN (lower dashed line) and ηLM (upper dashed line)

that are achieved with the multiobjective optimization together with the

decision heuristic as described above. The right plot of Figure 3.24 shows

the corresponding values of the optimization variable iSd that lies as expected

between the values of iSd for the individual maxima of the objectives.

In this figure, one can also observe the effect of the decision heuristic: for

example in the time interval from 50 to 60 seconds, where the values of the

charging state of the battery and the temperature of the secondary motor

part become higher and higher, Pareto points are chosen that more and more

move towards the maximum of ηSN.

The computation of Pareto sets for many discretized points of time, as

62 Multiobjective Optimization

Figure 3.24: Results of the multiobjective optimization for the linear drive illustrated

between the maxima of each individually optimized objective. On the left, the values of the

objectives are plotted whereas on the right, the corresponding values of the optimization

variable, the current iSd, are shown.

performed in the operating point assignment here, is computationally costly

and cannot be executed during operation time. To allow a multiobjective

optimization during operation time, the same problem has been considered

as a time-dependent multiobjective optimization problem. For this kind of

problem a numerical algorithm has been used that allows the efficient compu-

tation of Pareto optimal paths over time. This algorithm and its application

to the doubly-fed linear drive are described in Section 4.3.

Chapter 4

Parametric Multiobjective Optimization

In this chapter, multiobjective optimization problems that additionally de-

pend on an external parameter λ∈Rare studied. First, in Section 4.1 the

problem is stated formally, the Kuhn-Tucker theorem is reformulated for this

context and a motivating example is given.

Parametric multiobjective optimization problems occur in many real world

applications.

On the one hand, time-dependencies are included in many applications.

These often can be modeled by use of such an external parameter λ. By the

combination of techniques from multiobjective optimization and numerical

path following methods, Pareto optimal paths over time can be computed.

Numerical path following (cf. Section 2.4.2) allows to compute the solutions

of parameter-dependent systems of equations. Multiobjective optimization

and numerical path following can be linked together by means of the Kuhn-

Tucker necessary condition (3.1) (see page 37) which characterizes Pareto

optimal points as solutions of a certain system of equations. This approach

will be explained in more detail in Section 4.3. How this new concept has

been applied to the optimization of the operating point assignment for a

doubly-fed linear drive is described in Section 4.3.2. Part of the contents of

this section have already been published in [108] and [86].

On the other hand, the external parameter λmay describe the influence

of any other parameter to the objective functions. Imagine for instance the

design process of a car which is desired to be optimal with respect to comfort

(first objective) and safety (second objective). On the road, the car will be

caught in a cross-fire of influences, like side wind, wet roads, or changes in

temperature. The only information one has is that these influences can be

estimated to lie in a certain interval, probably given by the weather forecast.

Mathematically, this leads in the simplest case to the parametric multiob-

jective optimization problem minxF(x, λ) with F:Rn×R→Rk– thus the

solution (the Pareto set) also depends on the parameter λ. For the designer

of a car those Pareto points are desirable, where the Pareto points or their

images under Fchange as little as possible while the parameter varies.

64 Parametric Multiobjective Optimization

After a short summary of the state-of-the-art of robustness concepts in

multiobjective optimization in Section 4.4.1, two new concepts that describe

how to compute these robust Pareto points are introduced in Section 4.4.2.

In Section 3.3 dents in Pareto fronts have been studied. The considera-

tion of dents is extended to parametric multiobjective optimization problems

in Section 4.5 of this chapter. Here, the connection between results from

bifurcation theory and the computation of points in which dents originate or

vanish under the variation of the external parameter λis pointed out.

4.1 Problem setting

An unconstrained (one-) parametric multiobjective optimization problem is

given as

min

x{F(x, λ) : x∈Rn, λ ∈[λstart, λend]⊆R},(ParMOP)

where Fis defined as the vector of the objective functions, i. e.

F:Rn×[λstart, λend]→Rk, F(x, λ)=(f1(x, λ), . . . , fk(x, λ)).

The solution set of (ParMOP) is a λ-dependent family of Pareto sets.

Every point in this family satisfies the necessary condition of Kuhn and

Tucker with respect to the x-variables. As (ParMOP) is an unconstrained

multiobjective optimization problem, Theorem 3.7 reduces to the fact that

there exist multipliers α1, . . . , αk∈R+,0such that

HKT(x, α, λ) = Pk

i=1 αi∇xfi(x, λ)

i=1 αi−1= 0,(4.1)

where (x, λ) is a solution of (ParMOP).

For the numerical solution of (4.1), the non-negativity requirement for αi

might present a problem. This problem is avoided if one uses an equivalent1

formulation saying that there exist multipliers t1, . . . , tk∈Rsuch that

HKT(x, t, λ) = Pk

i=1 t2

i∇xfi(x, λ)

i=1 t2

i−1= 0,(4.2)

where (x, λ) is a solution of (ParMOP). In the following, both αiand t2

iwill

be used synonymously.

1Equivalence is meant here in the sense that the same set of substationary points (x, λ)

is described.

4.2 Numerical Path Following and Multiobjective Optimization 65

Definition 4.1 If x∈Rnsatisfies the Kuhn-Tucker condition (4.2) for a

specific value of λ, then it is called – as in the non-parametric case – a

substationary point. The set of all substationary points for the respective

value of λis denoted by Sλ.

Example 4.2 Two objective functions f1,2:R2×R→Rdefined as

f1(x, λ) = λ((x1−2)2+ (x2−2)2) + (1 −λ)((x1−2)4+ (x2−2)8)

f2(x, λ) = (x1+ 2λ)2+ (x2+ 2λ)2.

in which the parameter λis varies from 0 to 1 are considered. To provide

insight into the behavior of the Pareto sets for different values of λin this

problem, numerical approximations of the Pareto sets for some specific values

of λare shown in Figure 4.1 on the left. The right plot shows an approxima-

tion of the entire Pareto sets for λ∈[0,1] in x1-x2-λ-space.

Figure 4.1: Pareto sets for some specified values of λ(on the left) and numerical approx-

imation of the entire, λ-dependent Pareto set in x1-x2-λ-space (on the right) for Example

4.2.

4.2 Numerical Path Following and Multiobjective Optimization

In Chapter 2, Section 2.4.2, numerical path following methods have been

introduced. These methods allow to compute solutions to a parameter-

dependent system of equations

H(y, λ) = 0.

In the case of multiobjective optimization such a system of equations is given

by the necessary condition of Kuhn and Tucker (cf. Equation (4.2)). It can be

used to analyze the behavior of parameter-dependent sets of substationary

66 Parametric Multiobjective Optimization

points with respect to variations of the parameter λ. The Kuhn-Tucker

equations consist of n+1 equations in n+k+1 unknowns (given by x∈Rn,

t∈[0,1]k,λ∈R). Numerical path following methods can be applied to

systems of equations which contain only one more unknowns (given through

λ) than equations. Thus, additionally to the Kuhn-Tucker equations some

more equations have to be derived. These equations define the direction of

the path between the λ-dependent sets of substationary points.

In Figure 4.2 the principal idea of computing paths between λ-dependent

sets of substationary points is visualized.

Figure 4.2: Application of numerical path following methods to parameter-dependent

sets of substationary points.

How to choose the direction of the path depends on the application one

considers. In the following, additional equations for time-dependent applica-

tions and for paths that allow the study of robustness against λ-variations

are described. The initial solutions, i. e. starting points for λ=λstart, stem

from a numerical approximation of the Pareto set for λ=λstart.

Numerical path following methods have already been used in the con-

text of multiobjective optimization (see e. g. [53] and [26]), but only for the

generation of Pareto sets itself and not for varying external parameters in

parametric multiobjective optimization problems.

4.3 Time-dependent Multiobjective Optimization Problems

In this section, the parameter λis identified with the time T, i. e. the Pareto

set of the multiobjective optimization problems considered here changes over

time. In engineering problems it is often required that Pareto optimal solu-

tions over time can be computed very efficiently, preferably during runtime.

4.3 Time-dependent Multiobjective Optimization Problems 67

As numerical path following methods allow the fast generation of solutions

under the variation of the parameter, in this case time, they perfectly fit for

the solution of these problems. How the solution paths are computed is

described in more detail in Section 4.3.1. In Section 4.3.2 the application of

the new concept for the optimization of the operating point assignment of a

doubly-fed linear motor is described. The contents of this section can also

be found in [108].

4.3.1 Computation of Solution Paths

As mentioned above, the parameter-dependent Kuhn-Tucker system (4.2)

consists of n+ 1 equations and n+k+ 1 variables. If the weights αi=t2

are fixed to values ¯

i, then the Kuhn-Tucker system reduces to nequations

and n+ 1 variables. The values ¯

tican be computed for every starting point

xon the initial Pareto set by solving the Kuhn-Tucker equations for λ=

λstart. The system H(y, λ) = H(x, ¯

t, λ) is then simply given by the Kuhn-

Tucker equations with fixed values of t. It is assumed that the Jacobian of

HKT(x, t, λ) w. r. t. (x, t, λ) is regular. By this, one can apply the numerical

path following methods as described in Section 2.4.2 directly and follow the

curve which is generated when varying λ∈[λstart, λend] .

The result is a series of points that lie on the solution curve starting in

xstart ∈Sλstart and approximately ending in a point xend ∈Sλend . For every

starting point in the initial Pareto set for λ=λstart one obtains such a path,

i. e. a series

{u0= (xstart,¯

t, λstart), u1,··· , uN= (xend,¯

t, λend)},

where Ndenotes the corresponding number of predictor steps in the path

following algorithm, i. e. the solution curve conists of N+ 1 points.

Example 4.3 Consider again (as in Example 4.2) the two objective functions

f1,2:R2×R→Rdefined as

f1(x, λ) = λ((x1−2)2+ (x2−2)2) + (1 −λ)((x1−2)4+ (x2−2)8)

f2(x, λ) = (x1+ 2λ)2+ (x2+ 2λ)2.

in which the parameter λis varied from 0 to 1.

An approximation of the entire Pareto set for λ= 0 has been computed

using the set-oriented subdivision technique described in Section 3.2.3. By

inserting every point xcontained in this Pareto set into the Kuhn-Tucker

system and setting λ= 0, the corresponding α= ¯αwas computed by simply

solving these linear equations. For every starting point xin the computed

68 Parametric Multiobjective Optimization

Pareto set αis fixed to the computed value and paths for each starting point

are computed by use of the software package AUTO2000 [23]. In Figure 4.3

some of the resulting paths are illustrated.

Figure 4.3: Three examples for paths with a fixed weight vector αin x1-x2-λ-space,

visualized on the λ-dependent Pareto set, for Example 4.3.

In the case of time-dependent multiobjective optimization problems in

which solutions are required to be generated during runtime (online) it is not

possible to compute entire Pareto sets at each point in time (or a fine dis-

cretization of time). By keeping the weighting of the objectives constant

for certain intervals within which the solution is adapted to the current

point in time by the numerical path following method, solutions to the time-

dependent multiobjective optimization problem can be obtained efficiently.

The following three steps reflect this idea:

Step 1: Compute the entire Pareto set for the given problem at an

initial point in time. Based on a certain decision heuristic (i. e. a calcu-

lation rule for the choice of one point from the Pareto set that is based

on external variables which change situationally) the most preferred

adjustment for the system at this initial point in time is calculated.

4.3 Time-dependent Multiobjective Optimization Problems 69

Step 2: The corresponding ratio of the objectives (weight vector α)

is set fixed. Using path following techniques, the solution curve corre-

sponding to this αis computed over time.

Step 3: After a certain time, the entire actual Pareto set is recom-

puted, the decision heuristic is applied again, and the adjustment of

the system is updated. Then proceed with Step 2.

Figure 4.4 sketches Step 1 and Step 2 in objective space.

Figure 4.4: Visualization of Step 1 and Step 2 in the proposed treatment of time-

dependent multiobjective optimization problems

There are different ways how to decide that the new entire Pareto set for

the current point in time has to be computed in Step 3. The first trivial idea

is to compute the Pareto set at fixed points in time, e. g. every minute (as-

suming that the dimension of the problem is low enough). This computation

can be performed in parallel to the computation of the path of solutions so

that the assignment of the optimal solutions never has to be interrupted. The

computation of the entire Pareto set can also be started anew in reaction to

external influences. As an example in the case of the doubly-fed linear motor

(cf. Section 4.3.2) some precomputed velocity profiles are contained in the

optimization. If these profiles cannot be realized any more, e. g. because the

vehicle has to brake unexpectedly, then a recomputation of the entire Pareto

set and the corresponding path (based on the new profiles) is necessary.

Including such criteria, the system performs the self-optimizing scheme de-

scribed in Section 2.5.

70 Parametric Multiobjective Optimization

4.3.2 Application: Online Optimization of the Operating Point Assignment

of a Linear Motor2

In Section 3.4.4 the multiobjective optimization of the operating point as-

signment of a doubly-fed linear motor has been described. Whereas in that

section a simulated drive on the test track for the RailCab has been studied,

in this section the scenarios considered are driven on a test bed of the linear

motor. Figure 4.5 shows a picture of the test bed.

Figure 4.5: Photograph of the linear motor test bed of the Chair of Power Electronic

and Electrical Drives, University of Paderborn [86]

In this application, the optimization results depend on the current veloc-

ity, thrust and power of the vehicle which all can be represented as depending

on time. In the approach described in Section 3.4.4 Pareto sets for discretized

points in time have been approximated. This cannot be realized during run-

time as the computational effort is too high. By use of the algorithm for

the treatment of time-dependent multiobjective optimization algorithms de-

scribed in the last section, Pareto optimal paths of solutions can be generated

‘online’, i. e. during runtime. For this, the three steps given on page 68 have

been employed and adapted for this special application.

2in cooperation with the Chair of Power Electronics and Electrical Drives, University

of Paderborn, Germany, cf. [108, 86]

4.3 Time-dependent Multiobjective Optimization Problems 71

Step 1: Computation of Pareto sets and decision heuristic

As already described in Section 3.4.4 the Pareto set is approximated

by using a set-oriented subdivision technique contained in the software

tool GAIO (cf. Section 3.2.3). After the computation of the entire

Pareto set for an initial point in time, e. g. T=Tstart = 0, it is sensible

to choose one point in this set as the most preferred adjustment of the

system. The decision heuristic for the application considered here has

also already been described in Section 3.4.4.

Step 2: Numerical path following

As the objective functions in the case considered are convex all Pareto

optimal points are solutions of the Kuhn-Tucker equations. Thus, given

a Pareto optimal point that has been chosen in Step 1, the correspond-

ing weight vector αcan be computed by solving the Kuhn-Tucker sys-

tem for the fixed point in time. Then αis set fixed to the computed

value and a standard predictor-corrector method with a tangential pre-

dictor and a Newton corrector (cf. Section 2.4.2) is applied. The re-

sulting solution curve is stored in a buffer for the reference values and

fed to the controller of the linear motor at the corresponding positions

of the vehicle.

Step 3: Recomputation of the Pareto set

In the case of the doubly-fed linear motor two different scenarios have

been derived that require a recomputation of the Pareto set:

1. motor parameters that are modeled as fixed values have changed,

i. e. for example the air gap has changed, or

2. the decision variables, i. e. the state of charge of the battery and/or

the temperature of the secondary motor part, have changed dras-

tically, or,

3. the absolute value of the thrust is (almost) zero.

The repeated evaluation of Step 1 to Step 3 mirrors the idea of self-

optimization (cf. Section 2.5): The analysis of the current situation is per-

formed through the evaluation of the profiles for the maneuver, the values of

the decision variables and the motor parameters for certain points in time.

The determination of the system’s objectives is realized by the computation

of the Pareto set and the application of the decision heuristic, and the behav-

ior of the system is adapted by assigning the optimized values of the currents

resulting from the numerical path following to the motor during runtime.

The optimization algorithm is running on a PC that communicates with the

72 Parametric Multiobjective Optimization

linear motor test bed via LAN.

The implementation of the algorithm is supported by the concept of the

Operator-Controller-Module (OCM) (see Figure 4.6 for the OCM of the linear

motor and [33] for a more detailed description of the general OCM-concept).

At the lowest level the controllers perform the current- and speed-control

under hard real-time conditions. The reflective operator links the hard real-

time of the controller with the soft real-time of the optimization algorithm in

the cognitive operator. It buffers the calculated path from the cognitive op-

erator and feeds reference values to the controller. It also supports possible

emergency response in cases like unexpected change of these requirements

or changing parameters in the linear drive. Until a new optimization is per-

formed and a new path is available, the current optimization value is replaced

by a sub-optimal value from a look-up table. In this case, a new strategy for

following selected operating points influenced by changing conditions or pa-

rameters is required. This is realized through the application of the decision

heuristic to the new Pareto set and the subsequent numerical path following

process.

The main advantage of this very fast algorithm is that it prevents the

time-consuming calculation of a new Pareto set in every time step and allows

to use a multiobjective optimization approach for this complex application.

The results for one of the tested scenarios are described in the following.

A time-interval of 6 seconds is considered in which the motor accelerates up

to 2 m/s and then brakes down, cf. left plot of Figure 4.7. In the same figure

on the right the profile for the desired thrust F?

Mis plotted over time. While

the vehicle accelerates, the thrust is positive whereas it becomes negative

when the vehicle brakes. If the absolute value of the thrust is small, then the

required transferred power (which in this study has been set to a constant

value of ≈111 W) cannot be assigned. Thus, no optimization is reasonable in

these points. In such a case the Pareto set and the path has to be recomputed

at a certain point after this zero.

As mentioned before, the temperature of the secondary motor part and

the charging state of the batteries depend on the operating point. Here, it is

assumed that both values can be measured during the drive.

Figure 4.8 and Figure 4.9 show the results of the time-dependent multi-

objective optimization of the operating point assignment. In Figure 4.8 the

Pareto optimal values of the current are plotted over time. Here, the vertical

grey lines are the Pareto sets that have been computed at T= 0.3 s and at

T= 3.3 s. One point on these sets has been chosen by use of the decision

heuristic taking into account the measured values of the state of charge of the

4.3 Time-dependent Multiobjective Optimization Problems 73

control loop

linear motor

Operator Controller Module (OCM)

Cognitive Operator cognitive information processing

model-based Self-Optimization

Pareto-Optimization

objective 1

objective 2

decision making

cognitive loop

Reflective Operator reflective information processing

reference value transfer

(primary current and

frequency)

supervision

emergency

sequencer

reflective loop

Controller motor information processing

soft real-time

hard real-time

planning level

execution level

Figure 4.6: Operator-Controller-Module of the operating point assignment of the doubly-

fed linear motor [8]

74 Parametric Multiobjective Optimization

Figure 4.7: Profiles for the velocity and force of the vehicle in the scenario considered

Figure 4.8: Pareto optimal paths for a maneuver of the linear motor

battery and the temperature of the secondary motor part. The black stars

are the results of the numerical path following of this solution. The recom-

putation of the entire Pareto set for T= 3.3 s has been necessary because

the thrust is near zero in the time interval (2.7,3.3). Figure 4.9 visualizes

the same paths in objective space, i. e. the values of the objective functions

are plotted versus time.

4.4 Robust Pareto Points 75

Figure 4.9: Pareto fronts and Pareto optimal paths in objective space for a maneuver of

the linear motor

In another study of the doubly-fed linear drive two different objective

functions (minimization of total losses, maximization of transferred power)

and their changes over time have been considered. For more details, the

reader is referred to [86].

4.4 Robust Pareto Points

In this section, parametric multiobjective optimization problems are consid-

ered that are desired to be robust with respect to changes of the external

parameter. After an overview on existing robustness concepts in multiobjec-

tive optimization (not restricted to the parameter-dependent case) two new

concepts for robustness will be introduced.

The first one is based on the idea of finding curves of minimum length on

the set of substationary points. The mathematical formulation of this task

is based on the calculus of variations (cf. Section 2.3).

For the second robustness concept solution paths are computed that step-

wise vary as little as possible between the Pareto sets for discretized param-

eter values. This approach is less computationally costly and very intuitive.

Here, again techniques from multiobjective optimization and numerical path

76 Parametric Multiobjective Optimization

following have been combined. One special challenge in the context of this

robustness concept was the derivation of equations that steer a path on the

shortest possible, feasible way from one Pareto set to another. Based on these

new equations combined with the Kuhn-Tucker equations specific predictor-

corrector methods have been applied and related regularity conditions have

been proven which are also described in Section 4.4.2.

The last part of Section 4.4.2 is devoted to the comparison of the two

new robustness concepts. To make the concepts comparable the variational

problem arising in Concept I is reformulated for the case of fixed starting

points on a given initial Pareto set. It will turn out that the length of solution

paths w. r. t. Concept I is less or equal to the length of paths obtained with

Concept II. If a λ-robust Pareto point exists whose corresponding path has

length zero, then it is a solution to both robustness concepts.

Finally, in Section 4.4.3 an application in the design of integrated circuits

is given. Here, the robustness of Pareto points with respect to changes in

temperature and supply voltage has been computed making use of Concept

II.

4.4.1 Existing Robustness Definitions in Multiobjective Optimization

In multiobjective optimization, the study of robustness of solutions is a rela-

tively young area of research (cf. [16], [29] for example), especially in evolu-

tionary multiobjective optimization. Different kinds of robustness are studied

in the literature mainly motivated by engineering applications. On the one

hand uncertainty in the optimization variables can occur. Practically, this

can mean that the parameters for a Pareto optimal design of some system

cannot be manufactured with the desired accuracy or can only be modeled

inaccurately. On the other hand, external (also called environmental) pa-

rameters may influence the behavior of the system under consideration. In

practice, external parameters could characterize the influence on the system

under consideration through changing temperatures, wind velocity, air pres-

sure, etc. To put it in a nutshell, the multiobjective optimization problem

can be formulated depending on different kinds of parameters (cf. [10]):

min

x0,x00 F(x0, x00 +ε, λ) (4.3)

where x0∈Rn1are deterministic optimization variables, x00 +εdescribes

uncertain optimization variables with x00 ∈Rn2,n1+n2=n, and λ∈Rp

denotes external parameters.

4.4 Robust Pareto Points 77

Figure 4.10: Point A is more robust than point B with respect to perturbations of

x= (x1, x2, x3) [17]

In [17] two robustness definitions are given. They both treat the case of

uncertain optimization parameters only. The first one is based on using mean

effective objective functions instead of the original ones. Here, robustness is

understood in the sense that perturbations of the optimization parameters

lead to small changes in the objective values as illustrated in Figure 4.10.

Definition 4.4 (Multiobjective Robust Solution of Type I, Deb 2006 [17])

Consider a multiobjective optimization problem

min

x∈SF(x), F(x)=(f1(x), . . . , fk(x)) .

A point x?is called a multiobjective robust solution of type I if it is

a global, feasible Pareto optimal solution of the multiobjective optimization

problem

min

x∈SFeff(x)with Feff (x) = feff

1(x), . . . , feff

k(x)

and feff

j(x) = 1

|Uδ(x)|Zs∈Uδ(x)

fj(s)ds,

where Uδ(x)⊆Sis a δ-neighborhood of xand Sdenotes the feasible region.

In this definition, the neighborhood to be studied in parameter space is

set fixed through the parameter δ.

Remark 4.5 The definition of multiobjective robust solution of type I has

been inspired by a robustness concept for single objective optimization de-

scribed in [11] and [103], for example. The main idea of this single objective

optimization robustness concept is, that minima which are sharp peaks of

78 Parametric Multiobjective Optimization

Figure 4.11: Illustration of the fact that a local minimum point (A) can be more robust

with respect to perturbations of xthan the global minimum point (B) in single objective

optimization problems (cf. [17])

the objective functions are not robust (cf. Figure 4.11 for an intuitive un-

derstanding). To avoid the computation of these peaks, a mean effective

objective function is minimized instead of the original objective. This mean

objective function feff(x), as given in Definition 4.4, flattens sharp peaks by

taking the average values of the original objective function within certain

neighborhoods.

The second definition for robustness given in [17] (so-called robust solu-

tions of type II, cf. Definition 4.6) incorporates properties of the solution in

objective space. Here, the normalized difference between the objective values

of the perturbed function and the original function values is desired to be

less than a user-defined value. This inequality is included as a constraint to

the original multiobjective optimization problem in order to compute robust

solutions of type II.

Definition 4.6 (Multiobjective Robust Solution of Type II, Deb 2006 [17])

Consider a multiobjective optimization problem

min

x∈SF(x), F(x)=(f1(x), . . . , fk(x)) .

A point x?is called a multiobjective robust solution of type II if it is

a global, feasible Pareto optimal solution of the multiobjective optimization

problem

min

x∈SF(x)

subject to kFp(x)−F(x)k

kF(x)k≤η

4.4 Robust Pareto Points 79

where the limiting parameter ηcan be chosen as an arbitrary constant value,

Fp(x)denotes the function values of the perturbed point (e. g. Fp(x) = Feff (x)

can be used) and k.kis a suitable vector norm.

In [17] possible scenarios of the correspondence between the original Pareto

optimal solution (minimization of F) and Pareto optima of the mean effec-

tive objective function Feff is discussed. Moreover, the computation of robust

solutions with respect to these two robustness types for several test problems

has been considered in the same paper.

In [35] different fitness functions for multiobjective evolutionary algo-

rithms are given that lead to robust solutions. The authors distinguish be-

tween expectation measures and variance measures. Expectation measures

estimate the value of the objective function assuming a certain probability

distribution of disturbances of the optimization parameters within a neigh-

borhood. The main idea of variance measures is to formulate new objectives

that describe the mean and the variance of the original objective functions.

In [47] objective functions are studied that may depend on all kinds of

parameters mentioned in (4.3). Here, similar to Definition 4.6, a region

around the point on the Pareto front to be analyzed is set fixed in objective

space. The region in the space of the uncertain and external parameters

that leads to these objective values is determined, the so-called sensitivity

region. Here, the parameters are assumed to vary within known intervals.

The larger the sensitity region the more robust is the corresponding Pareto

optimal solution. As the sensitivity region may be assymetric, in [47] the

worst case sensitivity region is introduced which is given by a ball whose

radius equals the shortest distance to the boundary of the sensitivity region.

Figure 4.12 visualizes the principal idea of this robustness concept. For the

computation of robust Pareto sets, in [47] the condition that the radius of

the worst case sensitivity region is bigger than a user-defined value is handled

as a constraint to the original multiobjective optimization problem. In [65]

this concept is extended to the computation of the objective sensitivity region.

Among others things, in that work the effect of parameter variation within an

interval on the objective values is analyzed. Here, the ratio of the objective

sensitivity region to the user-defined acceptable objective variation is used

for the definition of a robustness measure, the so-called objective robustness

index.

In [109] robustness with respect to changes in external parameters is stud-

ied. It is assumed that the parameters change in a stochastic manner. In

this work, probabilistic robustness objectives are defined. In order to obtain

80 Parametric Multiobjective Optimization

Figure 4.12: Visualization of the sensitivity region and the worst case sensitivity region

as defined in [47]

so-called multiobjective probabilistic acceptable solutions the original multi-

objective optimization problem is reformulated by use of some violation prob-

ability of each objective. In this case, the violation probability is given by

the integral over the product of an indicator function that gives back if the

function values are acceptable or not, and the probability density function

over the expected external parameter space.

A lot of papers investigate multiobjective optimization problems with

fuzzy data. Here, the possible ranges of uncertain parameters are modelled

by fuzzy sets (cf. for example [56, 30]). A comparison of fuzzy approaches

to stochastic approaches is given in [94].

A different approach is to include robustness directly into the definition

of dominance (cf. Definition 3.1). In order to obtain a Pareto set that

is robust either with respect to uncertainty of the optimization variables

or noisy objective functions different concepts like probabilistic dominance

[100], ε-dominance [91] and many others (e. g. in [55, 28, 99, 84]) have been

developed.

4.4.2 New Concepts for Robustness against Variations of an External Pa-

rameter

In the following subsections, two new concepts are given which allow the com-

putation of substationary points that are robust with respect to changes of an

external parameter in one-parametric multiobjective optimization problems.

In contrast to the approaches for robustness that already have been devel-

oped in multiobjective optimization (as summarized in the last section), the

change of the Pareto sets themselves with respect to different values of the

external parameter is studied. Here, the objective functions stay the same

as in the original problem and no additional constraints are added.

4.4 Robust Pareto Points 81

In Example 4.2 one can observe that the Pareto sets for different values

of the parameter λintersect in some points and differ significantly in other

regions. In this section, algorithms and the theoretical background are de-

veloped that allow to compute how ‘robust’ a Pareto point is with respect

to changes of the parameter λwithin a given interval [λstart, λend]. Loosely

speaking, the more robust a Pareto point for a fixed external parameter

value is the less it changes to other Pareto points for different values of the

external parameter within a given interval. The same considerations can be

transferred to the study of robustness on Pareto fronts. In both cases, the

techniques used to obtain robust solutions are completely different from the

ones used in the approaches described above. The first concept, which we

have published in [107], is based on the calculus of variations whereas in the

second concept numerical path following methods are employed for a certain

system of equations (see also [21]).

Concept I: Robustness formulated via the classical calculus of variations

The classical calculus of variations allows, in the case of at least twice con-

tinuously differentiable objective functions, the computation of a substation-

ary point that varies as little as possible with respect to changes of the exter-

nal parameter λ. To be more precise, the aim is to determine a continuously

differentiable curve γ(λ) = (x(λ), t(λ))Tof minimal length from an arbitrary

starting point on the set of substationary points Sλstart to an arbitrary end

point on Sλend that lies within the λ-dependent set of substationary points.

This problem can be formulated as a variational problem by

min

γZλend

λstart kx0(λ)k2dλ(4.4)

s. t. HKT(γ(λ), λ)=0

with the boundary conditions x(λstart)∈Sλstart and x(λend)∈Sλend . Here,

the functional in (4.4) corresponds to the length of the curve x(λ) that

has to be minimized, and HKT(γ(λ), λ) describes the Kuhn-Tucker equa-

tions as given in Equation 4.2. Note, that due to the equality constraint

HKT (x(λ), t(λ), λ) = 0 the path is enforced to lie on the set of substationary

points, i. e. x(λ)∈Sλ∀λ∈[λstart, λend].

For the following considerations it is assumed that the curve x(λ) is reg-

ular, i. e. kx0(λ)k 6= 0 for all λ∈[λstart, λend].

82 Parametric Multiobjective Optimization

Definition 4.7 (Robustness w. r. t. Concept I)

Let γ?(λ)=(x?(λ), t?(λ))Tbe a solution of Problem (4.4) with the free bound-

ary conditions as stated above. Then x?(λ)is called a λ-robust solution path

of Concept I with respect to the interval [λstart, λend]. The point x?(λstart)

is called a λ-robust substationary point of Concept I w. r. t. the interval

[λstart, λend]. If the objective functions are convex and t?(λstart)6= 0, i. e. the

substationary point x?(λstart)is indeed a Pareto point, then x?(λstart)is called

aλ-robust Pareto point of Concept I with respect to the interval [λstart, λend].

Remark 4.8 The intuition behind Definition 4.7 is to study the influence on

a Pareto set when increasing the value of the external parameter. Instead,

using the same methodology as described in the following, one could consider

variations of the external parameter λin both directions. Starting with

the Pareto set for a fixed value λ=λ?one would consider the change of

λ∈[λ?−ε, λ?+ε] for a fixed value ε∈R. In this case, λ-robust substationary

points with respect to the interval [λ?−ε, λ?+ε] would be defined as solutions

of the variational problem

min

γZλ?+ε

λ?−εkx0(λ)k2dλ

s. t. HKT (x(λ), t(λ), λ) = 0.

The multiplier rule (Theorem 2.11) states that a necessary condition for

optimiality of this problem is given by the Euler-Lagrange equations for the

functional

L(γ(λ), γ0(λ), µ(λ), λ) = Zλend

λstart kx0(λ)k2+ (µ(λ))T·HKT(γ(λ), λ)dλ, (4.5)

where µ: [λstart, λend]→Rn+1,µ(λ)=(µ1(λ),··· , µn+1(λ))T(cf. Chapter 2,

Section 2.3). Defining

L(γ(λ), γ0(λ), µ(λ), λ) = kx0(λ)k2+ (µ(λ))T·HKT(γ(λ), λ),(4.6)

the Euler-Lagrange equations for (4.4) are given by

dλ∂L

∂γ0−∂L

∂γ = 0 (4.7)

HKT(γ(λ), λ) = 0 (4.8)

4.4 Robust Pareto Points 83

(the Kuhn-Tucker equations (4.8) stem from the derivative of Lwith respect

to µ). The single terms of this equation are given by

∂L

∂γ0=∂

∂γ0kx0(λ)k2+µ(λ)T·HKT(γ(λ), λ)

kx0(λ)k2·(x0

1(λ),··· , x0

n(λ),0)

dλ∂L

∂γ0=





x00

1(λ)

kx0(λ)k2−x0

1(λ)

kx0(λ)k3

2·(Pn

i=1 x0

i(λ)·x00

i(λ))

x00

n(λ)

kx0(λ)k2−x0

n(λ)

kx0(λ)k3

2·(Pn

i=1 x0

i(λ)·x00

i(λ))







and

∂L

∂γ =







(µ1(λ),··· , µn+1(λ)) ·





∂

∂x1H1(x(λ), t(λ), λ)

∂

∂x1Hn(x(λ), t(λ), λ)







(µ1(λ),··· , µn+1(λ)) ·





∂

∂xnH1(x(λ), t(λ), λ)

∂

∂xnHn(x(λ), t(λ), λ)







(µ1(λ),··· , µn+1(λ)) ·





∂

∂t1H1(x(λ), t(λ), λ)

∂

∂t1Hn+1(x(λ), t(λ), λ)







(µ1(λ),··· , µn+1(λ)) ·





∂

∂tkH1(x(λ), t(λ), λ)

∂

∂tkHn+1(x(λ), t(λ), λ)













Altogether, this leads to the Euler-Lagrange equations

x00 (λ)

kx0(λ)k2

−x0(λ)

kx0(λ)k3

2 n

i=1

i(λ)·x00

i(λ)!−



µ(λ)T·∂

∂x 









(γ(λ), λ)





= 0 (4.9)







−µ(λ)T·∂

∂t 





Hn+1







(γ(λ), λ)





= 0 (4.10)







Hn+1







(γ(λ), λ) = Pk

i=1(ti(λ))2∇xfi(x, λ)

i=1(ti(λ))2−1= 0.(4.11)

84 Parametric Multiobjective Optimization

The free boundary conditions (cf. Section 2.3) lead to the additional

conditions

∂L

∂x0λ=λstart ⊥ker ∂

∂xHKT(γ(λstart), λstart)

⇔1

kx0(λstart)k2·x0(λstart)⊥ker ∂

∂xHKT(γ(λstart), λstart)(4.12)

and

∂L

∂x0λ=λend ⊥ker ∂

∂xHKT(γ(λend), λend)

⇔1

kx0(λend)k2·x0(λend)⊥ker ∂

∂xHKT(γ(λend), λend).(4.13)

In order to compute a λ-robust solution numerically, the variational prob-

lem is discretized following the idea of the construction of variational integra-

tors [68]. Rather than discretizing the system of equations which consists of

the Euler-Lagrange equations and optionally additional constraints, the vari-

ational integral is discretized directly and a discrete version of the calculus

of variations is applied to derive the set of equations known as the discrete

Euler-Lagrange equations and discretized constraints. In the following, we

consider a discretization of the problem

min

γ,µ Zλend

λstart

L(γ(λ), γ0(λ), µ(λ), λ) dλ(4.14)

with free boundary conditions that satisfy the constraints

ϕ(x(λstart), λstart) = ϕ(x(λend), λend) = 0.

Note that, as before, Lis the Lagrangian given by

L(γ(λ), γ0(λ), µ(λ), λ) = C(γ(λ), γ0(λ), λ) + µ(λ)T·ϕ(γ(λ), λ).

To this aim the parameter λis assumed to grow with a fixed step size

h∈Rand we define

λd={λstart +jh}N

j=0

with λN=λend. The hitherto continuous curves γ(λ) and µ(λ) are now

replaced by discrete curves

γd:λd→Rn, γd={γj}N

j=0,where γj=γd(λj),

µd:λd→Rm, µd={µj}N

j=0,where µj=µd(λj).

4.4 Robust Pareto Points 85

Based on these discrete objects, the integral of the Lagrangian along a short

interval is approximated by a discrete Lagrangian Ldas

Zλj+1

λj

L(γ(λ), γ0(λ), µ(λ), λ)dλ ≈Ld(γj, µj, λj, γj+1, µj+1, λj+1) (4.15)

which depends on two neighboring points (γj, µj) and (γj+1, µj+1) and on

two external parameter values λjand λj+1. Finally, the discrete variational

integral is defined as

Ld(γd, µd) =

N−1

j=0

Ld(γj, µj, λj, γj+1, µj+1, λj+1).

Figure 4.13 visualizes the approximation of the integral by this finite sum.

Figure 4.13: Discretization of an integral by a finite sum as used in (4.16)

Different quadrature rules can be chosen for the approximation in (4.15)

(cf. [68]). For a second order approximation, typically the difference quotient

γj+1 −γj

is used for the approximation of derivatives of γat each discretization point.

Furthermore, following [68, 64], a midpoint evaluation for the function Cand

a trapezoidal rule for the constraints lead to the discrete variational integral

Ld(γd, µd) =

N−1

j=0

Ld(γj, µj, λj, γj+1, µj+1, λj+1)

N−1

j=0

h·Cγj+γj+1

2,γj+1 −γj

h,λj+λj+1

2+ (4.16)

2µT

j·ϕ(γj, λj)+1

2µT

j+1 ·ϕ(γj+1, λj+1).

86 Parametric Multiobjective Optimization

In the following, the first index corresponds to the dimension and the

second index corresponds to the discretization point on the respective dis-

cretized curves. The points on the discretized curves are given as

γj=





γ1,j

γn,j





, µj=





µ1,j

µm,j







for j= 0, . . . , N.

Let

ηd:λd→Rn+m, ηd={ηj}N

j=0,with ηj=ηd(λj),

be the discretization of a twice continuously differentiable curve.

Assume that

zd=γd

µdwith zj=zd(λj), j = 0, . . . , N

is the discretization of a minimizing curve of the variational problem (4.14).

In analogue to the continuous case, δzd=ηdis called a variation of zd. More

detailed, we have

ηj=





η1,j

ηn+m,j





=δγj

δµj=







δγ1,j

δγn,j

δµ1,j

δµm,j







for j= 0, . . . , N.

Let ε∈R. Similar to the derivation of the Euler-Lagrange equations for

the continuous case [41], the first variation δof Ldis defined as v0(0), where

v:R→R,

v(ε) =

N−1

j=0

Ld(zj+εηj, λj, zj+1 +εηj+1, λj+1).

The vanishing of the first variation of Ld(γd, µd) leads to the following

computations:

δ



N−1

j=0

h·Cγj+γj+1

2,γj+1 −γj

h,λj+λj+1

2+

2µT

jϕ(γj, λj)+1

2µT

j+1ϕ(xj+1, λj+1)= 0.

4.4 Robust Pareto Points 87

It follows that

N−1

j=0

h·∂

∂γjCγj+γj+1

2,γj+1 −γj

h,λj+λj+1

2+1

2µT

j·ϕ(γj, λj)δγj+

∂

∂γj+1 Cγj+γj+1

2,γj+1 −γj

h,λj+λj+1

2+

2µT

j+1 ·ϕ(γj+1, λj+1)δγj+1+

∂

∂µj1

2µT

j·ϕ(γj, λj)δµj+∂

∂µj+1 µT

j+1 ·ϕ(γj+1, λj+1)δµj+1= 0

⇔h·∂

∂γ0Cγ0+γ1

2,γ1−γ0

h,λ0+λ1

2+1

2µ0·ϕ(γ0, λstart)δγ0+

∂

∂γNCγN−1+γN

2,γN−γN−1

h,λN−1+λN

2+1

2µT

N·ϕ(γN, λend)δγN+

N−1

j=1

∂

∂γjCγj+γj+1

2,γj+1 −γj

h,λj+λj+1

2+

Cγj−1+γj

2,γj−γj−1

h,λj−1+λj

2+µT

j·ϕ(γj, λj)δγj+

∂

∂µ01

2µT

0·ϕ(γ0, λstart)δµ0+

∂

∂µN1

2µT

N·ϕ(γN, λend)δµN+

N−1

j=1

∂

∂µjµT

j·ϕ(γj, λj)δµj

= 0.

As the variations δγjand δµjare arbitrary for j= 0, . . . , N each term mul-

tiplied with them has to equal zero. It follows that for all j= 1, . . . , N −1

h·∂

∂γjCγj+γj+1

2,γj+1 −γj

h,λj+λj+1

2+

Cγj−1+γj

2,γj−γj−1

h,λj−1+λj

2+µT

jϕ(γj, λj)= 0

ϕ(γj, λj) = 0.

At the free ends, the variations δγ0,δγN,δµ0and δµNcan be arbitrarily

chosen as well and thus it turns out that the following terms have to vanish:

88 Parametric Multiobjective Optimization

h·∂

∂γ0Cγ0+γ1

2,γ1−γ0

h,λ0+λ1

2+1

2h·µT

∂

∂γ0

ϕ(γ0, λstart)T

= 0

ϕ(γ0, λstart)=0

h·∂

∂γNCγN−1+γN

2,γN−γN−1

h,λN−1+λN

2+1

2h·µT

∂

∂γN

ϕ(γN, λend)T

= 0

ϕ(γN, λend)=0.

To put it in a nutshell, one ends up with the system of equations

∀j= 0,...,N :ϕ(γj, λj)=0

∀j= 1,...,N −1 :

h·∂

∂γjCγj+γj+1

2,γj+1 −γj

h,λj+λj+1

2+

Cγj−1+γj

2,γj−γj−1

h,λj−1+λj

2+µT

jϕ(γj, λj)= 0

h·∂

∂γ0Cγ0+γ1

2,γ1−γ0

h,λ0+λ1

2+1

2h·µT

∂

∂γ0

ϕ(γ0, λstart)T

= 0

h·∂

∂γNCγN−1+γN

2,γN−γN−1

h,λN−1+λN

2+1

2h·µT

∂

∂γN

ϕ(γN, λend)T

= 0

ϕ(γN, λend)=0.

The solution of this system of equations provides a numerical approxi-

mation of the solution of the boundary value problem given by the Euler-

Lagrange equations (2.8)-(2.9) and the transversality condition (2.11) (see

pages 23/24). This can in particular be seen if we consider the special case of

computing λ-robust substationary points w. r. t. Concept I, where the func-

tions

C(γ(λ), γ0(λ), λ) = kx0(λ)k2and ϕ(γ(λ), λ) = HKT(γ(λ), λ)

are considered (remember that γ(λ) = (x(λ), t(λ))T). For this special case,

one ends up with the system of equations

∀j= 0, . . . , N :µT

j·∂

∂tj

HKT(xj, tj, λj)T

= 0

∀j= 0, . . . , N :HKT(xj, tj, λj) = 0

∀j= 1, . . . , N −1 :

h·xj+1 −xj

kxj+1 −xjk−xj−xj−1

kxj−xj−1k−µT

j·∂

∂xj

HKT(xj, tj, λj)T

= 0

h·x1−x0

kx1−x0k−1

2µT

0·∂

∂x0

HKT(x0, t0, λstart)T

= 0

h·xN−xN−1

kxN−xN−1k+1

2µT

N·∂

∂xN

HKT(xN, tN, λend)T

= 0.

4.4 Robust Pareto Points 89

The solution of this system of equations approximates the solution of the

Euler-Lagrange equations (4.9)-(4.13). This is obvious for the first two equa-

tions. To understand why the first part of the third equation also gives an

approximation of the first two terms in equation (4.9) one has to remember

that the term stems from the λ-derivative of x0(λ)

kx0(λ)k2. In the third equation,

this derivative is approximated by a difference quotient. The last two equa-

tions approximate the transversality conditions (4.12) and (4.13) since for a

matrix Ait holds (ker(A))⊥= im (AT)).

Remark 4.9 By solving this system of equations only one (local) solution

will be obtained. Which solution is found, highly depends on the initial values

of the parameters. If the same variational problem is formulated with fixed

starting point (x0, λstart) on the initial Pareto set, the function value of the

variational integral Rλend

λstart kx0(λ)k2dλcan be seen as a measure for robustness

of the starting point (x0, λstart).

Example 4.10 Consider the parametric multiobjective optimization prob-

lem minxF:R2×R→R2, F = (f1, f2),

f1(x, λ) = (x1−sin(λ))2+ (x2−cos(λ))2

f2(x, λ) = (x1−2 sin(λ))2+ (x2−2 cos(λ))2

in which the parameter λis varied from 0 to 2π.

The Pareto set of these objectives is given by a straight line of length one

that λ-dependently circles around the origin with a distance of one to two.

The discretization of the Euler-Lagrange equations as described above and

the solution of the resulting nonlinear system of equations with the MATLAB

routine fsolve (cf. [101]) leads to the results given in Figures 4.14 and 4.15.

Here, N= 32 discretization points have been used. As one could expect, the

solution curve of smallest length on the set of substationary points lies on

the ‘inner circle’.

Hitherto it has been assumed that kx0(λ)k 6= 0 holds. This assumption

can be cancelled if one considers the minimization of energy instead of length

of the curve x(λ). Here, energy is defined by the variational integral

Zλend

λstart

2kx0(λ)k2

2dλ. (4.17)

As the Kuhn-Tucker constraints of the variational problem (4.4) depend on

λexplicitly, the minimization of energy instead of length does not lead to

the same optimal solution (cf. [74]).

90 Parametric Multiobjective Optimization

Figure 4.14: Visualization of the λ-robust solution path (black) and λ-dependent Pareto

set

However, if a solution curve of length zero exists, i. e. there exists a point

in which the set of substationary points does not change in the x-space under

the variation of λ, this solution will be both obtained by minimizing length

and energy. Thus, if a λ-robust substationary point that stays constant under

the variation of λin x-space is to be computed, the following variational

problem can be considered instead of (4.4):

min

γZλend

λstart

2kx0(λ)k2

2dλ(4.18)

s. t. HKT(γ(λ), λ)=0

with the boundary conditions x(λstart)∈Sλstart and x(λend)∈Sλend .

In analogue to the computations for (4.4) this leads to the Euler-Lagrange

equations

x00(λ)

0−



µ(λ)T·∂

∂(x, t)





Hn+1





(x(λ), t(λ), λ)





= 0 (4.19)







Hn+1







(x(λ), t(λ), λ) = Pk

i=1(ti(λ))2∇xfi(x, λ)

i=1(ti(λ))2−1= 0 (4.20)

4.4 Robust Pareto Points 91

Figure 4.15: Projection of the solution visualized in Figure 4.14 onto the x1-x2-plane

with boundary conditions

x0(λstart)⊥ker ∂

∂xHKT(γ(λstart), λstart)(4.21)

x0(λend)⊥ker ∂

∂xHKT(γ(λend), λend),(4.22)

and the discretized Euler-Lagrange equations

HKT(xj, tj, λj)=0∀j= 0, . . . , N

µT

j·∂

∂tj

HKT(xj, tj, λj)T

= 0 ∀j= 0, . . . , N

xj+1 −2xj+xj−1

h2−µT

j·∂

∂xj

HKT(xj, tj, λj)T

= 0 ∀j= 1, . . . , N −1

x1−x0

h2−1

2µT

0·∂

∂x0

HKT(x0, t0, λstart)T

= 0

−xN−xN−1

h2−1

2µT

N·∂

∂xN

HKT(xN, tN, λend)T

= 0

92 Parametric Multiobjective Optimization

Example 4.11 Consider again the parametric multiobjective optimization

problem minxF:R2×R→R2, F = (f1, f2),

f1(x, λ) = λ(x1−2)2+ (x2−2)2+ (1 −λ)(x1−2)4+ (x2−2)8

f2(x, λ) = (x1+ 2λ)2+ (x2+ 2λ)2

in which each objective function depends on the parameter λ∈[0,1], i. e.

λstart = 0 and λend = 1.

To find out if one Pareto point exists for which all λ-dependent Pareto

sets intersect, Problem (4.18) has been considered. The discretized Euler-

Lagrange equations for energy minimization of this example have been solved

with the MATLAB routine fsolve (cf. [101]) using N= 20 discretization

points. The left plot in Figure 4.16 shows the solution path (green with

black dots) of the λ-robust Pareto point (red) in the x1-x2-λ-space. In this

plot, also some Pareto sets (gray curves) for different values of λare plotted.

In the right plot of Figure 4.16 a projection of the same data to the x1-x2-

plane is shown – one can observe that the λ-robust Pareto point (red) indeed

does not change under the variation of λ.

Figure 4.16: λ-robust solution path and some Pareto sets (on the left) and the projection

onto the x1-x2-plane (on the right)

Concept II: Locally robust Pareto points

In contrast to the robustness concept proposed in the last section now a local

strategy is considered. The following results have already been published in

a like manner in [21]. Again, it is assumed that the parameter λis varied

within a given interval [λstart, λend]⊂R. For each point of a discrete covering

of the initial Pareto set, λ-dependent solution paths are approximated that

satisfy the Kuhn-Tucker equations and do locally change as little as possible

4.4 Robust Pareto Points 93

under the variation of λ. Thus, as long as a starting point is feasible for

increasing values of λthe solution path is given by this constant value. If a

point on the path is not feasible for an increased value of λ, then the solution

path consists of those points that vary as little as necessary compared to

the previously computed point. The robustness of a Pareto point against

variations of the external parameter can be measured through the length of

these paths.

In order to realize the numerical approximation of these solution paths,

again numerical path following methods can come into play. In order to

force the path into that direction in which the Pareto point changes as little

as possible for increasing values of λthe Kuhn-Tucker system has to be

expanded by certain equations.

Approaching this problem, first only a given point y0∈Sλ0and a set of

substationary points Sλ1are considered. The aim is to compute a point on

Sλ1which has minimal distance to y0. This leads to a minimization problem

with equality constraints as described in Section 2.2 (pages 16 ff.).

The following proposition gives a necessary condition for a point on Sλ1

to have minimal distance to the point y0.

Proposition 4.12 Let λ0,λ1∈[λstart, λend]be two nonequal fixed values of

the continuation parameter λ. Let y0∈Sλ0be fixed, let x∈Sλ1and F=

(f1, . . . , fk)T. Let

∇(x,t)H1

KT(x, t, λ1),...,∇(x,t)Hn+1

KT (x, t, λ1)

be linearly independent. If

a) xhas the minimal Euclidean distance to y0or

b) F(x, λ1)has the minimal Euclidean distance to F(y0, λ0),

then there exist multipliers t∈Rkand (µ1, . . . , µn+1)T=µ∈Rn+1, such that







Hn+1







(x, t, λ1) = 





i=1

i∇xfi(x, λ1)

i=1

i−1







= 0







Hn+k





(x, t, µ, λ1) = d(x)

0−



µT·∂

∂(x,t)





Hn+1





(x, t, λ1)





= 0,

(4.23)

where – in the corresponding cases – d:Rn→Rnis given as

94 Parametric Multiobjective Optimization

a) d(x) = d(x;y0, λ0, λ1) = 2(x−y0)or

b) d(x) = d(x;y0, λ0, λ1)=2Pk

i=1(fi(x, λ1)−fi(y0, λ0))∇xfi(x, λ1).

Here, dis called a decision function.

Proof:

a) A point xwith minimal Euclidean distance to y0is given by the solution

of the optimization problem

min

xkx−y0k2

subject to x∈Sλ1.

The set Sλ1is described by the nKuhn-Tucker equations, and thus this

minimization problem leads to an optimization problem with equality

constraints:

min

xkx−y0k2

subject to 





Hn+1





(x, t, λ1) = 





i=1

i∇xfi(x, λ1)

i=1 t2

i−1





= 0.

If the point (x, t) is an extremum, then there exist Lagrangian multi-

pliers µ1,··· , µn+1 ∈R, so that

∇(x,t)kx−y0k2

2−µ1∇(x,t)H1

KT(x, t, λ1)−···

···−µn+1∇(x,t)Hn+1

KT (x, t, λ1) = 0

⇔2(x−y0)

0−µ1∇(x,t)H1

KT(x, t, λ1)−···

···−µn+1∇(x,t)Hn+1

KT (x, t, λ1) = 0

(by use of Theorem 2.7). Combining these n+kequations with the

equality constraints one obtains a system of equations as stated in the

proposition.

b) The same idea works in objective space. Here, the norm of the differ-

ence of the function values of xand y0has to be minimized:

min

x









f1(x, λ1)

fk(x, λ1)





−





f1(y0, λ0)

fk(y0, λ0)









subject to x∈Sλ1.

4.4 Robust Pareto Points 95

The gradient w. r. t. xof the objective function of this minimization

problem is given as

∇x













f1(x, λ1)

fk(x, λ1)





−





f1(y0, λ0)

fk(y0, λ0)















=





2(f1(x, λ1)−f1(y0, λ0))∂f1(x,λ1)

∂x1+···+ 2(fk(x, λ1)−fk(y0, λ0))∂fk(x,λ1)

∂x1

2(f1(x, λ1)−f1(y0, λ0))∂f1(x,λ1)

∂xn+···+ 2(fk(x, λ1)−fk(y0, λ0))∂fk(x,λ1)

∂xn







= 2 Pk

i=1(fi(x, λ1)−fi(y0, λ0))∇xfi(x, λ1)

Additionally,

∇t













f1(x, λ1)

fk(x, λ1)





−





f1(y0, λ0)

fk(y0, λ0)













= 0.

Combining this with the Lagrangian multipliers which stem from the

First-Order Necessary Condition given in Theorem 2.7, the desired re-

sult follows. 

Solutions of the system of equations given in (4.23) are isolated if the

corresponding Jacobian matrix is regular. This is in particular important

for the numerical computations described below, because the full rank of the

Jacobian is needed as an assumption for the numerical path following used

therein. In the following, it is proven that this Jacobian matrix is indeed

regular if the Second-order Sufficiency Condition (cf. Theorem 2.8) for the

underlying mimization problem described in the proof of Proposition 4.12

is satisfied. In Proposition 4.13 first the condition for the regularity of the

Jacobian Jis reformulated in a geometrical way and afterwards this condition

is derived from the Second-order Sufficiency Condition in Corrolary 4.14.

Proposition 4.13 Let

X=Pk

i=1 t2

∂2

∂x2fi2t1∇xf1··· 2tk∇xfk

0 2t1··· 2tk∈R(n+1)×(n+k)

and

Y=∂

∂x (d−mx)−(∂

∂x mt)T

−∂

∂x mt−∂

∂t (mt)∈R(n+k)×(n+k)

96 Parametric Multiobjective Optimization

with

mt= (µ1∇tH1

KT +. . . +µn+1∇tHn+1

KT ),

mx= (µ1∇xH1

KT +. . . +µn∇xHn

KT).

Let t?and µ?denote the corresponding multipliers from the Kuhn-Tucker-

and the Lagrangian equations.

The Jacobian Jof the left hand side in (4.23) is regular in the point

(x?, t?, µ?;y0, λ0, λ1)if and only if

imYker X∩(ker X)⊥={0}.(4.24)

Proof: First of all, the structure of the Jacobian of the system of equations

as stated in Proposition 4.23 is examined.

Claim: The Jacobian is given as J=X0

Y−XT∈R(2n+k+1)×(2n+k+1).

Proof: The Jacobian matrix consists of the following entries:

J=





∂H1,...,n

∂x

∂H1,...,n

∂t

∂H1,...,n

∂µ

∂Hn+1

∂x

∂Hn+1

∂t

∂Hn+1

∂µ

∂H1,...,n

∂x

∂H1,...,n

∂t

∂H1,...,n

∂µ

∂Hn+1,...,n+k

∂x

∂Hn+1,...,n+k

∂t

∂Hn+1,...,n+k

∂µ







=





K C 0

0v0

B H G

A L F





∈R(2n+k+1)×(2n+k+1)

4.4 Robust Pareto Points 97

where

i=1

∂2

∂x2fi∈Rn×n

B=∂

∂x(d−mx)∈Rn×n

with mx= (µ1∇xH1

KT +. . . +µn∇xHn

KT)

A=−∂

∂xmt∈Rk×n

with mt= (µ1∇tH1

KT +. . . +µn+1∇tHn+1

KT )

C=2t1∇xf1··· 2tk∇xfk∈Rn×k

H=−∂

∂tmx∈Rn×k

L=−∂

∂tmt∈Rk×k

G=−∇xH1

KT ··· −∇xHn

KT 0∈Rn×n+1

F=−∇tH1

KT ··· −∇tHn+1

KT ∈Rk×n+1

v=2t1··· 2tk∈Rk.

One can easily see that

H=−∂

∂tmx

=∂

∂t −µ1∇xH1

KT −. . . −µn+1∇xHn+1

KT 

=∂

∂t ∇x(−µ1H1

KT −. . . −µnHn+1

KT 

=∂

∂x (∇t(−µ1H1

KT −. . . −µnHn+1

KT )T

=AT.

98 Parametric Multiobjective Optimization

Setting ˜

K=K

0∈R(n+1)×nit follows that

G=−∇xH1

KT ··· −∇xHn

KT 0

=





−∂H1

∂x1··· −∂Hn

∂x10

−∂H1

∂xn··· −∂Hn

∂xn0







=−Pk

i=1 t2

∂2

∂x2fi0

=−˜

KT.

Defining ˜

C=C

vone gets

C=2t1∇xf1··· 2tk∇xfk

2t1··· 2tk

=





∂H1

∂t1··· ∂H1

∂tk

∂Hn

∂t1··· ∂Hn

∂tk

∂Hn+1

∂t1··· ∂Hn+1

∂tk







=





(∇tH1

KT)T

(∇tHn+1

KT )T





=∇tH1

KT ··· ∇tHn+1

KT T

=−FT.

Thus, including this structure the Jacobian is given as

J=



K˜

B AT−˜

A L −˜

CT

=X0

Y−XT∈R(2n+k+1)×(2n+k+1)

with X=˜

K˜

C∈R(n+1)×(n+k)and Y=B AT

A L ∈R(n+k)×(n+k).

The entries of these matrices are exactly as assumed in the proposition

and thus the claim is proven.

4.4 Robust Pareto Points 99

The Jacobian Jis regular if and only if for vectors a∈Rn+kand b∈Rn+1

X0

Y−XT·a

b= 0 ⇔a

b= 0,(4.25)

i. e. if the system of equations

Xa = 0

Y a −XTb= 0

implies a= 0 and b= 0. Therefore, Jis regular if for 0 6=a∈ker Xand any

06=b∈Rn+1,Y a 6=XTb, that is, Y a /∈imXT∀06=a∈ker X, which means

imYker X∩imXT={0}.

As im (XT) = (ker X)⊥(cf. e. g. [98]), this is equivalent to

imYker X∩(ker X)⊥={0}.



Corollary 4.14 Let D:Rn→Rbe a function with ∇xD=d. Assume there

is a point x?∈Rnthat satisfies the Second-order Sufficiency Condition given

in Theorem 2.8 for the problem

min

xD(x;y0, λ0, λ1)

subject to x∈Sλ1.(4.26)

Let t?and µ?denote the corresponding multipliers from the Kuhn-Tucker-

and the Lagrangian equations.

Then the Jacobian of the left hand side in (4.23) is regular in the point

(x?, t?, µ?;y0, λ0, λ1).

Proof: Solutions of (4.23) satisfy the equality constraints of the optimization

problem and also have the property that the gradient of the Lagrangian

function equals zero. Thus, the important assumption in Theorem 2.8 is the

positivity property of the Hessian matrix L00(x?, t?). Observe that, as the

Lagrangian function is given as

L(x, t;µ, y0, λ0, λ1) = D(x;y0, λ0, λ1)−µT·





Hn+1





(x, t;λ1),

100 Parametric Multiobjective Optimization

it holds

L00(x?, t?;µ?) = Y(x?, t?)µ=µ?.

Furthermore, the matrix Xis the Jacobian of the equality constraints in

problem 4.26 and thus, the set Mdefined in Theorem 2.8 equals ker X.

In the following, it is proven by contradiction that, if Yis positive definite

on ker X, then imYker X∩(ker X)⊥={0}:

Let 0 6=s∈imYker X∩(ker X)⊥. Then there exists

06=a∈ker Xwith Y a =sand s∈(ker X)⊥

and thus aTY a =aTs= 0, as aand sare orthogonal. This is a contradiction

to the assumption that Yis positive definite.

In particular, it now follows from Proposition 4.13 that the Jacobian Jis

regular if the Second-order Sufficiency Condition is satisfied for the underly-

ing optimization problem. 

Condition (4.24) can be interpreted geometrically. It indicates that the

set of points satisfying the Kuhn-Tucker equations may not approach a level

set of the function Dwith more than first order. As Dgives the distance

between Sλ1and y0this especially means that Sλ1is not allowed to be (partly)

circular around y0.

(x⋆, t⋆)

D(x) = c

HKT (x, t, λ1) = 0

Figure 4.17: Condition (4.24) is not satisfied in such a case

More precisely, consider a point (x?, t?) on the set STλ1, where

STλ1={(x, t)∈Rn×Rk|HKT(x, t, λ1) = 0},

and let µ?be the corresponding Lagrangian multiplier from Theorem 2.7.

In the following, the restriction of the Lagrangian Lto the set STλ1and a

4.4 Robust Pareto Points 101

fixed value µ=µ?will be considered defining ˜

L:STλ1→Rby ˜

L(x, t) =

L(x, t;µ?). As on STλ1the function HKT is identically zero, ˜

Lcoincides with

DSTλ1

. For the sake of brevity, in the following computation u= (x, t) and

u?= (x?, t?) are used. The Taylor expansion of ˜

Laround the point (x?, t?)

yields

L(u) = L(u?;µ?) + ∇uL(u?;µ?)(u−u?) + ···

2(u−u?)TL00(u?;µ?)(u−u?) + h. o. t.

Thm. 2.7

=L(u?;µ?) + 1

2(u−u?)TY(u?)µ=µ?(u−u?) + h. o. t.

From this it follows that condition (4.24) is satisfied if the Taylor expansion

of ˜

Lhas a positive definite term of second order. As Dequals ˜

Lon STλ1,

this is not the case in particular if STλ1approaches a level set of Dwith

more than first order, i. e. if the curvature of STλ1in (x?, t?) is equal to the

curvature of the level set of D. Figure 4.17 visualizes this forbidden case.

Algorithmic implementation

The aim is to detect those points x∈Sλstart that vary hardly under

the variation of the parameter λ– in preimage space or in objective space

respectively. Therefore, certain paths that contain substationary points for

different values of λvarying from λstart to λend are computed. These paths

are calculated in such a way that the distance from the previously computed

point to the next point – which has to lie on the set of substationary points

for the new λ-value – is minimal in every step. In this case, the situation

described in Proposition 4.12 arises in every step of a certain path following

method which is going to be described in the following.

As explained in Section 2.4.2 numerical path following can be performed

by predictor-corrector methods. The previously described predictor-corrector

methods are adapted for this special context: Starting on the Pareto set for

a special value of λ, first a solution for a higher value of λis predicted with

a fixed vector αand then the solution for the new fixed λis corrected to the

one with minimal distance to the preceding Pareto set or set of substation-

ary points respectively. These steps are repeated iteratively until λequals or

exceeds the desired value λend.

102 Parametric Multiobjective Optimization

SλS˜

(x, t, λ)

(x, t, ˜

λ)

Figure 4.18: Schematic illustration of the predictor step

Generation of starting points:

First of all, an approximation of the Pareto set for λ=λstart (e. g. using

the algorithms described in Section 3.2.3) is computed. This yields a set of

points which are in particular substationary points. For every point x0within

this set the corresponding vector t0(or α0respectively) can be computed by

solving the Kuhn-Tucker equations for x=x0,λ=λstart.

Initially, µ0= 0, (xold, λold)=(x0, λstart) and u= (x0, t0, λstart, µ0) are set.

Predictor step:

In this step, the value of λfor fixed values of (x, t, µ) (or (x, α, µ) respec-

tively) is simply increased, i. e.

uPred =u+











=











where his an adequately controlled stepsize.

Corrector step:

Now λ=˜

λis set fixed and x, t and µare varied until the point with

4.4 Robust Pareto Points 103

Figure 4.19: Schematic illustration of the corrector step

minimal distance to the preceding set Sλis determined. Therefore, the system

HCorr(x, t, µ) =







i=1 t2

i∇xfi(x, ˜

λ)

i=1 t2

i−1

d(x;xold, λold,˜

λ)

0−µ1∇(x,t)H1

KT(x, t, ˜

λ)−···

···−µn∇(x,t)Hn

KT(x, t, ˜

λ)−µn+1 





2t1

2tk













= 0

(4.27)

is considered and solved numerically with Newton’s method by using the pre-

dictor as an initial guess.

Let (xCorr, tCorr, µCorr) be a solution of HCorr(x, t, µ) = 0 and set

(xold, λold)=(xCorr,˜

λ) and u= (xCorr, tCorr,˜

λ, µCorr).

The predictor and corrector steps are repeated until ˜

λ≥λuis reached.

This algorithm comes up with different paths for different starting points

u0= (x0, t0, λstart, µ0). To measure the length of every path, the Euclidean

distances of the points xion that path are simply summed up in case a).

That means, if the path consists of N+ 1 points, its length is computed by

Path-II-Length(x0) = kx1−x0k+kx2−x1k+. . . +kxN−xN−1k(4.28)

for every starting point x0on the Pareto set for λ=λstart. In case b), i. e.

paths of minimal length in objective space, the Euclidean distances of the

104 Parametric Multiobjective Optimization

objective values for the computed paths are summed up. More precisely,

again assuming that N+ 1 points on this path have been computed,

Path-II-Length(F(x0)) =

kF(x1, λ1)−F(x0, λstart)k+. . . +kF(xN, λN)−F(xN−1, λN−1)k.

The aim is to determine the points in the Pareto set for λ=λstart that

hardly vary under the variation of λ. With the following definition it is

obvious how to compute these points.

Definition 4.15 (Robustness w. r. t. Concept II (cf. [21])) Starting points x0

whose corresponding paths have minimal Path-II-Length in preimage or ob-

jective space are called λ-robust Pareto points w. r. t. Concept II in preimage

or objective space respectively.

Example 4.16 Consider again the parametric multiobjective optimization

problem minxF:R2×R→R2, F = (f1, f2),

f1(x, λ) = λ(x1−2)2+ (x2−2)2+ (1 −λ)(x1−2)4+ (x2−2)8

f2(x, λ) = (x1+ 2λ)2+ (x2+ 2λ)2

for which each objective function depends on the parameter λ∈[0,1], i. e.

λstart = 0 and λend = 1. The Kuhn-Tucker equations for this multiobjective

optimization problem are given as

12λ(x1−2) + 4(1 −λ)(x1−2)3+ 2t2

2(x1+ 2λ) = 0

12λ(x2−2) + 8(1 −λ)(x2−2)7+ 2t2

2(x2+ 2λ) = 0

1+t2

2−1=0

(4.29)

a) Robust Pareto points in parameter space:

Expanding the Kuhn-Tucker systems as stated in Proposition 4.12 re-

sults in the following system of nonlinear equations for the corrector

step:

1(2˜

λ(x1−2) + 4(1 −˜

λ)(x1−2)3)+2t2

2(x1+ 2˜

λ) = 0

1(2˜

λ(x2−2) + 8(1 −˜

λ)(x2−2)7)+2t2

2(x2+ 2˜

λ) = 0

1+t2

2−1=0

2(x1−xold

1)−µ1(t2

1(2˜

λ+ 12(1 −˜

λ)(x1−2)2)+2t2

2) = 0

2(x2−xold

2)−µ2(t2

1(2˜

λ+ 56(1 −˜

λ)(x2−2)6)+2t2

2) = 0

−µ1(2˜

λ(x1−2) + 4(1 −˜

λ)(x1−2)3−(x1+ 2˜

λ)) . . .

. . . −µ2(2˜

λ(x2−2) + 8(1 −˜

λ)(x2−2)7−(x2+ 2˜

λ)) = 0

4.4 Robust Pareto Points 105

Making use of the numerical path following methods described in Sec-

tion 2.4.2 points on the solution curves varying λ∈[0,1] for every

starting point on the Pareto set for λ= 0 were computed. Some ex-

amples of these paths are shown in Figure 4.20 on the left. Having

generated these paths, the length of each path is computed by simply

summing up the squared Euclidean distances as mentioned above. The

result is shown on the right hand side of Figure 4.20. The length of each

path is plotted versus the ith starting point, where itraverses the set

of Pareto points for λ= 0. In this case the starting points are ordered

in the following way: they wander from below (point x1=x2= 0)

towards the upper points of the Pareto set (x1=x2= 2). One can

observe that the lengths of the paths decrease up to the 112th starting

point. This point is in fact (an approximation of) the one for which

the Pareto sets for every λ∈[0,1] coincide, i. e. one of the demanded

robust Pareto points. As one can see, the point x1=x2= 2 has

length zero, too, so it can also be detected as a robust Pareto point al-

though the Jacobian is not regular in this point. It can be determined

in this special case because x1=x2= 2 is a solution for every value

of λ∈[0,1]. Therefore, in our path following algorithm only predictor

steps are performed wherein the Jacobian is not required.

Figure 4.20: Some examples for the computed paths in parameter space (on the left)

and the length of each computed path (on the right)

b) Robust Pareto points in objective space:

As stated in the proposition the same ideas are working when consid-

ering the distances of the images of substationary points. This ansatz

106 Parametric Multiobjective Optimization

does in general not result in the same robust Pareto points as in pa-

rameter space, because the function values do not only depend on the

points in parameter space itself but also on the values of λ. For ex-

ample, in the previous case xs≈(1.1621,1.1621) is a robust Pareto

point in parameter space, but the function value for λ= 0 which is

(f1, f2)(xs,0) ≈(0.7359,2.7010) is far away from the one for λ= 1

which is (f1, f2)(xs,1) = (1.4042,19.9978).

For the computation of robust Pareto points in objective space, the

following equations have to be considered in addition to the Kuhn-

Tucker system in the corrector step:

2(f1(x, ˜

λ)−fold

1(x, ˜

λ))∂f1

∂x1

+ 2(f2(x, ˜

λ)−fold

2(x, ˜

λ))∂f2

∂x1

+···

−µ1(t2

1(2˜

λ+ 12(1 −˜

λ)(x−2)2) + 2t2

2)=0

2(f1(x, ˜

λ)−fold

1(x, ˜

λ))∂f1

∂x2

+ 2(f2(x, ˜

λ)−fold

2(x, ˜

λ))∂f2

∂x2

+···

−µ2(t2

1(2˜

λ+ 56(1 −˜

λ)(x2−2)6) + 2t2

2)=0

−2µ1t1(2˜

λ(x1−2) + 4(1 −˜

λ)(x1−2)3)

−2µ2t1(2˜

λ(x2−2) + ···

+8(1 −˜

λ)(x2−2)7)−2µ3t1= 0

−4µ1t2(x1+ 2˜

λ)−4µ2t2(x2+ 2˜

λ)−2µ3t2= 0

Some examples for resulting paths in objective space are shown in Fig-

ure 4.21. Comparing the distances in objective space, one finds that

the left blue path is the desired path of robust Pareto points. The

corresponding starting point is x≈(2,2). So this point varies as little

as possible both in objective and preimage space.

Figure 4.21 also shows the image of paths which have been optimized

with respect to the variation in preimage space for the same starting

points. As one can easily see these paths are not at all the same.

Example 4.17 Consider the multiobjective optimization problem

min

xF(x), F :R3×R→R3, F = (f1, f2, f3)

with the objective functions

f1(x, λ) = (x−4)2+ (y−4)2+ (z−4 + λ)2

f2(x, λ) = (x+ 4)2+ (y+ 4)2+ (z+4+λ)2

f3(x, λ) = (x+ 4)2+ (y−4)2+ (z+4+λ)2.

4.4 Robust Pareto Points 107

Figure 4.21: Examples of paths with minimum lengths in objective space (blue) and

preimage space (green) between the Pareto sets for λ= 0 (black) and λ= 1 (yellow),

visualized both in (f1, f2, λ)-space

The Pareto set is given by triangles in R3which move in the z-direction

when varying the parameter λ. The triangles lie in the plane Egiven by

E:



z

=



4 + λ

+t1·



1

+t2·



1



for t1, t2∈R. The vector v=



−1

is orthogonal to this plane.

Figure 4.22 shows some examples for paths computed with the previously

described algorithm. As one can observe these paths in fact follow the short-

est possible distance between the Pareto sets for λ=−1 and λ= 1. For

example, the black path exactly describes a translation by vof the starting

point on S−1to S1. At the boundary of the Pareto set, where an orthogo-

nal translation is not feasible, one can observe that indeed the shortest path

within the Pareto sets for fixed values of λis computed.

Comparison of Concept I and II

This section deals with the comparison of the two new concepts for robustness

defined above. To make the two approaches comparable, first of all the

variational approach is formulated in such a way that solutions from a fixed

starting point on the Pareto set for λ=λstart to an arbitrary end point on

108 Parametric Multiobjective Optimization

Figure 4.22: Some examples for computed paths between the Pareto sets for λ=−1

and λ= 1 in the 3d-example

Sλend can be computed which lie within the λ-dependent set of substationary

points. Thus, the starting point that so far has been free in Concept I has

to be fixed instead. This leads to the variational integral

min

γZλend

λstart kx0(λ)k2dλ(4.30)

s. t. HKT(x(λ), t(λ), λ)=0

with the boundary conditions x(λstart) = x0,t(λstart) = t0and the free end

condition x(λend)∈Sλend .

The same Euler-Lagrange equations as before result with the only differ-

ence that one only obtains equations from the transversality condition for

one free end. Therefore, in this case Equation (4.12) does not apply. To sum

up, in the case of a fixed starting point the Euler-Lagragrange equations are

given as:

x00 (λ)

kx0(λ)k2

−x0(λ)

kx0(λ)k3

2 n

i=1

i(λ)·x00

i(λ)!−



µ(λ)T·∂

∂x 









(γ(λ), λ)





= 0 (4.31)

−





µ(λ)T·∂

∂t 





Hn+1







(γ(λ), λ)





= 0 (4.32)







Hn+1







(γ(λ), λ) = Pk

i=1(ti(λ))2∇xfi(x, λ)

i=1(ti(λ))2−1= 0,(4.33)

4.4 Robust Pareto Points 109

and the end condition

kx0(λend)k2·x0(λend)⊥ker ∂

∂xHKT(γ(λend), λend).(4.34)

For numerical computations we again use the discretization of the varia-

tional problem, which in this case leads to the system of equations

hxj−xj−1

kxj−xj−1k−xj+1 −xj

kxj+1 −xjk+µT

∂

∂xj

HKT(xj, tj, λj)T

= 0(4.35)

µT

j·∂

∂tj

HKT(xj, tj, λj)T

= 0(4.36)

HKT(xj, tj, λj) = 0(4.37)

for all j= 1, . . . , N −1, and

h·−xN−xN−1

kxN−xN−1k+1

2µT

∂

∂xN

HKT(xN, tN, λend)T

= 0 (4.38)

µT

N·∂

∂tN

HKT(xN, tN, λend)T

= 0 (4.39)

HKT(xN, tN, λend)=0.(4.40)

Let pI= (x?

0, . . . , x?

N) with x?

0=x0be a solution path3which – together

with the corresponding multipliers – solves Equations (4.35) – (4.40). The

length of this solution path can be computed as follows:

Path-I-length(x?

0) = kx?

1−x?

0k+kx?

2−x?

1k+. . . +kx?

N−x?

N−1k

In the following example, solution paths of the discretized Euler-Lagrange

equations (4.35) – (4.40) are compared with the solution paths from the nu-

merical path following approach for determining λ-robust Pareto points (Con-

cept II). To allow a fair comparison, the external parameter λis discretized

with the same fixed step size both in the discretization of the variational

integral (4.30) and in the predictor step of the numerical path following algo-

rithm (see page 102). We consider λ-robust Pareto points in preimage space,

i. e. the decision function for Concept II is given as d(x;xold, λold, λold +h) =

2(x−xold).

3In the results presented here, the MATLAB solver fsolve [101] has been used to solve

Equations (4.35) – (4.40) numerically.

110 Parametric Multiobjective Optimization

Example 4.18 Consider again (as in Example ) the parametric multiobjec-

tive optimization problem minxF:R2×R→R2, F = (f1, f2),

f1(x, λ) = (x1−sin(λ))2+ (x2−cos(λ))2

f2(x, λ) = (x1−2 sin(λ))2+ (x2−2 cos(λ))2

in which the parameter λis varied from 0 to 2π.

In the following, λ-robust solutions w. r. t. Concept I (using the discretized

variational problem with fixed starting points) and w. r. t. Concept II (mak-

ing use of the numerical path following method) will be compared for this

example. To illustrate the difference between the two approaches, five start-

ing points at the initial Pareto set for λ= 0 have been considered. Figure

4.23 visualizes the results for robust solution paths w. r. t. both concepts.

One can observe that the computations that are based on the starting point

Figure 4.23: Results of the computation of λ-robust solution paths using the variational

approach (on the left) and the numerical path following algorithm (on the right) for Ex-

ample 4.18

(0,2) lead to the ‘outer circle’ which is the global maximum of both the

variational problem and each subproblem occurring in the numerical path

following method. As the concepts both only make use of necessary con-

ditions, these maximal solutions are also feasible results. Moreover it can

be seen that all other solution paths spiral towards the inner circle for both

concepts. The paths computed by the Concept I (plot on the left) approach

the inner circle faster than the paths generated with Concept II (plot on

the right). To illustrate this effect, in Figure 4.24 the two solution paths

presented in Figure 4.23 that both correspond to the same starting point

0= (0,1.75)Tare plotted. On the right of Figure 4.24 the lengths of all

4.4 Robust Pareto Points 111

the paths that have been visualized in Figure 4.23 are compared. Here one

also can observe that the minimization of the respective variational integral

indeed leads to shorter paths than the numerical path following approach.

Figure 4.24: Comparison of the two concepts for one fixed starting point, and comparison

of the lengths of the four exemplary paths that were considered in Example 4.18

The result that the paths w. r. t. Concept I are shorter than those w. r. t.

Concept II in Example 4.18 is not amazing. If one neglects the numerical

error that occurs from the discretization of the variational integral (4.30)

and assumes that the computed solution indeed minimizes the variational

integral, one can argue that the path w. r. t. Concept I is the shortest possible

path connecting the fixed starting point with a free end point at Sλend . On

the contrary, paths w. r. t. Concept II are computed by a local, step-wise

greedy strategy. Thus, it can be expected that

Path-I-Length(x)≤Path-II-Length(x)

for all x∈Pdiscrete, where Pdiscrete ={xstart

i}i=1,...,M is a set of Mstarting

points within the Pareto set for λ=λstart.

As mentioned on page 89, the computation of constant solution paths is

only possible by minimizing energy instead of length of the curve x(λ). In

this case, the consideration of fixed starting points leads to the variational

integral

min

γZλend

λstart

2kx0(λ)k2

2dλ(4.41)

s. t. HKT(γ(λ), λ)=0

112 Parametric Multiobjective Optimization

with the boundary conditions x(λstart) = x0,t(λstart) = t0and the free end

condition x(λend)∈Sλend .

If so, the discretization of the Euler-Lagrange equations is given as

µT

j·∂

∂tj

HKT(xj, tj, λj)T

= 0 ∀j= 1,...,N (4.42)

HKT(xj, tj, λj)=0∀j= 1,...,N (4.43)

xj+1 −2xj+xj−1

h2−µT

j·∂

∂xj

HKT(xj, tj, λj)T

= 0 ∀j= 1,...,N−1 (4.44)

−xN−xN−1

h2−1

2µT

N·∂

∂xN

HKT(xN, tN, λend)T

= 0.(4.45)

In the following, it is again assumed that Pdiscrete ={xstart

i}i=1,...,M is a set

of Mstarting points within the Pareto set for λ=λstart, and that the step

sizes in the computations w. r. t. Concept I and Concept II are chosen in the

same way. As before, for Concept II the preimage space decision function is

considered.

Assume that x?

0∈Pdiscrete. Assume further that for x?

j∈Rnthere exist

multipliers t?

j∈Rkand µ?

j∈Rn+1 such that equations (4.42) – (4.45) are

true for each discretization point λj.

Let the length of the corresponding solution path pIenergy = (x?

0, x?

1, . . . , x?

be defined as

Path-Ienergy-Length(x?

0) = kx?

1−x?

0k+kx?

2−x?

1k+. . . +kx?

N−x?

N−1k

(in analogue to the definition of the length of a λ-robust solution path w. r. t.

Concept II in (4.28) on page 103).

Proposition 4.19 Let x?

0∈Pdiscrete. Then,

Path-Ienergy-Length(x?

0)=0 ⇔Path-II-Length(x?

0)=0.

Proof:

”⇒” Let pIenergy = (x?

0, x?

1, . . . , x?

N) be a solution path that – together with

the corresponding multipliers – solves equations (4.42) – (4.45) and has

Path-Ienergy-Length(x?

0) = 0.

Path-Ienergy-Length(x?

0) = 0

⇔ kx?

1−x?

0k+kx?

2−x?

1k+. . . +kx?

N−x?

N−1k= 0

⇔x?

0=x?

1=. . . =x?

Thus, any path which has Path-Ienergy-Length zero is a path of constant

values, pIenergy = (x?

0, x?

0, . . . , x?

0).

4.4 Robust Pareto Points 113

By (4.43), there exist weight vectors t?

j,j= 1, . . . , N such that x?

0solves

the Kuhn-Tucker equations at each discretization point λj. Thus, after

each predictor step of the numerical path following used in Concept II

the Kuhn-Tucker equations are still satisfied. Moreover, the Euclidean

distance between two successive points on the path pIenergy equals zero,

and thus is minimal. Thus, no corrector steps of the numerical path

following used in Concept II are performed.

⇒The predictor-corrector algorithm used in Concept II (cf. page

102) generates the same path pII = (x?

0, x?

0, . . . , x?

0).

⇒Path-II-Length(x?

0) = 0.

”⇐” Let pII = (x?

0, x?

1, . . . , x?

N) be a path that has been generated by the

numerical path following algorithm of Concept II and assume that

Path-II-Length(x?

0) = 0. In this case,

Path-II-Length(x?

0) = 0

⇔ kx?

1−x?

0k+kx?

2−x?

1k+. . . +kx?

N−x?

N−1k= 0

⇔x?

0=x?

1=. . . =x?

and thus pII = (x?

0, x?

0, . . . , x?

0).

As pII is a solution path w. r. t. Concept II, the necessary conditions

(4.23) (cf. Proposition 4.12) are satisfied in each point on the path. As

in this special case d(x?) = 2(x?−x?) = 0, equation (4.23) says that

there exist multipliers t?

j∈Rkand µ?

j∈Rn+1, such that

−µ?

jT·∂

∂(x?

j, t?

j)HKT (x?

j, t?

j, λj) = 0 ∀j= 0, . . . , N,

and that additionally the Kuhn-Tucker equations are satisfied in each

point of pII.

⇒Equations (4.42) and (4.43) are satisfied. As x?−2x?+x?

h= 0 and

x?−x?

h2= 0, Equations (4.44) und (4.45) are also satisfied.

⇒pII is a solution path which – together with the corresponding

multipliers – solves the discretized Euler-Lagrange equations and

has Path-Ienergy-Length(x?) = 0.

114 Parametric Multiobjective Optimization

4.4.3 Application: Robust Pareto Points in the Design of Integrated Cir-

cuits4

Integrated circuits are composed of a couple of standard cells that are multi-

ply combined and repeated. Thus, one expects that an optimization of these

standard cells causes a remarkable improvement of the entire integrated cir-

cuit. In [7] three different standard cells were considered: inverters, NAND-

gates and NOR-gates (both in 65nm and 90nm technology).

These standard cells are a combination of the most basic elements, the

transistors, that deliver the desired functionality. In Figure 4.25 the principal

functioning of a metal-oxide semiconductor field-effect transistor (MOSFET)

is sketched. One distinguishes between pMOS and nMOS transistors. In

CMOS (complementary metal oxide semiconductor) technology, transistors

of these two types are combined to reach the desired functionality (see [4] for

an extensive introduction). The task of an inverter is to invert the incoming

Figure 4.25: Schematic illustration of a metal-oxide semiconductor field-effect transistor

(MOSFET) (cp. [4])

signal (1 is converted into 0 and vice versa). This can be reached by the

combination of two transistors. The CMOS NOR-gate is composed of four

transistors as shown in Figure 4.26. Its output is the negated value of the

boolean function OR of two inputs. Similarly, the CMOS NAND-gate delivers

the negated output of the boolean function AND of two inputs.

In [7, 96] it has been studied how to choose the width Wof each transistor

contained in inverters, NAND- and NOR-gates in order to guarantee a good

4in cooperation with the Department of System and Circuit Technology, Prof. Dr.-Ing.

U. R¨

uckert, Paderborn, especially Matthias Blesken, and in cooperation with Dominik

Steenken, cf. [96, 7]

4.4 Robust Pareto Points 115

performance of these standard cells. Here, the length Lis assumed to be as

small as technically realizable.

Three different objectives are taken into account:

•maximization of the noise margin NM, defined as the maximal possible

deviation of the input signal from the nominal value such that the input

signal is still interpreted correctly,

•minimization of the propagation delay tpd, defined as the time it takes

that a change in the input signal is reflected in the output,

•and minimization of the dynamic energy consumption Ein +Edyn which

sums up any energy losses that occur when the input signal changes.

These objective functions not only depend on the optimization variables

given by the widths of the transistors but also on several process parameters

(like doping) and runtime parameters (like temperature and supply voltage).

In [96] different robustness concepts have been studied and applied to the

case of varying temperatures and supply voltages. In this thesis only the

results for the 65nm CMOS NOR-gate are summarized.

Figure 4.26: Net list of a CMOS NOR-gate (cp. [4])

A NOR-gate consists of two nMOS and two pMOS transistors (see Fig-

ure 4.26). In order to make the results comparable to values proposed by a

commercial standard cell library, the widths of transistors of the same kind

are supposed to be the same (in [96] also a multiobjective optimization was

performed that allows different width of the pMOS transistors). Thus, two

different widths denoted by Wp(width of each pMOS transistor) and Wn

(width of each nMOS transistor) have to be optimized. The evaluation of

116 Parametric Multiobjective Optimization

the three objective functions mentioned above is very time-consuming as it is

performed using the circuit simulator HSPICE5. In order to reduce the com-

puting time, in [96] the set-oriented subdivision and recovering techniques

for the approximation of the Pareto set (cf. Section 3.2.3) have been paral-

lelized. A compute server has been developed that allows the distribution of

function evaluations to different clients. In Figure 4.27 the Pareto set of the

NOR-gate with respect to the three objectives mentioned above is plotted

both in parameter and objective space. Also in this figure the values pro-

posed by the standard cell library are given both in parameter and objective

space (black crosses). As one can observe they lie outside the Pareto front.

Thus, the performance of this gate (and also several other gates as reported

in [7, 96]) can be significantly improved by the multiobjective optimization

approach.

Figure 4.27: Results of the multiobjective optimization of the NOR-gate: the Pareto set

(on the left) and the Pareto front (on the right) and the reference values from the standard

cell library (black crosses) [96]

A study of the robustness of the Pareto optimal solutions with respect

to changes in the external parameters temperature and supply voltage can

help to support the decision which point to choose from the Pareto set for

transistor fabrication. The numerical path following method for computing

paths of mimimal length in preimage space described in Section 4.4.2 has

been applied to this problem. In order to make the computation possible the

three objective functions have been approximated by smoothing splines (cf.

[96] for more details). In Figures 4.28 and 4.29 the results are visualized.

Here, dark blue regions refer to Pareto points with small path lengths. The

technical interpretation of the results is actually still an object of research.

5HSPICE is a commercial software tool for circuit simulation developed by Synopsys

4.5 Dents in Parameter-dependent Pareto Fronts 117

Figure 4.28: Visualization of the degree of robustness with respect to temperature

changes from 10◦C to 75◦C [96]

Figure 4.29: Visualization of the degree of robustness with respect to changes in the

supply voltage within the inverval from 0.6 V to 1.8 V [96]

4.5 Origin of Dents in Parameter-dependent Pareto Fronts

In Section 3.3 dents in Pareto fronts have been defined motivated by the fact

that these points cannot be computed by the weighted sums method. Also,

dent border points have been defined. When considering parametric mul-

tiobjective optimization problems, naturally the question arises, how dents

118 Parametric Multiobjective Optimization

and especially dent border points evolve. The Kuhn-Tucker equations (4.2)

provide a necessary condition for Pareto optimality. Within this section this

parametric system of equations will be analyzed in order to obtain results

about the local behavior of the parameter-dependent Pareto fronts.

Solutions of parametric systems of equations have already been widely

studied in bifurcation theory. The first paragraph of this section deals with

the study of properties of dent border points. After summarizing some basics

from bifurcation theory it will be proven that under certain assumptions dent

border preimages are turning points of the Kuhn-Tucker equations. In the

second part of this section, several new numerical examples for parametric

multiobjective optimization problems in which dents occur are given.

Within this section it is assumed that the objective functions are at least

twice continuously differentiable. Only points x∈Pλare considered for

which the corresponding weight vector αis an element of (0,1)k. Define

Hα

KT :Rn×R→Rnby

Hα

KT(x, λ) =

i=1

αi∇xfi(x, λ).

4.5.1 Properties of Dent Border Points

First, it will be shown that dent border preimages can be characterized as

certain turning points of the Kuhn-Tucker equations. It has been shown

in Section 3.3 that in a dent border point a zero eigenvalue of the Hessian

of gαoccurs, where gα(x, λ) = Pk

i=1 αifi(x, λ). The Hessian of gαequals

∂

∂x Hα

KT, as Hα

KT(x, λ) = ∇xgα(x, λ). Thus, the implicit function theorem is

not applicable to the Kuhn-Tucker equations (with respect to x) in a dent

border point. The study of the behavior of solutions in such cases is the main

topic of bifurcation theory. Whenever the Jacobian with respect to xof a

parametric system of equations is singular, the structure of the solution set

may change. One possibility is that the system of equations has no solution

before the singularity occurs, and two solutions afterwards (here, ”before”

and ”afterwards” have to be understood in terms of the values of λ). In this

case, the solution curve ”turns” at the point (x?, λ?), where the Jacobian

with respect to xis singular. More formally, such a turning point – which

sometimes is also called saddle-node bifurcation or fold in the literature – is

defined as follows:

Definition 4.20 (Turning point (see [71])) Consider the solutions of a non-

linear system of equations H(x, λ)=0, where H:RN×R→RN. Assume

that (x?, λ?)is such a solution which satisfies

4.5 Dents in Parameter-dependent Pareto Fronts 119

(i) there exists φ?∈RN\{0}with ker ∂

∂x H(x?, λ?)= span{φ?},

(ii) ∂

∂λ H(x?, λ?)/∈im ∂

∂x H(x?, λ?).

Then, (x?, λ?)is called a turning point.

Let ψ?be a left eigenvector of the zero eigenvalue of ∂

∂x H(x?, λ?), i. e.

ψ?∂

∂xH(x?, λ?) = 0.

If in addition to (i) and (ii) ψ?∂2

∂x2H(x?, λ?)φ?φ?6= 0, then the point

(x?, λ?)is called a simple turning point.

In Figure 4.30 an example of an equation whose solution curve includes

a turning point is sketched. As one can observe, the solution curve turns in

the point (0,0).

Figure 4.30: For the equation H(x, λ) = x2−λ= 0, H:R×R→R, a turning point

occurs in the point (0,0)

Proposition 4.21 Let Pλ⊆Sλbe the Pareto set of a parametric multiob-

jective optimization problem min F:Rn×R→Rkwith

F(x, λ) = (f1(x, λ), . . . , fk(x, λ))T. Let x?∈Pλ?be a simple dent border

preimage. Let α?denote the weight vector corresponding to x?and assume

that the Jacobian Hα?

0(x, λ)has full rank.

Then, (x?, λ?)is a turning point of Hα?

KT(x, λ)with respect to λ.

120 Parametric Multiobjective Optimization

Proof: It has been shown in [53] (see also Section 3.3) that dent border

preimages x?are solutions of the Kuhn-Tucker equations Hα?

KT(x?, λ?)=0

in which ∂2

∂x2gα?(x?, λ?) is singular. Thus, there exists an eigenvector φ?of

∂2

∂x2gα?(x?, λ?) with

∂2

∂x2gα?(x?, λ?)φ?= 0.(4.46)

From the assumption that the dent border preimage is simple, i. e. exactly

one eigenvalue of ∂2

∂x2gα?(x?, λ?) equals zero (cf. Definition 3.11), it directly

follows that

dim ker ∂2

∂x2gα?(x?, λ?)= 1.(4.47)

As Hα

KT(x, λ) = ∇xgα(x, λ), and thus

∂

∂xHα

KT(x, λ) = ∂

∂x (∇xgα(x, λ)) = ∂2

∂x2gα(x, λ),

(4.46) is equivalent to

∂

∂xHα?

KT(x?, λ?)ϕ?= 0

and (4.47) is the same as

dim ker ∂

∂xHα?

KT(x?, λ?)= 1.

Thus, property (i) of Definition 4.20 is proven for H(x, λ) = Hα?

KT(x, λ).

Property (ii) of Definition 4.20 directly follows from the assumption that

the Jacobian Hα?

0(x, λ) has full rank, i. e. rank n: if the vector ∂

∂λ Hα?

KT(x?, λ?)

were in the image of the n×n-matrix ∂

∂x Hα?

KT(x?, λ?), then the rank of the

Jacobian Hα?

0(x, λ) were n−1, in contradiction to the assumption. Thus,

it has to be true that ∂

∂λ Hα?

KT(x?, λ?)/∈im ∂

∂x Hα?

KT(x?, λ?).

To sum up, both properties given in Definition 4.20 are satisfied, and thus

(x?, λ?) is a turning point of Hα?

KT(x, λ) with respect to λ.

Remark 4.22 Using the notation of the proof of Proposition 4.21 one ob-

serves that the matrix ∂

∂x Hα?

KT is symmetric, as it is the Hessian of the

weighted sums function gα. Thus, ψ?= (φ?)Tis a left eigenvector of

∂

∂x Hα?

KT(x?, λ?). It follows that, if additionally to (i) and (ii) of Definition 4.20

(φ?)T∂2

∂x2Hα?

KT(x?, λ?)φ?φ?6= 0,

4.5 Dents in Parameter-dependent Pareto Fronts 121

then (x?, λ?) is a simple turning point of Hα?

KT(x, λ) with respect to λ.

To sum up, a dent border preimage can be obtained by solving the system

of equations

Hα?

KT(x, λ) = 0

∂

∂xHα?

KT(x, λ)·φ= 0 (4.48)

lTφ−1 = 0

with an arbitrary but fixed vector l∈Rnwhich satisfies lTφ?6= 0 and has

non-zero entries, and x, φ ∈Rn,λ∈R. In the literature, this system of

equations is also called the extended system of Hα?

KT(x, λ) (cf. [71]).

Remark 4.23 A family of dent border preimages can be obtained by solving

∇xgα(x, λ) = 0

i=1

αi−1 = 0

∂2

∂x2gα(x, λ)·φ= 0 (4.49)

lTφ−1 = 0

with an arbitrary fixed vector l∈Rnwhich satisfies lTφ?6= 0 and has non-

zero entries, x, φ ∈Rn,λ∈Rand α∈Rkwith αi>0∀i= 1, . . . , k.

4.5.2 Examples for Parametric Multiobjective Optimization Problems with

Dents

In the following, several new examples for parametric multiobjective opti-

mization problems are presented. They all have in common that the cor-

responding Pareto fronts contain dents for specific values of the external

parameter λ. Moreover, under the variation of λ, dents originate or vanish

(cf. Examples 4.24 and 4.26), or dents double or merge (cf. Example 4.25).

Example 4.24 Consider the two objectives

f1(x1, x2, λ) = 1

2(p1+(x1+x2)2+p1+(x1−x2)2+x1−x2) + λ·e−(x1−x2)2

f2(x1, x2, λ) = 1

2(p1+(x1+x2)2+p1+(x1−x2)2−x1+x2) + λ·e−(x1−x2)2.

122 Parametric Multiobjective Optimization

Figure 4.31: Visualization of some Pareto sets and the solution curve of Hα?

KT(x, λ)=0

(black) for the dent border preimage x?(red) for Example 4.24

In Figure 4.31 the Pareto sets of these two objectives for (x1, x2)∈

[−1.3,1.3]2are plotted for different values of the external parameter λ: for

λ= 0 (green), λ= 0.2 (gray), λ= 0.4 (light blue), λ= 0.6 (cyan), and for

λ= 0.8 (magenta).

In the same figure, an example for a λ-dependent solution path of the

Kuhn-Tucker equations with a fixed weight vector α?≈(0.25,0.75) which

corresponds to the dent border preimage (x?

1, x?

2)≈(−0.28,0.28) of the dent

border point (y?

1, y?

2)≈(1.23,1.79), located on the Pareto front for λ?= 0.6,

is visualized for λ∈[0,1] (black paths). The paths have been computed with

the help of the software package AUTO2000 [23]. As one can observe, y?is

indeed a simple turning point of Hα?

KT(x, λ) with respect to λ. Figure 4.32

shows the same results in objective space.

In Figure 4.33 the entire curve of dent border points in objective space

is plotted. To compute this λ-dependent solution curve (red), again the

software package AUTO2000 has been used. One can observe that the point

(y?

1, y?

2, λ?) = (1.25,1.25,0.25) (with the corresponding weight vector α?=

(0.5,0.5)), marked by a black dot, is specific: in this point a dent originates,

i. e. for λ<λ?the Pareto front contains no dent whereas for λ>λ?a dent

is contained in the Pareto front.

In Figure 4.34 the solutions of Hα?

KT(x, λ) = 0 with α?= (0.5,0.5), i. e.

the λ-dependent path containing the specific point in which a non-dent point

changes into a dent point, are visualized for λ∈[0,1]. One can observe that

4.5 Dents in Parameter-dependent Pareto Fronts 123

Figure 4.32: Visualization of some Pareto fronts and the image of the solution curve of

Hα?

KT(x, λ) = 0 (black) for a dent border point y?(red) for Example 4.24

Figure 4.33: Some Pareto fronts, the curve of dent border points (red) and the point in

which the dent originates (black dot) for Example 4.24

a pitchfork bifurcation6occurs in this point. Figure 4.35 shows the same

results in objective space.

6The definition and statements about properties of pitchfork bifurcations can be found

in [42] and [105], for example.

124 Parametric Multiobjective Optimization

Figure 4.34: Visualization of some Pareto sets and the λ-dependent solution curve of

Hα?

KT(x, λ) = 0 with α?= (0.5,0.5) (black) for Example 4.24

Figure 4.35: Visualization of some Pareto fronts and the image of the solution curve of

Hα?

KT(x, λ) = 0 with α?= (0.5,0.5) (black) for Example 4.24

4.5 Dents in Parameter-dependent Pareto Fronts 125

Example 4.25 Consider the two objectives

f1(x1, x2, λ) = q1 + x2

1+q1 + x2

2+e−(x2−λ)2+e−(x2+λ)2−x2

f2(x1, x2, λ) = q1 + x2

1+q1 + x2

2+e−(x2−λ)2+e−(x2+λ)2+x2.

In Figure 4.36 the Pareto fronts which result from the minimization of

these two objectives are plotted for different values of λ. As one can observe

the Pareto front contains one dent for λ= 0.4, for example. Under the

variation of λit changes into two dents (cp. for instance λ= 0.8). In

between, there is a specific point in which the dent splits up into two dents,

which is given by (x1, x2, λ)≈(0,0,0.5716) with the corresponding weight

vector α?= (0.5,0.5). In Figure 4.37 the solutions of the Kuhn-Tucker

equations for the fixed weight vector α?= (0.5,0.5) are sketched. One can

observe that in the point where the dent splits up into two dents a pitchfork

bifurcation occurs.

Figure 4.36: Pareto fronts for the multiobjective optimization problem given in Example

4.25 for different values of λ

126 Parametric Multiobjective Optimization

Figure 4.37: Pareto fronts and solutions of the Kuhn-Tucker equations for α?= (0.5,0.5)

in (f1, f2, λ)-space for Example 4.25

Example 4.26 Consider the three objectives

f1(x1, x2, x3, λ) = q1 + x2

1+q1 + x2

2+q1 + x2

3+λ·e−(x2

2+x2

3)+√2x2

f2(x1, x2, x3, λ) = q1 + x2

1+q1 + x2

2+q1 + x2

3+λ·e−(x2

2+x2

3)−√2

2x2+r3

2x3

f3(x1, x2, x3, λ) = q1 + x2

1+q1 + x2

2+q1 + x2

3+λ·e−(x2

2+x2

3)−√2

2x2−r3

2x3.

Figure 4.38 shows the Pareto fronts which result when minimizing these

three objectives for x∈[−2,2]3for different values of λ. One can observe

that under the variation of λa dent originates.

Remark 4.27 It has been observed in Examples 4.24 and 4.25 that pitch-

fork bifurcations occur in those points where – under the variation of λ– a

dent originates in the Pareto front PFλ, or a dent splits up into two dents,

respectively. Pitchfork bifurcations typically occur if the system of equations

H(x, λ) = 0, in our case Hα?

KT(x, λ) = 0, includes a symmetry of the form

H(Sx, λ) = SH(x, λ),(Z2)

where Sis a suitable symmetry matrix with S6=

and S2=

(cf. [105]).

In the examples mentioned above, indeed symmetries occur. The Kuhn-

Tucker equations of the objective functions given in Example 4.24 have a

4.5 Dents in Parameter-dependent Pareto Fronts 127

Figure 4.38: Pareto fronts for the multiobjective optimization problem given in Example

4.26 for different values of the parameter λ

Z2-symmetry for α?= (0.5,0.5). In this case, possible symmetry matrices

are given as

S1=0 1

1 0and S2=−1 0

0−1.

The Kuhn-Tucker equations of the objective functions given in Example

4.25 satisfy the symmetry condition (Z2) with

S1=1 0

0−1if α?= (0.5,0.5),and

128 Parametric Multiobjective Optimization

S2=−1 0

0 1independent of the weight vector α.

The Kuhn-Tucker equations for the objective functions given in Example

4.26 also satisfy the symmetry condition (Z2) with

S=

−1 0 0

0 1 0

0 0 1



for arbitrary weight vectors α?.

Chapter 5

Conclusion and Outlook

In this thesis, four main areas have been addressed:

1. Robustness concepts for parametric multiobjective optimiza-

tion problems

The main issue of this thesis was the study of parametric optimiza-

tion problems. Two new robustness concepts have been developed that

allow to find out how Pareto optimal points evolve under the varia-

tion of an external, real parameter. In contrast to hitherto existing

approaches, it is requested that the solutions should stay Pareto op-

timal for the original objective functions w. r. t. the perturbed para-

meter values. Especially for technical systems in which the parameter

configuration can be adjusted during operation time and the external

parameter can be measured, the new robustness concepts offer big ad-

vantages. For instance, assume that there exists a point on a Pareto

front which stays constant under variations of the external parameter.

This robust Pareto point can be computed by the robustness concepts

proposed in this thesis. During operation time it would be possible to

switch parameter-dependently between solutions of the computed path

such that the values of the objective functions stay constant.

In the first concept presented in this thesis, robustness is defined by

use of the classical calculus of variations. A variational integral is mi-

nimized which computes the length of the solution curve under the

constraint that the curve lives on the parameter-dependent solution

set of the Kuhn-Tucker equations. To allow numerical computations, a

discrete version of the Euler-Lagrange equations, which give a necessary

condition for optimality of variational integrals, is derived. By this

approach a nonlinear system of equations is obtained whose solution

gives a discrete approximation of the λ-robust solution curve.

The second concept is of local nature. Here, the length of a solution

path is not required to be minimal over the entire interval the external

parameter is assumed to live in. Instead, the path consists of points

129

130 Conclusion and Outlook

that locally change as little as possible in x-space under the variation

of the external parameter λ. Alternatively, solution paths that change

as little as possible in objective space can be described by a similar ap-

proach. To compute these paths, numerical path following methods are

used. They allow to approximate solution curves of nonlinear systems

of equations that depend on one external parameter. The Kuhn-Tucker

equations do not only depend on the optimization parameters and the

external parameter but also on the weight vector. The main challenge in

applying numerical path following methods to the Kuhn-Tucker equa-

tions lies in the treatment of this weight vector. It characterizes the

direction into which a solution path moves under the variation of the

external parameter. In this thesis, additional equations that define

suitable directions have been derived. In order to attack this prob-

lem, firstly two fixed Pareto sets Pλ0and Pλ1have been considered. A

constrained nonlinear optimization problem has been formulated whose

solution is a point on Pλ1which has minimal Euclidean distance to a

fixed Pareto point on Pλ0. Analogously, a constrained nonlinear opti-

mization problem has been formulated which minimizes the distance

between the Pareto fronts. In order to obtain numerical results, again

a necessary condition is used which also leads to a nonlinear system of

equations.

For the numerical approximation of an entire solution path a predictor-

corrector method is used. Here, the new equations that define the path

direction are used in combination with the Kuhn-Tucker equations in

each corrector step. It is required for the predictor-corrector method

that the Jacobian matrix of this combined system of equations is regu-

lar. In this work, the structure of this special Jacobian has been stud-

ied. It has been proven that the Jacobian is indeed regular if a standard

assumption for the underlying minimization problem is satisfied. The

new robustness concept has been illustrated for several numerical ex-

amples and a technical application arising in the design of integrated

circuits.

To make both new robustness concepts comparable, the variational

problem of Concept I has been reformulated for fixed starting points

on the initial Pareto set. A comparison of both concepts shows that

typically the length of solution paths w. r. t. Concept I is less or equal

to the length of paths obtained with Concept II. It has been shown that

if there exists a substationary point x?which does not change under

the variation of the external parameter λ,λ∈[λstart, λend]⊂R(i. e.

the solution path x(λ) is constant), this path is a solution with respect

131

to both the variational approach using energy minimization and the

numerical path following approach for the determination of λ-robust

substationary points. However, in general it highly depends on the ap-

plication under consideration which concept to choose for the study of

robustness of Pareto optimal solutions.

There are various engineering applications including dependencies on

external parameters in which robustness with respect to parameter

changes in a multiobjective sense is required. Within the Collaborative

Research Centre 614 “Self-optimizing concepts and structures in me-

chanical engineering” especially one application has turned out to be of

great interest, for which robust solutions will be studied in the future.

It concerns an X-by-wire vehicle called “Cham¨

aleon”.1In this vehicle

any of the four wheels can be steered individually. As the vehicle is not

very heavy, the mass of the driver has a noticeable influence on the be-

havior of the system. The distribution of the forces acting on the wheels

has to be optimized with respect to several objectives. In addition, it

is desired to obtain solutions that are robust with respect to changes

of the drivers’ masses. Another value that influences the system is the

friction coefficient. It is worth investigating robustness against this pa-

rameter, too. In both cases, a parametric multiobjective optimization

problem arises that depends on additional equality constraints which

stem from the fact that the sum of forces and momenta has to equal a

constant value. Inspired by this example, in the future the robustness

techniques developed in this thesis will also be extended to the case of

constrained parametric multiobjective optimization problems.

2. Time-dependent multiobjective optimization problems

Motivated by the multiobjective optimization of a linear drive, the

special case of time-dependent multiobjective optimization problems

has also been studied. In order to follow solutions over time again

numerical path following methods have been used. The optimization

procedure proposed in this thesis consists of several recurring steps.

First, the initial Pareto set is computed, one solution is chosen and the

corresponding weight vector is set fixed. The decision which solution

to choose is based on the current situation, i. e. for example on pa-

1This vehicle is developed at the Chair of Control Engineering and Mechatronics, Uni-

versity of Paderborn

132 Conclusion and Outlook

rameters which are not modeled as optimization parameters but have

an influence on the properties of the technical system. Secondly, a

solution path over time consisting of substationary points is computed

by solving the Kuhn-Tucker equations for this fixed weight vector with

a classical predictor-corrector method. Depending on the situation,

during operation time it is decided if the computation of a new, entire

Pareto set is necessary, and the steps are repeated.

This new approach developed within this thesis allows to use a multi-

objective optimization approach for the generation of solution trajec-

tories during operation time (for appropriate applications). It has been

applied to the operating point assignment of a linear drive and was im-

plemented and tested at the test plant. For future considerations it is

interesting to study the influence of additional external parameters like

a changing air gap on the time-dependent solution trajectories. It is

worth investigating whether the robustness concepts mentioned above

can be extended to the treatment of solution trajectories.

3. Dents in Pareto fronts

In this thesis also the occurrence of dents in Pareto fronts has been stu-

died. A formal definition of a dent has been given. Points at the border

of a (complete) dent have a significant property. In these points a zero

eigenvalue of the Hessian of the weighted sum of the objectives occurs.

Thus, dent border points are solutions of a certain system of equations.

Given a sufficiently smooth multiobjective optimization problem it is

possible to find out if dent border points, and thus also possibly dents,

occur in the Pareto front by solving this system of equations. Con-

sequently, information about the geometry of the Pareto front can be

obtained without computing the entire Pareto set. This information

can for example serve as a criterion for the choice of the algorithm one

wants to use for solving the multiobjective optimization problem.

Based on theoretical results from bifurcation theory, parameter-depen-

dencies in multiobjective optimization problems have been studied in

this thesis. It has been proven that dent border points are turning

points of the Kuhn-Tucker equations with a fixed weight vector cor-

responding to the dent border point. Several examples for parametric

multiobjective optimization problems have been constructed in which

dents occur. In the future, the question will be addressed what hap-

pens if a dent originates or vanishes under the variation of the external

133

parameter. The examples given at the end of Section 4.5 lead to the

conjecture that in this case pitchfork bifurcations of the Kuhn-Tucker

equations occur. However, the theoretical analysis of this statement

will be addressed in future work.

4. Applications from mechatronics including multiobjective op-

timization problems

In the third chapter of this thesis, in addition to the introduction into

multiobjective optimization also several engineering applications are

presented which have been studied in cooperation with the respective

chairs. These applications are related to the RailCab system which

serves as a demonstrator for the self-optimizing concepts developed

within the CRC 614. Besides the basic study of a model for the oper-

ating point assignment of the linear drive which was the motivation for

developing the concepts for time-dependent multiobjective optimiza-

tion described above, two more applications have been considered.

The first one concerns a multiobjective optimization of the hybrid en-

ergy storage. From the mathematical point of view, the challenge in

this application was to compute an operation strategy that distributes

the power flows to the respective storage devices in an optimal way du-

ring a drive of the vehicle. In the approach presented in this work the

time interval under consideration has been discretized, and the battery

currents at the corresponding points were optimized with respect to

two objectives. Alternatively, it is possible to attack the same problem

with optimal control algorithms like DMOC2. The advantage would be

that a Pareto optimal profile for the battery current can be computed

also over longer time intervals with a fine discretization. The disadvan-

tage is that only single Pareto optimal trajectories can be computed by

optimizing a weighted sum of the objectives. In the future, the combi-

nation of DMOC with concepts for multiobjective optimization will be

investigated.

The second application dealt with the generation of Pareto optimal

reference trajectories for the guidance of the RailCab, i. e. an optimal

control problem occurred. The mathematical model of the guidance

module considered in this work was differentially flat, which means that

the inputs and states of the system can be represented as a function

of the outputs and a finite number of their derivatives w. r. t. time.

2Discrete Mechanics and Optimal Control, see [58]

134 Conclusion and Outlook

It has been shown in this work how the multiobjective optimal control

problem can be transformed into a classical multiobjective optimization

problem which can be solved with existing algorithms. Furthermore, it

has been described how self-optimization of the guidance module can

be performed during operation time.

So far, several subsystems of the RailCab system have been studied

independently from each other. Within the total system these subsys-

tems partly depend on the same parameters. For example, the energy

supply provided by the hybrid energy storage system is important for

the operating point assignment of the linear drive (how much energy

has to be transferred into the hybrid energy storage system to enable

the system to drive?) and the guidance module (how much energy may

the hydraulic actuators use?). Thus, at present a model that includes

the connections between the subsystems within the RailCab is investi-

gated within the CRC 614. Based on this model, it will be of interest to

integrate the concepts for the treatment of multiobjective optimization

problems with parameter-dependencies into a hierarchical framework.

To sum up, this thesis mainly contributes to the field of parametric mul-

tiobjective optimization by defining new robustness concepts, by studying

bifurcation phenomena in parametric Pareto fronts, and by providing an

algorithm that allows the computation of time-dependent Pareto optimal so-

lutions possibly even during operation time. Moreover, several engineering

applications in which multiobjective optimization problems arise have been

presented.

Bibliography

[1] P. Adelt, J. Donoth, J. Gausemeier, J. Geisler, S. Henkler,

S. Kahl, B. Kl¨

opper, A. Krupp, E. M¨

unch, S. Oberth¨

ur,

C. Paiz, M. Porrmann, R. Radkowski, C. Romaus, A. Schmidt,

B. Schulz, H. V¨

ocking, U. Witkowski, K. Witting, and O. Zna-

menshchykov,Selbstoptimierende Systeme des Maschinenbaus - Definitio-

nen, Anwendungen, Konzepte, HNI-Schriftenreihe 234, Bonifatius GmbH,

2009. [2, 30, 31, 48]

[2] E. L. Allgower and K. Georg,Numerical Continuation Methods,

Springer, 1990. [5, 25, 28, 30]

[3] Arakawa, Billaut, Coello Coello, Ehrgott, Gandibleux,

G¨

opfert, Jones, Kuk, Miettinen, Nakayama, Romero, Sakawa,

Steuer, T’Kindt, Tamiz, Tanino, and Yun,Multiple Criteria Opti-

mization. State of the Art Annotated Bibliographic Surveys, International

Series in Operations Research and Management Science 52, Kluwer Aca-

demic Publishers, Boston, 2002. [34, 35, 38]

[4] R. J. Baker,CMOS: Circuit Design, Layout, and Simulation, Wiley-

Interscience, second ed., 2008. [114, 115]

[5] B. Bank, J. Guddat, D. Klatte, B. Kummer, and K. Tammer,Non-

Linear Parametric Optimization, Birkh¨

auser, 1983. [25]

[6] G. Bigi and M. Castellani,Uniqueness of KKT multipliers in multiobjec-

tive optimization, Applied Mathematics Letters 17, no. 11 (2004), pp. 1285–

1290. [35]

[7] M. Blesken, U. R¨

uckert, D. Steenken, K. Witting, and M. Dell-

nitz,Multiobjective Optimization for Transistor Sizing of CMOS Logic Stan-

dard Cells Using Set-Oriented Numerical Techniques, in Proceedings of the

27th Norchip Conference, 2009. [114, 116]

[8] J. B¨

ocker, B. Schulz, T. Knoke, and N. Fr¨

ohleke,Self-optimization

as a framework for advanced control systems, in Int. Electronics Conference

(IECON), Paris, Frankreich, 2006. [73]

[9] O. Bolza,Vorlesungen ¨

uber Variationsrechnung, Chelsea Publishing Com-

pany, New York, USA, 1909. [7, 19]

135

136 Bibliography

[10] J. Branke,Robustness and reliability in EMO. Talk at Dagstuhl Seminar

09041, Dagstuhl, Germany, 2009. [6, 76]

[11] J. Branke,Creating robust solutions by means of evolutionary algorithms,

in Parallel Problem Solving from Nature, LNCS 1498, Springer-Verlag, 1998,

pp. 119–128. [77]

[12] C. A. Coello Coello, G. Lamont, and D. V. Veldhuizen,Evolution-

ary Algorithms for Solving Multi-Objective Optimization Problems, Springer,

Berlin, Germany, second ed., 2007. [1, 38]

[13] I. Das and J. Dennis,A closer look at drawbacks of minimizing weighted

sums of objectives for Pareto set generation in multicriteria optimization

problems, Structural Optimization 14, no. 1 (1997), pp. 63–69. [8, 39]

[14] I. Das and J. E. Dennis,Normal boundary intersection: a new method for

generating the Pareto surface in nonlinear multicriteria optimization prob-

lems, SIAM J. Optim. 8(1998), pp. 631–657. [1, 38]

[15] K. Deb,Multi-Objective Optimization using Evolutionary Algorithms,

Wiley-Interscience Series in Systems and Optimization, John Wiley & Sons,

Chichester, England, 2001. [1, 38]

[16] K. Deb, S. Greco, K. Miettinen, and E. Zitzler,09041 summary –

hybrid and robust approaches to multiobjective optimization, Dagstuhl Sem-

inar Proceedings, Dagstuhl, Germany, 2009, Schloss Dagstuhl - Leibniz-

Zentrum fuer Informatik, Germany. [6, 76]

[17] K. Deb and H. Gupta,Introducing robustness in multi-objective optimiza-

tion, Evolutionary Computation 4, no. 14 (2006), pp. 463–494. [77, 78, 79]

[18] A. Dell’Aere,Multi-objective optimization in self-optimizing systems, in

Proceedings of the IEEE 32nd Annual Conference on Industrial Electronics

(IECON), 2006, pp. 4755 – 4760. [42]

[19] A. Dell’Aere, M. Hirsch, B. Kl¨

opper, M. Koester, A. Krupp,

M. Kr¨

uger, T. M¨

uller, S. Oberth¨

ur, S. Pook, C. Priester-

jahn, C. Romaus, A. Schmidt, C. Sondermann-W¨

olke, M. Tichy,

H. V¨

ocking, and D. Zimmer,Verl¨

asslichkeit selbstoptimierender Systeme

- Potenziale nutzen und Risiken vermeiden, HNI-Schriftenreihe 235, Boni-

fatius GmbH, 2009. [31]

[20] M. Dellnitz, O. Sch¨

utze, and T. Hestermeyer,Covering Pareto sets

by multilevel subdivision techniques, Journal of Optimization Theory and

Application 124 (1) (2005), pp. 113–136. [34, 40, 41]

Bibliography 137

[21] M. Dellnitz and K. Witting,Computation of robust Pareto points, Int.

Journal of Computing Science and Mathematics (IJCSM) 2 (3) (2009),

pp. 243–266. [81, 92, 104]

[22] P. Deuflhard and A. Hohmann,Numerical Analysis in Modern Scien-

tific Computing, Springer, New York, NY, USA, 2003. [5, 28]

[23] E. J. Doedel, A. R. Champneys, R. C. Paffenroth, T. F. Fair-

grieve, Y. A. Kuznetsov, B. E. Oldeman, B. Sandstede, and X.-

J. Wang,AUTO2000: Continuation and bifurcation software for ordinary

differential equations (with homcont), tech. report, California Institute of

Technology, Pasadena, California USA, 2000. [30, 68, 122]

[24] M. Ehrgott,Multicriteria Optimization, Lecture Notes in Economics and

Mathematical Systems 491, Springer-Verlag, Berlin, 2000. [1]

[25] M. Ehrgott,Multicriteria Optimization, Springer-Verlag, Berlin, sec-

ond ed., 2005. [35]

[26] R. Enkhbat, J. Guddat, and A. Chinchuluun,Parametric multiob-

jective optimization, Springer Optimization and Its Applications 17 (2008),

pp. 529–538. [66]

[27] A. Fiacco,Sensitivity, Stability and Parametric Analysis, Elsevier Science

Ltd, 1983. [26, 27]

[28] J. E. Fieldsend and R. M. Everson,Multi-objective optimisation in

the presence of uncertainty, in Proceedings of the 2005 IEEE Congress on

Evolutionary Computation (CEC05), 2005, pp. 476–483. [80]

[29] J. Figueira, M. Geiger, S. Greco, J. Jahn, K. Klamroth,

M. Inuiguchi, V. Mousseau, S. Sayin, R. Slowinski, M. M. Wiecek,

and K. Witting,09041 working group on mcdm for robust multiobjec-

tive optimization (1st round), in Hybrid and Robust Approaches to Mul-

tiobjective Optimization, K. Deb, S. Greco, K. Miettinen, and E. Zitzler,

eds., no. 09041 in Dagstuhl Seminar Proceedings, Dagstuhl, Germany, 2009,

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. [6, 76]

[30] J. Figueira, S. Greco, and M. Ehrgott (eds.),Multiple Criteria De-

cision Analysis: State of the Art Surveys, International Series in Operations

Research & Management Science 78, Springer Science + Business Media B.

V., New York, 2005. [80]

[31] M. Fliess, J. L´

evine, P. Martin, and P. Rouchon,Flatness and de-

fect of non-linear systems: Introductory theory and examples, International

Journal of Control 61, no. 6 (1995), pp. 1327–1361. [3, 46, 52]

138 Bibliography

[32] C. M. Fonseca, P. J. Fleming, E. Zitzler, K. Deb, and L. Thiele,

Evolutionary Multi-Criterion Optimization. Second International Conference

EMO 2003, Springer, 2003. [1]

[33] U. Frank, J. Gausemeier, H. Giese, F. Klein, O. Oberschelp,

A. Schmidt, B. Schulz, H. V¨

ocking, and K. Witting,Selbstopti-

mierende Systeme des Maschinenbaus - Definitionen und Konzepte, HNI-

Schriftenreihe 155, Bonifatius GmbH, 2004. [31, 72]

[34] P. Funk,Variationsrechnung und ihre Anwendung in Physik und Technik,

Springer-Verlag, second ed., 1970. [19]

[35] A. Gaspar-Cunha and J. A. Covas,Robustness in multi-objective op-

timization using evolutionary algorithms, Journal of Computational Opti-

mization and Applications 39, no. 1 (2008), pp. 75–96. [79]

[36] S. Gass and T. Saaty,The computational algorithm for the parametric

objective function, Naval Research Logistics Quarterly 2 (1955), pp. 39–45.

[38, 39]

[37] C. Geiger and C. Kanzow,Numerische Verfahren zur L¨

osung unre-

stringierter Optimierungsaufgaben, Springer, Berlin, 1999. [14, 15]

[38] J. Geisler, K. Witting, A. Tr¨

achtler, and M. Dellnitz,Multiob-

jective optimization of control trajectories for the guidance of a rail-bound

vehicle, in 17th IFAC World Congress, July 6-11, 2008, Seoul, Korea, 2008.

[51, 52, 54]

[39] J. Geisler, K. Witting, A. Tr¨

achtler, and M. Dellnitz,Self-

optimization of the guidance module of a rail-bound vehicle, in 7th Interna-

tional Heinz Nixdorf Symposium ‘Self-optimizing Mechatronic Systems: De-

sign the Future’, February 20-21, 2008, Paderborn, J. Gausemeier, F. Ram-

mig, and W. Sch¨

afer, eds., Paderborn, 2008, HNI-Verlagsschriftenreihe,

pp. 85–100. [51, 53, 54]

[40] A. M. Geoffrion,Proper efficiency and the theory of vector maximization,

Journal of Mathematical Analysis and Applications 22 (3) (1968), pp. 618–

630. [36]

[41] M. Giaquinta and S. Hildebrandt,Calculus of Variations I, Springer-

Verlag, 1996. [19, 21, 23, 86]

[42] M. Golubitsky and D. G. Schaeffer,Singularities and groups in bi-

furcation theory. Vol. I, Applied Mathematical Sciences 51, Springer-Verlag,

New York, 1985. [123]

[43] A. G¨

opfert and R. Nehse,Vektoroptimierung, Teubner Verlagsge-

sellschaft Leipzig, 1990. [36, 37]

Bibliography 139

[44] J. Guddat, F. Guerra Vasquez, and H. T. Jongen,Parametric Opti-

mization: Singularities, Pathfollowing and Jumps, John Wiley & Sons Ltd,

1990. [25, 28]

[45] J. Guddat, F. Guerra Vasquez, K. Tammer, and K. Wendler,Mul-

tiobjective and Stochastic Optimization Based on Parametric Optimization,

Akademie-Verlag, Berlin, 1985. [35]

[46] J. Guddat, F. G. Vasquez, K. Tammer, and K. Wendler,Multi-

objective and Stochastic Optimization Based on Parametric Optimization,

Mathematical Research 26, Akademie-Verlag Berlin, 1985. [25]

[47] S. Gunawan and S. Azarm,Multi-objective robust optimization using a

sensitivity region concept, Structural and Multidisciplinary Optimization 29,

no. 1 (2005), pp. 50–60. [79, 80]

[48] Y. Y. Haimes, L. S. Lasdon, and D. A. Wismer,On a bicriterion for-

mulation of the problems of integrated system identification and system op-

timization, IEEE Transactions on Systems, Man, and Cybernetics 1(1971),

pp. 296–297. [38]

[49] C. Henke, N. Fr¨

ohleke, and J. B¨

ocker,Advanced convoy control strat-

egy for autonomously driven railway vehicles, in Proceedings of the IEEE

Conf. on Intelligent Transportation Systems, Toronto, Kanada, September

2006. [56, 58]

[50] M. Henke,Antrieb mit doppeltgespeistem Linearmotor f¨

ur ein spurgef¨

uhrtes

Bahnfahrzeug, PhD thesis, University of Paderborn, Germany, 2003. [56]

[51] T. Hestermeyer, P. Schlautmann, and C. Ettingshausen,Active

suspension system for railway vehicles – system design and kinematics, in

2nd IFAC - Conference on Mechatronic Systems, Berkeley, California, USA,

2002. [47]

[52] H. Heuser,Analysis 2, Teubner Verlag, fourth ed., 1988. [11, 26]

[53] C. Hillermeier,Nonlinear Multiobjective Optimization: A Generalized

Homotopy Approach, Birkh¨

auser, 2001. [36, 38, 41, 42, 44, 66, 120]

[54] R. Horst and H. Tuy,Global Optimization: Deterministic Approaches,

Springer, 1996. [13]

[55] E. Hughes,Evolutionary multi-objective ranking with uncertainty and noise,

in EMO ’01: Proceedings of the First International Conference on Evolu-

tionary Multi-Criterion Optimization, London, UK, 2001, Springer-Verlag,

pp. 329–343. [80]

140 Bibliography

[56] M. Inuiguchi,Robust optimization under softness in a fuzzy linear program-

ming problem, International Journal of Approximate Reasoning 18, no. 1-2

(1998), pp. 21 – 34. [80]

[57] F. Jarre and J. Stoer,Optimierung, Springer, Berlin, 2004. [13]

[58] O. Junge, J. E. Marsden, and S. Ober-Bl¨

obaum,Discrete mechanics

and optimal control, Proc. IFAC Conf., Prague, June 2005. [133]

[59] B. Kim, E. Gel, J. Fowler, W. Carlyle, and J. Wallenius,Eval-

uation of nondominated solution sets for k-objective optimization problems:

An exact method and approximations, European Journal of Operational Re-

search 173 (2) (2006), pp. 565–582. [35]

[60] D. Klatte and B. Kummer,Nonsmooth Equations in Optimization: Reg-

ularity, Calculus, Methods and Applications (Nonconvex Optimization and

Its Applications), Kluwer Academic Publishers, 2002. [25]

[61] K. K¨

onigsberger,Analysis 2, Springer-Verlag, second ed., 1997. [11, 52]

[62] J. Knowles, D. Corne, and K. Deb,Multiobjective Problem Solving

from Nature: From Concepts to Applications (Natural Computing Series),

Springer, 2008. [38]

[63] H. Kuhn and A. Tucker,Nonlinear programming, Proc. 2nd Berkeley

Symp. Math. Statist. Probability, (J. Neumann, ed.) (1951), pp. 481–492.

[4, 36, 37]

[64] S. Leyendecker, J. E. Marsden, and M. Ortiz,Variational integrators

for constrained dynamical systems, J. Applied Mathematics and Mechanics

88, no. 9 (2008), pp. 677–708. [85]

[65] M. Li,Robust Optimization and Sensitivity Analysis with Multi-objective

Genetic Algorithms: Single- and Multi-Disziplinary Applications, PhD the-

sis, 2007. [79]

[66] R. Li, A. Pottharst, K. Witting, O. Znamenshchykov, J. B¨

ocker,

N. Fr¨

ohleke, R. Feldmann, and M. Dellnitz,Design and imple-

mentation of a hybrid energy supply system for railway vehicles, in Proc.

of APEC2005, IEEE Applied Power Electronics Conference 2005, Austin,

Texas, USA, 2005, pp. 474–480. [48]

[67] D. G. Luenberger,Linear and Nonlinear Programming, Addison Wesley

Publishing Company, second ed., 1984. [13, 16, 17]

[68] J. E. Marsden and M. West,Discrete mechanics and variational inte-

grators, Acta Numerica , no. 10 (2001), pp. 357–514. [7, 84, 85]

Bibliography 141

[69] K. Miettinen,Nonlinear Multiobjective Optimization, Kluwer Academic

Publishers, 1999. [1, 35, 36, 37, 38, 42]

[70] M. Milam, K. Mushambi, and R. Murray,A new computational ap-

proach to real-time trajectory generation for constrained mechanical systems,

in Proceedings of the 39th IEEE Conference on Decision and Control, 2000,

pp. 845–551. [3, 46, 53]

[71] G. Moore and A. Spence,The calculation of turning points of nonlinear

equations, SIAM Journal of Numerical Analysis 17, no. 4 (1980), pp. 567–

576. [118, 121]

[72] R. Murray, M. Rathinam, and W. Sluis,Differential flatness of me-

chanical control systems: A catalog of prototype systems, in Proceedings of

the 1995 ASME International Congress and Exposition, San Francisco, 1995.

[3, 46, 52]

[73] ”‘Neue Bahntechnik Paderborn”’ – Project,http://www.railcab.de.

Web-Page. [2, 46]

[74] S. Nishikawa,Variational problems in geometry, American Mathematical

Society, 2002. [89]

[75] J. Ortega and W. Rheinboldt,Iterative Solution of Nonlinear Equations

in Several Variables, Academic Press, Inc., London, 1970. [5, 28]

[76] V. Pareto,Manual of Political Economy, The MacMillan Press, 1971 (orig-

inal edition in French in 1927). [33]

[77] L. A. Pars,An Introduction to the Calculus of Variations, Heinemann,

London, 1962. [20]

[78] N. Petit, M. Milam, and R. Murray,Inversion based constrained tra-

jectory optimization, in 5th IFAC Symposium on Nonlinear Control Systems,

2001. [53]

[79] E. R. Pinch,Optimal Control and the Calculus of Variations, Oxford Uni-

versity Press, 1993. [19, 20]

[80] A. Pottharst,Energieversorgung und Leittechnik einer Anlage mit Lin-

earmotor getriebenen Bahnfahrzeugen, PhD thesis, University of Paderborn,

Germany, 2006. [47]

[81] A. Pottharst, K. Baptist, O. Sch¨

utze, J. B¨

ocker, N. Fr¨

ohlecke,

and M. Dellnitz,Operating point assignment of a linear motor driven

vehicle using multiobjective optimization methods, in Proc. of the 11th Inter-

national Conference EPE-PEMC 2004, Riga, Latvia, 09/2004. [56, 58]

142 Bibliography

[82] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flan-

nery,Numerical Recipes in C: The Art of Scientific Computing, Cambridge

University Press, New York, NY, USA, 1992. [53]

[83] C. Romaus, J. B¨

ocker, K. Witting, A. Seifried, and O. Znamen-

shchykov,Optimal energy management for a hybrid energy storage system

combining batteries and double layer capacitors, in Proceedings of the IEEE

Energy Conversion Congress and Exposition (ECCE), 2009. [48, 49]

[84] R. Roy, Y. Azene, D. Farrugia, C. Onisa, and J. Mehnen,Evo-

lutionary multi-objective design optimisation with real life uncertainty and

constraints, CIRP Annals - Manufacturing Technology 58, no. 1 (2009),

pp. 169 – 172. [80]

[85] S. Sch¨

affler, R. Schultz, and K. Weinzierl,A stochastic method for

the solution of unconstrained vector optimization problems, J. Opt. Th. Appl.

114 (1) (2002), pp. 209–222. [1, 38]

[86] T. Schneider, B. Schulz, C. Henke, K. Witting, D. Steenken, and

J. B¨

ocker,Energy transfer via linear doubly-fed motor in different operating

modes, in Proceedings of the International Electric Machines and Drives

Conference, May 3-6, 2009, Miami, Florida, USA. [56, 60, 63, 70, 75]

[87] O. Sch¨

utze,Set Oriented Methods for Global Optimization, PhD thesis,

University of Paderborn, Germany, 2004. [40, 41]

[88] O. Sch¨

utze,A new data structure for the nondominance problem in multi-

objective optimization, in Evolutionary Multi-Criterion Optimization (EMO

03), C. M. Fonseca, P. J. Fleming, E. Zitzler, K. Deb, and L. Thiele, eds.,

Springer 2, 2003, pp. 509–518. [40, 41]

[89] O. Sch¨

utze, A. Dell’Aere, and M. Dellnitz,On continuation methods

for the numerical treatment of multi-objective optimization problems, in Prac-

tical Approaches to Multi-Objective Optimization, J. Branke, K. Deb, K. Mi-

ettinen, and Steuer, R. E. (eds.), eds., no. 04461 in Dagstuhl Seminar Pro-

ceedings, Dagstuhl, 2005, Internationales Begegnungs- und Forschungszen-

trum (IBFI), Schloss Dagstuhl, Germany. [41]

[90] O. Sch¨

utze, S. Mostaghim, M. Dellnitz, and J. Teich,Covering

Pareto sets by multilevel evolutionary subdivision techniques, in Evolution-

ary Multi-Criterion Optimization, C. M. Fonseca, P. J. Fleming, E. Zit-

zler, K. Deb, and L. Thiele, eds., Lecture Notes in Computer Science, 2003,

pp. 118–132. [40, 41]

[91] O. Sch¨

utze, M. Vasile, and C. A. Coello Coello,Approximate so-

lutions in space mission design, Lecture Notes in Computer Science 5199

(2008), pp. 805–814. [80]

Bibliography 143

[92] O. Sch¨

utze, K. Witting, S. Ober-Bl¨

obaum, and M. Dellnitz,Set

oriented methods for the numerical treatment of multiobjective optimization

problems. To appear in EVOLVE – A Bridge Between Probability, Set Ori-

ented Numerics, and Evolutionary Computation, Emilia Tantar et al., eds.,

Springer, 2011. [1, 38, 40]

[93] P. K. Shukla, J. Dutta, and K. Deb,On properly pareto op-

timal solutions, in Practical Approaches to Multi-Objective Optimiza-

tion, J. Branke, K. Deb, K. Miettinen, and R. E. Steuer, eds.,

no. 04461 in Dagstuhl Seminar Proceedings, Internationales Begegnungs-

und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany,

2005. http://drops.dagstuhl.de/opus/volltexte/2005/240. [36]

[94] R. Slowinski and J. Teghem (eds.),Stochastic versus Fuzzy approaches

to Multiobjective Mathematical Programming under uncertainty, Kluwer

Academic, Dordrecht, 1990. [80]

[95] P. Spellucci,Numerische Verfahren der nichtlinearen Optimierung,

Birkh¨

auser Verlag, 1993. [13]

[96] D. Steenken,Multiobjective optimization and sensitivity evaluation of IC

base components using set-oriented methods, 2009. Diploma thesis, Univer-

sity of Paderborn, Germany. [42, 114, 115, 116, 117]

[97] R. E. Steuer,Multiple Criteria Optimization: Theory, Computation, and

Application, John Wiley & Sons, Inc., 1986. [35]

[98] G. Strang,Introduction to linear algebra, Wellesley-Cambridge Press, 1993.

[99]

[99] A. S¨

ulflow, N. Drechsler, and R. Drechsler,Robust multi-objective

optimization in high dimensional spaces, in Evolutionary Multi-Criterion Op-

timization, Lecture Notes in Computer Science, 2006, pp. 715–726. [80]

[100] J. Teich,Pareto-front exploration with uncertain objectives, in EMO ’01:

Proceedings of the First International Conference on Evolutionary Multi-

Criterion Optimization, London, UK, 2001, Springer-Verlag, pp. 314–328.

[80]

[101] The MathWorks Company,http://www.mathworks.com/access/

helpdesk/help/toolbox/optim/ug/fsolve.html. Web-Page. [89, 92, 109]

[102] C. Tiahrt and A. Poore,A bifurcation analysis of the nonlinear paramet-

ric programming problem, Mathematical Programming 47 (1990), pp. 117–

141. [25]

144 Bibliography

[103] S. Tsutsui and A. Gosh,Genetic algorithms with a robust solution search-

ing scheme, IEEE Transactions on Evolutionary Computation 1, no. 3

(1997), pp. 201–219. [77]

[104] M. J. Van Nieuwstadt and R. M. Murray,Real-time trajectory gen-

eration for differentially flat systems, International Journal of Robust and

Nonlinear Control 8 (11) (1998), pp. 995–1020. [3, 46, 53, 56]

[105] B. Werner and A. Spence,The computation of symmetry-breaking bi-

furcation points, SIAM Journal on Numerical Analysis 21, no. 2 (1984),

pp. 388–399. [123, 126]

[106] D. Werner,Funktionalanalysis, Springer-Verlag, 2005. [37]

[107] K. Witting, S. Ober-Bl¨

obaum, and M. Dellnitz,A new definition for

robustness in parametric multiobjective optimization problems based on the

calculus of variations (2011). Submitted to the Journal of Global Optimiza-

tion, Special Issue on Multiobjective Optimization. [81]

[108] K. Witting, B. Schulz, M. Dellnitz, J. B¨

ocker, and N. Fr¨

ohleke,

A new approach for online multiobjective optimization of mechatronic sys-

tems, International Journal on Software Tools for Technology Transfer STTT

10 (3) (2008), pp. 223–231. [56, 63, 67, 70]

[109] Y. Xue, D. Li, W. Shan, and C. Wang,Multi-objective robust opti-

mization using probabilistic indices, 2007. Third International Conference

on Natural Computation (ICNC 2007). [79]

[110] B. Yang, M. Henke, and H. Grotstollen,Pitch analysis and control

design for the linear motor of a railway carriage, 2001. IEEE Industrial

Applications Society Annual Meeting (IAS), Chicago, USA, pp. 2360-2365.

[47]

[111] L. Zadeh,Optimality and non-scalar-valued performance criteria, IEEE

Transactions on Automatic Control 8(1963), pp. 59–60. [38, 39]

[112] E. Zitzler, M. Laumanns, and L. Thiele,SPEA2: Improving the

strength of pareto evolutionary algorithms for multiobjective optimization,

in Evolutionary Methods for Design, Optimisation and Control with Appli-

cation to Industrial Problems (EUROGEN 2001), 2002, pp. 95–100. [1]

Index

M-properly Pareto optimal, 60

λ-robust solution path, 82

active suspension module, 47

admissible, 35

affine, 37

application

guidance module, 51

hybrid energy storage, 48

integrated circuit design, 114

linear drive, 56, 70

RailCab, 46

Brachistochrone problem, 19

clearance, 52

CMOS, 114

complete dent, 43

constrained, 13

constraint, 13

continuation methods, 28

convex, 37

corrector, 29

CRC 614, 45

curve, 12

decision heuristic, 58, 68

decision making, 33, 58

dent, 42, 43

complete, 43

in parametric problems, 117

point, 43

preimage, 43

dent border, 44

preimage, 44

point, 44

dent border point

simple, 44

dent border preimage

simple, 44

differentiable, 11

curve, 12

differential, 11

differential flatness, 52

dominance, 34

ε-, 80

probabilistic, 80

dynamic energy consumption, 115

efficient, 35

energy, 89

energy storage system, 48

environmental parameters, 76

equality-constrained optimization, 16

Euler, 19

Euler-Lagrange equations, 21

discrete, 84

evolutionary algorithms, 38

example

constrained, nonlinear optimization,

dents, 44

dents in parametric MOPs, 121, 125

M-proper Pareto optimality, 36

nonlinear optimization, 13, 15

parametric MOP, 65

parametric optimization, 27

paths in parametric MOPs, 67

robust Pareto points, 89, 92, 104,

106, 110

variational calculus, 21

expectation measure, 79

extended system, 121

feasible set, 13

first variation, 20

first-order necessary condition

equality-constrained, 16

unconstrained, 14

flatness, 52

fold, 118

global minimizer, 13

global minimum, 13

gradient, 12

guidance module, 46, 51

HES, 48

145

146 Index

Hessian matrix, 12

homotopy methods, 25

hybrid energy storage system, 48

image set oriented recovering, 42

implicit function theorem, 26

implicitly defined, 26

indefinite, 15

indesfinite, 15

inverter, 114

isolated minimum, 13

isoperimetric problem, 19

Kuhn-Tucker necessary condition, 37

Lagrange, 19

Lagrangian function, 16

length, 89

linear drive, 47

local minimizer, 13

local minimum, 13

M-properly Pareto optimal, 36

mechanical engineering, 45

method

continuation, 28

numerical path following, 28

mimimizer

global, 13

local, 13

minimizer

strict global, 13

strict local, 13

minimum

global, 13

local, 13

MOP, 34

multiobjective

evolutionary algorithms, 38

Multiobjective Optimization

Parametric, 63

multiobjective optimization, 33

methods, 38

multiobjective optimization problem, 34

parametric, 64

Multiobjective Robust Solution of Type

II, 78

Multiobjective Robust Solution of Type

I, 77

multiplier rule

variational problems, 23

NAND-gate, 114

negative definite, 15

Neue Bahntechnik Paderborn, 46

NLO, 13

noise margin, 115

nondominated, 35

noninferior, 35

nonlinear, 13

nonlinear optimization, 13

NOR-gate, 114

numerical path following, 28

objective function, 13

ophelimity, 33

optimality condition

equality-constrained, 16

unconstrained, 14

optimality conditions, 14

optimization

parametric, 25

multiobjective, 33, 34

nonlinear, 13

parametric

unconstrained, 26

optimization problem, 13

equality-constrained, 16

nonlinear, 13

unconstrained, 13, 14

parametric

optimization

unconstrained, 26

programming, 25

Parametric Multiobjective Optimization,

parametric multiobjective optimization prob-

lem, 64

parametric optimization, 25

parametrized curve, 12

Pareto, 33

Pareto front, 34

Pareto optimal

M-properly, 36

weakly, 35

Pareto optimality, 34

Pareto point, 34

Pareto set, 34

partial derivative, 11

Index 147

path

λ-robust, 82

path following, 28

pitchfork bifurcation, 123, 125

positive definite, 15

predictor, 29

programming

parametric, 25

propagation delay, 115

proposition

comparison of robustness concepts,

112

dent border points are turning points,

119

minimal distance between Pareto sets,

regularity of Jacobian, 95

RailCab, 46

recovering

image set oriented, 42

recovering techniques, 39, 41

regular curve, 81

regular point, 16

Robust Pareto point w. r. t. Concept I, 82

Robust substationary point w. r. t. Con-

cept I, 82

saddle point, 15

saddle-node bifurcation, 118

second-order sufficiency condition

equality-constrained, 17

unconstrained, 15

sensitivity analysis, 26

sensitivity region, 79

set-oriented methods, 40

set-oriented techniques, 38

simple

turning point, 119

simple dent border point, 44

simple dent border preimage, 44

smoothing spline, 116

spline

B-, 53

cubic, 53

smoothing, 116

stationary point, 15

subdivision techniques, 38, 40

substationary point, 37, 65

system

extended, 121

targets, 42

taylor expansion, 101

theorem

first-order necessary condition for equality-

constrained optimization prob-

lems, 16

first-order necessary condition for un-

constrained optimization prob-

lems, 14

implicit function, 26

Kuhn-Tucker for MOP, 37

multiplier rule for variational prob-

lems, 23

second-order sufficient condition for

equality-constrained optimization

problems, 16

second-order sufficient condition for

unconstrained optimization prob-

lems, 15

sensitivity analysis for uPOP, 26

transversality conditions, 24

turning point, 119

simple, 119

unconstrained, 13

unconstrained optimization, 14

uNLO, 14

uPOP, 26

variance measure, 79

variation, 20

first, 20

vector minimum point, 35

weight vector

corresponding to a Pareto point, 37

weighted sums method, 39, 117

worst case sensitivity region, 79