Project topics and materials
Get Complete Project Material File(s) Now! »
Background on Nonlinear Multiobjective Optimization
NonLinear (Constrained) MultiObjective Optimization (NLMOO) is the problem of simultaneously minimizing several criteria [25, 85] and can be formally defined as :with x 2 Rn the decision variables, f : Rn ! Rm the objective functions, g : Rn ! Rp inequality constraints and h : Rn ! Rq equality constraints. The feasible region X is the set of decision vectors that satisfy all the constraints, i.e., X := fx 2 Rn : g(x) 0; h(x) = 0g. Its image Y = f(X) in the objective space is called the feasible objective region. This problem is nonlinear if at least one of the objective or constraint functions is nonlinear.
Solving Problem (3.1) implies finding the solutions yielding to an optimal trade-off of the objectives ; in other words, solutions for which there is no other solution strictly improving one of the objective.
Contracting, Inflating and Certifying parallelotopes
In Section 2.3.1.3 (p. 29), parallelelotopes domains are introduced as a way of rigorously computing
manifolds of solutions to underconstrained systems of equations. This preliminary section introduces algorithms that apply the techniques introduced in Chapter 2, and that will be used for the design of the certified continuation algorithm presented in Section 4.3. Two algorithms are required : one for contracting parallelotopes to the curve of solutions, one for certifying a parallelotope to enclose curve of solutions starting from an initial guess.
Algorithm 5 applies the interval Newton for parallelotopes inductively until some fixed point is reached or a maximum of iterations is reached (by default k = 15). It aims at reducing a parallelotope without loosing any solution to F(x) = 0. Formally, it satisfies 8x 2 bx ; F(x) = 0 =) x 2 Contract(F;bx); (4.1) which is a direct consequence of Theorem 2.3.6 (p. 27) for the parametric interval Newton operator.
It turns out to be also useful to inflate a box in such a way that the interval Newton operator strictly contracts it. This is even critical in the context of certified continuation where the certification has to be performed from a initial non-rigorous guess. In the context of certification of manifolds using parallelotopes, inflating a parallelotope consists in inflating its characteristic box u corresponding to the non-parametric dimensions. To this end, Algorithm 6 implements a two stage inflation process adapted from a box-inflation process proposed in [40, 56] : The main inflation is performed by the interval Newton operator itself at Line 6.4, applying it without intersecting the previous domain so as to allow shifting and inflating the box. When this inflation process succeeds (informally the initial parallelotope has to be small enough and close enough to a regular manifold), it often converges to a limit parallelotope from the inside, which does not allow observing the strict contraction necessary to certify the manifold. Therefore, a static (relative and absolute) inflation is performed at Line 6.9, before applying the interval Newton operator, in order to allow the latter to be strictly contracting (such a static inflation is similar to the – inflation described in [111]). A larger static inflation eases the interval Newton contraction, but also deteriorates the overall convergence of the inflation iteration. Although the behavior of the process seems to be not very sensitive to reasonable changes of the static inflation parameters and , experiments have shown that = 1:1 (which is compatible with the value recommended in [111]) and = 1012 represent a good setting in general (although obviously depends on the machine and the problem). Finally, the iteration is stopped as soon as u int(u0), i.e. such that the property (2.33) holds, or when divergence is observed, either by monitoring the distance between successive iterates and enforcing a decrease of at least (by default = 1:0, aiming only at detecting divergence), or by enforcing a safeguarding maximum number of steps (by default k = 15). Algorithm 6 returns a pair of results composed of a boolean indicating whether it was able to strictly contract u, i.e., to certify the parallelotope ; and the resulting parallelotope. The latter is typically quite large due to the double inflation process, which is in fact advantageous since the existence and uniqueness of the solutions hold inside its whole region. When necessary, tighter parallelotopes could be computed by bisecting and contracting them as done in [39]. Note that each iteration of Algorithm 6 involves the interval evaluation of a function, that of a Jacobian matrix and O(n3) interval operations for the right-preconditioning of the interval Jacobian.
The properties of Algorithm 6 are summarized in the following theorem (whose proof is derived
straightforwardly from [36, 39, 56] and from Theorem
Parallelotope Continuation ParCont
The method we propose, called ParCont, interleaves local curve certifications using Algorithm 6 with several checks, which intend in particular to certify the connections between successive parallelotopes and to ensure no backtrack. It is formally defined in Algorithm 7 whose description resides in Subsection 4.3.1. It takes as inputs the system F whose solution set is the curve to follow, an initial point x0 on (or very close to) this curve, and an initial box domain xinit within which the curve is to be followed. A direction d 2 f1; 1g for the continuation is also provided, in order to be able to perform two continuations processes in different direction (see the definition of Ck in Subsection 4.3.1.1). It iteratively builds two sequences of parallelotopes (bx k) and (byk). Each parallelotopebx k is crossed from one input side to the opposite output side by one unique component of the curve. Each parallelotope byk encloses the single solution of the curve on the output side of bx k. The parallelotopes byk enclose a unique solution and are therefore tiny (usually of width approximately 1014). The connection between two consecutive parallelotopes bx k andbx k+1 is ensured since both enclose the certified solution within parallelotope byk. A special
case is by0 which encloses the solution of the curve on the input side of bx 1. It is used to detect
loops, i.e., connection between the first and last parallelotopes in the sequence (bx k). The correctness, halting and asymptotic convergence of ParCont are investigated in Subsection 4.3.2. Finally, the limitations of ParCont are emphasized in Subsection 4.3.3.
Properties of the Algorithm
The three statements provided in this subsection involve real interval arithmetic. The first two, related to the correctness and termination of Algorithm 7, remain correct in outwardly rounded floating interval arithmetic. The third statement is about the asymptotic convergence of Algorithm
7, which is valid only in real interval arithmetic, but provides a good insight on the normal behavior of the floating point implementation of Algorithm 7. All parameters of the algorithms are assumed to lie inside the domains provided in each algorithm description.
Correctness
Theorem 4.2.1 shows that each validated parallelotope bx k is crossed by a piece of solution curve k(t). The following Theorem 4.3.2 is dedicated to show that they can be glued together to a global solution curve (t) (using the solutions yk in parallelotopes byk that are common to successive parallelotopes bx k), hence ensuring the connectivity of the continuation, and that there is no unwanted backtrack during the continuation process (using the validating conditions (4.11a)).
Before stating this theorem, we need to prove a property on parametric curves solving the system
F(x) = 0.
Table of contents :
Résumé de la thèse
1 Introduction
1.1 The problem
1.2 Motivation and scope of the thesis
1.3 Contribution
1.4 Outline of the thesis Notations
2 Preliminaries on Interval Analysis
2.1 Introduction
2.2 Basic Definitions
2.2.1 Interval arithmetic
2.2.2 Interval extension of functions
2.2.3 Rounded Computations
2.3 Constraint satisfaction problems
2.3.1 Solving systems of equations
2.3.2 Contractors and constraint propagation
2.3.3 Search strategy
2.3.4 Convergence
2.4 Global optimization
2.4.1 Pruning
2.4.2 Bounding
2.4.3 Search strategy
2.4.4 Convergence
2.5 Conclusion
3 Overview of nonlinear multiobjective optimization
3.1 Introduction
3.2 Background on Nonlinear Multiobjective Optimization
3.2.1 Definitions and notations
3.2.2 Optimality conditions
3.3 Solving multiobjective problems
3.3.1 Scalarization methods
3.3.2 Continuation methods
3.3.3 Global search methods
3.3.4 Performance assessment
3.4 Conclusion
4 Certified Parallelotope Continuation for one-manifold
4.1 Introduction
4.2 Contracting, Inflating and Certifying parallelotopes
4.3 Parallelotope Continuation ParCont
4.3.1 Algorithm Description
4.3.2 Properties of the Algorithm
4.3.3 Limitations of ParCont
4.4 Experiments
4.4.1 Influence of the manifold topology
4.4.2 Influence of the conditioning
4.4.3 Influence of the embedding space dimension
4.4.4 Homotopy continuation
4.4.5 Control synthesis
4.4.6 Conclusion
4.5 Adaptation to biobjective optimization
4.5.1 Detecting rigorously changes of constraint activity
4.5.2 Limitations
4.6 Biobjective experiments
4.6.1 Illustration of change of active constraints
4.6.2 Following many changes of constraint activity
4.6.3 Connectivity of the Pareto front through nonoptimal solutions
4.7 Conclusion
5 Biobjective Branch & Bound
5.1 Introduction
5.2 Implementing biobjective interval Branch & Bound
5.2.1 Constraint propagation towards feasible nondominated solutions
5.2.2 Bounding
5.2.3 Search strategy
5.2.4 Convergence
5.3 Experiments
5.3.1 Comparing dominance contractor
5.3.2 Comparing search strategies
5.4 Discussion and further inverstigations
5.4.1 Lower and upper bounding
5.4.2 Search strategy
5.4.3 Hybridizing direct and inverse Branch & Bound
5.5 Conclusion
6 Conclusion and Perspectives
6.1 Conclusion
6.2 Perspectives
6.2.1 Newton-based contractor and first-order conditions
6.2.2 Integration of ParCont within Branch & Bound
6.2.3 Towards multiobjective optimization
6.2.4 Other perspectives
A Biobjective Benchmark problems
A.1 LZ3 Modified
A.2 Kim and DeWeck (KIM)
A.3 Osyczka (OSY)
A.4 NBI
A.5 SpeedReducer (SR)
A.6 MOP
B Detailed results of Section
Bibliography
