1
Introduction

In this chapter, the fundamental concepts of mathematical optimization and multi-parametric programming will be presented. Such concepts will be the foundation towards the development of state-of-the-art multi-parametric programming strategies and applications, which will appear in this book in the next chapters.

1.1 Concepts of Optimization

1.1.1 Convex Analysis

This section presents the idea of convex sets and introduces function convexity. Convexity plays a vital role to establish the required properties which will enable a multi-parametric solution to hold. In this setting, the following definitions are established.

1.1.1.1 Properties of Convex Sets

Let and be convex sets defined in . Then

1. The intersection of is a convex set.
2. The summation of two convex sets is a convex set.
3. Let be a real number. The product is a convex set.

Examples of convex sets include lines, polytopes and polyhedra, and open and closed halfspaces.

1.1.1.2 Properties of Convex Functions

1. Let be convex functions defined on a convex subset . Their summation (1.5) is convex, and if at least of one is a strictly convex function, then their summation is strictly convex.
2. Let a be a positive number and be a (strictly) convex function defined in a convex subset . Then the product is (strictly) convex.
3. Let be a (strictly) convex function defined in , and be an increasing convex function defined on the range of in . Then, the composite function defined in is a (strictly) convex function.
4. Let be convex functions defined on a convex subset . If these functions are bounded from above, their pointwise supremum (1.6) is a convex function on .
5. Let be concave functions defined on a convex subset . If these functions are bounded from below, their pointwise infimum (1.7) is a concave function on .

1.1.2 Optimality Conditions

We introduce the following definitions for the solution of general nonlinear optimization problems:

A constrained nonlinear optimization problem, which aims to minimize a real valued function subject to the inequality constraints and equality constraints is denoted as

Problem (1.10) is a nonlinear optimization problem, if and only if, at least one of is a nonlinear function. We assume that the aforementioned functions are continuous and differentiable.

The first-order constraint qualifications that will be presented in the following text are necessary prerequisites to identify whether a feasible point is a local optimum of the function .

• Linear independence constraint qualification: The gradients for all and for all are linearly independent.
• Slater constraint qualification: The constraints for all are pseudo-convex1 at , while the constraints for all are quasi-convex or quasi-concave.2 In addition, the gradients are linearly independent and there exists such that and .

1.1.2.1 Karush-Kuhn-Tucker Necessary Optimality Conditions

Let and be differentiable at a feasible solution , and let have continuous partial derivatives at . In addition, let be the number of active inequality constraints at . Then if one of the aforementioned constraint qualifications hold, there exist Lagrange multipliers such that

These conditions are the Karush-Kuhn-Tucker (KKT) Necessary Conditions and they are the basis for the solution of nonlinear optimization problems.

1.1.2.2 Karun-Kush-Tucker First-Order Sufficient Optimality Conditions

Consider the sets and . Then, if the following conditions hold:

• is pseudo-convex at with respect to all other feasible points x.
• for all are quasi-convex at with respect to all other feasible points x.
• for all are quasi-convex at with respect to all other feasible points x.
• for all are quasi-concave at with respect to all other feasible points x.

then is a global optimum of problem (1.10). If the aforementioned conditions hold only within a ball of radius around , then is a local optimum of problem (1.10).

1.1.3 Interpretation of Lagrange Multipliers

Consider the following problem:

Let be the global minimum of problem (1.12), and that the gradient of the equality constraints are linearly independent. In addition, assume that the corresponding Lagrange multiplier is . The vector is a perturbation vector. The solution of problem (1.12) is a function of the perturbation vector along with the multiplier. Hence, the Lagrange function can be written as

Calculating the partial derivative of the Lagrange function with respect to the perturbation vector, we have

which yields

Hence, the Lagrange multipliers can be interpreted as a measure of sensitivity of the objective function with respect to the perturbation vector of the constraints at the optimum point .

1.2 Concepts of Multi-parametric Programming

1.2.1 Basic Sensitivity Theorem

Having the essentials of optimization for the purposes of this book covered, the objective of this subchapter is to introduce the role of parameters in an optimization formulation. In this context, the following multi-parametric programming problem is considered:

where is the vector of the continuous optimization variables, is the vector of the uncertain parameters, and the sets , correspond to the inequality and equality constraint sets, respectively.

If there exist Lagrange multipliers, and , such that the first-order KKT conditions hold, then we have:

and the vector is defined as follows:

Furthermore, if there exists for which

the Basic Sensitivity Theorem holds, and it is identically satisfied for a neighborhood around and can be differentiated with respect to to yield explicit expressions for the partial derivatives of the vector function .

The first-order estimate of the variation of an isolated local solution x() of (1.16) and the associated unique Lagrange multipliers and can be approximated, given that is known and that is available.

In particular, let be the concatenation of the vectors and . The first-order Taylor expansion of the vector F around can be expressed as follows:

Under the assumptions and the principles of the Basic Sensitivity Theorem, in a neighborhood of the first-order KKT conditions hold and the value of F() around remains zero. For systems that consist of polynomial objective functions of up to second degree and linear constraints, with respect to the optimization variables and the uncertain parameters, the first-order Taylor expansion is exact. Hence, the exact multi-parametric solution can be obtained for the following multi-parametric quadratic programming problem

where matrices , and , , and the scalars , correspond to the and inequality and equality constraints of the sets and , respectively. This problem serves as the basis that will be discussed in Part I, where its solution properties and solution strategies among other things are in focus. Part II then focusses on the application of such problems to optimal control, as the use of parameters enables the formulation of explicit model predictive control problems.

1.3 Polytopes

Multi-parametric programming is intimately related to the properties and operations applicable to polytopes. In the following, some basic definitions on polytopes are stated, which are used throughout the book.

A schematic representation of a polytope is given in Figure 1.1.

Figure 1.1 A schematic representation of a two-dimensional polytope .

In addition to Definition...