Finite Dimensional Convexity and Optimization

Frontmatter

1. Convexity in ℝ n

Abstract

Let x and y be two points of ℝ ⁿ . The set

$$ [x,y]: = \{ z \in \mathbb{R}^n |z = \alpha x + (1 - \alpha )y,\alpha \in \mathbb{R}and0 \leqslant \alpha \leqslant 1\} $$

is called closed line segment joining x and y. One also denotes

$$ \begin{gathered} [(x,y): = [x,y]\backslash \{ y\} = \{ z \in \mathbb{R}^n |z = \alpha x + (1 - \alpha )y,\alpha \in \mathbb{R}and0 < \alpha \leqslant 1\} , \hfill \\ [(x,y: = [x,y]\backslash \{ x\} = \{ z \in \mathbb{R}^n |z = \alpha x + (1 - \alpha )y,\alpha \in \mathbb{R}and0 \leqslant \alpha < 1\} . \hfill \\ \end{gathered} $$

The set

$$ \begin{gathered} \left[ x \right.,\left. y \right): = \left[ {x,y} \right]\backslash \left\{ y \right\} = \left\{ {z \in \mathbb{R}^n \left| {z = \alpha x + \left( {1 - \alpha } \right)y,\alpha \in \mathbb{R} and 0 < \alpha \leqslant 1} \right.} \right\}, \hfill \\ = \left\{ {z \in \mathbb{R}^n \left| {z = \alpha x + \left( {1 - \alpha } \right)y, \alpha \in \mathbb{R} and 0 < \alpha < 1} \right.} \right\}. \hfill \\ \end{gathered} $$

is called open line segment joining x and y. It may also be noted ]x,y[.

Monique Florenzano, Cuong Le Van

2. Separation and Polarity

Abstract

Let H = x ∈ ℝ ⁿ | p · x = α be a hyperplane in ℝ ⁿ (p ∈ ℝ ⁿ \ {0}, α ∈ ℝ). The sets F = x ∈ ℝ ⁿ | p · x ≤ α and G = x ∈ ℝ ⁿ | p · x ≥ α are called closed half-spaces associated with (or determined by) H. Obviously, they are convex and topologically closed as the inverse images of the closed intervals of ℝ: ] - ∞, α] and [α,+ ∞[ respectively by the (continuous) linear functional: x → p · x. The complementary sets V = x ∈ℝ ⁿ | p · x > α and U = x ∈ℝ ⁿ | p · x < α are obviously convex and topologically open; they are called open half-spaces associated with (or determined by) H.

Monique Florenzano, Cuong Le Van

3. Extremal Structure of Convex Sets

Abstract

Let A be a convex subset of ℝ ⁿ . A point x ∈ A is an extreme point of A if and only if there exists no open segment contained in A and containing x, that is, if and only if there is no way to express x as a convex combination x = λy + (1 - λ)z such that y ∈A, z ∈ A and 0 < λ < 1, except by taking x = y = z. Easy computations show that an equivalent characterization for an extreme point x of A is that the relations x = (1/2)y + (l/2)z together with y ∈ A, z ∈ A imply x = y = z. Obviously, if A = a, then a is an extreme point of A.

Monique Florenzano, Cuong Le Van

4. Linear Programming

Abstract

A linear programming problem consists in finding the maximum (resp. minimum) value of a linear functional, subject to a finite number of linear constraints. If c and a ⁱ , i = 1,…, m are elements of ℝ ⁿ , and if b = (b₁,…, b _m ) belongs to ℝ ^m , the most general form of a linear programming problem is the following: Maximize (resp. minimize)

$$ f(x) = c \cdot x $$

subject to the conditions

$$ a^i \cdot x\mathop {\left( {\begin{array}{*{20}c} \leqslant \\ = \\ \geqslant \\ \end{array} } \right)}\limits_{x \in \mathbb{R}^n .} b_i ,i = 1,...,m $$

Monique Florenzano, Cuong Le Van

5. Convex Functions

Abstract

This chapter is devoted to a class of functions from ℝ ⁿ into ℝ∪ +∞ called convex functions and to give a first important property of such functions. Any convex function is continuous on the interior of its domain if this one is nonempty. If the domain of a convex function f has an empty interior, then the restriction of f to the affine set spanned by its domain is continuous on the relative interior of its domain (this expression makes sense because the domain of a convex function is a convex set).

Monique Florenzano, Cuong Le Van

6. Differential Theory of Convex Functions

Abstract

In this chapter, we give three notions of differentiability for convex functions. The first one is the directional derivative which always exists inℝ∪ +∞ at any point in the relative interior of the domain of a convex function. While the differential of a function is a linear functional, the directional derivative is only a sublinear function.

Monique Florenzano, Cuong Le Van

7. Convex Optimization With Convex Constraints

Abstract

In this chapter we want to solve the problem minf(x) | x ∈ C, where f is a convex function on ℝ ⁿ , and C is a convex, nonempty subset of ℝ ⁿ . A point x^* ∈ C is a global solution, or more simply a solution to this problem, or a minimizer of f on C, if f(x*) ≤ f(x), ∀x ∈ C. We say that x^* is a local solution to this problem if there exists a relatively open set U of C such that f(x^*) ≤ f (x), ∀x ∈ U.

Monique Florenzano, Cuong Le Van

8. Non Convex Optimization

Abstract

In the previous chapter, we study the minimization problem of a convex function under convex constraints. In this chapter, we study the minimization problem for two other classes of functions. The first ones are quasi-convex functions. We know (see Chapter 5) that for a convex function f, any level set of f is convex. But the converse is not true. The functions which have the property that every level set is convex are precisely called quasi-convex functions. In the first section we give necessary and sufficient conditions for a point to be a solution to a minimization problem of a quasi-convex function under convex constraints.

Monique Florenzano, Cuong Le Van

Backmatter