My Math Forum  

Go Back   My Math Forum > College Math Forum > Linear Algebra

Linear Algebra Linear Algebra Math Forum


Thanks Tree1Thanks
  • 1 Post By SDK
Reply
 
LinkBack Thread Tools Display Modes
February 20th, 2019, 06:41 AM   #1
Senior Member
 
Joined: Apr 2014
From: Glasgow

Posts: 2,157
Thanks: 732

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 1-dimensional simplex is a line segment;
- a 2-dimensional simplex is a triangle (including its interior); and
- a 3-dimensional 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
Benit13 is offline  
 
February 20th, 2019, 03:47 PM   #2
SDK
Senior Member
 
Joined: Sep 2016
From: USA

Posts: 635
Thanks: 401

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\}$.
Thanks from Benit13
SDK is offline  
February 20th, 2019, 07:14 PM   #3
Senior Member
 
Joined: Feb 2016
From: Australia

Posts: 1,834
Thanks: 650

Math Focus: Yet to find out.
Ever watched any lectures from Boyd? Quite a character
Joppy is offline  
February 21st, 2019, 01:30 AM   #4
Senior Member
 
Joined: Apr 2014
From: Glasgow

Posts: 2,157
Thanks: 732

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.
Benit13 is offline  
February 21st, 2019, 06:46 AM   #5
Senior Member
 
Joined: Apr 2014
From: Glasgow

Posts: 2,157
Thanks: 732

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!
Benit13 is offline  
Reply

  My Math Forum > College Math Forum > Linear Algebra

Tags
simplexes



Thread Tools
Display Modes






Copyright © 2019 My Math Forum. All rights reserved.