跳到主要內容

發表文章

目前顯示的是 六月, 2015的文章

[凸分析] 淺談 Logconcavity

凸分析 (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 。
==================
Proof:
$(\Rightarrow)$ 假設 $f$…