.md .pdf

repository open issue

Contents

9.1. Convex Optimization

Main references for this section are [5, 7, 10].

9.1.1. Convex Optimization Problems

Definition 9.1 (Convex optimization problem general form)

Let $\mathbb{V}$ be an $n$-dimensional real vector space. Let $f:\mathbb{V}\to \mathbb{R}$ be a convex function with $S=\mathrm{dom}f$. Let $C\subseteq S\subseteq \mathbb{V}$ be a convex set.

A mathematical optimization problem of the form

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & \mathbf{x}\in C\end{array}$$

is known as a convex optimization problem.

In other words, a convex optimization problem minimizes a convex function over a convex set. We can write the optimal value of the minimization problem as

$$p^{\ast }=inf\{f(\mathbf{x})|\mathbf{x}\in C\}.$$

The set of optimal points for the minimization problem is

$$X_{\text{opt}}=\{\mathbf{x}\in C|f(\mathbf{x})=p^{\ast }\}.$$

Note

1. $f$ is the objective function (or cost function) being minimized.

2. $\mathbf{x}$ is the optimization variable.

3. $C$ is the feasible set. Any $\mathbf{x}\in C$ is a feasible point.

4. The problem is feasible if $C\ne \varnothing$.

5. If $C=\varnothing$, then the problem is infeasible.

6. If the problem is infeasible then $p^{\ast }=\mathrm{\infty }$.

7. If the problem is feasible then $p^{\ast }<\mathrm{\infty }$.

8. If $p^{\ast }=-\mathrm{\infty }$, then the problem is unbounded below.

9. We say that ${\mathbf{x}}^{\ast }$ is an optimal point for the minimization problem if $f({\mathbf{x}}^{\ast })=p^{\ast }$.

10. If $X_{\text{opt}}$ is nonempty, then we say that the optimal value $p^{\ast }$ is attained at some point.

11. It is possible that $p^{\ast }$ is finite and yet the optimal set is empty.

Remark 9.1 (Closedness of the feasible set)

Some authors prefer to define convex optimization as the minimization of a convex function over a closed and convex set.

1. We have not insisted that $C$ be a closed set in the general definition of convex optimization problem.

2. The closedness of $C$ is an additional property which can provide additional guarantees on the existence of an optimal point. We shall introduce it whenever needed in the discussion below.

3. Recall from Theorem 8.170 that a closed and convex set $C$ is an intersection of all the halfspaces that contain it. Let $\{A_i{\}}_{i\in I}$ be the set of halfspaces that contains $C$.

4. Then, each half space can be written as

   $$A_i=\{\mathbf{x}\in \mathbb{V}|⟨\mathbf{x},{\mathbf{a}}_i⟩\le b_i\}.$$

5. Thus, $\mathbf{x}\in C$ is equivalent to $⟨\mathbf{x},{\mathbf{a}}_i⟩\le b_i$ for every $i\in I$.

6. This gives us the motivation to consider the feasible set in the form of intersection of sublevel sets of convex functions.

Majority of convex optimization problems can be transformed into a functional form where the constraints are expressed in the form of sublevel sets of convex functions and the level sets of affine functions.

9.1.1.1. Convex Optimization Standard Form

Definition 9.2 (Convex optimization problem standard form)

Let $\mathbb{V}$ be an $n$-dimensional real vector space. A mathematical optimization problem of the form

(9.1)$$\begin{array}{rlrl}& \text{minimize }& & f_0(\mathbf{x})\\ & \text{subject to }& & f_i(\mathbf{x})\le 0,& i=1,\dots ,m\\ & & & h_j(\mathbf{x})=0,& j=1,\dots ,p\end{array}$$

with optimization variable $\mathbf{x}\in \mathbb{V}$ is called a convex optimization problem in standard form if

1. The objective function $f_0:\mathbb{V}\to \mathbb{R}$ is a convex function.

2. The inequality constraint functions $f_i:\mathbb{V}\to \mathbb{R}$ are convex functions for $i=1,\dots ,m$.

3. The equality constraint functions $h_j:\mathbb{V}\to \mathbb{R}$ are affine functions for $j=1,\dots ,p$.

Observation 9.1 (Discussion on the convex optimization standard form)

1. The domain of the problem is given by

   $$\mathcal{D}=\mathrm{dom}{f}_0\cap \bigcap _{i=1}^m\mathrm{dom}{f}_i\cap \bigcap _{j=1}^p\mathrm{dom}{h}_j.$$

