While self-studying Rockafellar's Convex Analysis, I am struggling with the proof on Rockafellar's note on page 6 about proving the definition of the affine hull. Note that I don't want the intuitive definition of the affine hull as most of the existing answers did. Rather I want a rigorous proof of the following section.

Therefore given any $S \subset R^n$ there exists a unique smallest affine set containing S (namely the intersection of the collection of affine sets $M$ such that $M\supset S$). This set is called affine hull of S and is denoted by aff S. It can be proved as an exercise, that aff S consists of the vectors of the form $\lambda_1 x_1 + \ldots+\lambda_m x_m$, such that $x_i \in S$ and $\lambda_1 + \ldots + \lambda_m = 1$.

Now I see the proof other way around, that is given S an affine space any convex combination of the points will lie in S. Also intuitively we understand that the points inside the hull has to be comvex combination in order to fall inside S, otherwise it will go outside. But I can't prove it. Please help.

  • $\begingroup$ I have often found Stephen Boyd's convex optimization to be a better self study book rather than rockafella.. Maybe you can try that it $\endgroup$
    – rostader
    Apr 18 at 6:52
  • $\begingroup$ I agree but, I find Rochafellar really concise. I fear I would not be able to cover Boyd in my lifetime. $\endgroup$ Apr 18 at 12:49
  • $\begingroup$ @rostader That book has two authors. $\endgroup$ Apr 18 at 12:50
  • 1
    $\begingroup$ @HirakSarkar I've answered your question I believe, in great detail. I also struggled with this topic when reading Vick's Homology Theory. $\endgroup$ Aug 2 at 5:18

Usually when you have a space $X(S)$ associated to a set $S$, that is the smallest set satisfying a certain property $P$ (in this case, being affine), to prove that another set $Y$ is $X(S)=Y$, what you do is 1) Prove that $Y$ is contained in every set with property $P$ (which is what you did, every convex combination of points of $S$ lies in every affine space containing $S$) and 2) Prove that $Y$ has the property $P$ (in this case, prove that all convex combinations of points in $S$ form an affine set), then $$Y\subseteq X(S)$$ by point 1) and $$X(S)\subseteq Y$$ being $X(S)$ the $\textit{smallest}$ set satisfying $P$, so you reach the conclusion $$X(S)=Y$$So, can you prove that all convex combinations of points in $S$ form an affine set? in which case you're done

Edit Addressing the comment: I don't know if there is a way to directly prove that every element of $\text{aff}(S)=X(S)$ is a convex combination of elements from $S$ from the definition of $X(S)$. The definition of $X(S)$ only tells you that it is the intersection of all affine spaces containing $S$. In particular, it doesn't tell you what's the form of a generic element of $X(S)$, so to prove that every element $v\in X(S)$ is a convex combination of elements in $S$, the only way I see would be to prove that a point $v$ that is not a convex combination of elements from $S$ doesn't belong to $X(S)$ by showing that there is an affine set $A$ containing $S$ and not containing $v$. The best choice for this affine set $A$ is the set $CC(S)$ of all convex combinations of elements in $S$ and if you prove that $CC(S)$ is an affine set, then by definition $$X(S)\subseteq CC(S)$$ which proves that every element in $X(S)$ is indeed a convex combination of elements from $S$. So in the end, it all comes down to prove that $CC(S)$ is an affine space, thus it contains $X(S)$.

  • $\begingroup$ Thanks, actually I indeed could do the proof in that way, but I was wondering if there is a way to prove $\sum_i \lambda_i = 1$ when we consider the smallest intersection of the affine spaces. $\endgroup$ Apr 18 at 12:45

Let $S \subset \Bbb{R}^n$ be any set and define its convex hull to be the intersection of all convex sets containing $S$, where a convex set $C$ is defined to be a set such that the segment between any two points lies entirely in $C$.

Let $X = \{ \sum_{i=1}^n t_i x_i: \sum_i t_i = 1, x_i \in S\}$ be the set of convex combinations of points in $S$.

The proof that $S \subset X$ is straight-forward, however, I will go through it (since the version I needed about convex hulls of a $p$-simplex is slightly different).

It is enough to show that $X$ is a convex set since then by definition of $S$ being the intersection of all convex sets, we have automatically $S \subset X$.

Consider the segment as $0 \leq t \leq 1$: $s(t) = (1-t)x + ty$ where $z= \sum_{x\in S} t_x x \in X$ and $y = \sum_{x \in S} s_x x \in X$ and where $\sum_{x\in S} s_x = 1$ and $\sum_{x \in S} t_x = 1$ are both convergent sums. If you need to, impose that $t_x, s_x = 0$ for all but a finite number or $x \in S$.

Then we have:

$$ s(t) = (1-t)\sum_x t_x z + t\sum_x s_x x = \\ \sum_x \left((1-t) t_x + t s_x \right) x $$

Then $r_x = (1-t)t_x + ts_x$ is such that $\sum_x r_x = 1$ since: $\sum_x r_x = \sum_x t_x - t \sum_x t_x + t\sum_x s_x$. Then two sums on the right cancel each other, and you're left with $\sum_x t_x = 1$. If in addition we needed positive $t_x, s_x \geq 0$, then $r_x \geq 0$ as well in that case (some problems specify non-negativity of the coefficients).

Thus we've proven that $X$ is convex or that $S \subset X$.

But not only that, we proved that the set of all "convergent" convex combinations is convex (i.e. not just usual, finite convex combinations).

Now, to prove the converse to me seems a little more tricky. We want to show that $S$ is closed under taking convex combinations of points of $S$ since then, by definition of $X$ we would have $X \subset S$.

Let $y = \sum_{x \in S} t_x x$ be a convex combination of the points of $S$, i.e. $\sum_{x \in S} t_x = 1$ (and if the problem requires, also specify that $t_x \geq 0, \forall x$).

Then $y = \sum_{x \in S} t_x x = t_{x'}x' + \sum_{x \in S \\ x \neq x'} t_x x$, where $x'$ is chosen so that $t_{x'} \neq 0$, which must exist since $\sum_{x \in S} t_x = 1$.

Now write $y = t_{x'} x' + (1 - t_{x'})\sum_{x \in S \\ x \neq x'} \dfrac{t_x}{1-t_{x'}} x \tag{1}$.

Clearly, $\sum_{x \in S \\ x \neq x'} \dfrac{t_x}{1 - t_{x'}} = 1$. Now, unless there is some way to do induction "on an arbitrary subset" of $\Bbb{R}^n$, we must now use the fact that our convex combinations are finite sums ($t_x = 0$ for all but a finite number of $x \in S$) Clearly then, by induction we have that the sum on the write is a strictly smaller convex combination and of course the base case is true. On the other hand $y$ split up that way as in (1) is itself a convex combination of two points of $S$. And we're done. $\square$

The above is clearly general enough to handle the case of $p$-simplices as well, which is what I was after when reading Vick's Homology Theory - an Introduction to Algebraic Topology. That is the remark right above Proposition 1.2 on page 2.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.