February 20th, 2019, 06:41 AM  #1 
Senior Member Joined: Apr 2014 From: Glasgow Posts: 2,142 Thanks: 726 Math Focus: Physics, mathematical modelling, numerical and computational solutions  Simplexes
I am currently studying the following book on convex optimization: https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf However, I'm confused about the part on simplexes, their visualization and what makes them different from polyhedra (see page 33): Simplexes Simplexes are another important family of polyhedra. Suppose the $\displaystyle k + 1$ points $\displaystyle v_0, . . . , v_k \in \mathbb{R}^n$ are affinely independent, which means $\displaystyle v_1 − v_0, . . . , v_k − v_0$ are linearly independent. The simplex determined by them is given by $\displaystyle C = \text{conv}\{v_0, . . ., v_k\}=\{\theta_0v_0 + . . . + \theta_kv_k  \theta \succeq 0, I^T\theta = 1 \}$ where I represents a vector with all entries equal to one. ... Example 2.5: Some common simplexes:  a 1dimensional simplex is a line segment;  a 2dimensional simplex is a triangle (including its interior); and  a 3dimensional simplex is a tetrahedron" My questions are: 1. Is the key feature of a simplex the fact that it is a polyhedron made up from the convex hull of a set of (affinely independent) points rather than, say, a set of hyperplanes or halfspaces? Is it possible to construct a simplex without referring to an explicit set of points by, for example, determining particular vertices of interest along known hyperplanes? 2. What if the number of points in the convex set is greater than the number of dimensions? E.g. a 2D set with five points (k=4; the set $\displaystyle C = {v_0, v_1, v_2, v_3, v_4}$)? Is it a simplex? If not, is it because the points in this no longer become affinely independent? Any help is appreciated 
February 20th, 2019, 03:47 PM  #2 
Senior Member Joined: Sep 2016 From: USA Posts: 578 Thanks: 345 Math Focus: Dynamical systems, analytic function theory, numerics 
You should think about the "standard simplex" for gaining intuition. This is the simplex obtained by taking your vertices to be the origin, and the points $(1,0,\dots,0), (0,1,0,\dots,0), \dots, (0,\dots,0,1)$. for the remaining $n$ vertices. The importance is that a simplex is a compact convex polytope making it an extremely nice space to work in. To answer your questions: 1. There is no need to have coordinates in order to talk about simplices which is why we so often just assume we are working with the standard simplex. Every simplex is homeomorphic to one another. This is analogous to the way we work with $C([0,1])$ as our model space for compactly support continuous functions. 2. Only $n+1$ points are required since if you a simplex generated by $n+1$ affinely independent vectors, $\{v_0,\dots,v_n\}$ and you add one more vertex to the set, $w$, it is easy to prove that only 2 things can be true. (You should do this as an exercise) (i) $w$ lies in the convex hull of the previous vectors, i.e. $w$ lies in the simplex generated by $\{v_0,\dots,v_n\}$. (ii) There exists exactly one index, $i \in \{0,\dots,n\}$, such that $v_i$ lies in the convex hull generated by the vectors $\{v_0,\dots,v_n,w\} \setminus \{v_i\}$. 
February 20th, 2019, 07:14 PM  #3 
Senior Member Joined: Feb 2016 From: Australia Posts: 1,769 Thanks: 626 Math Focus: Yet to find out. 
Ever watched any lectures from Boyd? Quite a character

February 21st, 2019, 01:30 AM  #4 
Senior Member Joined: Apr 2014 From: Glasgow Posts: 2,142 Thanks: 726 Math Focus: Physics, mathematical modelling, numerical and computational solutions 
Much thanks for that. I wouldn't know where to start with proving those things (I'm absolutely terrible at proofs), but I'll give them a shot anyway.
Last edited by Benit13; February 21st, 2019 at 01:53 AM. 
February 21st, 2019, 06:46 AM  #5 
Senior Member Joined: Apr 2014 From: Glasgow Posts: 2,142 Thanks: 726 Math Focus: Physics, mathematical modelling, numerical and computational solutions 
I asked a friend at work about proving those things and he recommended "Baby Rudin" and a book "Understanding Analysis" by Stephen Abbot. Time to get cracking! 

Tags 
simplexes 
Thread Tools  
Display Modes  
