Convex optimization book - solution - exercise - 2.2 - intersection with a line is convex

Introduction

This tutorial provides a step-by-step guide to understanding a key exercise in convex optimization, specifically Exercise 2.2 from the book "Convex Optimization" by Stephen Boyd and Lieven Vandenberghe. The exercise explores the properties of convex and affine sets through their intersections with lines. This guide will clarify how to demonstrate that the intersection of convex sets is convex and that the intersection of affine sets is affine.

Step 1: Understand the Definitions

Before diving into the problem, it's essential to grasp the definitions of convex and affine sets.

• Convex Set: A set ( C ) is convex if for any two points ( x, y \in C ) and any ( \lambda ) such that ( 0 \leq \lambda \leq 1 ), the point ( \lambda x + (1 - \lambda)y ) is also in ( C ).
• Affine Set: A set ( A ) is affine if it contains all affine combinations of its points. This means for any points ( x, y \in A ) and any scalars ( \alpha, \beta ) such that ( \alpha + \beta = 1 ), the point ( \alpha x + \beta y ) is also in ( A ).

Step 2: Show Convexity of Intersection with a Line

To demonstrate that the intersection of a convex set with any line is convex, follow these steps:

1. Select a Convex Set: Let ( C ) be a convex set in ( \mathbb{R}^n ).
2. Define a Line: Consider a line ( L ) defined by points ( p ) and direction ( d ): [ L(t) = p + td \quad \text{for } t \in \mathbb{R} ]
3. Identify Intersection: The intersection ( C \cap L ) consists of all points on the line ( L ) that are also in the set ( C ).
4. Pick Points in the Intersection: Let ( x_1, x_2 \in C \cap L ). This means both points are expressible as: [ x_1 = p + t_1 d \quad \text{and} \quad x_2 = p + t_2 d ]
5. Show Convexity: For any ( \lambda ) where ( 0 \leq \lambda \leq 1 ), consider the point: [ x = \lambda x_1 + (1 - \lambda)x_2 = \lambda(p + t_1 d) + (1 - \lambda)(p + t_2 d) = p + (\lambda t_1 + (1 - \lambda)t_2)d ] Since ( \lambda t_1 + (1 - \lambda)t_2 ) is a linear combination of ( t_1 ) and ( t_2 ), ( x ) lies on the line ( L ) and is in ( C ) (because ( C ) is convex). Thus, ( x \in C \cap L ).

Step 3: Show Affinity of Intersection with a Line

Next, we need to show that the intersection of affine sets with any line is affine.

1. Select an Affine Set: Let ( A ) be an affine set in ( \mathbb{R}^n ).
2. Define a Line: Use the same line ( L ) defined earlier.
3. Identify Intersection: Consider the intersection ( A \cap L ).
4. Pick Points in the Intersection: Let ( x_1, x_2 \in A \cap L ).
5. Show Affinity: For scalars ( \alpha, \beta ) such that ( \alpha + \beta = 1 ): [ x = \alpha x_1 + \beta x_2 ] Since ( x_1 ) and ( x_2 ) are in ( A ), and ( A ) is affine, ( x ) is also in ( A ). Furthermore, ( x ) lies on the line ( L ), thus ( x \in A \cap L ).

Conclusion

In this tutorial, we explored how to demonstrate that the intersection of convex sets with lines is convex and that the intersection of affine sets with lines is affine. Understanding these properties is fundamental in convex optimization and can be applied in various mathematical and real-world contexts, including economics and engineering. Next, consider practicing with different sets and lines to solidify your understanding of these concepts.