2. $\mathrm{dom}{h}_j=\mathbb{V}$ for every $j=1,\dots ,p$ since $h_j$ are affine functions.

3. Thus,

   $$\mathcal{D}=\mathrm{dom}{f}_0\cap \bigcap _{i=1}^m\mathrm{dom}{f}_i.$$

4. By definition $\mathrm{dom}{f}_i$ are convex for $i=0,\dots ,m$. Hence $\mathcal{D}$ is convex.

5. The feasible set $C$ is given by

   $$C=\mathrm{dom}{f}_0\cap \bigcap _{i=1}^m{f}_i^{-1}(-\mathrm{\infty },0]\cap \bigcap _{j=1}^p{h}_j^{-1}(0).$$

6. Then, $f_i^{-1}(-\mathrm{\infty },0]$ are sublevel sets of convex functions hence they are also convex sets.

7. By Theorem 4.211, the level sets of affine functions are affine sets.

8. Thus, $h_j^{-1}(0)$ is an affine set. Hence, it is a convex set.

9. Thus, $C$ is an intersection of convex sets.

10. Thus, $C$ is a convex set.

11. We note that we can rewrite the standard form as

    $$\begin{array}{rlrl}& \text{minimize }& & f_0(\mathbf{x})\\ & \text{subject to }& & \mathbf{x}\in C\end{array}$$

    to match with Definition 9.1.

Remark 9.2 (Adding closedness of objective and constraint functions)

Suppose we add an additional requirement that the function $f_i$ for $i=0,\dots ,m$ are closed.

1. Recall from Definition 3.64 that a function is closed if all its sublevel sets are closed.

2. In particular, this means that the domain of a closed function is also closed.

3. Thus, $\mathcal{D}$ is a closed set.

4. Then, $f_i^{-1}(-\mathrm{\infty },0]$ are closed sets since $f_i$ are closed functions.

5. Since $\mathbb{V}$ is finite dimensional, hence affine sets are closed. Hence $h_j^{-1}(0)$ is closed for every $j=1,\dots ,p$.

6. Thus, $C$ is an intersection of closed and convex sets.

7. Thus, $C$ is a closed and convex set.

8. Recall from Theorem 3.92 that a function is closed if and only if it has a closed epigraph.

9. Also, recall from Theorem 3.119 that a function is closed if and only if it is l.s.c. (lower semicontinuous).

10. Further, recall from Theorem 8.172 that every convex function has a closure which is l.s.c. (hence closed) given by its lower semicontinuous hull and the closure of a convex function is also convex.

11. Thus, if any of the $f_i$ for $i=0,\dots ,m$ is convex but not a closed function, we can replace it by its lower semicontinuous hull to convert it to a closed convex function. This way, be can bring such problems to the standard form for convex optimization.

Remark 9.3 (Comparison of two forms)

We have seen two forms of describing convex optimization problems.

1. Definition 9.1 describes it as minimizing a convex function over a convex set.

2. Definition 9.2 describes it in the form of minimizing a convex objective function with convex inequality constraints and affine equality constraints.

3. As seen in comments above, the second form can be converted into the first form.

4. The first form is more general. It is very useful in establishing the theoretical properties of convex optimization problems.

5. The second form is more useful from practical perspective. Almost all real life convex optimization problems can be reduced to this form. It is easier to describe algorithms to solve convex optimization problems in terms of this form.

In the sequel, we will liberally use either form for proving theoretical results and developing algorithms.

Definition 9.3 (Concave function maximization problem)

Let $\mathbb{V}$ be an $n$-dimensional real vector space. A mathematical optimization problem of the form

(9.2)$$\begin{array}{rlrl}& \text{maximize }& & f_0(\mathbf{x})\\ & \text{subject to }& & f_i(\mathbf{x})\le 0,& i=1,\dots ,m\\ & & & h_j(\mathbf{x})=0,& j=1,\dots ,p\end{array}$$

with optimization variable $\mathbf{x}\in \mathbb{V}$ is called a concave maximization problem if

1. The objective function $f_0:\mathbb{V}\to \mathbb{R}$ is a concave function.

2. The inequality constraint functions $f_i:\mathbb{V}\to \mathbb{R}$ are convex functions for $i=1,\dots ,m$.

3. The equality constraint functions $h_j:\mathbb{V}\to \mathbb{R}$ are affine functions for $j=1,\dots ,p$.

Remark 9.4 (Concave maximization as a convex optimization problem)

