凸优化基础之计算几何、凸集、凸函数、凸规划

目录

• 一、计算几何
• 1.什么是计算几何
• 2.计算几何理论中过两点的一条直线的表达式，是如何描述的？
• 二、凸集
• 1.什么是凸集
• 2.如何表达三维空间中的一个平面
• 3.如何表达超平面
• 4.什么是凸函数及如何判别
• 5.什么是凸规划及如何判别

一、计算几何

1.什么是计算几何

计算几何是计算机理论科学的一个重要分支.自20世纪70年代末从算法设计与分析中独立出来起，不到30年，该学科已经有了巨大的发展，不仅产生了一系列重要的理论成果，也在众多实际领域中得到了广泛的应用.
计算几何基本概念和常用算法包括如下内容：
矢量的概念
矢量加减法
矢量叉积
折线段的拐向判断
判断点是否在线段上
判断两线段是否相交
判断线段和直线是否相交
判断矩形是否包含点
判断线段、折线、多边形是否在矩形中
判断矩形是否在矩形中
判断圆是否在矩形中
判断点是否在多边形中
判断线段是否在多边形内
判断折线是否在多边形内
判断多边形是否在多边形内
判断矩形是否在多边形内
判断圆是否在多边形内
判断点是否在圆内
判断线段、折线、矩形、多边形是否在圆内
判断圆是否在圆内
计算点到线段的最近点
计算点到折线、矩形、多边形的最近点
计算点到圆的最近距离及交点坐标
计算两条共线的线段的交点
计算线段或直线与线段的交点
求线段或直线与折线、矩形、多边形的交点
求线段或直线与圆的交点
凸包的概念
凸包的求法

想要深入了解这些内容可参考这个博客

2.计算几何理论中过两点的一条直线的表达式，是如何描述的？

设点为Q，线段为P1P2 ，判断点Q在该线段上的依据是：( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1，P2为对角顶点的矩形内。前者保证Q点在直线P1P2上，后者是保证Q点不在线段P1P2的延长线或反向延长线上，对于这一步骤的判断可以用以下过程实现：

ON-SEGMENT(pi,pj,pk)

if min(xi,xj) <= xk <= max(xi,xj) and min(yi,yj) <= yk <= max(yi,yj)

then return true;

else return false;

特别要注意的是，由于需要考虑水平线段和垂直线段两种特殊情况，min(xi,xj)<=xk<=max(xi,xj)和min(yi,yj)<=yk<=max(yi,yj)两个条件必须同时满足才能返回真值。

二、凸集

1.什么是凸集

集合C中任两点之间的点仍在C中，称C为凸集。
即x.x∈C,成+(1-0)xq∈C, 其中θ∈[:1]b 显然仿射集是凸集。
凸组合$\sum^{}_{}\theta_iX_i$∑​θi​Xi​,其中$\sum^{}_{}θ_i$∑​θi​,的值为1。
集合C是凸集<=>C包含其任意点的凸组合
凸包，C为任意集合，
$cnov C= {\sum^{}_{}\theta_iX_i |X_i\in C_z, \theta_i \geq0 ,\theta_i=1 }$cnovC=∑​θi​Xi​∣Xi​∈Cz​,θi​≥0,θi​=1
凸包是包含集合C的最小的凸集

直线的表示： $y= \theta x_1 + (1-\theta)x_2, \theta \in R,$y=θx1​+(1−θ)x2​,θ∈R,
直线是仿射集，而仿射集一定是凸集，所以直线是凸集。

2.如何表达三维空间中的一个平面

三维空间中的平面由两个量确定：
① 一个法向量（垂直于该平面的向量）
② 一个已知点（位于该平面上的一个点）
平面法向量为： $\overrightarrow{n}= \begin{Bmatrix} 1 & 2 & 3 \end{Bmatrix} \tag{3}\top$n={1​2​3​}⊤(3)

平面一个已知点： $P= \begin{Bmatrix} x_0 & y_0 & z_0 \end{Bmatrix} \tag{3}\top$P={x0​​y0​​z0​​}⊤(3)
平面方程为：$ax+by+cz−(ax0+by0+cz0)=0ax+by+cz−(ax0+by0+cz0)=0$ax+by+cz−(ax0+by0+cz0)=0ax+by+cz−(ax0+by0+cz0)=0
平面方程的另外一种写法：$ax+by+cz+d=0ax+by+cz+d=0$ax+by+cz+d=0ax+by+cz+d=0，其中，$d=−(ax0+by0+cz0)$d=−(ax0+by0+cz0)

3.如何表达超平面

n 维空间中的超平面由下面的方程确定:
$W_{}^{T} x + b =0$WT​x+b=0
其中，w 和 x 都是 n 维列向量，x 为平面上的点，w 为平面上的法向量，决定了超平面的方向，b 是一个实数，代表超平面到原点的距离。且
$x = (x_1,x_2,...x_d)^{T}$x=(x1​,x2​,...xd​)T
$w = (w_1,w_2,...w_d)^{T}$w=(w1​,w2​,...wd​)T
那么，w 为什么是法向量呢？b 为什么表示平面到原点的距离呢？下面给出详细解释：

我们对“平面”概念的理解，一般是定义在三维空间中的，即
$Ax +By +Cz + D =0$Ax+By+Cz+D=0
这个平面由两个性质定义：1、方程是线性的，是由空间点的各分量的线性组合。2、方程数量是1。这个平面是建立在“三维”上的。如果我们撇开“维度”这个限制，那么就有了超平面的定义。实际上，超平面是纯粹的数学概念，不是物理概念，它是平面中的直线、空间中的平面的推广，只有当维度大于3，才称为“超”平面。它的本质是*度比空间维度小1。*度的概念可以简单的理解为至少要给定多少个分量的值才能确定一个点. 例如, 三维空间里的(超)平面只要给定了(x,y,z)中任意两个分量, 剩下的一个的值就确定了. 先确定值的两个分量是*的, 因为它们想取什么值就能取什么值;剩下的那个是"不*的", 因为它的值已经由另外两确定了. 二维空间里的超平面为一条直线. 一维空间里超平面为数轴上的一个点。

百度百科上对超平面的数学定义是这样的：超平面H是从n维空间到n-1维空间的一个映射子空间，它有一个n维向量和一个实数定义。因为是子空间，所以超平面一定过原点。

通常，R2（二维空间）中的点集 i = （x,y）满足等式 (点集 i 实际为一条直线)：

ax + 1/by + c = 0 (1) (这里使用1/b 是为了后续计算好表示)
其中，a，b，c均为标量，a，1/b至少有一个不为0.我们假设 b 不为0。，那么

y = -abx - cb 此时，使用换元法，令 t = x,（显然，t 为标量） 则点集 i (x,y) 可以表示成
i (x,y) = ( t, -abt - cb） = t (1, -ab) + (0, -cb)

这条直线是什么？实际上就是过 (0, -cb) 点，方向为 (1, -ab) 的直线 L。

进一步，我们令向量 n = （a,1/b），则 （1）可以表示成n* i + c = 0 (2)

神奇的一刻来临了。假设在直线 L 上取一点 p0(x0，y0），显然，n* p0 + c = 0，那么 c = -n* p0.

更进一步，将 （2）改写，可得 n* i-n* p0 = 0 ，即可 n* （i - p0 ) = 0。

因为 n 和（i - p0 ) 均是向量，（i - p0 ) 在直线 L 上， 所以，n 垂直直线L ,即n为直线L 的法向量。更进一步，我们可以得到，那些与p的差向量与 n 向量正交的点，就是点集 i (x,y).
原文链接：https://blog.csdn.net/dengheCSDN/article/details/77313758

