Function Operations
Contents
9.10. Function Operations#
In this section we discuss various operations which generate new functions from a given function, a pair of functions or a family of functions. We discuss if the properties like convexity and closedness are preserved under these function operations. Such operations include, scaling, sum, composition, pointwise supremum, partial minimization, etc..
Main references for this section are [9, 17].
9.10.1. Scaling and Addition of Convex Functions#
Here we show some basic results about operations that preserve convexity
Theorem 9.101 (Nonnegative multiplication)
If \(f\) is convex, then so is \(\alpha f\) for all \(\alpha \geq 0\).
Proof. Assume \(f\) is convex. Note that \(\dom f = \dom \alpha f\). Thus, \(\dom \alpha f\) is convex since \(\dom f\) is convex.
Now, let \(\bx, \by \in \dom f\) and \(t \in [0,1]\). Then
Thus, \(\alpha f\) is convex for every \(\alpha \geq 0\).
Theorem 9.102 (Convex function sum)
If \(f\) and \(g\) are convex, then so is \(f + g\) with \(\dom (f + g) = \dom f \cap \dom g\).
Proof. We discussed earlier that \(\dom (f + g) = \dom f \cap \dom g\) as \(f + g\) is defined only for the points where both \(f\) and \(g\) are defined.
Recall from Theorem 9.25 that intersection of convex sets is convex. Thus, \(\dom (f + g)\) is convex since \(\dom f\) and \(\dom g\) are both convex.
Now let \(\bx, \by \in \dom (f + g)\) and \(t \in [0, 1]\).
Since \(f\) is convex, hence
\[ f(t\bx + (1-t) \by) \leq t f(\bx) + (1-t) f(\by). \]Since \(g\) is convex, hence
\[ g(t\bx + (1-t) \by) \leq t g(\bx) + (1-t) g(\by). \]Adding the two inequalities, we get:
\[\begin{split} & f(t\bx + (1-t) \by) + g(t\bx + (1-t) \by) \leq t f(\bx) + (1-t) f(\by) + t g(\bx) + (1-t) g(\by)\\ & \implies (f + g)(t\bx + (1-t) \by) \leq t (f + g)(\bx) + (1-t) (f + g)(\by). \end{split}\]Thus, \(f+g\) is convex.
Theorem 9.103 (Conic combinations of convex functions)
If \(f_1, \dots, f_n\) are convex, then for any \(t_1, \dots, t_n \geq 0\), the conic combination of functions given by:
is also convex.
The conic combinations are also called nonnegative weighted sums.
Proof. Due to Theorem 9.101, \(t_i f_i\) are convex since \(f_i\) are convex and \(t_i \geq 0\).
Due to Theorem 9.102, sum of two convex functions is convex.
It can be easily shown by mathematical induction that sum of \(n\) convex functions is convex too.
Thus, \(f\) is convex.
Theorem 9.104
The set of convex functions in the vector space of real valued functions form a convex cone.
Note that the set of real valued functions forms a vector space over \(\RR\) with the standard definitions of function scalar multiplication and function addition. We are examining the convexity of the set of functions under this vector space.
Proof. Since every conic combination of convex functions is convex, hence the set of convex functions is a convex cone.
Theorem 9.105 (Concave function sum)
If \(f\) and \(g\) are concave, then so is \(f + g\) with \(\dom (f + g) = \dom f \cap \dom g\).
Proof. We proceed as follows:
Let \(f\) and \(g\) be concave.
\(-f\) and \(-g\) are convex.
By Theorem 9.102, \((-f) + (-g) = -(f + g)\) is convex.
Thus, \(f+g\) is concave.
Theorem 9.106 (Conic combinations of cave functions)
If \(f_1, \dots, f_n\) are concave, then for any \(t_1, \dots, t_n \geq 0\), the conic combination of functions given by:
is also concave.
Proof. We proceed as follows:
If \(f_1, \dots, f_n\) are concave then \(-f_1, \dots, -f_n\) are convex.
By Theorem 9.103, \((-t_1 f_1) + \dots + (-t_n f_n)\) is convex.
Thus, \(-(t_1 f_1 + \dots + t_n f_n)\) is convex.
Thus, \(t_1 f_1 + \dots + t_n f_n\) is concave.
9.10.2. Composition with Nondecreasing Functions#
Theorem 9.107 (Composition with a convex nondecreasing function preserves convexity)
Let \(\VV\) be a real vector space. Let \(f : \VV \to \RERL\) be a proper convex function. Let \(g : \RR \to \RERL\) be a convex function which is nondecreasing.
Then, their composition \(h = g \circ f\) given by:
with \(g(\infty) = \infty\), is convex on \(\VV\).
Proof. We note that \(\dom h = \dom f \cap \dom g\). Since both \(f\) and \(g\) are convex, hence \(\dom f\) and \(\dom g\) are convex and hence \(\dom h\) is convex.
Choose any \(\bx, \by \in \VV\) and \(t \in (0, 1)\).
We need to show that
\[ h((1-t) \bx + t \by) \leq (1-t) h(\bx) + t h(\by). \]If \(\bx \notin \dom f\), then \(h(\bx) = g(f(\bx)) = \infty\). Similarly, if \(\by \notin \dom f\), then \(h(\by) = g(f(\by)) = \infty\).
In either case, the convexity inequality will be satisfied trivially.
Let us now consider the case where \(\bx, \by \in \dom f\).
By convexity of \(f\), we have:
\[ f((1-t) \bx + t \by) \leq (1-t) f(\bx) + t f(\by). \]Note that \((1-t) f(\bx) + t f(\by)\) is a convex combination of \(f(\bx)\) and \(f(\by)\).
Since \(g\) is nondecreasing, hence if \(r \leq s\) then \(g(r) \leq g(s)\).
By applying \(g\) on both sides of the previous inequality, we obtain
\[\begin{split} h ((1-t) \bx + t \by) &= g (f ((1-t) \bx + t \by)) \\ &\leq g((1-t) f(\bx) + t f(\by)) \\ &\leq (1-t) g(f(\bx)) + t g(f(\by)) \\ &= (1-t) h(\bx) + t h(\by). \end{split}\]Thus, \(h\) is convex.
Example 9.50 (Exponential of a convex function)
Recall from Example 9.42 that the exponential function \(e^x\) is convex.
Then, for any convex \(f\), \(h(x) = e^{f(x)}\) is convex due to Theorem 9.107.
Example 9.51 (Power of a nonnegative convex function)
Let \(f: \VV \to \RR\) be a proper convex and nonnegative function.
Then, \(f(x) = | f(x) |\).
Let \(p \geq 1\) and consider the function \(g(x) = |x|^p\). By Example 9.31, \(g\) is convex.
Then, \( h = g \circ f\) given by
is also convex.
Example 9.52 (Power of a norm)
Let \(\| \cdot \| : \VV \to \RR\) be a norm on the real vector space \(\VV\). Let \(p \geq 1\).
Then, the \(p\)-th power of the norm given by
is convex.
The norm is a convex and nonnegative function.
\(g(x) = |x|^p\) is convex.
By Theorem 9.107, \(\| \cdot \|^p\) is convex.
Example 9.53 (Reciprocal of a concave function)
Let \(g\) be a concave function. Then, \(h(\bx) = \frac{1}{g(\bx)}\) is convex on the set \(C = \{\bx \ST g(\bx) > 0 \}\).
Since \(g\) is concave, hence \(f = -g\) is convex.
For all \(\bx \in C\), \(f(\bx) < 0\).
Consider the function
\[\begin{split} \phi(x) = \begin{cases} \frac{1}{x} & \text{ if } & x < 0\\ \infty & \text{ if } & x \geq 0. \end{cases} \end{split}\]It is easy to see that \(\phi\) is convex with the domain \(\RR_{++}\) (Example 9.44).
We can see that, \(h = \phi \circ f\).
Since \(f\) is convex and negative, \(h\) is also convex with \(\dom h = C \cap \RR_{++}\).
Example 9.54 (Scaling and translation of a convex function)
Let \(f : \VV \to \RR\) be a proper convex function.
Let \(m \geq 0\) and \(c \in \RR\).
Let \(g : \RR \to \RR\) be given by
Then, \(g\) is convex (in fact affine) and nondecreasing.
Thus, \(h = g \circ f = m f + c\) is also a proper convex function due to Theorem 9.107.
9.10.3. Composition with Affine Mapping#
Theorem 9.108 (Affine transformations preserve convexity)
Let \(\VV\) and \(\WW\) be real vector spaces. Let \(T : \VV \to \WW\) be a linear transformation. Let \(\bb \in \WW\). Let \(f : \WW \to \RR\) be a function. Define \(g : \VV \to \RR\) as:
with \(\dom g = \{\bx \in \VV \ST T(\bx) + \bb \in \dom f \}\).
If \(f\) is convex, then so is \(g\). If \(f\) is concave, then so is \(g\).
Proof. Assume \(f\) is convex.
If we define \(A : \VV \to \WW\) as \(A(\bx) = T(\bx) + \bb \) then \(\dom g = A^{-1}(\dom f)\).
\(A\), so defined, is an affine transformation.
By Theorem 9.32, \(\dom g\) is convex since \(\dom f\) is convex.
Let \(\bx, \by \in \dom g\).
\(g(\bx) = f(T(\bx) + \bb)\). Define \(\bu = T(\bx) + \bb\).
\(g(\by) = f(T(\by) + \bb)\). Define \(\bv = T(\by) + \bb\).
By definition, \(\bu, \bv \in \dom f\).
Let \(t \in [0,1]\).
Since \(f\) is convex, hence
\[ f(t\bu + (1-t) \bv) \leq t f(\bu) + (1-t)f(\bv). \]Now
\[\begin{split} g(t\bx + (1-t) \by) &= f(T(t\bx + (1-t) \by) + \bb)\\ &= f(tT(\bx) + (1-t) T(\by) + (t + (1-t))\bb)\\ &= f(t(T(\bx) + \bb) + (1-t) (T(\by) + \bb))\\ &= f(t\bu + (1-t) \bv )\\ &\leq t f(\bu) + (1-t) f(\bv)\\ &= t g(\bx) + (1-t) g(\by). \end{split}\]Thus, \(g\) satisfies the convexity defining inequality (9.1).
Thus, \(g\) is convex.
A similar argument shows that if \(f\) is concave then so is \(g\).
9.10.4. Sum of Functions#
Theorem 9.109 (Sum of convex functions)
Let \(\VV\) be a real vector space. Let \(f_1 : \VV \to \RERL\) and \(f_2 : \VV \to \RERL\) be proper convex functions. Then, the function \(f = f_1 + f_2\) is a proper convex function.
We note that since both \(f_1\) and \(f_2\) are proper, hence neither attains a value of \(-\infty\), thus undesired sums like \(\infty - \infty\) are avoided.
Proof. Convexity of the domain
Since \(f_1\) is convex, hence \(\dom f_1\) is a convex set.
Since \(f_2\) is convex, hence \(\dom f_2\) is a convex set.
By definition of function sum \(\dom f = \dom f_1 \cap \dom f_2\).
Intersection of convex sets is convex.
Hence, \(\dom f\) is convex.
We note that \(f(\bx) < \infty\) if and only if \(f_1(\bx) < \infty\) and \(f_1(\bx) < \infty\).
If \(\dom f = \EmptySet\), then by Observation 9.4, \(f\) is convex. We are left with the case where \(\dom f\) is not empty.
Convexity inequality
Let \(\bx, \by \in \dom f\). Let \(t \in (0, 1)\).
Then, \(\bx, \by \in \dom f_1\) as well as \(\bx, \by \in \dom f_2\).
By convexity of \(f_1\)
\[ f_1(t \bx + (1-t) \by) \leq t f_1(\bx) + (1-t)f_1(\by). \]By convexity of \(f_2\)
\[ f_2(t \bx + (1-t) \by) \leq t f_2(\bx) + (1-t)f_2(\by). \]Summing these inequalities, we get:
\[ f(t \bx + (1-t) \by) \leq t f(\bx) + (1-t)f(\by). \]
Corollary 9.7 (Sum of multiple convex functions)
Let \(\VV\) be a real vector space. Let \(f_1, \dots, f_k : \VV \to \RERL\) be proper convex functions. Then, the function \(f = f_1 + \dots + f_k\) is a proper convex function.
Proof. We note that \(\dom f = \bigcap_{i=1}^k \dom f_k\). \(\dom f\) is convex since it is an intersection of convex sets. The proof of convexity is a simple application of mathematical induction.
Let \(g_r = f_1 + \dots + f_r\) for \(r \in 2,\dots, k\).
By Theorem 9.109, \(g_2 = f_1 + f_2\) is a proper convex function.
Assume that \(g_r\) is a proper convex function for some \(r\).
Then, \(g_{r+1} = g_r + f_{r+1}\).
Since both \(g_r\) and \(f_{r+1}\) are proper convex, hence \(g_{r+1}\) is also a proper convex function.
Theorem 9.110 (Conic combination of convex functions)
Let \(\VV\) be a real vector space. Let \(f_1, \dots, f_k : \VV \to \RERL\) be proper convex functions. Let \(r_1, \dots, r_k \geq 0\).
Then, the function \(f = r_1 f_1 + \dots + r_k f_k\) is a proper convex function. \(f\) is a conic combination of \(f_1, \dots, f_k\).
Proof. By Example 9.54, \(r_i f_i\) are proper convex functions.
By Corollary 9.7, their sum is a proper convex function.
Example 9.55 (Restricting the domain of a convex function)
Let \(f : \VV \to \RR\) be a convex function with \(\dom f = \VV\).
Let \(C \subseteq \VV\) be a convex set. Let \(I_C\) be the indicator function for the set \(C\) given by
Consider the proper function \(h = f + I_C\) given by
By Theorem 9.109, \(h\) is a proper convex function. \(\dom h = \dom f \cap \dom I_C = \VV \cap C = C\).
Thus, \(h\) restricts the effective domain of \(f\) to \(C\).
9.10.5. Construction from \(\VV \oplus \RR\)#
One way to construct convex functions on \(\VV\) is from convex sets in \(\VV \oplus \RR\).
Theorem 9.111 (Construction from convex sets of \(\VV \oplus \RR\))
Let \(\VV\) be a real vector space. Let \(F \subseteq \VV \oplus \RR\) be a convex subset of \(\VV \oplus \RR\). Let \(f : \VV \to \RERL\) be defined as
Then, \(f\) is a proper convex function on \(\VV\).
We note that \(f(\bx) = \infty\) if there is no \(t \in \RR\) such that \((\bx, t) \in F\). This is consistent since \(\inf \EmptySet = \infty\).
Proof. Convexity of domain of \(f\)
We note that for some \(\bv \in \VV\), if there is no \(t \in \RR\) such that \((\bv, t) \in F\), then \(f(\bv) = \infty\) and \(\bv \notin \dom f\).
Thus, if \(\bv \in \dom f\), then there exists \(t \in \RR\) such that \((\bv, t) \in F\).
Let \(\bx, \by \in \dom f\) and \(t \in (0, 1)\).
Then, there exists \((\bx, p) \in F\) and \((\by, q) \in F\) for some \(p,q \in \RR\).
Since \(F\) is convex, hence
\[ t(\bx, p) + (1-t)(\by, q) = (t \bx + (1-t) \by, t p + (1-t)q ) \in F. \]But then, \(f(t \bx + (1-t) \by) \leq t p + (1-t)q \in \RR\).
Thus, \(t \bx + (1-t) \by \in \dom f\).
Thus, \(\dom f\) is convex.
Convexity inequality in the domain
Let \(\bx, \by \in \dom f\) and \(t \in (0, 1)\).
Let \(X = \{v \in \RR \ST (\bx, v) \in F \}\).
Let \(Y = \{v \in \RR \ST (\by, v) \in F \}\).
By definition of \(f\), \(f(\bx) = \inf X\) and \(f(\by) = \inf Y\).
Let \(\bz = t \bx + (1-t) \by\).
Let \(Z = \{v \in \RR \ST (\bz, v) \in F \}\).
We have \(f(\bz) = \inf Z\).
Since \(F\) is convex, hence for every \(p \in X\) and every \(q \in Y\), the point \((t\bx + (1-t)\by, t p + (1-t) q) = (\bz, t p + (1-t) q) \in F\).
Thus, for every \(p \in X\) and every \(q \in Y\), \(t p + (1-t) q \in Z\).
But then, \(\inf Z \leq t p + (1-t) q\) for every \(p \in X\) and every \(q \in Y\).
Thus, taking infimum on the R.H.S. over \(X\) and \(Y\),
\[ \inf Z \leq \inf_{p \in X} \inf_{q \in Y} (t p + (1-t) q ) = t \inf X + (1-t) \inf Y. \]In other words
\[ f(t \bx + (1-t) \by) = f(\bz) \leq t f(\bx) + (1-t) f(\by). \]Thus, \(f\) is convex.
We note that \(F \neq \epi f\). Although, \(F \subseteq \epi f\) and can be easily extended to become \(\epi f\).
9.10.6. Pointwise Supremum#
9.10.6.1. Two Functions#
Theorem 9.112 (Pointwise maximum of two convex functions)
Let \(f_1\) and \(f_2\) be convex functions. Define their pointwise maximum as
with \(\dom f = \dom f_1 \cap \dom f_2\). Then, \(f\) is convex.
Proof. \(\dom f\) is an intersection of convex sets. Hence, it is convex.
Let \(\bx, \by \in \dom f\) and \(t \in [0,1]\).
Thus, \(f\) is convex.
9.10.6.2. Multiple Functions#
Theorem 9.113 (Pointwise maximum of multiple convex functions)
Let \(f_1, f_2, \dots, f_n\) be convex functions. Define their pointwise maximum as
with \(\dom f = \dom f_1 \cap \dots \cap \dom f_n\). Then, \(f\) is convex.
Proof. The result has been proved for the base case of 2 functions in Theorem 9.112.
Assume that it is true for \(n\) functions. We can easily show it true for \(n+1\) functions since
Thus, by principle of mathematical induction, the result is true for all \(n\).
9.10.6.3. Family of Functions#
Theorem 9.114 (Pointwise supremum of a family of convex functions)
Let \(I\) be an index set. Let \(\{ f_i : \VV \to \RR \}_{i \in I}\) be a family of convex functions. Define their pointwise supremum as
with
Then, \(f\) is convex. Moreover,
Consequently, if \(f_i\) are closed and convex for every \(i \in I\), then \(f\) is closed and convex.
Proof. We shall first verify the epigraph equality.
Let \((\bx, t) \in \epi f\).
Then, \(f(\bx) \leq t\).
Thus, \(f_i(\bx) \leq t\) for all \(i \in I\) since \(f(\bx) = \sup \{f_i(\bx)\}_{i \in I}\).
Thus, \((\bx, t) \in \epi f_i\) for all \(i \in I\).
Thus, \(\epi f \subseteq \bigcap_{i \in I} \epi f_i\).
Now, for the converse:
Let \((\bx, t) \in \bigcap_{i \in I} \epi f_i\).
Thus, \((\bx, t) \in \epi f_i\) for all \(i \in I\).
Thus, \(f_i(\bx) \leq t\) for all \(i \in I\).
Taking the supremum over \(i \in I\) on the L.H.S., we obtain:
\[ \sup \{f_i(\bx)\}_{i \in I} = f(\bx) \leq t. \]Thus, \((\bx, t) \in \epi f\).
Thus, \(\bigcap_{i \in I} \epi f_i \subseteq \epi f\).
Combining the two, we get:
Since \(f_i\) are convex functions, hence \(\epi f_i\) are convex sets due to Theorem 9.71.
Thus, \(\epi f\) is a convex set due to Theorem 9.26.
But then, \(f\) is convex again due to Theorem 9.71.
Closedness
If \(f_i\) are closed for every \(i \in I\), then \(\epi f_i\) is closed for every \(i \in I\).
Consequently, \(\epi f\) is closed, since its an intersection of closed sets.
Hence \(f\) is a closed function.
9.10.6.4. Largest Entry#
Example 9.56 (Convexity of the largest entry in a vector)
Let \(h : \RR^n \to \RR\) be defined as
If we introduce coordinate functions \(f_i : \RR^n \to \RR\) as
then, we can write \(h\) as
Each of the coordinate functions is linear hence convex. Thus, \(h\) is a maximum of convex functions. Hence \(h\) is convex.
9.10.6.5. Sum of \(k\) Largest Entries#
Example 9.57 (Sum of \(k\) largest entries in a vector)
Consider a vector \(\bx \in \RR^n\) with \(\bx = (x_1, \dots, x_n)\).
Let \(x_{[i]}\) denote the \(i\)-th largest entry of \(\bx\).
In particular, \(x_{[1]} = \max \{ x_1, \dots, x_n \}\) is the largest entry of \(\bx\).
Then,
\[ x_{[2]} = \max \left (\{ x_1, \dots, x_n \} \setminus \{ x_{[1]}\} \right ) \]is the second largest entry of \(\bx\).
Similarly,
\[ x_{[k]} = \max \left (\{ x_1, \dots, x_n \} \setminus \{ x_{[1]}, \dots, x_{[k-1]}\} \right ) \]is the \(k\)-th largest entry of \(\bx\).
In other words, if we sort the entries of \(\bx\) in descending order, we can pick the largest entries one by one.
We can introduce functions \(g_i : \RR^n \to \RR\) as
As shown in Example 9.56, \(g_1\) is convex. However, \(g_2,\dots, g_n\) are not convex.
We now introduce a function which computes the sum of \(k\) largest entries. Let \(h_k : \RR^n \to \RR\) be given by
Then, \(h\) is convex. To see this, we proceed as follows:
There are \(N = {n \choose k}\) ways of choose \(k\) indices from the set \(1,\dots,n\).
Let \(I_l = \{i_1^l, \dots, i_k^l \}\) be one of the \(N\) ways to choose \(k\) indices for \(l=1,\dots,N\).
Let \(F_l : \RR^n \to \RR\) be given by
\[ F_l (\bx) = x_{i_1^l} + \dots + x_{i_k^l} \]for \(l=1,\dots,N\).
Then, \(F_l\) is a linear (hence convex) function for every \(l=1,\dots,N\).
We can now see that
\[ h_k(\bx) = \max \{ F_1(\bx), \dots, F_N(\bx) \}. \]Thus, \(h_k\) is a maximum of \(N\) convex functions.
Hence \(h\) is convex.
9.10.6.6. Piecewise Linear Function#
Definition 9.54 (Piecewise linear function)
Let \(\ba_1, \dots, \ba_n \in \VV\). Let \(b_1, \dots, b_n \in \RR\).
A function \(f: \VV \to \RR\) given by:
is called a piecewise linear or piecewise affine function.
Theorem 9.115
Piecewise linear functions are convex.
Proof. Each of the functions \(f_i (\bx) = \langle \bx, \ba_i \rangle + b_i\) is affine functionals. Thus, \(f_i\) are convex (Theorem 9.68). \(f\) is a pointwise maximum of \(n\) convex functions. Hence, \(f\) is convex (Theorem 9.113).
9.10.7. Projection#
Theorem 9.116 (Projection for extended valued functions)
Let \(\VV\) and \(\WW\) be finite dimensional real normed linear spaces. Let \(f : \VV \oplus \WW \to \ERL\) be a convex function. Let \(g_{\bx} : \WW \to \ERL\) be defined by
If \(f\) is convex, then \(g_{\bx}\) is convex.
If \(f\) is proper and \(f(\bx, \by) < \infty\) for some \(\by\), then \(g_{\bx}\) is proper.
If \(f\) is closed, then \(g_{\bx}\) is closed.
Proof. Convexity
Let \(\by_1, \by_2 \in \WW\) and \(t \in [0,1]\).
Then
\[\begin{split} g_{\bx}(t \by_1 + (1-t) \by_2) &= f(\bx, t \by_1 + (1-t) \by_2) \\ &= f(t\bx + (1-t) \bx, t \by_1 + (1-t) \by_2) \\ &= f(t (\bx, \by_1) + (1-t)(\bx, \by_2)) \\ &\leq t f(\bx, \by_1) + (1-t) f(\bx, \by_2) \\ &= t g_{\bx}(\by_1) + (1-t) g(\by_2). \end{split}\]Hence \(g\) is convex.
Properness
Since \(f\) is proper, hence \(g_{\bx} > -\infty\) for every \(\by\).
Since \(f(\bx, \by) < \infty\) for some \(\by\), hence \(g_{\bx}(\by) < \infty\) for the same \(\by\).
Hence \(g_{\bx}\) is proper.
Closedness
Let \(G_t = \sublevel(g_{\bx}, t)\) for any \(t \in \RR\).
Let \(F_t = \sublevel(f, t)\) for any \(t \in \RR\).
By hypothesis, \(F_t\) is closed for every \(t\).
Consider a converging sequence \(\{ \by_k \}\) of \(G_t\) with \(\lim \by_k = \by\).
Then \(g_{\bx} (\by_k ) \leq t\) for every \(k\).
Thus \(f(\bx, \by_k) \leq t\) for every \(k\).
Hence \(\{ (\bx, \by_k) \}\) is a converging sequence of \(F_t\).
Since \(F_t\) is closed, hence \(\{ (\bx, \by_k) \}\) converges in \(F_t\).
Hence \((\bx, \by) \in F_t\).
Hence \(f(\bx, \by) \leq t\).
Hence \(g_{\bx}(\by) \leq t\).
Hence \(\by \in G_t\).
Hence \(G_t\) is closed.
Hence all sublevel sets of \(g_{\bx}\) are closed.
Hence \(g_{\bx}\) is a closed function.
9.10.8. Partial Minimization#
9.10.8.1. Real Valued Convex Functions#
Theorem 9.117 (Partial minimization)
Let \(\VV\) and \(\WW\) be real vector spaces. Let \(f : \VV \oplus \WW \to \RR\) be a convex function with \(C \oplus D = \dom f\). Define a function \(g : \VV \to \RR\) as
Assume that the infimum is finite for every \(\bx \in C\). Then, \(g\) is convex with \(C = \dom g\).
Note that it is possible that \(g(\bx)\) is finite for some \(\bx \in C\) and yet there is no \(\by \in D\) such that \((\bx, \by) \in C \oplus D\). In other words, we only assume that the infimum is finite at every \(\bx \in C\). We don’t require that the infimum is attained at some point \((\bx, \by) \in C \oplus D\).
Proof. Since \(f\) is convex, hence \(\dom f\) is convex. Thus, \(C \oplus D\) is convex. By Theorem 9.41, \(C\) and \(D\) are convex.
Since the infimum is finite for every \(\bx \in C\), hence \(\dom g = C\).
Thus, \(\dom g\) is a convex subset of \(\VV\).
Let \(\bx_1, \bx_2 \in C\) and \(t \in (0, 1)\).
Take any \(r > 0\).
By definition of the infimum, there exist some \(\by_1, \by_2 \in D\) such that
\[\begin{split} & f(\bx_1, \by_1) \leq g(\bx_1) + r, \\ & f(\bx_2, \by_2) \leq g(\bx_2) + r. \end{split}\]Let \((\bx, \by) = t (\bx_1, \by_1) + (1-t) (\bx_2, \by_2)\).
Since \(f\) is convex, hence
\[\begin{split} f(\bx, \by) &\leq t f(\bx_1, \by_1) + (1-t) f(\bx_2, \by_2) \\ &\leq t (g(\bx_1) + r) + (1- t) (g (\bx_2) + r) \\ = t g(\bx_1) + (1-t) g(\bx_2) + r. \end{split}\]By definition of \(g\)
\[ g(\bx) \leq f(\bx, \by) \leq t g(\bx_1) + (1-t) g(\bx_2) + r. \]Since this inequality is valid for every \(r > 0\), hence
\[ g(\bx) \leq t g(\bx_1) + (1-t) g(\bx_2) \]holds true for every \(\bx_1,\bx_2 \in C\) and \(t \in (0,1)\).
Thus, \(g\) is convex.
Example 9.58 (Convexity of the distance from a convex set function)
Let \(C \subseteq \VV\) be a convex set. The set distance function \(d_C : \VV \to \RR\) is defined by
We define a function \(f : \VV \oplus \VV \to \RR\) as
Since the norm is convex, hence \(f\) is convex over \(\VV \oplus \VV\). In particular \(f\) is convex over the subset \(\VV \oplus C\).
Then, by Theorem 9.117, \(d_C\) is convex.
9.10.8.2. Proper Convex Functions#
Theorem 9.118 (Partial minimization for proper convex functions)
Let \(\VV\) and \(\WW\) be real vector spaces. Let \(f : \VV \oplus \WW \to \RERL\) be a proper convex function satisfying the following property:
For every \(\bx \in \VV\), there exists \(\by \in \WW\) for which \(f(\bx, \by) < \infty\).
Let \(g : \VV \to \LERL\) be defined by
Then \(g\) is convex.
Proof. We first mention that since for every \(\bx \in \VV\), there exists at least one \(\by\) such that \(f(\bx, \by) < \infty\), hence \(g(\bx) < \infty\) for every \(\bx\). This is why, the range of \(g\) is \(\LERL\). Although it still leaves open the possibility that \(g(\bx) = -\infty\) for some \(\bx \in \VV\).
We now show that \(g\) satisfies the convexity inequality.
Let \(\bx_1, \bx_2 \in \VV\) and \(t \in (0,1)\).
We consider the two cases
Both \(g(\bx_1), g(\bx_2) > -\infty\).
At least one of them equals \(-\infty\). Without loss of generality, assume that \(g(\bx_1) = -\infty\).
Case 1: \(g(\bx_1), g(\bx_2) > -\infty\)
Choose some \(\epsilon > 0\).
By the infimum property, there exist \(\by_1, \by_2 \in \WW\) such that
\[\begin{split} & f(\bx_1, \by_1) \leq g(\bx_1) + \epsilon; \\ & f(\bx_2, \by_2) \leq g(\bx_2) + \epsilon. \end{split}\]Since \(f\) is convex, hence
\[\begin{split} & f(t \bx_1 + (1-t) \bx_2, t \by_1 + (1-t) \by_2) \\ & \leq t f(\bx_1, \by_1) + (1-t) f(\bx_2, \by_2) \\ & \leq t (g(\bx_1) + \epsilon) + (1-t) (g(\bx_2) + \epsilon)\\ & = t g(\bx_1) + (1-t) g(\bx_2) + \epsilon. \end{split}\]By the definition of \(g\), we have
\[ g(t \bx_1 + (1-t) \bx_2) \leq f(t \bx_1 + (1-t) \bx_2, t \by_1 + (1-t) \by_2). \]Thus we have
\[ g(t \bx_1 + (1-t) \bx_2) \leq t g(\bx_1) + (1-t) g(\bx_2) + \epsilon. \]Since this inequality is valid for every \(\epsilon > 0\), hence
\[ g(t \bx_1 + (1-t) \bx_2) \leq t g(\bx_1) + (1-t) g(\bx_2). \]Thus \(g\) is convex for this case.
Case 2: \(g(\bx_1) = -\infty\).
To show that \(g\) is convex, we need to show that \(g(t \bx_1 +(1-t) \bx_2) = -\infty\).
Choose any \(M \in \RR\).
Since \(g(\bx_1) = -\infty\), there exists \(\by_1 \in \WW\) such that
\[ f(\bx_1, \by_1) \leq M. \]By hypothesis in the theorem, there exists \(\by_2 \in \WW\) such that
\[ f(\bx_2, \by_2) < \infty. \]In other words, \(f(\bx_2, \by_2)\) is finite.
Using the convexity of \(f\), we have
\[\begin{split} & f(t \bx_1 + (1-t) \bx_2, t \by_1 + (1-t) \by_2) \\ & \leq t f(\bx_1, \by_1) + (1-t) f(\bx_2, \by_2) \\ & \leq t M + (1-t) f(\bx_2, \by_2). \end{split}\]By definition of \(g\), we have
\[ g(t \bx_1 + (1-t) \bx_2) \leq t M + (1-t) f(\bx_2, \by_2). \]Since the inequality holds for any \(M \in \RR\) and the quantity \(f(\bx_2, \by_2)\) is finite, hence taking the limit \(M \to -\infty\) on the R.H.S., we get
\[ g(t \bx_1 + (1-t) \bx_2) = -\infty. \]Thus \(g\) is convex for this case too.
Combining the two cases, \(g\) is convex.
9.10.8.3. Extended Valued Convex Functions#
Theorem 9.119 (Partial minimization for extended valued convex functions)
Let \(\VV\) and \(\WW\) be real vector spaces. Let \(f : \VV \oplus \WW \to \ERL\) be a convex function. Let \(g : \VV \to \ERL\) be defined by
Then \(g\) is convex.
Proof. We proceed as follows.
If \(g(\bx)\) is \(\infty\) everywhere then \(\epi g\) is empty, and \(g\) is convex.
Hence assume that \(\epi g \neq \EmptySet\).
If \(\dom g\) is singleton, then also \(g\) is convex and we are done.
Hence assume the case where \(\dom g\) is not a singleton.
Let \((\bx_a, r_a)\) and \((\bx_b, r_b)\) belong to \(\epi g\).
Hence \(g(\bx_a) \leq r_a\) and \(g(\bx_b) \leq r_b\).
By definition of \(g\), we must have sequences \(\{ \bu_k \}\) and \(\{ \bv_k \}\) of \(\WW\) so that
\[ f(\bx_a, \bu_k) \to g(\bx_a) \text{ and } f(\bx_b, \bv_k) \to g(\bx_b). \]Pick some \(t \in [0,1]\).
By definition of \(g\)
\[ g(t \bx_a + (1-t) \bx_b) \leq f(t \bx_a + (1-t) \bx_b, t \bu_k + (1-t) \bv_k) \Forall k. \]By convexity of \(f\)
\[ f(t \bx_a + (1-t) \bx_b, t \bu_k + (1-t) \bv_k) \leq t f(\bx_a, \bu_k) + (1-t) f(\bx_b, \bv_k) \Forall k. \]Hence we have
\[ g(t \bx_a + (1-t) \bx_b) \leq t f(\bx_a, \bu_k) + (1-t) f(\bx_b, \bv_k) \Forall k. \]Taking limit \(k \to \infty\) on the R.H.S., we obtain
\[ g(t \bx_a + (1-t) \bx_b) \leq t g(\bx_a) + (1-t) g(\bx_b) \leq t r_a + (1-t) r_b. \]Hence the point \((t \bx_a + (1-t) \bx_b, t r_a + (1-t) r_b) \in \epi g\).
Hence \(\epi g\) is convex.
Hence \(g\) is convex.
9.10.9. Partial Minimization and Closedness#
The closedness of a function doesn’t imply the closedness of its partial minimization. The problem is that the projection operation of a closed set to a subspace doesn’t always preserve the closedness. In this subsection, we review specific conditions under which the closedness of a function is guaranteed after partial minimization.
The results in this section draw heavily on Recession Cones. The reader is encouraged to familiarize themselves with the concepts of recession cones and lineality spaces of convex sets.
We first establish the relationship between the sublevel sets of the original function and the sublevel sets of its partial minimization.
9.10.9.1. Sublevel Sets#
Lemma 9.3 (Partial minimization and sublevel-sets)
Let \(\VV\) and \(\WW\) be Euclidean spaces. Let \(f : \VV \oplus \WW \to \ERL\) be a convex function. Let \(g : \VV \to \ERL\) be defined by
Let \(G_t\) denote the set \(\sublevel(g, t) = \{ \bx \in \VV \ST g(\bx) \leq t \}\). Then
where \(\{ t_k \}\) is any nonincreasing sequence with \(t_k \downarrow t\).
We further note that the set on the R.H.S. is the projection on \(\VV\) of the set \(\sublevel(f, t_k)\) where the projection is given by \((\bx, \bz) \mapsto \bx\).
Proof. \(t_k \downarrow t\) means that
\(t_k > t\) for every \(k\).
\(t_{k+1} \leq t_k\) for every \(k\).
For every \(\epsilon > 0\), there exists a \(k\) such that \(t_k \leq t + \epsilon\).
Let \(X_t\) denote the set
We first show that \(G_t \subseteq \bigcap_{k=1}^{\infty} X_{t_k}\).
Let \(\bx \in G_t\).
Then \(g(\bx) \leq t\).
Thus \(\inf_{\bz \in \WW} f(\bx, \bz) \leq t\).
Hence for every \(\epsilon > 0\), there exists \(\bz\) such that \(f(\bx, \bz) \leq t + \epsilon\).
Since \(t_k > t\) for every \(k\), hence for every \(k\), there exists \(\bz\) such that \(f(\bx, \bz) \leq t_k\).
Hence \(\bx \in X_{t_k}\) for every \(k\).
Hence \(\bx \in \bigcap_{k=1}^{\infty} X_{t_k}\).
Hence \(G_t \subseteq \bigcap_{k=1}^{\infty} X_{t_k}\).
Now for the converse,
Let \(\bx \in \bigcap_{k=1}^{\infty} X_{t_k}\).
Then for every \(k\), \(\bx \in X_{t_k}\).
Hence for every \(k\), there exists \(\bz_k\) such that \(f(\bx, \bz_k) \leq t_k\).
Also, \(g(\bx) \leq f(\bx, \bz_k) \leq t_k\) for every \(k\).
Taking the infimum on the R.H.S., we get \(g(\bx) \leq t\).
Hence \(\bx \in G_t\).
Hence \(\bigcap_{k=1}^{\infty} X_{t_k} \subseteq G_t\).
Combining, we get
We see that the sublevel set of \(g\) is an infinite intersection of projections of a nested sequence of sublevel sets of \(f\). If the projections are closed, then the sublevel set of \(g\) is also closed. Thus, to show that \(g\) is closed, it is sufficient to show that the projections of the sublevel sets of \(f\) on \(\VV\) are closed.
9.10.9.2. Closedness Conditions I#
Theorem 9.120 (Partial minimization and closedness I)
Let \(\VV\) and \(\WW\) be Euclidean spaces. Let \(f : \VV \oplus \WW \to \RERL\) be a proper, closed and convex function.
Let \(g : \VV \to \ERL\) be defined by
Assume that there exists a vector \(\tilde{\bx} \in \VV\) and a scalar \(\gamma\) such that the set
is nonempty and compact. Then \(g\) is proper, closed and convex. Furthermore, for each \(\bx \in \dom g\), the set of points that attain the infimum of \(f(\bx, \cdot)\) over \(\WW\) is nonempty and compact.
Proof. Due to Theorem 9.119, \(g\) is convex. However, this result alone doesn’t guarantee that \(g\) is proper or closed.
We shall denote the sublevel sets of \(f\) as
We first establish that for any nonempty sublevel set \(V_t\), there is no nonzero direction of recession of the form \((\bzero, \by)\).
By hypothesis \(\VV_{\gamma}\) is nonempty since there exists a \(\bz\) such that \(f(\tilde{\bx}, \bz) \leq \gamma\).
By Definition 9.68, all nonempty sublevel sets of \(f\) have the same recession cone given by \(R_f\).
Let \((\bzero, \by) \in R_f\) be a direction of recession of \(f\).
Then \((\bzero, \by)\) is also a direction of recession of \(V_{\gamma}\).
For any \((\tilde{\bx}, \bz) \in V_{\gamma}\), such a direction of recession will satisfy
\[ f(\tilde{\bx}, \bz + \alpha \by) \leq \gamma \Forall \alpha \geq 0. \]Since, by hypothesis, the set \(\{ \bz \ST f(\tilde{\bx}, \bz) \leq \gamma \}\) is compact, hence the previous statement can be true only if \(\by = \bzero\).
Thus there is no nonzero direction of recession of \(V_{\gamma}\) of the form \((\bzero, \by)\).
Since all sublevel sets share the same recession cone, hence for any nonempty sublevel set \(V_t\), there is no nonzero direction of recession of the form \((\bzero, \by)\).
We now show that \(g\) is a closed function. For this, we shall show that the projection of every sublevel set of \(f\) to \(\VV\) is closed.
If \(V_t\) is an empty sublevel set of \(f\) then its projection to \(\VV\) is also an empty set which is a closed set.
Now let \(V_t\) be any nonempty sublevel set of \(f\).
Let \(p : \VV \oplus \WW \to \VV\) denote the projection operator given by
\[ p(\bx, \by) = \bx. \]Note that \(p\) is a linear operator.
The nullspace of this projection operator is the set of vectors of the form \((\bzero, \by)\).
Hence the nullspace of \(p\) doesn’t contain any nonzero direction of recession of \(V_t\).
Also, \(R_{V_t} \cap (\nullspace p) = \{ (\bzero, \bzero) \} \subseteq L_{V_t}\) since \((\bzero, \bzero)\) always belongs to the lineality space of \(V_t\).
Hence, due to Theorem 9.193, the projection of \(V_t\) to \(\VV\) under \(p\) is closed.
By Lemma 9.3, a sublevel set of \(g\) is an infinite intersection of projections of a nested sequence of sublevel sets of \(f\).
Since projection of every nonempty sublevel set of \(f\) is closed, hence an intersection of any sequence of such projections is closed.
Thus every sublevel set of \(g\) is closed.
Hence \(g\) is closed.
We introduce a function \(h_{\bx} : \WW \to \RERL\) as
For every \(\bx \in \dom g\), there exists \(\bz \in \WW\) such that \(f(\bx, \bz) < \infty\).
Hence for every \(\bx \in \dom g\), the function \(h_{\bx}\) is proper, closed and convex due to Theorem 9.116.
We can see that
\[ g(\bx) = \inf_{\bz \in \WW} h_{\bx}(\bz). \]By our previous argument, the function \(h_{\bx}\) has no nonzero direction of recession.
Hence the recession cone of every nonempty sublevel set of \(h_{\bx}\) is \(\{ \bzero \}\).
Then due to Theorem 9.181, every nonempty sublevel set is closed and bounded, hence compact.
Then due to Weierstrass theorem (Theorem 8.9), the set of minimizers of \(h_{\bx}\) is nonempty and compact (since one of the sublevel sets is nonempty and bounded).
We now show that \(g\) is proper.
\(g(\tilde{\bx}) = \inf_{\bz \in \WW} f(\tilde{\bx}, \bz)\).
By hypothesis, there exist \(\bz \in \WW\) such that \(f(\tilde{\bx}, \bz) \leq \gamma\).
Hence \(g(\tilde{\bx}) \leq \gamma < \infty\).
Let \(\bx \in \dom g\).
We have shown that the set of minimizers of \(h_{\bx}\) is nonempty and compact.
Hence \(g(\bx) > -\infty\) for every \(\bx \in \dom g\).
Hence \(g\) is proper.
9.10.9.3. Closedness Conditions II#
Theorem 9.121 (Partial minimization and closedness II)
Let \(\VV\) and \(\WW\) be Euclidean spaces. Let \(f : \VV \oplus \WW \to \RERL\) be a proper, closed and convex function.
Let \(g : \VV \to \ERL\) be defined by
Assume that there exists a vector \(\tilde{\bx} \in \VV\) and a scalar \(\gamma\) such that the set
is nonempty and its recession cone is equal to its lineality space. Then \(g\) is proper, closed and convex. Furthermore, for each \(\bx \in \dom g\), the set of points that attain the infimum of \(f(\bx, \cdot)\) over \(\WW\) is nonempty.
Proof. The proof is along similar lines. Due to Theorem 9.119, \(g\) is convex.
We shall denote the sublevel sets of \(f\) as
By hypothesis \(\VV_{\gamma}\) is nonempty since there exists a \(\bz\) such that \(f(\tilde{\bx}, \bz) \leq \gamma\).
Let \((\bzero, \by) \in R_f\) be a direction of recession of \(f\).
Then \((\bzero, \by)\) is also a direction of recession of \(V_{\gamma}\).
For any \((\tilde{\bx}, \bz) \in V_{\gamma}\), such a direction of recession will satisfy
\[ f(\tilde{\bx}, \bz + \alpha \by) \leq \gamma \Forall \alpha \geq 0. \]Thus for every \(\bz \in K\) and \(\alpha \geq 0\), we have \(\bz + \alpha \by \in K\).
Then \(\by\) is a direction of recession of \(K\).
By hypothesis \(R_K = L_K\).
Hence \(-\by\) is also a direction of recession of \(K\).
Thus For any \((\tilde{\bx}, \bz) \in V_{\gamma}\),
\[ f(\tilde{\bx}, \bz - \alpha \by) \leq \gamma \Forall \alpha \geq 0. \]Thus, \((\bzero, -\by)\) is also a direction of recession for \(V_{\gamma}\) due to Theorem 9.179.
Hence \((\bzero, -\by) \in R_f\).
Since both \((\bzero, \by) \in R_f\) and \((\bzero, -\by) \in R_f\), hence \((\bzero, \by) \in L_f\).
Hence \((\bzero, \by)\) is a direction along with \(f(\tilde{\bx}, \cdot)\) is constant.
Hence for any nonempty sublevel set \(V_t\) of \(f\), a direction of recession of the form \((\bzero, \by)\) is also in the lineality space of \(V_t\).
We now show that \(g\) is closed.
Let \(V_t\) be any nonempty sublevel set of \(f\).
Let \(p\) be the projection operator as defined in the proof of Theorem 9.119.
Then \(\nullspace p = \{ (\bzero, \by) \ST \by \in \WW \}\).
If \((\bzero, \by) \in R_{V_t}\) then \((\bzero, \by) \in L_{V_t}\) by the previous argument.
Hence \(R_{V_t} \cap \nullspace p \subseteq L_{V_t}\).
Hence, due to Theorem 9.193, the projection of \(V_t\) to \(\VV\) under \(p\) is closed.
Hence \(g\) is closed.
As before, we define \(h_{\bx} : \WW \to \RERL\) as a projection of \(f\) by fixing \(\bx\).
For every \(\bx \in \dom g\), \(h_{\bx}\) is proper, closed and convex.
By the previous argument \(R_{h_{\bx}} = L_{h_{\bx}}\).
Following the arguments of Theorem 10.26, the set of minimizers of \(h_{\bx}\) is nonempty.
Hence \(g(\bx)\) is finite for every \(\bx \in \dom g\).
In particular \(g(\tilde{\bx}) < \infty\) since \(K\) is nonempty.
Hence \(g\) is proper.