We note that maximizing $f_0$ is same as minimizing $-f_0$. Further, if $f_0$ is concave then $-f_0$ is convex. Thus, (9.2) is equivalent to the problem

$$\begin{array}{rlrl}& \text{minimize }& & -f_0(\mathbf{x})\\ & \text{subject to }& & f_i(\mathbf{x})\le 0,& i=1,\dots ,m\\ & & & h_j(\mathbf{x})=0,& j=1,\dots ,p\end{array}$$

which is a convex optimization problem in standard form. With an abuse of notation, we shall call a concave function maximization program also a convex optimization program.

9.1.1.2. Proper Convex Functions

It is useful to extend these definitions to proper convex functions as objective functions and/or inequality constraint functions.

Definition 9.4 (Optimization problem general form for proper convex functions)

Let $\mathbb{V}$ be an $n$-dimensional real vector space. Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper convex function with $S=\mathrm{dom}f$. Let $X\subseteq \mathbb{V}$ be a convex set.

A mathematical optimization problem of the form

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & \mathbf{x}\in X\end{array}$$

is known as a convex optimization problem for proper convex functions.

In other words, this problem minimizes a proper convex function over a convex set. We can write the optimal value of the minimization problem as

$$p^{\ast }=inf\{f(\mathbf{x})|\mathbf{x}\in X\}.$$

The set of feasible points is given by $C=X\cap \mathrm{dom}f$ which is a convex set.

The set of optimal points for the minimization problem is

$$X_{\text{opt}}=\{\mathbf{x}\in C|f(\mathbf{x})=p^{\ast }\}.$$

Definition 9.5 (Convex optimization problem standard form for proper convex functions)

Let $\mathbb{V}$ be an $n$-dimensional real vector space. A mathematical optimization problem of the form

(9.3)$$\begin{array}{rlrl}& \text{minimize }& & f_0(\mathbf{x})\\ & \text{subject to }& & f_i(\mathbf{x})\le 0,& i=1,\dots ,m\\ & & & h_j(\mathbf{x})=0,& j=1,\dots ,p\end{array}$$

with optimization variable $\mathbf{x}\in \mathbb{V}$ is called a convex optimization problem in standard form for proper convex functions if

1. The objective function $f_0:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ is a proper convex function.

2. The inequality constraint functions $f_i:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ are proper convex functions for $i=1,\dots ,m$.

3. The equality constraint functions $h_j:\mathbb{V}\to \mathbb{R}$ are affine functions for $j=1,\dots ,p$.

The reader can check that the definitions of problem domain, feasible set, optimal value, optimal solutions/points, etc. can be easily extended by using the effective domains of $f_0,\dots ,f_m$.

9.1.1.3. Local and Global Optima

Theorem 9.1 (Local minimum is a global minimum in convex optimization)

Let $f:\mathbb{V}\to \mathbb{R}$ be a convex function. Let $C\subseteq \mathrm{dom}f$ be a convex set. Consider the problem of minimizing $f$ over $C$. Let ${\mathbf{x}}^{\ast }$ be locally optimal for $f$ over $C$. Then, ${\mathbf{x}}^{\ast }$ is globally optimal for $f$ over $C$.

In other words,

$$f(\mathbf{y})\ge f({\mathbf{x}}^{\ast })\mathrm{\forall }\mathbf{y}\in C.$$

Proof. Since ${\mathbf{x}}^{\ast }$ is a local minimum of $f$ over $C$, hence there exists $r>0$ such that

$$f({\mathbf{x}}^{\ast })=inf\{f(\mathbf{z})|\mathbf{z}\in B[\mathbf{x},r]\cap C\}.$$

In other words, $f(\mathbf{x})\ge f({\mathbf{x}}^{\ast })$ for every $\mathbf{x}\in B[\mathbf{x},r]\cap C$.

1. Let $\mathbf{y}\in C$ be any point such that $\mathbf{y}\ne {\mathbf{x}}^{\ast }$.

2. We need to show that $f(\mathbf{y})\ge f({\mathbf{x}}^{\ast })$.

3. Let $t\in (0,1]$ be such that $\mathbf{z}={\mathbf{x}}^{\ast }+t(\mathbf{y}-{\mathbf{x}}^{\ast })\in B[\mathbf{x},r]$.

4. Since $C$ is convex, hence $\mathbf{z}\in C$ as ${\mathbf{x}}^{\ast },\mathbf{y}\in C$ and $\mathbf{z}$ is their convex combination.

