Tag Archives: 凸集

凸函數

本文的閱讀等級:中級 令 為一個非空凸集,也就是說,給定任意兩點 和 ,點 屬於 (見“凸組合、凸包與凸集”)。凸函數 (convex function) 是一個實函數 滿足下列性質:對於任意 且 , 。 若定義式等號僅發生於 和 ,我們稱 是一個嚴格凸函數。相反的,若 是一個 (嚴格) 凸函數,則 稱為 (嚴格) 凹函數。圖一顯示一個單變量凸函數 ,任一弦 (連結點 和 的紅色線段) 必位於函數 (藍色曲線) 的上方。下面列舉一些單變量凸函數:,, 和 。對於 ,仿射函數 和向量 -範數 ,,都是凸函數 (見“向量範數”)。本文將討論凸函數的一些性質和判別方法。 Advertisements

Posted in 線性代數專欄, 仿射幾何 | Tagged , , , , , , | 2 Comments

數值域

本文的閱讀等級:高級 給定一 階矩陣 ,矩陣譜 (spectrum) 是所有特徵值所形成的集合,表示為 ;譜半徑 (spectrum radius) 是包含特徵值的最小半徑 (原點是圓中心),記為 (見“譜半徑與矩陣範數”)。類似矩陣譜的表達方式, 的數值域 (numerical range 或 field of values) 定義如下: , 或以 Rayleigh 商表示為 。 這兩個定義是等價的,證明見“Hermitian 矩陣特徵值的變化界定”。為了測量數值域的大小, 的數值半徑 (numerical radius) 定義為包含數值域的最小圓半徑: 。 矩陣譜 是一離散集合,稍後我們將證明數值域 是一連通緊凸集 (connected compact convex set)。如同矩陣譜的功用,數值域也可以幫助我們了解矩陣的本質,尤其是不具特殊形態的一般矩陣。

Posted in 特徵分析, 線性代數專欄 | Tagged , , , , , , , , | Leave a comment

線性規劃 (二):端點與基解

本文的閱讀等級:中級 線性規劃的標準型問題具有下列形式: 其中 是一個 階矩陣, 是 維向量, 是 維向量, 是 維未知向量 (見“線性規劃 (一):標準型問題”)。如果 無解,線性規劃問題即不成立。因為這個緣故,我們要求 ,即約束等式的數目不多於未知數的數目。如果 有線性相關的列向量 (row vector),表示系統存在冗餘的約束條件 (可將多餘條件刪除),譬如,,,或約束條件彼此矛盾 (此時系統無解),譬如,,。為了避免捲入這些無謂的情況,以下假設 有 個線性獨立的列向量,即 ,且 (若 ,則 有唯一解)。

Posted in 線性代數專欄, 應用之道 | Tagged , , , , , | 5 Comments

多胞形

本文的閱讀等級:中級 在最佳化領域,多胞形 (polytope) 是一種應用廣泛的特殊凸集[1]。多胞形可以存在於任何有限維的幾何座標空間,多邊形是二維多胞形,多面體是三維多胞形, 的多胞形稱為 多胞形。淺白地說,多胞形的邊界都是平的。本文討論的多胞形限定為有界閉集,定義如下:若 是屬於 的有限向量集,凸包 稱為一多胞形。因為凸包是凸集,凸包定義的多胞形自然是一有界閉凸集 (見“凸組合、凸包與凸集”)。本文將介紹多胞形的幾何性質,並推導有界閉凸集的一個重要定理,它指引了一條解決線性規劃問題的捷徑。

Posted in 線性代數專欄, 仿射幾何 | Tagged , , , | Leave a comment

凸組合、凸包與凸集

本文的閱讀等級:初級 幾何座標空間 的一個向量 表示該向量端點的座標。點與座標向量具有一對一的對應關係,因為這個緣故,我們經常以座標向量代表點。本文介紹一種別於子空間與仿射空間 (子空間的平移) 的向量集。我們稱一個向量集 是凸集 (convex set),若給定任兩點 和 ,點 屬於 。淺白地說,在凸集中,任兩個點皆可「看見」彼此,連接這兩點的直線段不含集合以外的點。見圖一的例子。比較特別的是, 所包含的子空間與仿射空間都是凸集。

Posted in 線性代數專欄, 仿射幾何 | Tagged , , , , | 5 Comments