# Thread: Basic Solutions and Extreme Points

1. ## Basic Solutions and Extreme Points

$\displaystyle Let \hspace{1 mm} S = \{x:x^Tx \hspace{1 mm}$\leq$1\}.\hspace{1 mm}Prove\hspace{1 mm}that\hspace{1 mm}the\hspace{1 mm}extreme\hspace{1 mm}points\hspace{1 mm}of\hspace{1 mm}S\hspace{1 mm}are\hspace{1 mm}the\hspace{1 mm}points\hspace{1 mm}on\hspace{1 mm}its\hspace{1 mm}boundary.$

So $\displaystyle x$ is an extreme point of $\displaystyle S$ iff it is a basic feasible solution.

Would proof by contradiction be appropriate? Assume that the extreme points of $\displaystyle S$ are not on the boundary?

2. If I have understood correctly your question, for any linear function $\displaystyle f:S\to \mathbb{R}$ , $\displaystyle f(x)=\sum_{j=1}^nc_jx_j$ (not all $\displaystyle c_j\neq 0$ ) we have no critical points in $\displaystyle x^tx<1$ . On the other hand, $\displaystyle S$ is compact so, being $\displaystyle f$ continuous on $\displaystyle S$ we have absolute maximum and minimum on $\displaystyle S$. Necessarily this must occur on the boundary of $\displaystyle S$ : $\displaystyle x^tx=1$ .