5. Thus, $\mathbf{z}\in B[\mathbf{x},r]\cap C$.

6. By the local optimality condition

   $$\begin{array}{rl}f({\mathbf{x}}^{\ast })& \le f(\mathbf{z})\\ & =f({\mathbf{x}}^{\ast }+t(\mathbf{y}-{\mathbf{x}}^{\ast }))\\ & =f((1-t){\mathbf{x}}^{\ast }+t\mathbf{y})\\ & \le (1-t)f({\mathbf{x}}^{\ast })+tf(\mathbf{y}).\end{array}$$

   We used the fact that $f$ is convex.

7. Cancelling and rearranging the terms, we get $tf({\mathbf{x}}^{\ast })\le tf(\mathbf{y})$.

8. Since $t>0$, hence it reduces to $f({\mathbf{x}}^{\ast })\le f(\mathbf{y})$.

9. Thus, ${\mathbf{x}}^{\ast }$ is indeed globally optimal.

Corollary 9.1 (Local minimum is a global minimum in for proper convex functions)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper convex function. Let $X$ be a convex subset of $\mathbb{V}$. Consider the problem of minimizing $f$ over $X$. Let ${\mathbf{x}}^{\ast }$ be locally optimal for $f$ over $X$. Then, ${\mathbf{x}}^{\ast }$ is globally optimal for $f$ over $X$.

In other words,

$$f(\mathbf{y})\ge f({\mathbf{x}}^{\ast })\mathrm{\forall }\mathbf{y}\in X.$$

Proof. We note that the feasible set is $C=X\cap \mathrm{dom}f$. Since both $X$ and $\mathrm{dom}f$ are convex, hence $C$ is convex.

1. If $C=\varnothing$, then there are no feasible points. Hence, no local/global optima.

2. We now consider the case where $C\ne \varnothing$.

3. Following the argument in Theorem 9.1, if ${\mathbf{x}}^{\ast }$ is locally optimal for $f$ over $C$, then it is globally optimal for $f$ over $C$.

4. Consequently, it is globally optimal for $f$ over $X$ as $f(\mathbf{x})=\mathrm{\infty }>f({\mathbf{x}}^{\ast })$ for every $\mathbf{x}\in X\setminus \mathrm{dom}f$.

The argument can be modified to show that if $f$ is strictly convex, then a locally optimal point for $f$ is strictly globally optimal point.

Theorem 9.2 (Local minimum is strict global minimum for strictly convex functions)

Let $f:\mathbb{V}\to \mathbb{R}$ be a strictly convex function. Let $C\subseteq \mathrm{dom}f$ be a convex set. Let ${\mathbf{x}}^{\ast }$ be locally optimal for $f$ over $C$. Then, ${\mathbf{x}}^{\ast }$ is strictly globally optimal for $f$ over $C$.

In other words,

$$f(\mathbf{y})>f({\mathbf{x}}^{\ast })\mathrm{\forall }\mathbf{y}\in C.$$

Proof. There exists $r>0$ such that $f(\mathbf{x})\ge f({\mathbf{x}}^{\ast })$ for every $\mathbf{x}\in B[\mathbf{x},r]\cap C$.

1. Let $\mathbf{y}\in C$ be any point such that $\mathbf{y}\ne {\mathbf{x}}^{\ast }$.

2. Let $t\in (0,1)$ be such that $\mathbf{z}={\mathbf{x}}^{\ast }+t(\mathbf{y}-{\mathbf{x}}^{\ast })\in B[\mathbf{x},r]$.

3. Since $C$ is convex, hence $\mathbf{z}\in C$ as ${\mathbf{x}}^{\ast },\mathbf{y}\in C$ and $\mathbf{z}$ is their convex combination.

4. Thus, $\mathbf{z}\in B[\mathbf{x},r]\cap C$.

5. Note that $\mathbf{z}=(1-t){\mathbf{x}}^{\ast }+t\mathbf{y}$. Thus, $\mathbf{z}$ is distinct from ${\mathbf{x}}^{\ast }$ and $\mathbf{y}$ and lies in the line segment between them.

6. By the local optimality condition

   $$\begin{array}{rl}f({\mathbf{x}}^{\ast })& \le f(\mathbf{z})\\ & =f((1-t){\mathbf{x}}^{\ast }+t\mathbf{y})\\ & <(1-t)f({\mathbf{x}}^{\ast })+tf(\mathbf{y}).\end{array}$$

   We used the fact that $f$ is strictly convex.

