凸优化学习笔记03(凸集、锥、超平面和半空间、Euclid球和椭球)

克夏

2240人浏览 · 2021-10-07 20:14:46

克夏 · 2021-10-07 20:14:46 发布

凸集

定义：集合C中任意两点间的线段仍在C中，那么该集合即为凸集。

数学表达： $\forall x_1,x_2 \in C, 0 \leq \theta \leq 1,$ 有 $\theta x_1 +(1-\theta)x_2 \in C.$

通俗理解：凸集C里任意找两点，其连线必定还在凸集C内部。

凸组合

定义：与仿射组合类似【仿射组合定义可回顾凸优化读书笔记01_Bryant_cqc的博客-CSDN博客】

凸集与凸组合的关系

凸集包含其中所有点的凸组合。

凸包

定义：与仿射包类似【仿射包定义可回顾凸优化读书笔记01_Bryant_cqc的博客-CSDN博客】

锥

定义：如果对于任意 $x \in C$ 和 $\theta \geq 0$ ，都有 $\theta x \in C$ ，我们称集合C是锥或者非负齐次。

扩展：若集合C是锥，并且满足凸集条件，则集合C称为凸锥。

锥组合

定义：具有 $\theta_1x_1+...+\theta_kx_k, \theta_1,...,\theta_k \geq 0$ 形式的点称为 $x_1,...,x_k$ 的锥组合(或非负线性组合)。

延伸：集合C是凸锥的充要条件是它包含其元素的所有锥组合。

锥包

定义：与仿射包类似，只是约束条件变成了 $\theta_i \geq 0,i=1,...,k$ 。包含集合C的最小的凸锥。

常见凸集

a. 空集 $\varnothing$ 、任意一个点 $\begin{Bmatrix} x_0 \end{Bmatrix}$ 、全空间 $R^n$ 都是 $R^n$ 的仿射（自然也是凸的）子集。

b. 任意直线是仿射的。如果直线通过零点，即为子空间，因此，也是凸锥。【解释：因为当 $\theta \geq 0$ 时，只有子空间在 $x > 0$ 时， $\theta x \geq 0$ ； $x < 0$ 时， $\theta x \leq 0$ ，其他直线不符合该要求】

c. 一条线段是凸的，但不是仿射的(除非退化为一个点)。

d. 一条射线，既具有形式 $\begin{Bmatrix} x_0+\theta v | \theta \geq 0 \end{Bmatrix}$ ， $v \neq 0$ 的集合，是凸的，但不是仿射的。如果射线的基点 $x_0$ 是0，则它是凸锥。

e. 任意子空间是仿射的、凸锥。

超平面与半空间

超平面

定义：关于x的非平凡线性方程的解空间（是一个仿射集合）。

表示：集合 $\begin{Bmatrix} x|a^Tx = b \end{Bmatrix}$ ，其中 $a \in R^n,a \neq 0, b \in R$ 。

几何解释：与给定向量 $a$ 的内积为常数的点的集合，也可以看成法线方向为 $a$ 的超平面，而常数 $b \in R$ 决定了这个平面从原点的偏移。

根据这个几何解释，可将超平面表示成下面两种形式：

$\begin{Bmatrix} x|a^T(x-x_0)=0 \end{Bmatrix}=x_0+a^\perp,$

其中 $x_0$ 是超平面上的任意一点（即任意满足 $a^T x_0= b$ 的点）, $a^\perp$ 表示 $a$ 的正交补，即与 $a$ 正交的向量集合：

$a^\perp = \begin{Bmatrix} v|a^T v=0 \end{Bmatrix},$

直观表示：

半空间

来源：一个超平面将 $R^n$ 划分为两个半空间。

数学表示： $\begin{Bmatrix} x|a^Tx \leq b \end{Bmatrix}$ 或 $\begin{Bmatrix} x|a^Tx > b \end{Bmatrix}$ $(a \neq 0)$

特点：半空间是凸的，但不是仿射的。

边界： $\begin{Bmatrix} x|a^Tx = b \end{Bmatrix}$ ，开半空间： $\begin{Bmatrix} x|a^Tx < b \end{Bmatrix}$

直观表示：

Euclid 球和椭球

Euclid球

数学形式： $B(x_c,r)=\begin{Bmatrix} x| \left \| x-x_c \right \|_2 \leq r \end{Bmatrix}=\begin{Bmatrix} x|(x-x_c)^T(x-x_c) \leq r^2 \end{Bmatrix}$

其中 $r > 0$ , $\left \| \cdot \right \|_2$ 表示欧几里得范数,向量 $x_c$ 是球心，标量 $r$ 为半径。

特点：Euclid球是凸集。

椭球

数学形式： $\varepsilon = \begin{Bmatrix} x|(x-x_c)^T P^{-1} (x-x_c) \leq 1 \end{Bmatrix}$

其中 $P = P^T \succ 0$ ，即 $P$ 是对称正定矩阵。向量 $x_c \in R^n$ 为椭球中心。矩阵 $P$ 决定了椭球从 $x_c$ 向各个方向扩展的幅度。 $\varepsilon$ 的半轴长度由 $\sqrt \lambda_i$ 给出，这里 $\lambda_i$ 为 $P$ 的特征值。

例子：球可看做 $P = r^2I$ 的椭球。

特点：椭球是凸集。

术语解释

对称正定矩阵：举个例子，A为n阶方阵，若A还满足对称矩阵（即 $A =A^T$ ），对任意的非零向量 $X \in R^n$ ，都有 $X^TAX > 0$ ，则称A为对称正定矩阵[1]。

参考文献

[1] 正定矩阵_百度百科

[美]S. Boyd, L. Vandenberghe. 凸优化[M]. 王书宁, 许鋆, 黄晓霖. 北京: 清华大学出版社, 2013.

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

Handy 离线语音转写教程：免费开源，本地跑不连网

你肯定遇到过：语音输入 5 分钟，云转写服务要登录、要付费；或者出差没网，想口述一段会议纪要，发现全都没法用。Handy 离线语音转写工具就是为解决这个问题做的，声音全程不出你的电脑。## 🎯 这个工具是什么Handy 是一款免费、开源、跨平台（Windows / macOS / Linux）的离线语音转写应用。按住快捷键说话，松手后文字直接粘贴进任意输入框，全程不联网。核心能力就三条：

天工造物局

Supabase Edge Functions 编写与部署完整指南：Deno 运行时上的无服务器利器

Supabase Edge Functions 是基于 Deno 运行时编写、面向 Web 的无服务器函数服务，帮你把后端逻辑部署到全球边缘节点。作为 Postgres 开发平台的核心能力之一，它让你用 TypeScript 就能快速搭建低延迟的 API 端点、Webhook 接收器和 AI 集成服务，无需管理任何服务器。本文将从零带你完成一个 Edge Function 的创建、本地调试与全球部

天工造物局

celld从v0.1.0到v0.2.0为何不能滚动升级：两个破坏性变更详解

celld 是一个自托管、分布式的 Durable Objects 开源守护进程，它在你自己的机器上运行 Cloudflare Workers，每个对象对应一个独立的 SQLite 数据库，并持续复制到你自己拥有的 S3 兼容存储桶中。如果你正准备把 v0.1.0 的集群（fleet）升级到 v0.2.0，这篇文章必须先读：这次升级**不能滚动升级**，必须采用"先停光、再启动"的一次性发布方式。