【凸优化】maximal 与 maximum的不同

(96) 2024-04-26 13:01:01

这是一个很久之前的草稿,我在听国立清华大学赵启超教授的《离散数学L8B》,学到了Hasse diagram的概念,解释了greatest element 和maximal element之间区别。这让我想到了Boyd凸优化里面的maximum和maximal定义(当时还挺难理解的,因为它出现在广义不等式generalized inequality这一部分)。我凭印象把它整理出来,欢迎批评。

下面是三张Hasse diagram,分别写出了maximal, minimal, greatest element, least element。从中我们可以看出,maximal, minimal不唯一,而greatest, least最多只会有一个。
(注:下面图上的结点附近的数字只是个标记而已,并无实际含义)
【凸优化】maximal 与 maximum的不同 (https://mushiming.com/)  第1张

greatest element从最上面的一个点往下走,能够走到所有点,那么这个点就是gratest element;

least element, 从最下面的一点往上走,能够走过所有点,则称这个点就是least element

greatest element 与maiximal element之所以会不同,是因为partial order 的定义本身暗示了不是任意两个元素都是可比的(comparable);
如果是total order,那么greatest element就是maximal element,least element就是minimal element,具体可以参考上面HASSE diagram a);

Convex Optimization

这本书是介绍了minimum element 和 minmal的概念
【凸优化】maximal 与 maximum的不同 (https://mushiming.com/)  第2张
左边, x 1 x_1 x1是集合 S 1 S_1 S1的mimimum element。
而右边, x 2 x_2 x2是集合 S 2 S_2 S2的mimimal element, 可以看到红色圆圈和 x 2 x_2 x2之间无法比较。

这是两种定义概念。
minimum element是比集合S 中所有元素都小(这暗含了它和集合中所有元素都是可以比较的);
minimal element是**集合S中所有和它能够比较的* *元素中它是最小的(就像上图红色框的右上角与集合 S 2 S_2 S2的交集),或者说 所有比它更小的元素 都不在集合S中(就像上面右边那张图的淡灰色区域与集合 S 2 S_2 S2没有交集)。

摘自原书的定义

【凸优化】maximal 与 maximum的不同 (https://mushiming.com/)  第3张

THE END

发表回复