7. Cancelling and rearranging the terms, we get $tf({\mathbf{x}}^{\ast })<tf(\mathbf{y})$.

8. Since $t>0$, hence it reduces to $f({\mathbf{x}}^{\ast })<f(\mathbf{y})$.

9. Thus, ${\mathbf{x}}^{\ast }$ is indeed strictly globally optimal.

Corollary 9.2 (Local minimum is strict global minimum for proper strictly convex functions)

Let $f:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be a proper strictly convex function. Let $X$ be a convex subset of $\mathbb{V}$. Let ${\mathbf{x}}^{\ast }$ be locally optimal for $f$ over $X$. Then, ${\mathbf{x}}^{\ast }$ is strictly globally optimal for $f$ over $X$.

In other words,

$$f(\mathbf{y})>f({\mathbf{x}}^{\ast })\mathrm{\forall }\mathbf{y}\in X.$$

9.1.1.4. Optimal Sets

The optimal sets of a convex optimization problem are also convex.

Theorem 9.3 (Optimal set is convex for a convex optimization problem)

Let $f:\mathbb{V}\to \mathbb{R}$ be a convex function. Let $C\subseteq \mathrm{dom}f$ be a convex set. Let the optimal value for the minimization of $f$ over $C$ be given by

$$p^{\ast }=inf\{f(\mathbf{x})|\mathbf{x}\in C\}.$$

Let the optimal set (the set of optimal points) be given by

$$X_{\text{opt}}=\{\mathbf{x}\in C|f(\mathbf{x})=p^{\ast }\}.$$

Then, $X_{\text{opt}}$ is a convex set.

Proof. If $X_{\text{opt}}$ is empty, then it is convex trivially. Now consider the case where $X_{\text{opt}}$ is nonempty.

1. Let $\mathbf{x},\mathbf{y}\in X_{\text{opt}}$.

2. Then, $\mathbf{x},\mathbf{y}\in C$.

3. Let $t\in [0,1]$.

4. Let $\mathbf{z}=t\mathbf{x}+(1-t)\mathbf{y}$.

5. Since $C$ is convex, hence $\mathbf{z}\in C$. Thus, $\mathbf{z}\in \mathrm{dom}f$.

6. Since $f$ is convex, hence

   $$f(\mathbf{z})\le tf(\mathbf{x})+(1-t)f(\mathbf{y})=t{p}^{\ast }+(1-t)p^{\ast }=p^{\ast }.$$

7. But $p^{\ast }=inf\{f(\mathbf{x})|\mathbf{x}\in C\}$.

8. Thus, $f(\mathbf{z})\ge p^{\ast }$.

9. Combining, the two inequalities, we get $p^{\ast }=f(\mathbf{z})$.

10. Thus, $\mathbf{z}\in X_{\text{opt}}$.

11. Thus, for every $\mathbf{x},\mathbf{y}\in X_{\text{opt}}$ and every $t\in [0,1]$, $\mathbf{z}=t\mathbf{x}+(1-t)\mathbf{y}\in X_{\text{opt}}$.

12. Thus, $X_{\text{opt}}$ is indeed convex.

Theorem 9.4 (Optimal points for minimization of strictly convex functions)

Let $f:\mathbb{V}\to \mathbb{R}$ be a strictly convex function. Let $C\subseteq \mathrm{dom}f$ be a convex set. Then, the minimization problem

$$\begin{array}{rlrl}& \text{minimize }& & f(\mathbf{x})\\ & \text{subject to }& & \mathbf{x}\in C\end{array}$$

has at most one optimal point.

Proof. Let the optimal value for the minimization of $f$ over $C$ be given by

$$p^{\ast }=inf\{f(\mathbf{x})|\mathbf{x}\in C\}.$$

Let the optimal set (the set of optimal points) be given by

$$X_{\text{opt}}=\{\mathbf{x}\in C|f(\mathbf{x})=p^{\ast }\}.$$

1. By Theorem 9.1, $X_{\text{opt}}$ is a convex set.

2. If $X_{\text{opt}}$ is empty or a singleton, there is nothing more to prove.

3. For contradiction, assume that there are two distinct points $\mathbf{x},\mathbf{y}\in X_{\text{opt}}$.

4. We have $p^{\ast }=f(\mathbf{x})=f(\mathbf{y})$.

5. Let $\mathbf{z}=\frac{1}{2}\mathbf{x}+\frac{1}{2}\mathbf{y}$.

