4.极点，极锥

极点

定义：设 $x$ 为非空凸集 $C$ 中向量，若对 $C$ 中任意不同于 $x$ 的 $y, z$ ，以及任意标量 $\alpha \in (0,1)$ ，使得 $x = \alpha y + (1-\alpha)z$ 均不成立，则称 $x$ 为集合 $C$ 的极点或顶点 (extreme point)。

极点示意图

注意事项

极点不能由凸集中其他点的凸组合来表示。
开集中无极点。
凸锥至多有一个极点，即原点。
凸多面体极点个数是有限的，亦可能没有。
多面体上的凹函数至少会在某个极点处取到最小值。

定理 (凸集与其低维线性子集的极点)
设集合 $C \subseteq \mathbb{R}^n$ 为凸集， $C$ 属于超平面 $H$ 对应的某个闭半空间，则 $C \cap H$ 的极点必是 $C$ 的极点且属于 $H$ ，反之亦成立。

图例

定理 (极点存在的直线条件)
设集合 $C \subseteq \mathbb{R}^n$ 为非空闭凸集，则 $C$ 含有至少一个极点当且仅当 $C$ 不包含直线。
定理 (多面体集极点定理)
设 $\mathbb{R}^n$ 中多面体集：
$P = \{ x \mid a_j^T x \leq b_j, j = 1, \ldots, r \}$
其中 $a_j \in \mathbb{R}^n$ , $b_j \in \mathbb{R}$ , $j = 1, \ldots, r$ ，则向量 $\mathbf{v}$ 是 $P$ 的极点当且仅当集合：
$A_v = \{ a_j \mid a_j^T \mathbf{v} = b_j, j \in \{1, \ldots, r\} \}$ 含有 $n$ 个线性无关的向量。

极锥

定义：设 $C$ 为任意非空集合，其极锥 (polar cone) 定义如下：
$C^* = \{ y \mid y^{\top} x \leq 0, \forall x \in C \}.$

极锥

极锥的性质

设 $C$ 为非空集合，有
$C^* = (cl(C))^* = (conv(C))^* = (cone(C))^*.$
设 $C$ 为非空锥集合，有
$(C^*)^* = cl(conv(C)),$ 特别地，若 $C$ 是闭凸集，则 $(C^*)^* = C$ 。

多面体表示

定义：若多面体 $C \subseteq \mathbb{R}^n$ 可表示成如下形式：
$C = \{ x \mid a_j^{\top} x \leq 0, j = 1, \ldots, r \}$
其中 $a_j \in \mathbb{R}^n$ ， $r$ 是某个正整数，则称 $C$ 为多面体锥 (polyhedral cone)。意思是多面体锥可以表示成若干个闭半空间的交集。

多面体锥

有限生成锥

定义：若锥 $C$ 可表示成如下形式：
$C = \operatorname{cone}\left(\left\{a_1, \ldots, a_r\right\}\right) = \left\{ x \mid x = \sum_{j=1}^r \mu_j a_j, \mu_j \geq 0, j = 1, \ldots, r \right\},$

其中 $a_j \in \mathbb{R}^n$ ， $r$ 是某个正整数，则称 $C$ 为有限生成锥 (finitely generated cone)。

有限生成锥

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 225,151评论 6赞 523
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 96,465评论 3赞 405
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 172,429评论 0赞 368
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 61,147评论 1赞 301
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 70,149评论 6赞 400
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 53,614评论 1赞 315
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 41,965评论 3赞 429
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 40,950评论 0赞 279
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 47,486评论 1赞 324
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 39,524评论 3赞 347
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 41,640评论 1赞 355
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 37,228评论 5赞 351
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 42,976评论 3赞 340
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 33,407评论 0赞 25
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 34,552评论 1赞 277
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 50,215评论 3赞 381
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 46,714评论 2赞 366

4.极点，极锥

极点

极锥

多面体表示

有限生成锥

推荐阅读更多精彩内容