4.什么是凸函数及如何判别

凸函数,是数学函数的一类特征。凸函数就是一个定义在某个向量空间的凸子集c（区间）上的实值函数。
凸函数是一个定义在某个向量空间的凸子集c（区间）上的实值函数f，而且对于凸子集c中任意两个向量x1,x2,$f((x1+x2)/2)≤（f(x1)+f(x2))/2$f((x1+x2)/2)≤（f(x1)+f(x2))/2。
于是容易得出对于任意（0,1)中有理数p,$f(px1+(1-p)x2）≤pf(x1)+(1-p)f(x2）$f(px1+(1−p)x2）≤pf(x1)+(1−p)f(x2）如果f连续，那么p可以改成任意（0,1）中实数。
若这里凸集c即某个区间i，那么就是：设f为定义在区间i上的函数，若对i上的任意两点x1，x2和任意的实数λ∈（0，1），总有
$f（λx1+(1-λ）x2）≤λf(x1)+(1-λ）f(x2)$f（λx1+(1−λ）x2）≤λf(x1)+(1−λ）f(x2),
则f称为i上的凸函数。
判定方法可利用定义法、已知结论法以及函数的二阶导数
对于实数集上的凸函数，一般的判别方法是求它的二阶导数，如果其二阶导数在区间上非负，就称为凸函数。（向下凸）
如果其二阶导数在区间上恒大于0，就称为严格凸函数

5.什么是凸规划及如何判别

定义
在凸集范围内，求凸函数在约束条件下的最小值成为凸规划,即：
设f(x)及gi（x）i=1,2…, m均为R"上的凸函数，则称最优化问题
$minf(x)$minf(x)
$s.t.=\begin{cases} g_i(x) \leq0,i=1,2,m\\ a_{j}^{T}=b_j,j =1,2,p\\ \end{cases}$s.t.={gi​(x)≤0,i=1,2,majT​=bj​,j=1,2,p​
为凸规划。
与一般的最优化问题标准形式相比。凸规划有三点附加条件。
(1)目标函数f (x)必须是凸函数，
(2)不等式约束函数gi(x)必须是凸函数，不等式gi(x)≤ 0组成的区域为凸集:
(3)等式约束函数$h_j(x)=a_{j}^{T}-b_j$hj​(x)=ajT​−bj​;必领是仿射的(即线性函数和常函数的和画数)。
因此我们得出以下结论，凸规划的可行域是凸集。因为每个约束条件的点集都见凸集，它们的交集也见凸集。

这里举一个例子判断下面方程是否为凸规划问题

$\begin{cases} min f(x_1,x_2,x_3)=2x_{1}^{2}+x_{2}^{2}+2x_{3}^{2}+x_1x_3-x_1x_2+x_1+2x_2\\ s.t. \quad g_1(x)=x_{1}^{2}+x_{2}^{2}-x_3≤0\\ \quad\quad g_2(x)=x_{1}^{}+x_{2}^{}+2x_3≤16\\ \quad\quad g_3(x)=-x_{1}^{}-x_{2}^{}+x_3≤0\\ \end{cases}$⎩⎪⎪⎪⎨⎪⎪⎪⎧​minf(x1​,x2​,x3​)=2x12​+x22​+2x32​+x1​x3​−x1​x2​+x1​+2x2​s.t.g1​(x)=x12​+x22​−x3​≤0g2​(x)=x1​+x2​+2x3​≤16g3​(x)=−x1​−x2​+x3​≤0​
判断过程：字丑见谅

再来一道例题 凸规划问题还可以采用kkt条件进行判别，不清楚kkt条件的可以先去了解一下kkt条件。

求解方法