Basic Solutions and Extreme Points

**bulldog106** · April 12th 2011, 06:55 PM

$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 $x$ is an extreme point of $S$ iff it is a basic feasible solution.

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

**FernandoRevilla** · April 13th 2011, 03:39 AM

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

Thread: Basic Solutions and Extreme Points

LinkBack

Thread Tools

Display

Basic Solutions and Extreme Points

Similar Math Help Forum Discussions

differentiability and extreme points question

Extreme Points

Lagrange finding extreme points.

Analyze the function for local extreme points, concavity and inflection points

Crit points, extreme values, and basic algebra

Search Tags