MCMC幾何問題框架可推導(dǎo)許多凸優(yōu)化理論台腥。
定義：設(shè) 為
中非空子集：
-
極小公共點(diǎn)問題 (minimal common problem): 找出
與
軸的公共點(diǎn)中第
極小公共點(diǎn)問題 -
極大交叉點(diǎn)問題 (maximal crossing problem): 找出將
極大交叉點(diǎn)問題
一脐往、求不等式約束優(yōu)化問題對(duì)偶問題：
考慮不等式約束優(yōu)化問題：
其中：
是
的非空子集，
瘤礁，
是給定函數(shù)梅尤。
-
引入：
- 擾動(dòng)約束集合
- 函數(shù)
- 擾動(dòng)約束集合
顯然對(duì)于
有
巷燥。
原始函數(shù) )
定義如下:
另一方面亡脑，
稱 為對(duì)偶函數(shù)或 Lagrangian函數(shù)邀跃。
二蛙紫、線性規(guī)劃的對(duì)偶問題
考慮如下形式的線性規(guī)劃：
其中坑傅，
，
唁毒，
浆西。
由對(duì)偶函數(shù)知近零，對(duì)于
有
對(duì)于其它的
有
，因此對(duì)偶問題為
三漓摩、對(duì)偶間隙
定義：若 成立入客，稱為弱對(duì)偶(weak duality)成立；若
桌硫，則稱強(qiáng)對(duì)偶(strong duality)成立或?qū)ε奸g隙(duality gap)為零鞍泉。
Theorem (弱對(duì)偶定理)
極小公共點(diǎn)問題與極大交叉點(diǎn)問題最優(yōu)值分別為 和
，則
