3  Convex set

Author

Affiliation

Your name

Maybe your workplace?

4 Some standard convex sets

4.1 Affine sets

An affine set is one that contains the entire line through any two of its points. Concretely, if \(x_1,x_2\) lie in an affine set \(S\), then for all $ hetaR$ the combination

\[ x(\theta) = \theta x_1 + (1-\theta) x_2 \]

also lies in \(S\). Special cases:

For \(\theta \in[0,1]\), \(x(\theta)\) traces the line segment between \(x_1\) and \(x_2\).

For \(\theta<0\) or \(\theta>1\), it extends beyond the endpoints.

import numpy as np
import matplotlib.pyplot as plt

# Define two points x1 and x2
x1 = np.array([1, 2])
x2 = np.array([4, 0])

# Sample theta values
thetas = np.array([-0.2, 0.0, 0.6, 1.0, 1.2])
points = [(theta * x1 + (1 - theta) * x2) for theta in thetas]

# Generate full line between extended range of theta
theta_full = np.linspace(-0.4, 1.4, 100)
line = np.array([theta * x1 + (1 - theta) * x2 for theta in theta_full])

# Plot
plt.figure(figsize=(6, 4))
plt.plot(line[:, 0], line[:, 1], 'k-', label='Line through x1 and x2')
plt.scatter(*x1, color='red', zorder=5)
plt.text(x1[0]+0.1, x1[1]+0.1, 'x1', fontsize=9)
plt.scatter(*x2, color='blue', zorder=5)
plt.text(x2[0]+0.1, x2[1]-0.3, 'x2', fontsize=9)

# Plot labeled theta points
for theta, pt in zip(thetas, points):
    plt.scatter(pt[0], pt[1], s=40)
    plt.text(pt[0]+0.1, pt[1]+0.1, f'θ = {theta}', fontsize=8)

plt.axis('equal')
plt.grid(True, linestyle='--', alpha=0.5)
plt.title('Affine Set: Line through x1 and x2')
plt.xlabel('x')
plt.ylabel('y')
plt.legend()
plt.tight_layout()
plt.show()

Example: The solution set of linear equation

\[ {x| Ax=b} \]

is affine

Every affine set is a solution set of linear equations

Every affine set \(S \subseteq \mathbb{R}^n\) can be expressed as: \[ S = \{x \in \mathbb{R}^n \mid A x = b\} \] for some matrix \(A \in \mathbb{R}^{m \times n}\) and vector \(b \in \mathbb{R}^m\).

Proof sketch

Let \(S\) be an affine set. Pick any point \(x_0 \in S\), and define: \[ V = \{x - x_0 \mid x \in S\} \]

This set \(V\) is a vector subspace of \(\mathbb{R}^n\), because affine sets are closed under affine combinations, and subtraction cancels the translation offset.

Since \(V\) is a subspace, it can be written as the null space of some matrix \(A \in \mathbb{R}^{m \times n}\): \[ V = \{x \in \mathbb{R}^n \mid A x = 0\} \]

Hence the original affine set is: \[ S = \{x \in \mathbb{R}^n \mid A(x - x_0) = 0\} = \{x \in \mathbb{R}^n \mid A x = A x_0\} \]

Let \(b = A x_0\). Then: \[ S = \{x \in \mathbb{R}^n \mid A x = b\} \]

So \(S\) is the solution set of a system of linear equations.

✅ Q.E.D.