6. Thus, it is a convex combination of $\mathbf{x}$ and $\mathbf{y}$.

7. By convexity of $X_{\text{opt}}$, $\mathbf{z}\in X_{\text{opt}}$. Thus, $f(\mathbf{z})=p^{\ast }$.

8. By strict convexity of $f$

   $$f(\mathbf{z})<\frac{1}{2}f(\mathbf{x})+\frac{1}{2}f(\mathbf{y})=p^{\ast }.$$

9. This contradicts the fact that $p^{\ast }$ is the optimal value for the minimization problem.

10. Thus, $X_{\text{opt}}$ must be either empty or a singleton.

11. Thus, the minimization problem has at most one optimal point.

9.1.2. Concave Objective Functions

Theorem 9.5 (Minimization of concave function and relative interior)

Let $\mathbb{V}$ be an $n$-dimensional real normed linear space. Let $f:\mathbb{V}\to \mathbb{R}$ be a concave function with $S=\mathrm{dom}f$. Let $C\subseteq S$ be a convex set. Consider the problem of minimizing $f$ over $C$. Let the optimal value be given by

$$p^{\ast }=inf\{f(\mathbf{x})|\mathbf{x}\in C\}.$$

Let the set of optimal points for the minimization problem be given by

$$X_{\text{opt}}=\{\mathbf{x}\in C|f(\mathbf{x})=p^{\ast }\}.$$

If $X_{\text{opt}}$ contains a relative interior point of $C$, then $f$ must be constant over $C$; i.e.,

$$X_{\text{opt}}=C.$$

Proof. Assume that $\mathbf{x}\in \mathrm{ri}C\cap X_{\text{opt}}$.

1. Let $\mathbf{y}\in C$ be any vector distinct from $\mathbf{x}$.

2. Since $\mathbf{x}\in \mathrm{ri}C$, hence due to Theorem 8.144, there exists $s>1$ such that $\mathbf{z}=\mathbf{x}+(s-1)(\mathbf{x}-\mathbf{y})\in C$. $\mathbf{z}$ is a point behind $\mathbf{x}$ on the line from $\mathbf{y}$ to $\mathbf{x}$ which belongs to $C$.

3. Letting $t=\frac{1}{s}$ we can rewrite it as

   $$\mathbf{x}=t\mathbf{z}+(1-t)\mathbf{y}.$$

4. Thus, $\mathbf{x}$ is a convex combination of $\mathbf{z}$ and $\mathbf{y}$.

5. By concavity of $f$, we have

   $$f(\mathbf{x})\ge tf(\mathbf{z})+(1-t)f(\mathbf{y}).$$

6. Since $\mathbf{x}$ is an optimal point over $C$ and $\mathbf{z},\mathbf{y}\in C$, hence $f(\mathbf{x})\le f(\mathbf{z})$ and $f(\mathbf{x})\le f(\mathbf{y})$.

7. Thus,

   $$f(\mathbf{x})\ge tf(\mathbf{z})+(1-t)f(\mathbf{y})\ge tf(\mathbf{x})+(1-t)f(\mathbf{x})=f(\mathbf{x}).$$

8. This can be true only if $f(\mathbf{x})=tf(\mathbf{z})+(1-t)f(\mathbf{y})$ which in turn implies that $f(\mathbf{x})=f(\mathbf{z})=f(\mathbf{y})$.

9. Thus, $f$ must be constant over $C$.

Corollary 9.3 (Linear functions attain minimum only at boundary points)

Let $\mathbb{V}$ be an $n$-dimensional real normed linear space. Let $f:\mathbb{V}\to \mathbb{R}$ be a nonzero linear functional. Let $C\subseteq \mathbb{V}$ be a convex set. Then, $f$ cannot attain a minimum at any relative interior point of $C$.

In other words, $f$ can attain a minimum only at the relative boundary of $C$ (if it does attain a minimum over $C$).

Proof. We note that every linear functional is also concave.

1. Let $\mathbf{x}\in \mathrm{ri}C$.

2. Then, there exists $r>0$ such that $B(\mathbf{x},r)\cap \mathrm{aff}C\subseteq C$.

3. Since $f$ is linear, hence $f$ cannot be constant over $B(\mathbf{x},r)\cap \mathrm{aff}C$.

4. Thus, by Theorem 9.5, it cannot attain a minimum at $\mathbf{x}$.

previous

9. Convex Optimization

next

9.2. Projection on Convex Sets