Re: [其他] extreme point證明

[Vulpix (Sebastian)]

※ 引述《c96a111 (拉~阿~!)》之銘言：
: Prove that the extreme point of S={x | (x^t)x≦1}
: are the point on its boundary.
: 這題小弟我想好久了...
: 真的不知道該怎去證明端點在邊界上
: 希望有高手能幫忙一下

Given x \in S

i) x = 0

  take y = [1 0 ... 0]^t, z = -y

  then x = y/2 + z/2

  hence x is not an extreme point of S

ii) x \in int(S), x≠0  i.e. (x^t)x < 1, x≠0

  take y = x/|x|, z = 0

  then x = |x|y + (1-|x|)z

  hence x is not an extreme point of S (∵0 < |x| < 1)

iii) x \in bd(S)  i.e. (x^t)x = 1

  suppose that x is not an extreme point of S
                                                      __
  then there is a segment in S passing through x, say yz

  let u be the unit vector pointing inward to S along this segment
                           ^^^^^^^^^^^^^^^^^^^^
                           this means that (u^t)x≦0
                           since x is the outward normal vector of S at x

  then the segment may be parametrized as x + su, where s is a real number

  because the segment is contained in S

  so [(x + su)^t](x + su)≦1 <=> 0≦s≦-2(u^t)x

  then y = x + au, z = x + bu, where 0≦a,b≦-2(u^t)x

  and x = ry + (1-r)z = x + (ra + (1-r)b)u for some r

  so r = b/(b-a)

  since 0<r<1, we have b>0, b>a, a<0

  but a<0 is impossible, which is a contradiction

  it means that x is an extreme point

Combining i, ii and iii

we conclude that the extreme points of S = {x | (x^t)x≦1} are

the points on its boundary

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.248.46.14
推 c96a111     :謝謝v大
→ c96a111     :請問 "\" 是什麼意思
推 jacky7987   :LaTeX的符號 \in是屬於的那個符號
推 jacky7987   :不過為什麼可以確定0<r<1呢?
→ jacky7987   :感覺就圖形上來說y,z應該都在x的外面 要用他們的線性
→ jacky7987   :會有點像外點公式那樣?
→ Vulpix      :只是因為假設 "x is not an extreme point"。
推 jacky7987   :恩了解 因為可以找到一些點使得他更大或更小?
推 jacky7987   :或是更好的解釋是 極點只能用極點表示?
推 c96a111     :第一部分 |X|有特別意義嗎 還是隨便寫個未知數也可以
推 jacky7987   :x的長度...
→ c96a111     :我想問說 我如果寫成y=x/a z=0
→ c96a111     :那 x=ay+(1-a)z表示 他不是extreme point
→ THEJOY      :a>1會出問題
→ c96a111     :不太懂為什麼(u^t)x≦0 想不太通
推 jacky7987   :挑的 我們挑反方向的所以小於0
→ c96a111     :u要向內能想像 x的方向難理解
→ jacky7987   :畫出原點拉到x你就知道x的方向了
※ 編輯: Vulpix          來自: 111.248.46.14        (10/16 00:23)
→ Vulpix      :其實不見得需要u向內。u如果向外，s就是負的而已。
→ Vulpix      :(u^t)x≦0的意思是 u, x 的夾角大於等於90度。