1

Can someone provide intuition & proof for why a ray is convex, I don't see the sum to $1$ constraints for theta :

A ray of the form $\left\{x_{0}+\theta v \mid \theta \geq 0\right\}$, where $v$ != $0$ is convex, but not affine. It is a convex cone if its base $x_{0}$ is $0.$

From Boyd & Vandenberghe Convex Optimization pg. 27

Rodrigo de Azevedo
  • 1
stateless
  • 121
  • 7

2 Answers2

2

I will prove the case where $x_0 = 0$, since convexity is invariant under translation.

According to the definition, your ray is of the form, for a fixed $\mathbf{x} \in \mathbb{R}^d$,

$$R= \{\lambda\mathbf{x} : \lambda \geqslant 0\}$$

Now let $\mathbf{y},\mathbf{z} \in R$, so $\mathbf{y} = y\mathbf{x}$ and $\mathbf{z} = z\mathbf{x}$ for some $y,z\geqslant 0$ by definition of the ray. As this is a subset of a $2$-dimensional linear (affine, if $x_0 \neq 0$) subspace, all convex combinations will require at most two terms without any redundancy (it is not hard to show for many-termed sums, I will leave this as an exercise to help understand the proof). So for all $t \in [0,1]$, it suffices to show:

$$t\mathbf{y} + (1-t)\mathbf{z} \in R$$

The terms $t\mathbf{y}, (1-t)\mathbf{z}$ are the same as $ty\mathbf{x}$ and $(1-t)z\mathbf{x}$ by the result above, and as $t$ and $(1-t)$ are both at least $0$, $t\mathbf{y}$ and $(1-t)\mathbf{z}$ are in the ray. As such, the above sum is just:

$$(ty + (1-t)z)\mathbf{x}$$

which is in the ray, so the ray is convex.

Generally, proving shapes convex involve showing the conditional:

$$\{\mathbf{x}\}_i \in X \Longrightarrow \sum_i \lambda_i \mathbf{x}_i \in X$$

for $\sum \lambda_i =1$ and each $\lambda_i \geqslant 0$, holds true. You can see how the above proof is essentially just this conditional.

Geometrically and intuitively, a shape is convex when the line between any two points is in the shape. I dare you to find two points in a ray where the line between them is not in the ray.

While I Am
  • 2,380
0

According to the definition of convex sets, we can prove it.

A ray is given by a set $C$: $ \{x_0 + \theta v| \theta\geq0 \}$. Suppose $x_1$ and $x_2$ belong to $C$, i.e., $x_1\in C, x_2\in C$.

In other words, $x_1 = x_0 + \theta_1 v$, $x_2 = x_0 + \theta_2 v$, $\theta_1\geq0, \theta_2\geq0 $.

According to the definition of convex sets, we have to prove that $\alpha x_1 + (1-\alpha)x_2 \in C$, where $0 \leq \alpha \leq 1$.

$$ \begin{align}\alpha x_1 + (1-\alpha)x_2 & = \alpha x_0 + \alpha\theta_1 v + (1-\alpha)x_0 + (1-\alpha)\theta_2 v \\ & = \alpha\theta_1 v +x_0 + (1-\alpha)\theta_2 v =x_0 + [\alpha\theta_1+\theta_2(1-\alpha)]v \tag{1}. \end{align} $$

Since $0 \leq \alpha \leq 1$ and $\theta_1, \theta_2 \geq 0$, we can get that $[\alpha\theta_1+\theta_2(1-\alpha)] \geq 0$, equation (1) satisfies the definition of a ray. Therefore, a ray is convex.

If we want to prove whether equation (1) is affine, according to the definition of affine sets, $\alpha$ can be a negative number, such as -100. Hence $\alpha\theta_1+\theta_2(1-\alpha) \leq 0$, i.e., equation (1) does not satisfy the definition of ray. So a ray is not affine.

When $x_0$ is $0$, $\{\theta v|v\geq 0 \}$ is a convex cone, according to the definition of cone.

Wills
  • 1