Boyd 5.3節有關於Slater』s constraint推導使用的一個結論存疑？

01-21

primal problem：
$minimize f_0(mathbf{x})\ subject to f_i(mathbf{x}) leq 0, i=1,...,m\ h_i(mathbf{x}) = 0, i=1,...,p \ mathbf{x}in R^n$
定義集合A：

為什麼primal problem 是 convex problem的時候A是一個凸集？
說明：限制在convex problem里意味著 $f_i(x), i=0,...,m$ 是convex function， $h_i(x), i=1,...,p$ 是affine function

謝邀。

根據定義驗證就行了。取兩個A裡面的元素，他們分別對應x和y（定義裡面的x y），那麼這兩個元素的凸組合對應x和y的凸組合，那麼你驗證x和y的凸組合會使得那兩個元素的凸組合也落在A里就行。

不要看到一大堆記號就失去了思考的勇氣。數學裡面很多時候就是用一大堆符號來講述一件很trivial的事情而已。

感謝 @Yuhang Liu 大神的提示，按照你的指導我嘗試著寫下貌似確實不算困難的證明，其實拋開這個本身問題不說，大神說的以下這段話非常值得吾人思考：

不要看到一大堆記號就失去了思考的勇氣。數學裡面很多時候就是用一大堆符號來講述一件很trivial的事情而已。

下面開始簡單論證，題面：

$A={ (u,v,t) | exists x in D,f_i(x)leq u_i,i=1,...,m,\ h_i(x)=v_i,i=1,...,p, f_0(x)leq t }$

其中 $f_i,i=0,...,m$ 是convex function， $h_i,i=1,...,p$ 是affine function，求證 $A$ 是凸集。

證明：

取 $A$ 中任意兩點 $a=(u_a,v_a,t_a)in A, b=(u_b,v_b,t_b)in A$ ，設 $heta in(0,1)$

則可以得到：

$exists x_a in D$

$f_i(x_a)leq u_{ai},i=1,...,m\ h_i(x_a)=v_{ai},i=1,...,p \ f_0(x_a)leq t_a$

$exists x_b in D$

$f_i(x_b)leq u_{bi},i=1,...,m\ h_i(x_b)=v_{bi},i=1,...,p \ f_0(x_b)leq t_b$

則有以下三條重要關係：

$f_i( heta x_a+(1- heta)x_b)leq heta f_i(x_a)+(1- heta)f_i(x_b)leq heta u_{ai}+(1- heta)u_{bi}, i=1,...,m$

$h_i( heta x_a+(1- heta)x_b)= heta h_i(x_a)+(1- heta)h_i(x_b)= heta v_{ai}+(1- heta)v_{bi}, i=1,...,p$

$f_0( heta x_a+(1- heta)x_b)leq heta f_0(x_a)+(1- heta)f_0(x_b)leq heta t_a+(1- heta)t_b$

所以 $exists( heta x_a+(1- heta)x_b)in D$ 對於 $( heta u_a+(1- heta)u_b, heta v_a+(1- heta)v_b, heta t_a+(1- heta)t_b)$ 有上述三條重要關係成立。

所以 $( heta u_a+(1- heta)u_b, heta v_a+(1- heta)v_a, heta t_a+(1- heta)t_a)in A$

所以根據凸集定義集合 $A$ 是凸集。

證畢。

不妨從上境圖（epigraph）的角度考慮這個問題。我們知道 $mathbf{epi} f = left{ (x,t) | f (x) leq t ight}$ , function $f$ is convex iff its epigraph is convex. 那麼集合 $left{ (x,u_i) | f_i(x) leq u_i ight}$ 是凸集，同樣 $left{ (x,t) | f_0(x) leq t ight}$ 也是凸集,而 $left{ (x,v_j) | h_j(x) = v_j ight}$ 是 hyperplane, 顯然也是凸集。令 $S = left{ (x,u,v,t) | f(x) leq u, f_0(x) leq t, h(x) = v ight}$ . 注意到 $x in R^n$ , $f(x)$ 和 $g(x)$ 是向量值函數，上述不等式代表逐項不等。 $S$ 就是 $R^n imes R^m imes R^p imes R$ 空間中上述各凸集的交集，因而還是凸集。將這一凸集向 $x$ 方向投影，就是題目中給出的 $cal{A}$ , convexity is preserved.

PS. 感覺題主自己給出的證明有一點flaw. 因為集合A的定義中只有u,v,t沒有x, 好像x 是給定的; 而兩點組合就變化了x的值。