凸優化理論

一、計算幾何是研究什麼的？

計算幾何研究的對象是幾何圖形。
計算幾何作爲CAD的基礎理論之一，主要研究內容是幾何形體的數學描述和計算機表述。

二、計算幾何理論中（或凸集中）過兩點的一條直線的表達式，是如何描述的？與初中數學中那些直線方程有什麼差異？

對一元函數f(x)在幾何上af(x1)+(1-a)f(x2)=0 (0≤a≤1)表示連接（x1,f(x1)),(x2,f(x2))的線段
f(ax1+(1-a)x2)表示在點 ax1+(1-a)x2處的函數值。
也就是說，一元凸函數表示連接函數圖形上任意兩點的線段總是位於曲線弧的上方。

初中數學中直線方程的表示：

一般式:Ax+By+C=0
點斜式:y-y0=k(x-x0)（斜率爲k，且過點（x0,y0））
截距式:x/a+y/b=1（表示與x軸、y軸相交，且x軸截距爲a，y軸截距爲b的直線）
斜截式:y=kx+b（表示斜率爲k且y軸截距爲b的直線）
兩點式：
(x1≠x2，y1≠y2)

交點式: f1(x,y) *m+f2(x,y)=0（表示過直線f1(x,y)=0與直線f2(x,y)=0的交點的直線）
點平式:f(x,y) -f(x0,y0)=0（表示過點（x0,y0）且與直線f（x,y）=0平行的直線）
法線式：xcosα+ysinα-p=0（過原點向直線做一條的垂線段，該垂線段所在直線的傾斜角爲α，p是該線段的長度）
點向式：(x-x0)/u=(y-y0)/v (u≠0,v≠0)（表示過點(x0,y0)且方向向量爲（u,v ）的直線）
法向式：a（x-x0）+b（y-y0）=0 （表示過點（x0，y0）且與向量（a，b）垂直的直線）

三、凸集是什麼？ 直線是凸集嗎？是仿射集嗎？

凸集是在凸組合下閉合的仿射空間的子集。更具體地說，在歐氏空間中，凸集是對於集合內的每一對點，連接該對點的直線段上的每個點也在該集合內。

在一維空間中，凸集是單點或一條不間斷的線（包括直線、射線、線段）；二、三維空間中的凸集就是直觀上凸的圖形。（在二維中有扇面、圓、橢圓等，在三維中有實心球體等；多數情況下，兩個凸集的交集也是凸集，空集也是凸集）

如果一個集合c是仿射集，那麼

ax1+(1-a)x2這個點（過x1, x2的直線上的點）也在集合c內。(一條直線上的點組成的集合是仿射集，一個二維平面上的點組成的集合也是仿射集；但是線段就不是仿射集了)。

四、三維空間中的一個平面，如何表達？

一般方程：
Ax+By+Cz+D=0
點法式方程：
A(x-x0)+B(y-y0)+C(z-z0)=0
點向式方程：
(x-x0)/A=(y-y0)/B=(z-z0)/C
截距式方程：
x/a+y/b+z/c=1
法線式方程：
xcosα+ycosβ+zcosγ=p

五、更高維度的「超平面」，如何表達？

n 維空間中的超平面由下面的方程確定:

其中，w 和 x 都是 n 維列向量，x 爲平面上的點，w 爲平面上的法向量，決定了超平面的方向，b 是一個實數，代表超平面到原點的距離。且

六、什麼是「凸函數」定義？什麼是Hessen矩陣? 如何判別一個函數是凸函數？f(x)=x^3 函數是凸函數嗎？

1.凸函數的定義

對於一元函數f(x)如果對於任意tϵ[0,1]均滿足：f(tx1+(1−t)x2)≤tf(x1)+(1−t)f(x2) 則稱f(x)爲凸函數

如果對於任意tϵ(0,1)均滿足：f(tx1+(1−t)x2)<tf(x1)+(1−t)f(x2)，則稱f(x)爲嚴格凸函數

2.Hessen矩陣

由高等數學知識可知，若一元函數f(x)在x=x(0)點的某個領域內具有任意階導數，則f(x)在x(0)點處的泰勒展開式爲：

其中

二元函數

f(x1,x2)在

點處的泰勒展開式爲：

其中

將上述展開式寫成矩陣形式，則有：

即

其中：

G(x(0))是f(x1,x2)在x(0)點處的Hessen矩陣。它是由函數f(x1,x2)在x(0)點處的二階偏導數所組成的方陣。

多元函數

在x(0)點處的泰勒展開式的矩陣形式爲：

其中：

是f(x)在點x(0)處的梯度

爲函數f(x)在x(0)點處的Hessen矩陣。

Hessen矩陣是由目標函數 在點X處的二階偏導數組成的 階對稱矩陣

3.判別一個函數是凸函數

對於一元函數f(x)，我們可以通過其二階導數f″(x) 的符號來判斷。如果函數的二階導數總是非負，即f′′(x)≥0f″(x)≥0 ，則f(x)是凸函數

對於多元函數f(X)，我們可以通過其Hessian矩陣（Hessian矩陣是由多元函數的二階導數組成的方陣）的正定性來判斷。如果Hessian矩陣是半正定矩陣，則是f(X)凸函數

4. f(x)=x^3 函數是凸函數嗎？

由3，我們可以很容易知道f’(x)=3x²，f’’(x)=6x，而對於一元函數的凸函數來說若f’’(x)總是非負則f(x)爲凸函數，而f(x)=x^3 的二階導數爲f’’(x)=6x不總是非負，所以f(x)=x^3 不是凸函數。

七、什麼是「凸規劃」？如何判別一個規劃問題是凸規劃問題。舉例說明？

1.凸規劃

若最優化問題的目標函數爲凸函數，不等式約束函數也爲凸函數，等式約束函數是仿射的，則稱該最優化問題爲凸規劃。凸規劃的可行域爲凸集，因而凸規劃的局部最優解就是它的全局最優解。當凸規劃的目標函數爲嚴格凸函數時，若存在最優解，則這個最優解一定是唯一的最優解。

2.判別凸規劃問題

參考文章

https://blog.csdn.net/denghecsdn/article/details/77313758 https://www.cnblogs.com/always-fight/p/9377554.html