一、論述題
- 簡述超平面分離住册、嚴(yán)格超平面分離咕晋、以及正常超平面分離定義以及成立條件雹拄。
- 分離超平面定理
設(shè)和
是
中的非空凸集,若
和
不相交掌呜,則存在一個的超平面分離
和
滓玖,即存在向量
滿足
- 嚴(yán)格超平面分離
定義:集合、
和超平面
质蕉,對于所有
和
呢撞,如果
二者之一始終成立,則稱
是
和
的嚴(yán)格分離超平面或
嚴(yán)格分離
和
饰剥。
- 嚴(yán)格超平面分離定理
設(shè)和
是
中的非空凸集殊霞,若
和
不相交,且
為閉集汰蓉,則存在一個的超平面嚴(yán)格分離
和
绷蹲。
- 正常分離超平面
定義:對于集合、
和超平面
,若
或
成立祝钢,則稱 是
和
的正常分離超平面或
正常分離
和
比规。
- 分析討論凸函數(shù)回收函數(shù)與其函數(shù)值增減性之間的關(guān)系。
-
回收函數(shù)定義
定義:
對于一個凸函數(shù)拦英,它的回收函數(shù)(Recession function)定義為:
其中
是一個給定的方向蜒什。回收函數(shù)表示了凸函數(shù)在“遠(yuǎn)離原點(diǎn)”的極限行為疤估,即隨著
增大灾常,函數(shù)值相對于
的增長速度。
-
增減性對回收函數(shù)的影響
①如果原函數(shù)在某方向
上是單調(diào)遞增的铃拇,那么回收函數(shù)
也會表現(xiàn)出單調(diào)遞增的趨勢钞瀑。因為原函數(shù)的增長速度隨著
的增大會趨向于某個常數(shù),而這個常數(shù)會反映出函數(shù)在遠(yuǎn)離原點(diǎn)時的增長趨勢慷荔。
② 如果原函數(shù)在某方向
上是單調(diào)遞減的雕什,那么回收函數(shù)
會表現(xiàn)為單調(diào)遞減∠跃В回收函數(shù)的值趨向于負(fù)的常數(shù)贷岸,反映出在遠(yuǎn)離原點(diǎn)時,函數(shù)值的變化趨于某個負(fù)值磷雇。
- 簡述極小共同問題與極大交叉問題并寫出等式約束優(yōu)化原始問題與對偶問題凰盔。
定義:設(shè)為
中非空子集:
-
極小公共點(diǎn)問題 (minimal common problem): 找出
與
軸的公共點(diǎn)中第
個分量最小的點(diǎn)。
-
極大交叉點(diǎn)問題 (maximal crossing problem): 找出將
包含于其“上閉半空間”的超平面與
軸的交點(diǎn)中第
個分量最大的點(diǎn)倦春。
- 簡述梯度法與次梯度法基本原理與收斂性質(zhì)。
梯度法 (Gradient Method)
- 基本原理:
梯度法用于求解無約束凸優(yōu)化問題落剪,其基本思想是通過迭代的方法沿著目標(biāo)函數(shù)的梯度方向進(jìn)行優(yōu)化睁本。每次迭代更新:
其中是步長
是目標(biāo)函數(shù)
在點(diǎn)
處的梯度。
- 收斂性:
①對于光滑的凸函數(shù)忠怖,梯度法通常具有線性收斂性呢堰。
② 對于強(qiáng)凸函數(shù),梯度法的收斂速度更快凡泣,通常是二次收斂枉疼。
③收斂速度受步長的影響,步長選擇得當(dāng)時能保證較快的收斂鞋拟。
次梯度法 (Subgradient Method)
- 基本原理:
次梯度法是梯度法的推廣骂维,適用于不可微的凸函數(shù)。每次迭代沿著目標(biāo)函數(shù)的次梯度方向進(jìn)行更新:
其中贺纲,
是目標(biāo)函數(shù)在點(diǎn)
處的次梯度航闺。
- 收斂性:
①次梯度法對一般凸函數(shù)也具有漸近收斂性。
② 收斂速度通常較慢,通常為次線性收斂潦刃,即侮措,但對于非光滑函數(shù),仍然有效乖杠。
總的來說分扎,梯度法適用于光滑問題,收斂性較好胧洒;次梯度法適用于非光滑問題畏吓,收斂速度較慢但仍然有效。
二略荡、計算題
- 令
為定義在
上的二次函數(shù)庵佣,試求該函數(shù)的回收函數(shù)以及常值空間
。
- 回收函數(shù)
的定義為:
- 計算
首先計算 :
展開:
因此汛兜, 為:
- 計算回收函數(shù)
回收函數(shù)是:
分解為:
- 如果
巴粪,則:
所以:
- 對于非零的方向
,回收函數(shù)的值趨于:
顯然粥谬, 時:
綜合上述情況肛根,回收函數(shù) 的顯式表達(dá)式為:
- 因此常值空間
- 寫出集合
的所有極點(diǎn)構(gòu)成的集合。
解答:
- 利用 MC/MC 對偶求解如下線性規(guī)劃問題的對偶問題形式:
其中 .
這里:
-
是決策變量漏策。
-
是目標(biāo)函數(shù)的系數(shù)向量派哲。
-
是
個不等式約束。
對偶問題的構(gòu)建
根據(jù) MC/MC對偶 的思想掺喻,我們引入 拉格朗日乘子 對應(yīng)于每個不等式約束
芭届。
拉格朗日函數(shù) 定義為:
其中 是非負(fù)的拉格朗日乘子向量。
接下來我們分步驟構(gòu)建對偶問題感耙。
- 拉格朗日函數(shù)的極小化
為了將原問題轉(zhuǎn)化為對偶形式褂乍,我們對 進(jìn)行極小化,得到:
將拉格朗日函數(shù)整理一下:將 相關(guān)的項提取出來:
對于固定的 即硼,為了使
有界(或極刑悠),我們要求:
這表示 可以表示為
-加權(quán)的
只酥,即:
- 對偶目標(biāo)函數(shù)
在滿足 的條件下褥实,拉格朗日函數(shù)的極小值為:
因此,對偶問題的目標(biāo)函數(shù)為:
- 對偶問題的約束
為了使拉格朗日函數(shù) 有界裂允,我們得到
的約束條件:
此外损离,由于 是拉格朗日乘子,對應(yīng)于不等式約束绝编,所以必須滿足非負(fù)性:
- 對偶問題形式
將以上結(jié)果總結(jié)草冈,得到原問題的 對偶問題:
4.定義函數(shù):
計算其共軛函數(shù)以及二次共軛函數(shù)。
- 我們需要計算
- 首先,考慮目標(biāo)函數(shù)
怎棱,對其求導(dǎo):
令其為零哩俭,得到:
- 平方兩邊,解出
和
的關(guān)系
對方程兩邊平方拳恋,得到:
展開并整理得到:
因此凡资, 可以表示為:
- 帶入原式求共軛函數(shù)
現(xiàn)在將 代入目標(biāo)函數(shù)
,計算:
因此谬运,共軛函數(shù) 為:
- 二次共軛函數(shù)
二次共軛函數(shù) 是對共軛函數(shù)
再次應(yīng)用共軛操作隙赁。由于
只在
取有限值,因此
會恢復(fù)原函數(shù)
梆暖。因此伞访,二次共軛函數(shù)是:
并且
對于
。
5.定義函數(shù):
計算次微分 .
-
對于
部分:
- 若
轰驳,次微分
厚掷。
- 若
,次微分
级解。
- 若
冒黑,次微分
。
- 若
-
對于
部分:
- 導(dǎo)數(shù)是:
勤哗。
- 該部分在
內(nèi)是光滑的抡爹。
- 導(dǎo)數(shù)是:
-
合并兩部分次微分:
- 當(dāng)
:
。
- 當(dāng)
:
芒划。
- 當(dāng)
:
冬竟。
- 當(dāng)
- 定義
中集合:
計算 C 在 ,
兩點(diǎn)處的切錐與法錐。
-
在點(diǎn)
:
- 切錐:
- 法錐:
- 切錐:
-
在點(diǎn)
:
- 切錐:
- 法錐:
- 切錐:
三民逼、證明題
- 令
為凸函數(shù)泵殴,且
,證明:
證明:因為根據(jù)凸函數(shù)的性質(zhì)
化簡可得原式缴挖。
-
令
為非空集合,證明:
①我們先證:
顯然有焚辅,
從而②再證明
證明: 對于任意映屋,存在
和
使得
。
其中每個可以表示為
中元素的凸組合同蜻,即
其中
和
且
棚点。
因此,可以重寫為
中元素的凸組合湾蔓,即
瘫析,其中
。這表明
。
若
是
中的非空集合贬循,證明:
證明分兩部分進(jìn)行:
①證明
設(shè) 咸包,根據(jù)凸包的定義,存在有限個點(diǎn)
和非負(fù)權(quán)重
(滿足
)杖虾,使得:
其中
烂瘫。
從而
注意到 是集合
的凸組合,因此屬于
奇适。類似地坟比,
。因此:
由此可得:
② 證明
設(shè) 嚷往,則存在
和
葛账,使得
。根據(jù)凸包的定義皮仁,分別有:
其中 籍琳。
因此:
通過重新組合權(quán)重,構(gòu)造新的凸組合:
其中
魂贬,且
巩割,并且:
因此, 是
的凸組合付燥,屬于
宣谈。由此得出:
- 設(shè)
為
中的凸集,試證明
是凸集键科。
我們先回憶凸集和相對內(nèi)部的定義:
-
凸集
:若對于任意
和任意
闻丑,有
,則稱
是凸的勋颖。
-
相對內(nèi)部
:
在其仿射閉包中的內(nèi)部點(diǎn)構(gòu)成的集合嗦嗡。換句話說,
是
的所有點(diǎn)
饭玲,滿足存在一個以
為中心的相對開球完全包含在
中侥祭。
證明
- 假設(shè)有
設(shè),則根據(jù)相對內(nèi)部的定義茄厘,存在 公共
矮冬,使得下面的兩個相對開球:
其中
表示
的仿射包。
- 任取
次哈,證明
我們需要驗證 滿足相對內(nèi)部的定義胎署。定義:
對于這樣一個相對開球中的任意一個元素,我們有:
注意到:
-
窑滞,
-
琼牧。
由于 是凸的恢筝,并且
,由凸性的定義可知:
因此巨坊,
撬槽。結(jié)合
,我們可以得出
抱究。
綜上恢氯,我們發(fā)現(xiàn),對于連接的線段上的任意一點(diǎn)
,我們都可以找到包含
的一個相對開球鼓寺,包含于
勋拟,由此可以證明
也是一個凸集。
- 設(shè)
為非空錐集合妈候,證明:
定義與性質(zhì)回顧
-
錐集合
:如果
且
敢靡,則
。
-
對偶錐
:對偶錐是所有與
中每個元素的內(nèi)積非負(fù)的向量組成的集合苦银。
- 證明
設(shè) 啸胧,則對
中的任意
,有:
利用內(nèi)積的線性性幔虏,得:
由于這個式子對任意
和
成立纺念,因此可以分別得到:
- 令
的模長趨近于
,可以得到:
- 令
的模長趨近于
,可以得到:
這表明
且
想括,因此:
由此得到:
-
證明
設(shè)陷谱,則對任意
和
,有:
因此瑟蜈,對任意
烟逊,即
(其中
),有:
這表明
铺根。因此:
綜上可以得到:
- 令
為凸集宪躯,
為
中某向量,證明:
在
處的可行方向集為凸集位迂。
-
證明
假設(shè)為
在
處的可行方向访雪。
我們知道,對于任意的掂林,都有
.
考慮兩個可行方向的凸組合
根據(jù)凸集的性質(zhì)臣缀,我們知道這個凸組合是包含于
的。
所以說在
處的可行方向集是一個凸集党饮。