謝宗翰的隨筆

凸分析 (Convex Analysis) 可以說是 最佳化問題中最重要的數學分析工具之一，其本質在於 若能識別一個 (最小化)最佳化問題使其形成凸最佳問題；亦即 成本函數 為 convex 且其 拘束集合 為 convex set，則該問題的 局部最佳解(local optimum) 等同 全域最佳解(globally optimum)。 但是若該我們所具有的成本函數本質不凸 (nonconvex) 的時候，是否可找出其他方式來進行分析 ? 以下介紹的 logconcavity 便為其中一種方式 =================== Definition: Logarithmically Concave Function 函數 $f : \mathbb{R}^n \to \mathbb{R}$ 為 log-concave 若下列條件成立： 1. 對任意 $x \in dom\{f\}$，$f(x) >0$ 2. $\log f$ 為 concave。 =================== Comments: a. 上述定義亦可用於 convex function 若 條件 2 改為 $\log f$ 為 convex。 b. 一般而言，我們可進一步放寬條件 1. 使其允許 $f =0 $ 且 定義 $\log f(x) = -\infty$ 。我們稱此 $f$ 為 log-concave 若其 擴展值域函數 (extended-value function) $\log f$ 為 concave。 c. log-concave 函數有另外一種等價定義：亦即，給定 $x,y \in \mathbb{R}^n$ 且 $\lambda \in [0,1]$ 下列不等式滿足 \[ f(\lambda x +(1 - \lambda)y ) \ge f(x)^\lambda f(y)^{1-\lambda} \] 在此不贅述有興趣讀者可參閱 [1]。 由上述 logconcave 與 logconvex 函數的 定義我們可立即得到以下結果： ================== FACT: $f$ 為 log-convex 若且為若 $1/f$ 為 log-concave 。 ==================