A****s
发帖数: 129 | 1 不是很复杂很严格，但构思的过程却很有意思
比如这个题我想到的一个方法自己觉得还比较巧妙（当然没准也有不对的地方
），有兴趣的不妨做做。
题目就是说任给一个Rn里的闭凸集C(不等于Rn）,在C上定义f
为C里的点x到C补集的最短距离，证这个f是凹的 | H****h
发帖数: 1037 | 2 在C的每个边界点上都可以做一个平面和C相切。设G为所有平面组成的集合。
那么x到C补集的距离就是x到所有属于G的平面的距离的最小值。
对与G中每个平面P，可以定义f_P是x到P的距离，其限制在C上是仿射函数，所以凹。
最后因为f=min f_P，所以f也是凹的。
【在 A****s 的大作中提到】
: 不是很复杂很严格，但构思的过程却很有意思
: 比如这个题我想到的一个方法自己觉得还比较巧妙（当然没准也有不对的地方
: ），有兴趣的不妨做做。
: 题目就是说任给一个Rn里的闭凸集C(不等于Rn）,在C上定义f
: 为C里的点x到C补集的最短距离，证这个f是凹的
| A****s
发帖数: 129 | 3 晕，这么简单
不过后面有关仿射函数那部分没看懂，是定理么？
【在 H****h 的大作中提到】
: 在C的每个边界点上都可以做一个平面和C相切。设G为所有平面组成的集合。
: 那么x到C补集的距离就是x到所有属于G的平面的距离的最小值。
: 对与G中每个平面P，可以定义f_P是x到P的距离，其限制在C上是仿射函数，所以凹。
: 最后因为f=min f_P，所以f也是凹的。
| H****h
发帖数: 1037 | 4 所谓平面我的意思是n-1维的子空间。
与平面的距离做为函数，限制在平面的任何一侧，就是一个仿射函数
所谓仿射函数，指的是线性函数加上一个常数。
【在 A****s 的大作中提到】
: 晕，这么简单
: 不过后面有关仿射函数那部分没看懂，是定理么？
| A****s
发帖数: 129 | 5 I understand this part.
But why "其限制在C上是仿射函数，所以凹"?
【在 H****h 的大作中提到】
: 所谓平面我的意思是n-1维的子空间。
: 与平面的距离做为函数，限制在平面的任何一侧，就是一个仿射函数
: 所谓仿射函数，指的是线性函数加上一个常数。
| H****h
发帖数: 1037 | 6 仿射函数既是凹函数又是凸函数。
【在 A****s 的大作中提到】
: I understand this part.
: But why "其限制在C上是仿射函数，所以凹"?
| n******t
发帖数: 4406 | 7 这个是一个convex optimization里面基本的结论吧。
【在 A****s 的大作中提到】
: 不是很复杂很严格，但构思的过程却很有意思
: 比如这个题我想到的一个方法自己觉得还比较巧妙（当然没准也有不对的地方
: ），有兴趣的不妨做做。
: 题目就是说任给一个Rn里的闭凸集C(不等于Rn）,在C上定义f
: 为C里的点x到C补集的最短距离，证这个f是凹的
| A****s
发帖数: 129 | 8 yes..and health's proof is quite clear.
I just had another similar proof. for any x1, x2, and x3 as (x1+x2)/2
y3 as the point on the boundary of the set where d(x3,y3)=f(x3)
then I could draw two lines from (x1,y1) (x2,y2) on the 2-dimension plane
(x1,x2,y3) which parallel to (x3, y3), on the same side of (x1,x2),
and make their length as f(x1), f(x2). So y1 y2 are in this convex
set and (y1+y2)/2 is,too. Moreover, (y1+y2)/2 lies on (x3,y3) while y3 is on
the boundary. so d(x3,(y1+y2)/2) is smal
【在 n******t 的大作中提到】
: 这个是一个convex optimization里面基本的结论吧。
| H****h
发帖数: 1037 | 9 没有太看明白。好像还有一种直观些的证明。比如有x1和x2两点，到C的边界的
距离分别为d1和d2。那么C包含两个球B(x1,d1)和B(x2,d2)。因为C是凸集，所以
C也包含两个球的并集的凸包。然后x1和x2连线段上的一点x_3=p*x1+(1-p)*x2到
C的边界的距离不小于到这个凸包边界的距离。后者距离恰好是p*d1+(1-p)*d2。
on
【在 A****s 的大作中提到】
: yes..and health's proof is quite clear.
: I just had another similar proof. for any x1, x2, and x3 as (x1+x2)/2
: y3 as the point on the boundary of the set where d(x3,y3)=f(x3)
: then I could draw two lines from (x1,y1) (x2,y2) on the 2-dimension plane
: (x1,x2,y3) which parallel to (x3, y3), on the same side of (x1,x2),
: and make their length as f(x1), f(x2). So y1 y2 are in this convex
: set and (y1+y2)/2 is,too. Moreover, (y1+y2)/2 lies on (x3,y3) while y3 is on
: the boundary. so d(x3,(y1+y2)/2) is smal
| A****s
发帖数: 129 | 10 Not sure if this is correct but what i mean is alike. if we have
d1,d2,d3,just "rotate" d1 and d2 to make them parallel to d3 on the
plane spanned by d3 and (x1,x2). Then the new "d1" and "d2" are still
inside of the convex set. and their combination will coincide with
d3 only shorter since d3's another end point lies on the boundary.
【在 H****h 的大作中提到】
: 没有太看明白。好像还有一种直观些的证明。比如有x1和x2两点，到C的边界的
: 距离分别为d1和d2。那么C包含两个球B(x1,d1)和B(x2,d2)。因为C是凸集，所以
: C也包含两个球的并集的凸包。然后x1和x2连线段上的一点x_3=p*x1+(1-p)*x2到
: C的边界的距离不小于到这个凸包边界的距离。后者距离恰好是p*d1+(1-p)*d2。
:
: on
|
|
