凸优化（一）凸集和仿射集

2018-12-10 本文已影响0人 SaySei

1. 概述

从这里开始，为了复习所学知识，也是为了更加深刻地探讨优化理论中的相关知识，所以将凸优化中的基础概念做一个整理，然后形成一个凸优化系列随笔。本系列将涉及部分数学推导，强调理论性，所以按需阅读（~~能不能通俗地表达出来我就不知道了~~）。凸优化问题通俗地讲，是一种优化问题，而且是一种简单的优化问题（因为生活中大部分例子与问题都是非凸优化问题，但是部分可以转换为凸优化）。当然，大家高中应该学过线性规划（目标函数和可行解域由线性不等式构成），可以将凸优化看做线性规划的拓展。

2. 预备知识

（1）直线的表示，假设有一个n维空间，已知两点（ $x_1，x_2$ ，统一用向量形式表示）， $x_1，x_2 \in R^n$ ，则有参数 $\theta\in R^n$ ，直线表示为 $y = \theta{x_1}+(1-\theta)x_2$ 。换成这样的形式更好懂一点： $y = x_2+\theta(x_1-x_2)$ ，还是比较通俗易懂得的吧，从x2点出发，沿（x2-x1）向量的方向移动 $\theta$ 长度即直线。

（2）线段的表示，聪明的你一定已经想到了，只要限定参数 $\theta$ 即可表示线段，木有错，只要参数 $\theta\in[0,1]$ 即可表示，x1和x2构成的线段。

3. 仿射集（affine Set）：

3.1 定义

（1）仿射（affine）定义：对于集合 $C\subseteq{R^n}$ ，如果通过集合C中任意两个不同点之间的直线仍在集合C中，则称集合C为仿射（affine）。也就是说，C包括了在C中任意两点的线性组合，即： $x_1,x_2\in C,\theta\in R, \theta{x_1}+(1-\theta)x_2\in C$ 这个概念可以推广到n个点，即 $\theta_1{x_1}+\theta_2{x_2}+...+\theta_n{x_n}$ ，其中 $\theta_1+\theta_2+...+\theta_n=1$ 。从属于C中点钟选择k个点，构成的 $\theta_1{x_1}+\theta_2{x_2}+...+\theta_k{x_k}$ 也称为仿射组合。

（2）仿射集（affine set）定义：仿射集包含了集合内点的所有仿射组合。若C是仿射集， $x_1,x_2...x_n\in C,\theta_1+\theta_2+...+\theta_n=1$ ，则 $\theta_1{x_1}+\theta_2{x_2}+...+\theta_n{x_n}$ 也属于仿射集合C。

（3）仿射包（affine hull）定义：仿射包是包含C的最小的仿射集，表示为： $aff\quad C=\{\theta_1{x_1}+\theta_2{x_2}+...+\theta_n{x_n}|x_1,x_2...x_n\in C,\theta_1+\theta_2+...+\theta_n=1\}$

定义看上去可能有些复杂（~~能来看这文章的应该都能看懂~~），意思很简单，就是说从一个仿射集中选取k个点，然后这k个点的线性组合依旧属于这个仿射集。

3.2 性质

（1）性质一，即仿射集的定义，任意属于仿射集的点的线性组合，且满足权重之和为1，其组合点依旧属于仿射集。

$\quad$ emmm,证明嘛，可以通过数学归纳法证明，简单演示一下3维空间的情况吧：假设有仿射集C， $x_1,x_2,x_3\in C,\theta_i\in R,且\theta_1+\theta_2+...+\theta_n=1$ ,已知二维空间里 $\theta_1{x_1}+(1-\theta)x_2\in C$ ,那么即证明 $\theta_1{x_1}+\theta{x_2}+\theta_3{x_3}\in C$ 。首先构造这样的形式： $\frac{\theta_1}{\theta_1+\theta_2}x_1+\frac{\theta_2}{\theta_1+\theta_2}x_2\tag{1}$ 显然其属于仿射集C，然后接着构建 $(\theta_1+\theta_2)(1)+(1-\theta_1-\theta_2)x_3\tag{2}$ ,显此点依旧在仿射集C内，打开此式，得到 $\theta_1{x_1}+\theta{x_2}+\theta_3{x_3}]\tag{3}$ ,而（2）式即为（3）式，得证。

（2）性质二， $V = C-x_0=\{x-x_0|x \in C\},且\forall x_0\in C$ 。意思就是任对所有的仿射集元素减去一个确定在仿射集中的元素x0，得到的新集合依旧是仿射集，称其为C相关的子空间，其实还有个特殊性质，就是V这个集合里的 $\theta\in R$ 。证明就略过吧，和性质一类似。

（3）性质三（important），线性方程组的解集是仿射集。 $C = \{x|Ax=b\},A\in R^{m\times n},b\in R^{m},x\in R^n$ .

$\quad$ 这个概念很重要，来让我们证明证明，首先已知线性方程组 $Ax=b，\forall x_1,x_2\in C$ ,则满足 $Ax_1=b,Ax_2=b$ ,然后呢，构建参数 $\theta\in R$ ,只要证明 $A(\theta{x_1}+(1-\theta)x_2)=b$ 即可。简单代入一下得到 $\theta{Ax_1}+(1-\theta)Ax_2$ 显然等于b。原命题得证。附加一点，其子空间 $V = \{x|Ax=0,A\in R^{m\times n},x\in R^n\}$ 是一个化零空间。