
The link to Chapter-3: Some Important Convex Sets is here. Chapter 4 is about some topics that will assist us in understanding optimization even better and even help us in solving optimization problems. These topics mostly relate to the different properties of convex functions. The topics that we will cover in this chapter are:
- Affine combination and affine space
- Conic combination and conic hull
- Epigraph
- Jensen’s inequality
- Operations that preserve convexity
- Quasi-convex functions
We are not very far from reaching the fun part of the series, where we will deal with real optimization problems. So hold on. This chapter will revolve around properties of convex sets and functions. Also, don’t forget to check out the solutions, to questions that I asked in chapter 3, present in the end of the chapter.
Before we start with affine combinations of vectors, we need to go a little back and look into what linear combination of vectors are. A linear combination of vectors is given by:

Similar to linear combination of vectors, affine combination of vectors is nothing but a linear combination of the vectors such that summation of the coefficients is 1. This is shown as:

Now, lets look into affine span. A set of all affine combination of vectors in a set is called affine span. So, an affine span that is denoted by ‘y’ is given as

Lets look at a practical example of the above concept.

In the diagram above, you will notice that any affine combination of vectors V1 and V2 will lie on the black line that also has the vector 3V1+(-2V2). Note that 3+(-2) = 1. Hence, the black line is the affine span of the vectors V1 and V2. This means that any combination of vectors V1 and V2 such that the sum of the coefficients is 1 will lie on the black line. This can be proven theoretically as well. Consider any vector that is an affine combination of V1 and V2. Therefore,

Comparing equations 1 and 2, we can say that any vector that satisfies the affine combination of V1 and V2 will also lie in the line joining V1 and V2. At the same time, if you compare the general equation of an affine span with that of a convex set, you will see that the equations are pretty much the same. Hence, an affine span or an affine space is a convex set. In set builder notation, an affine space is given by:

In the above equation of the line x+y=3, x can be replaced with x1 and y can be replaced with x2. So clearly, x belongs to a 2D space and hence n=2. Again, b has only 1 value. So, m=1. Therefore, A would be of mXn dimension to be able to multiply with ‘x’ to produce ‘b’, 1×2 in this case.
Here, I have a question for you. If the linear combination of n number of vectors lies in a n-dimensional space, what dimensional space do you think does the affine combination of these vectors lie in? To find the answer, check out the last section of the next chapter here.
Now lets look into Conic combinations. Conic combinations are similar to affine combinations but there is a difference in the constraint. However, let us first understand what a convex cone is.

From the diagram above, we can say that all such rays, which are a set of different positive multiples of a point lying in the ray, contribute towards forming a cone. Rays passing through vector points V1 and V2 form the boundary of the cone.

Now that we know about a convex cone, let’s see what a conic hull is. The concept is very similar to that of a convex hull. The conic hull of a set S (conic S) is the smallest convex cone that contains S. It is the set of all possible conic combinations present in S. In set builder notation, a conic hull is defined as:

The below diagram shows a conic and a convex (in red) hull. The black dots constitute the set S. And the conic hull formed by the blue rays make the smallest cone that can hold the set S. Applications of a conic hull are similar to those of a convex hull, except that in this case, the concerned boundary shape is limited to that of a cone.

Here, I have a question for you. What do u think a convex cone or a conic hull would look like in 3-D? To find the answer, check out the last section of the next chapter here.
In this section, we will explore the concept of an epigraph. Epigraph of a function f(x) where x ∈ S, is a collection of all points (x,α) such that f(x)≤α. Confused? Don’t be. Refer to the diagram below to understand what this means. Refer the 2D space as shown below:


Note that values of α have to be relevant and cannot be lesser than the lowest value of f(x). It is to be noted that the collection of points (x,α) lies in a dimension that is one higher than the dimension that set S lies in. In this case, x lies in a 1-D line and the epigraph lies in a 2-D plane. Also, if y=α, then S1 and S2 define the sub-level set of the function. Just as in the case of an epigraph, a function is convex if and only if its sublevel set is also convex. In the above case, the sub level set of the function f(x) is a straight line joining points S1 and S2 and we know that a straight line is given by an affine span, which is a convex set. So, the function f(x) is also convex. The sublevel set of a function, in set builder notation, is defined as:

The epigraph of a convex function in set builder notation is given by:

Below is the epigraph of a convex function in 3D. The shaded space forms the epigraph and the sub level set is formed by the square in the x-y plane.

Now, it can be said that a function f is convex, if and only if its epigraph is a convex set. To visualize this, take any 2 points x1 and x2 in the epigraph above. You will notice that all points on the line joining x1 and x2 lies inside the epigraph. The mathematical proof for this has been shown below. In this case, we will have to prove the property from both sides. This means that we will have to take a convex function and show that its epigraph is a convex set. After that we will take a convex epigraph set and show that the corresponding function is a convex function.

