type
status
date
slug
password
summary
tags
category
icon
Assume that we want to verify convexity of a set by drawing all lines between points within the set and checking whether the lines are contained.
Prove that it is sufficient to check only the points on the boundary. 要驗證集合的凸性，只要檢查連接邊界上的點的線就夠了。
如果集合 是凸集，則對於 中的任兩點 ，經過 和 的直線 包含在 中。
- 假設是凸的。設 為兩點。根據凸性的定義，線段完全包含在中。由於是經過和的線，因此它包含。因此也包含在中。
- 假設不是凸的。那麼， 中存在兩個點，使得經過 和 的直線 不完全包含在 中。這表示在上存在一個點。
- 由於，的邊界必定存在一點，使得線段與的邊界在某一點相交。 （否則， 將包含在 中。）
- 現在，考慮穿過 和 的線 。由於和在的邊界上，是連接邊界上的兩點的線。我們將證明 並不完全包含在 中。
- 為了矛盾起見，假設 完全包含在 中。那麼線段就完全包含在中。由於 位於直線 上，因此 上存在一點，使得 與 平行。透過作相似三角形，我們可以證明也在的邊界上。這意味著 完全包含在 中，這與我們假設 相矛盾。
因此，我們得出結論，如果不是凸的，則存在一條連接邊界上的兩點的線，並且該線不完全包含在中。這樣就完成證明了。
上面看不懂? 那麼看下面這個更一般的證明: that it is sufficient to check only the vertices of the set. 僅檢查多面體（具有有限數量頂點的集合）的頂點就足以驗證其凸性。
充分條件：假設多面體的所有頂點都是凸的。我們需要證明多面體是凸的。
設 為多胞形中的任兩點。我們需要證明線段 完全包含在多面體中。
由於多面體是多面體()，因此可以將其表示為其頂點的凸包。令 為多胞形的頂點集合。那麼可以寫成中頂點的凸組合：
其中 。
- 把它想像成一個食譜。想像一下，您正在混合不同的成分（點 ）來創建一道新菜（點 ）。權重 代表配方中每種成分的比例。條件 確保比例加起來為 100%，這表示整道菜都是由這些成分組成的。
現在，考慮線段。這條線段上的任一點都可以寫成：
由於所有頂點 都是凸的，因此所有 的係數 。因此，是中頂點的凸組合，這意味著在多胞形中。
必要條件：假設多胞形是凸的。我們需要證明它的所有頂點都是凸的。
令 為多面體的一個頂點。考慮多胞形中的任兩點 。由於多胞形是凸的，因此線段 完全包含在多胞形中。
由於是一個頂點，因此存在一個支援處多面體的超平面。令 為平行於$H$ 並且穿過 和 的超平面。那麼線段就包含在中。
由於 是一個頂點，因此它不在多面體的內部。因此， 必定位於多胞形的邊界上。由於多胞形是凸的，因此邊界是凸曲線。因此，頂點是凸的。
透過結合充分必要條件，我們得出結論：僅檢查多面體的頂點就足以驗證其凸性。
上面證明太抽象看不懂???也可以例如：考慮由平面中所有點 組成的集合 ，使得：
此集合 是一個以 為中心、半徑為 的封閉圓盤。顯然就是一個凸函數
的邊界： 的邊界是圓：代入”只要檢查連接邊界上的點的線就夠了”這個條件:
讓我們在 的邊界上取兩個點： 和 。通過 和 的線 是：
- 驗證凸性：我們需要檢查 行是否完全包含在 中。由於線 與圓相交於兩點 和，而這兩點之間的線段完全包含在 中，因此我們可以得出結論： 行完全包含在 中。
Denote by the ball of radius using the -norm. Prove that is convex for all .
有:
其中 為 -範數。
證明:
假設, 即 和。
我們需要證明對任意 , 有 。
由於 -範數滿足三角不等式:
由於 且 , 我們有:
因此, , 這說明 是一個凸集。
Given convex functions and , show that is convex, too. Prove that is not convex.
對於任意 和 , 我們有:
因此, 是凸函數。
證明 不是凸函數:
我們只需要找到一個反例。
設 和 , 顯然 和 都是凸函數。
Prove that the normalization of the softmax function is convex. More specifically prove the convexity of .
我們需要證明對任意 和 , 有:
證明如下：
先觀察到對任意 ，都有 。
然後有：
其中第三個等號是由於 函數的性質,第一個不等號是由於 函數是凹函數(即 )。是一個凸函數
Prove that linear subspaces, i.e., , are convex sets
為了證明 是凸集,我們需要證明對於任意 和 , 有 。
- 因為 , 所以有 和 。
- 對於 , 我們有:
- 因此, 。
Show that for twice-differentiable convex functions we can write for some .
首先,由於 是二次可微,我們可以使用泰勒展開得到原式:
接下來,我們要證明 ,因為 是凸函數。
- 凸函數的定義是: 對於任意 和 , 有:
對於 ,取 , 則有:
這說明 ,因為如果 ,則上述不等式將不成立
Given a convex set and two vectors and , prove that projections never increase distances, i.e., .
假設 是凸集, 和 是兩個向量。記 和 為 和 在 上的投影。我們要證明:
證明如下:
- 由於 是 在 上的投影,根據投影的性質,有: (y同理)
- 取 和 ,可得:
- 兩式相加有:
最後取平方根就是答案
上一篇
Deep learning Guide 13: Stochastic Gradient Descent 隨機梯度下降
下一篇
Deep learning Guide 11: The Transformer Architecture
- Author:tom-ci
- URL:https://www.tomciheng.com//article/Convexity
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!