r******r
发帖数: 74 | 1 f(x,y) 在定义域S内concave
f(1,y)<=f(1,1)，对所有的y成立
f(x,1)<=f(1,1)，对所有的x成立
那么在S内，f(1,1)是否是最大值？ | d******e
发帖数: 7844 | 2 对于可导的函数应该是成立的，Coordinate Descent就是基于这个原理的。
对不可导的不清楚。
【在 r******r 的大作中提到】
: f(x,y) 在定义域S内concave
: f(1,y)<=f(1,1)，对所有的y成立
: f(x,1)<=f(1,1)，对所有的x成立
: 那么在S内，f(1,1)是否是最大值？
| r******r
发帖数: 74 | 3 函数的可以求导的，能够给个证明么，谢谢？
【在 d******e 的大作中提到】
: 对于可导的函数应该是成立的，Coordinate Descent就是基于这个原理的。
: 对不可导的不清楚。
| d******e
发帖数: 7844 | 4 你的定义域S是凸的么？
【在 r******r 的大作中提到】
: 函数的可以求导的，能够给个证明么，谢谢？
| d******e
发帖数: 7844 | | r******r
发帖数: 74 | 6 对，是convex set
【在 d******e 的大作中提到】
: 你的定义域S是凸的么？
| Q***5
发帖数: 994 | 7 If S = R^2, this is easy to prove by concavity, because:
any (x,y) can be written as (x,y) = a* (x1,1) + (1-a)*(1,y1), where 0<=a<=1,
and f(x,y)<= a f(x1,1) + (1-a) f(1,y1)<= f(1,1)
For general case of S, as long as (1,1) is an interior point of S, the
conclusion still holds. You can prove it in two steps:
(1) (1,1) is a local maximum point -- using similar argument as above.
(2) (1,1) is a global maximum point -- otherwise, suppose there is (x,y)\in
S, such that f(x,y)>f(1,1), then, by concavit
【在 r******r 的大作中提到】
: f(x,y) 在定义域S内concave
: f(1,y)<=f(1,1)，对所有的y成立
: f(x,1)<=f(1,1)，对所有的x成立
: 那么在S内，f(1,1)是否是最大值？
| d******e
发帖数: 7844 | 8 你写错了。对于concave function f(x,y)>=af(x1,1)+(1-a)f(1,y1).
这道题不是这么证明的。
应该是这个思路，由于f(1,1)是S的一个内点，那么可以知道f在(1,1)点的梯度为0，那
么如果f(1,1)为可导凹函数，那么(1,1)就应该是极值点。用Taylor级数的一阶展开证
明f(x+y)<=f(x)+(f的梯度@x)*(y)就行了。
1,
in
any
(1
【在 Q***5 的大作中提到】
: If S = R^2, this is easy to prove by concavity, because:
: any (x,y) can be written as (x,y) = a* (x1,1) + (1-a)*(1,y1), where 0<=a<=1,
: and f(x,y)<= a f(x1,1) + (1-a) f(1,y1)<= f(1,1)
: For general case of S, as long as (1,1) is an interior point of S, the
: conclusion still holds. You can prove it in two steps:
: (1) (1,1) is a local maximum point -- using similar argument as above.
: (2) (1,1) is a global maximum point -- otherwise, suppose there is (x,y)\in
: S, such that f(x,y)>f(1,1), then, by concavit
| Q***5
发帖数: 994 | 9 Ooops....
You are right.
I think the conclusion is true even without the assumption about the
existence of gradient...
【在 d******e 的大作中提到】
: 你写错了。对于concave function f(x,y)>=af(x1,1)+(1-a)f(1,y1).
: 这道题不是这么证明的。
: 应该是这个思路，由于f(1,1)是S的一个内点，那么可以知道f在(1,1)点的梯度为0，那
: 么如果f(1,1)为可导凹函数，那么(1,1)就应该是极值点。用Taylor级数的一阶展开证
: 明f(x+y)<=f(x)+(f的梯度@x)*(y)就行了。
:
: 1,
: in
: any
: (1
| c*m
发帖数: 1114 | 10 你这个f(x,y)< a f(x1,1) + (1-a) f(1,y1)<= f(1,1)怎么得来的？
x1=(x-1+a)/a, y1=(y-a)/(1-a),what if (x1,y1) 掉出来定义域S呢？
同样道理，你这个condition(2)也仅当定义域是convex形状才成立
1,
in
any
(1
【在 Q***5 的大作中提到】
: If S = R^2, this is easy to prove by concavity, because:
: any (x,y) can be written as (x,y) = a* (x1,1) + (1-a)*(1,y1), where 0<=a<=1,
: and f(x,y)<= a f(x1,1) + (1-a) f(1,y1)<= f(1,1)
: For general case of S, as long as (1,1) is an interior point of S, the
: conclusion still holds. You can prove it in two steps:
: (1) (1,1) is a local maximum point -- using similar argument as above.
: (2) (1,1) is a global maximum point -- otherwise, suppose there is (x,y)\in
: S, such that f(x,y)>f(1,1), then, by concavit
| | | c*m
发帖数: 1114 | 11 你这个f在(1,1)上梯度为0也没法直接从题目得到，一个二维函数在某点x方向和y方向
梯度为0并不等于该点的梯度为0.后面的结论就都不成立了。
【在 d******e 的大作中提到】
: 你写错了。对于concave function f(x,y)>=af(x1,1)+(1-a)f(1,y1).
: 这道题不是这么证明的。
: 应该是这个思路，由于f(1,1)是S的一个内点，那么可以知道f在(1,1)点的梯度为0，那
: 么如果f(1,1)为可导凹函数，那么(1,1)就应该是极值点。用Taylor级数的一阶展开证
: 明f(x+y)<=f(x)+(f的梯度@x)*(y)就行了。
:
: 1,
: in
: any
: (1
| r******r
发帖数: 74 | 12 如果（1,1)不是内点，而是在边界上呢？
【在 d******e 的大作中提到】
: 你写错了。对于concave function f(x,y)>=af(x1,1)+(1-a)f(1,y1).
: 这道题不是这么证明的。
: 应该是这个思路，由于f(1,1)是S的一个内点，那么可以知道f在(1,1)点的梯度为0，那
: 么如果f(1,1)为可导凹函数，那么(1,1)就应该是极值点。用Taylor级数的一阶展开证
: 明f(x+y)<=f(x)+(f的梯度@x)*(y)就行了。
:
: 1,
: in
: any
: (1
| c*m
发帖数: 1114 | 13 你这个命题应该是不一定是，
考虑一个case, f(x,y)=-x^2-y^2
他的等高线是x^2+y^2=const.
你画两条等高线，x^2+y^2=2和4,这个环带里面的值都比f(1,1)小，
环带里面都比f(1,1)大，假设环区域为A1,内环里面区域为A2(x^2+y^2<2)
再建一个正方形区,x从-1到1,y从-1,到1,设这个区域为S1,
你可以建立一个S区，从(1,1)出发到A2 U (not S1) 区里面转一下，再去环区域A1里面
转一下。这样的区域(1,1)不是最大值。
A2 U (not S1)就是圆区域减去正方形区域。
【在 r******r 的大作中提到】
: f(x,y) 在定义域S内concave
: f(1,y)<=f(1,1)，对所有的y成立
: f(x,1)<=f(1,1)，对所有的x成立
: 那么在S内，f(1,1)是否是最大值？
| c*m
发帖数: 1114 | 14 另外补充一下，这个范例是基于你的f(1,1)>f(x,1),f(1,1)>f(1,y)定义在S内部的。
如果你的f(1,1)>f(x,1), f(1,1)>f(1,y）定义在整个[-inf~inf, -inf~inf],该命题照
样不成立。
具体可以考察最简单的基于(1,1)中心对称的马鞍形函数，它的二阶导数四个象限(中心
点在[-1,1])交错反号，
x=1,y=1是这二阶导数变号的分界线，而(1,1)是x=1,y=1两条线上的极大值点。
稍微对这个马鞍形函数做一个小旋转，让分界线偏离x=1,y=1,同时该二阶导数小于0的
区域中(S所属的区)极值在分界线上达到。不难可以造出这样一个S,使得(1,1)并非S中
最大值。
【在 c*m 的大作中提到】
: 你这个命题应该是不一定是，
: 考虑一个case, f(x,y)=-x^2-y^2
: 他的等高线是x^2+y^2=const.
: 你画两条等高线，x^2+y^2=2和4,这个环带里面的值都比f(1,1)小，
: 环带里面都比f(1,1)大，假设环区域为A1,内环里面区域为A2(x^2+y^2<2)
: 再建一个正方形区,x从-1到1,y从-1,到1,设这个区域为S1,
: 你可以建立一个S区，从(1,1)出发到A2 U (not S1) 区里面转一下，再去环区域A1里面
: 转一下。这样的区域(1,1)不是最大值。
: A2 U (not S1)就是圆区域减去正方形区域。
| r******r
发帖数: 74 | 15 这样的话S就不是convex set了呀。
【在 c*m 的大作中提到】
: 你这个命题应该是不一定是，
: 考虑一个case, f(x,y)=-x^2-y^2
: 他的等高线是x^2+y^2=const.
: 你画两条等高线，x^2+y^2=2和4,这个环带里面的值都比f(1,1)小，
: 环带里面都比f(1,1)大，假设环区域为A1,内环里面区域为A2(x^2+y^2<2)
: 再建一个正方形区,x从-1到1,y从-1,到1,设这个区域为S1,
: 你可以建立一个S区，从(1,1)出发到A2 U (not S1) 区里面转一下，再去环区域A1里面
: 转一下。这样的区域(1,1)不是最大值。
: A2 U (not S1)就是圆区域减去正方形区域。
| r******r
发帖数: 74 | 16 马鞍函数就不是concave function了呀。
【在 c*m 的大作中提到】
: 另外补充一下，这个范例是基于你的f(1,1)>f(x,1),f(1,1)>f(1,y)定义在S内部的。
: 如果你的f(1,1)>f(x,1), f(1,1)>f(1,y）定义在整个[-inf~inf, -inf~inf],该命题照
: 样不成立。
: 具体可以考察最简单的基于(1,1)中心对称的马鞍形函数，它的二阶导数四个象限(中心
: 点在[-1,1])交错反号，
: x=1,y=1是这二阶导数变号的分界线，而(1,1)是x=1,y=1两条线上的极大值点。
: 稍微对这个马鞍形函数做一个小旋转，让分界线偏离x=1,y=1,同时该二阶导数小于0的
: 区域中(S所属的区)极值在分界线上达到。不难可以造出这样一个S,使得(1,1)并非S中
: 最大值。
| c*m
发帖数: 1114 | 17 查了一下，原来concave function都是定义在convex set上面的，那我上面那个-x^2-y
^2的例子就不对了。不过后来想了一下，这个马鞍形函数照样可以做反例，
S区域是取在马鞍形函数concave part上的，就是四个区域中二阶导数小于0的那个区域
上的。极值点出现在交界线上，但经过旋转后交界线已经不是x=1,y=1了，这样你完全
可以话一个S区域导致(1,1)并不是最大点。
【在 r******r 的大作中提到】
: 马鞍函数就不是concave function了呀。
| r******r
发帖数: 74 | 18 马鞍函数是对x是concave的，对y是convex的，那如何找一个区域对x和y是joint
concave呢？
刚才那个－x^2-y^2倒是提醒了我，如果（1,1)是S内x方向和y方向惟一的一个点，这个
结论就不成立了，所以现在重新的定义一下，这个S是个box:
0<=x<=1;
0<=y<=2.
-y
【在 c*m 的大作中提到】
: 查了一下，原来concave function都是定义在convex set上面的，那我上面那个-x^2-y
: ^2的例子就不对了。不过后来想了一下，这个马鞍形函数照样可以做反例，
: S区域是取在马鞍形函数concave part上的，就是四个区域中二阶导数小于0的那个区域
: 上的。极值点出现在交界线上，但经过旋转后交界线已经不是x=1,y=1了，这样你完全
: 可以话一个S区域导致(1,1)并不是最大点。
| c*m
发帖数: 1114 | 19 基本上就是图中这个意思，用paint手画的，比较丑，见谅。
-y
【在 c*m 的大作中提到】
: 查了一下，原来concave function都是定义在convex set上面的，那我上面那个-x^2-y
: ^2的例子就不对了。不过后来想了一下，这个马鞍形函数照样可以做反例，
: S区域是取在马鞍形函数concave part上的，就是四个区域中二阶导数小于0的那个区域
: 上的。极值点出现在交界线上，但经过旋转后交界线已经不是x=1,y=1了，这样你完全
: 可以话一个S区域导致(1,1)并不是最大点。
| c*m
发帖数: 1114 | 20 hehe,看看我下面的图，反例中[1,1]不一定需要是边界点，你对我那个图稍微变动一下
就能得到在[1,1]是内点情况下的反例（把[1,1]附近一小块区域圈进去，同时该区域的
函数稍微变动一下，导致该小区域仍然是concave的，可能表述的不很清楚，不过意思
在那里)
【在 r******r 的大作中提到】
: 马鞍函数是对x是concave的，对y是convex的，那如何找一个区域对x和y是joint
: concave呢？
: 刚才那个－x^2-y^2倒是提醒了我，如果（1,1)是S内x方向和y方向惟一的一个点，这个
: 结论就不成立了，所以现在重新的定义一下，这个S是个box:
: 0<=x<=1;
: 0<=y<=2.
:
: -y
| | | r******r
发帖数: 74 | 21 还是不明白怎么找到一个区域让这个马鞍函数成为一个concave function。
【在 c*m 的大作中提到】
: hehe,看看我下面的图，反例中[1,1]不一定需要是边界点，你对我那个图稍微变动一下
: 就能得到在[1,1]是内点情况下的反例（把[1,1]附近一小块区域圈进去，同时该区域的
: 函数稍微变动一下，导致该小区域仍然是concave的，可能表述的不很清楚，不过意思
: 在那里)
| c*m
发帖数: 1114 | 22 你题目里面只是保证定义域S内函数是concave,
马鞍形函数是定义在整个面上的，完全可以选取其中的一小部分区域，在这个小部分区
域内该马鞍形函数是concave的。而且我前面都被你搞糊涂了，-x^2-y^2的例子照样可
行，可以做成个convex set,再在[1,1]附近对该函数稍作改变，就能handle [1,1]是内
点的case.
【在 r******r 的大作中提到】
: 还是不明白怎么找到一个区域让这个马鞍函数成为一个concave function。
| r******r
发帖数: 74 | 23 比如说
f(x,y)=x^2-y^2，这就是一个马鞍函数，但是无论在什么区域内，它都不可能是
concave的。
【在 c*m 的大作中提到】
: 你题目里面只是保证定义域S内函数是concave,
: 马鞍形函数是定义在整个面上的，完全可以选取其中的一小部分区域，在这个小部分区
: 域内该马鞍形函数是concave的。而且我前面都被你搞糊涂了，-x^2-y^2的例子照样可
: 行，可以做成个convex set,再在[1,1]附近对该函数稍作改变，就能handle [1,1]是内
: 点的case.
| r******r
发帖数: 74 | 24 如果（1,1)是个内点，用KKT条件可以得出 f(x,y)在（1,1）这个点上，在x和y方向上的偏导都为零（再加上一个条件，f是连续二阶偏导），
那么 f(1,1)就是一个极值，又因为f是concave，所以f(1,1)是global maximum。
【在 c*m 的大作中提到】
: 你题目里面只是保证定义域S内函数是concave,
: 马鞍形函数是定义在整个面上的，完全可以选取其中的一小部分区域，在这个小部分区
: 域内该马鞍形函数是concave的。而且我前面都被你搞糊涂了，-x^2-y^2的例子照样可
: 行，可以做成个convex set,再在[1,1]附近对该函数稍作改变，就能handle [1,1]是内
: 点的case.
| c*m
发帖数: 1114 | 25 sorry，我说错了，不是马鞍形函数，是类似这种的函数
f(x,y)=
x^2+y^2 if x>0,y>0
-x^2-y^2 if x<0,y<0
x^2-y^2 if x>0,y<0
-x^2+y^2 if x<0,y>0,
也是二阶连续，在第三象限是concave，在第一象限是convex
【在 r******r 的大作中提到】
: 比如说
: f(x,y)=x^2-y^2，这就是一个马鞍函数，但是无论在什么区域内，它都不可能是
: concave的。
| d******e
发帖数: 7844 | 26 肯定是全局最优了。
上的偏导都为零（再加上一个条件，f是连续二阶偏导），
【在 r******r 的大作中提到】
: 如果（1,1)是个内点，用KKT条件可以得出 f(x,y)在（1,1）这个点上，在x和y方向上的偏导都为零（再加上一个条件，f是连续二阶偏导），
: 那么 f(1,1)就是一个极值，又因为f是concave，所以f(1,1)是global maximum。
| d******e
发帖数: 7844 | 27 没有可导的限定条件的话，是无法保证全局最优的。因为subgradient和Gradient的性
质可不完全一样。如果函数等高线是倾斜的菱形，你可以试试看，是无法是用普通的
coordinate descent的。
【在 Q***5 的大作中提到】
: Ooops....
: You are right.
: I think the conclusion is true even without the assumption about the
: existence of gradient...
| r******r
发帖数: 74 | 28 如果找到一个f是concave的区域，那只可能是在第三象限，其他象限定义的函数，对这
个问题么有作用呀。
【在 c*m 的大作中提到】
: sorry，我说错了，不是马鞍形函数，是类似这种的函数
: f(x,y)=
: x^2+y^2 if x>0,y>0
: -x^2-y^2 if x<0,y<0
: x^2-y^2 if x>0,y<0
: -x^2+y^2 if x<0,y>0,
: 也是二阶连续，在第三象限是concave，在第一象限是convex
| r******r
发帖数: 74 | 29 现在（1,1)不是内点了
定义域为一个矩形区域： 0<=x<=1, 0<=y<=2；
也就是（1,1)在边界上
f仍然是二届可导。
【在 d******e 的大作中提到】
: 肯定是全局最优了。
:
: 上的偏导都为零（再加上一个条件，f是连续二阶偏导），
| d******e
发帖数: 7844 | 30 如果函数和限制都是已知的，你先看看能不能解一下不就知道是不是最优了么。
这种box constraint解起来再容易不过了。
【在 r******r 的大作中提到】
: 现在（1,1)不是内点了
: 定义域为一个矩形区域： 0<=x<=1, 0<=y<=2；
: 也就是（1,1)在边界上
: f仍然是二届可导。
|
|