From the inequality above, it can be said that f is a convex function. Thus, it has been proved that if f is a convex function if and only if its epigraph is a convex set.
In this section, we will see what Jensen‘s inequality is. Refer to the diagram shown below.

In the case above, we have a finite number of elements. Extending this idea over an infinite number of elements, we get:

In this section, we will try to mathematically prove some important function to be convex functions.


In the next section, we will look into some operations that preserve convexity and some properties of convex functions. Preserving convexity basically means that the result of these operations on convex sets result in a different convex set. Note that we have seen some of these operations in detail in Chapter-2: Convex Sets and Functions here. However, I will still mention them here to maintain a complete list. Note that the below 3 points are related to convex sets and not convex functions.
- The resultant set from the intersection of any collection of convex sets is also a convex set.
- The vector sum of two convex sets result is a convex set.
- The set αC is convex for any convex set C and scalar α.
Note that these are the ones that have been covered in detail in Chapter-2. Below are some of the new operations that preserve convexity in convex functions.
- If image of a set S, given by f(S), is convex, then the pre-image S will also be convex if the function f is either an affine function or a perspective function or a linear fractal function. Perspective and linear fractal functions are not very important though the forms of these function as shown below:

- Let f1, f2,…,fn be convex functions defined in the same domain D. In that case the non-negative weighted sum of these functions, f(x) given by f(x)=w1f1(x)+w2f2(x)+…+wnfn(x) will also be a convex function, where wi>0. For example, the following function f(x) is a convex function:

- If f and g are convex functions defined in the same domain D, then f+g, αf (α>0) and max{f(x), g(x)} are all convex functions. Lets look at a proof here for the f+g case:

The proof for αf (α>0) and max{f(x), g(x)} can also be shown likewise.
- If a function f(x) is convex and another function g(x) is an affine function, then the composition of f(x) and g(x), which is given by f(g(x)) is a convex. Example:

Now lets look at some properties of convex functions.
- A convex function need not be differentiable. Also it does not need to be continuous in a closed interval set since the function may be non-continuous at the end point of the closed interval. However, a convex is always continuous in an open interval. We know from high school mathematics that the meaning of continuous is that the function should not break at any point. The check for continuity at any point p in the domain of f is given below:

Some examples of continuous and non-continuous functions are shown below:

Again, a function f is differentiable if its derivative exists at each and point of its domain. The check for differentiability is given below:

Examples of differentiable and non-differentiable functions are shown below:

- Every local minimum of a convex function f on a convex set S⊆ℝ is a global minimum. Let us first try and understand what exactly local minimum and global minimum is. Consider any convex function f with domain of S. So, local minima of f(x) at a point in the domain of f(x) would mean:

Again, global minima of f(x) at a point x̄ in the domain of f(x), shown below would mean:

Now, let us see on what ground does the property stand. Below is the proof of the property. We will use proof through contradiction here.

- Let f1, f2,…, fk be convex functions defined on the same domain D, then the function f(x)=max{f1(x), f2(x),…,fk(x)} is also a convex function with dom f=dom f1∩dom f2. This is called pointwise maximum. Lets look at an example here.

- The next property of a convex function is related to a concept called supremum and infimum. So, supremum of a set S is the smallest value that is greater than the highest value of set S. Similarly, infimum of a set S is the highest value that is smaller than the smallest value of set S. Refer to the diagram below for a better understanding. Consider a set S defined in the real number line, ℝ.

So, the property says that the supremum and infimum of a family of arbitrary convex functions f1(x), f2(x),…, fn(x) is also a convex function. The supremum of the convex functions is shown as:

Similar, the infimum of the convex functions is given as:

In this section, we will look into a very interesting kind of function called quasi-convex function. So, what does quasi-convex mean? It means "as if convex". Expanding this further, quasi-convex gives a weak sense of convexity. It is not a proper convex function, but only a weak notion of it. There are two different ways that a quasi convex function is defined.

Another definition to understand quasi-convex sets uses the concept of contours. So what is a contour? A contour is nothing but the boundary of something. This something could be anything such as a mountain, a sculpture, a utensil. In our case, we will use the contours of sets. So, the second definition of a quasi-convex function is given as:


And so, with this we have come to the end of this chapter.
In the earlier Chapter-3: Some Important Convex Sets, the first question that I asked was "What do you think will be the equation of the half space created by a hyperplane that passes through origin?" The answer is pretty simple.

The second question that I had asked was "Can you tell the magnitude of the vector whose norm ball has been shown in the diagram above?" This is even simpler. The magnitude of the vector whose norm ball has been shown is ‘r’, which is the radius as shown in the diagram.
Continue to the next chapter, Chapter-5: Pre-requisites to Solve Optimization Problems here