1
$\begingroup$

I would like some clarification on a proof about convexity. This is from Boyd and Vandenberghe's Convex Optimization book. and it has been answered before. It's been over 10 years since the questions was posted, and my question is not necessarily about the proof, but the reasoning bheind it. Therefore, I think it's OK to post it here. Question 2.1 ask the states the following.

Let $C \subseteq \mathbb{R}^n$ be a convex set, with $x_1, ..., x_k \in C$, and let $\theta_1, ..., \theta_k \in \mathbb{R}$ satisfy $\theta_i \geq 0, \theta_1 + ... + \theta_k = 1$. Show that $\theta_1x_1 + ... + \theta_kx_k \in C$. (The definition of convexity is that this holds for k = 2; you must show it for an arbitrary k.) Hint. Use induction on k.

I initially I thought this is trivial because

  1. $x_1, ..., x_k \in C$
  1. The restrictions on $\theta$, namely $\theta_i \geq 0, \theta_1 + ... + \theta_k = 1$, satisfy the conditions for a convex combination.

Yet, I didn't know how to go about the proof. I tried writing it out as

\begin{align} \theta_1x_1 + \theta_2x_2 + ... + \theta_kx_k =&\\ =& \ \theta_1x_1 + \theta_2x_2 + ... + (1 - \theta_1 - ... - \theta_{k-1})x_k \end{align}

Then I thought all I had to do was to show that each term in the last summation belongs to $C$. I tried reasoning how to show that $\theta_i x_i$ belong to $C$ knowing that $\theta \in [0,1]$. But then, I thought that if $x_i = (5,5)$ and $C$ is the unit circle with center on $(5,5)$, $\theta_i x_i = (0,0)$ if $\theta = 0$, and $(0,0) \notin C$.

In the solution manual, the authors say

This is readily shown by induction from the definition of convex set. We illustrate the idea for $k = 3$, leaving the general case to the reader. Suppose that $x_1, x_2, x_3 ∈ C$, and $θ_1 + θ_2 + θ_3 = 1$ with $θ_1, θ_2, θ_3 ≥ 0$. We will show that $y = θ_1x_1 + θ_2x_2 + θ_3x_3 ∈ C$. At least one of the $θ_i$ is not equal to one; without loss of generality we can assume that $θ_1 \neq 1$. Then we can write $$y = θ_1x_1 + (1 − θ_1)(µ_2x_2 + µ_3x_3)$$ where $µ_2 = θ_2/(1 − θ_1)$ and $µ_2 = θ_3/(1 − θ_1)$. Note that $µ_2, µ_3 ≥ 0$ and $µ_1 + µ_2 = (θ_2 + θ_3)/(1 − θ_1) = (1 − θ_1)/(1 − θ_1) = 1$. Since $C$ is convex and $x_2, x_3 ∈ C$, we conclude that $µ_2x_2 + µ_3x_3 ∈ C$. Since this point and $x_1$ are in $C$, $y ∈ C$.

My question (if a bit convoluted) is: what makes one assume at least one $\theta \neq 1$ and use it as the starting point for the proof? If I were to bet my money, I'd say there are other ways to prove this, but what's the reasoning that would make one follow the steps in the results shown in the manual?

$\endgroup$
1
  • $\begingroup$ Samael Manasseh provided a good and intuitive explanation and that I accepted as the answer. I will welcome other intuitive explanations, though. $\endgroup$
    – Jxson99
    Oct 23, 2023 at 3:45

1 Answer 1

2
$\begingroup$

When I first solved this problem I solved it basically the same way as the manual. This is roughly how I remember coming up with it:

In proofs of this kind is it often helpful to consider the case $k=3$ so when considering this question, one would want to be able to somehow use the known previous case $k=2$ (this is how induction works) so if you have a convex combination $a_1 x_1 +a_2x_2 + a_3x_3 $, how can we reduce this to say a linear combination of only two terms? well you can just write:

$$a_1 x_1 + (1-a_1) \left( \frac{a_2x_2 + a_3x_3}{1-a_1} \right) $$

here is where $\theta_1 \neq 1 $ comes from : one you have reached this point in your though process you should think " what prevents $1-a_1$ from being $0$ ? if this happened then my proof wold be wrong", from here you add the justification they gave and explain why you can assume that this is not the case

I hope this helps

$\endgroup$
1
  • $\begingroup$ Thanks a lot, Samael Manasseh. This does help and I'll flag it as the answer. $\endgroup$
    – Jxson99
    Oct 23, 2023 at 3:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .