应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

Znn3bq.jpeg
小木虫论坛-学术科研互动平台 » 专业学科区 » 数学 » 运筹学与控制论 » 大规模优化数值计算，梯度的计算方式讨论
251/1返回列表
查看: 3396  |  回复: 24
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

chaogumath

铜虫 (小有名气)

[交流] 大规模优化数值计算，梯度的计算方式讨论

各位，
    最近在做非线性规划的大规模数值计算。用的是向前差分近似计算梯度：
g=[f(xi+h)-f(xi)]/h，用for i=1:n 进行循环计算。但是大家看到，如果变量有500个的话，就要计算500次f(xi+h)，这个计算量太大了。例如：f(xi+h)计算1次需要0.001秒，那么，计算梯度g就需要5秒。这已经占了整个计算时间的70%。咋办？请教各位同仁。
回复此楼

» 本帖已获得的红花（最新10朵）

chaogumath chaogumath

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:

» 抢金币啦！回帖就可以得到:

查看全部散金贴
1楼 2011-08-30 06:31:05
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

pengyehui

木虫 (正式写手)
★
chaogumath(金币+2):谢谢参与
500不叫大
计算500次不叫多
计算1次需要0.001秒，你的机子比蜗牛还慢，的改善硬件！
赞一下(1人) 回复此楼
2楼2011-08-30 07:23:32
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

chaogumath

铜虫 (小有名气)
送鲜花一朵
只是举个例子，500只能算小规模的。
这句话看了没有？“这已经占了整个计算时间的70%。”一个循环需要8秒的话，计算g就需要5秒。你做实验的时候是这样的吗？
请大侠分析得透彻一点，否则云里雾里的，抓不到本质。呵呵。
赞一下 回复此楼
3楼2011-08-30 08:24:27
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

pengyehui

木虫 (正式写手)
★
chaogumath(金币+2):谢谢参与
你这里关键是函数值的计算耗费时间，与优化算法没什么关系啊？
如果你的函数计算，要解一个pde或者cfd，那就慢了，
所以，你的从函数计算着手解决问题
赞一下(1人) 回复此楼
4楼2011-08-30 11:13:15
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

saladin983

铁杆木虫 (正式写手)
★
chaogumath(金币+2):谢谢参与
如果是用matlab，把for循环去掉估计能省下不少时间。否则的话，很难。优化问题中梯度、Hessian之类的信息一向都是难点。在一些特殊问题上，人们会有特别的方法来对待，不过通行的技巧据我所知是不存在的。通过算法上的改进来控制总体的计算量，这样的可能性当然存在，可以选取合适的全局算法，比如某些单调问题的免梯度算法，即便是计算梯度，也许也可以引入其他技巧，但是这个对于问题本身的依赖很强。建议多看看同类问题的文献，或许能有收获。
赞一下(1人) 回复此楼
5楼2011-08-30 20:40:19
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

chaogumath

铜虫 (小有名气)
这个for循环确实厉害。使我想到一句话，中国人民的事情，就算再小，乘以13亿就是大事了。呵呵。谢谢各位指点。
赞一下 回复此楼
6楼2011-09-03 23:28:15
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

潇湘子博客

木虫 (职业作家)
★
chaogumath(金币+2):谢谢参与
nono2009: 专业区讨论贴请勿灌水赚金币！ 2011-09-05 21:33:50
支持五楼！！
回复此楼
7楼2011-09-04 01:09:16
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

潇湘子博客

木虫 (职业作家)
★
chaogumath(金币+2):谢谢参与
六楼！这是周总理说的话。
赞一下(1人) 回复此楼
8楼2011-09-04 01:10:22
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

潇湘子博客

木虫 (职业作家)
★
chaogumath(金币+2):谢谢参与
的确啊！！中国人民的事情，就算再小，乘以13亿就是大事了
赞一下(1人) 回复此楼
9楼2011-09-04 01:10:59
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

saladin983

铁杆木虫 (正式写手)
★
chaogumath(金币+2):谢谢参与
引用回帖:
6楼: Originally posted by chaogumath at 2011-09-03 17:28:15:
这个for循环确实厉害。使我想到一句话，中国人民的事情，就算再小，乘以13亿就是大事了。呵呵。谢谢各位指点。

关于Matlab的循环，多说两句吧。因为Matlab是执行脚本的，而不是像C++之类的编译后执行，循环的本质是每次都重新读取代码执行，这个效率是极其低下的，所以尽量避免使用循环语句是Matlab编程的一条基本准则。而Matlab也提供很多内建的程序使得很多情况下剔除循环语句成为可能。
赞一下(1人) 回复此楼
10楼2011-09-04 03:31:26
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

chaogumath

铜虫 (小有名气)
fortran语言是编译后执行吗？应该比matlab好？
我现在用Octave，他的循环也是跟matlab一样的吧？时间超长。
赞一下 回复此楼
12楼2011-09-04 21:40:54
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

saladin983

铁杆木虫 (正式写手)
★
chaogumath(金币+2):谢谢参与
引用回帖:
12楼: Originally posted by chaogumath at 2011-09-04 15:40:54:
fortran语言是编译后执行吗？应该比matlab好？
我现在用Octave，他的循环也是跟matlab一样的吧？时间超长。

Fortran我没有用过，但是因为是编译后执行，所以效率更高应该是没有问题的。Octave算是Matlab的效仿者吧，而且逐渐流行也是因为开源和与Matlab兼容比较好，两者应该是差不多的。
赞一下(1人) 回复此楼
13楼2011-09-05 15:46:58
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

chaogumath

铜虫 (小有名气)
有什么方法能去除for循环
赞一下 回复此楼
17楼2011-09-07 08:51:46
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huyunq

新虫 (初入文坛)
★
小木虫(金币+0.5):给个红包，谢谢回帖
尽量用解析表达式。如果避免不了，才考虑使用数值求导，即你所说的差分表达式。
赞一下(1人) 回复此楼
18楼2011-11-19 23:18:21
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

daicong

木虫 (小有名气)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
10楼: Originally posted by saladin983 at 2011-09-03 07:31:26:
关于Matlab的循环，多说两句吧。因为Matlab是执行脚本的，而不是像C++之类的编译后执行，循环的本质是每次都重新读取代码执行，这个效率是极其低下的，所以尽量避免使用循环语句是Matlab编程的一条基本准则。而M ...

看到高手了，你能否指点一下下面这个问题呢？
我就开门见山的说问题了：举一个例子

min   z=14.3-6*x-21*y
s.t.   x+y-c=0.99
x+y+c=1.41
x+2y-c=1.57
x+2y+c=2.03
x+3y-c=1.9
x+3y+c=2.3
c>=0

求解：x,y的范围。应该用什么方法？
赞一下(1人) 回复此楼
19楼2011-12-09 03:59:19
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

saladin983

铁杆木虫 (正式写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
19楼: Originally posted by daicong at 2011-12-08 21:59:19:
看到高手了，你能否指点一下下面这个问题呢？
我就开门见山的说问题了：举一个例子

min   z=14.3-6*x-21*y
s.t.   x+y-c=0.99
x+y+c=1.41
x+2y-c=1.57
x+2y+c=2.03
x+3y-c=1.9
x+3y+c=2.3
c>=0

...

线性规划的解法比如单纯形法或许能给出解，不过如果是给出范围的话，恐怕需要去看看运筹学的书了，印象当中可以画割线图求解，毕竟只有二维。最大的问题在于，这里的c到底是常量还是变量。如果是常量，就有矛盾的方程了，充其量能给个某种意义下的最小二乘解。如果是变量，那么这个问题的维度就提高了。
赞一下(1人) 回复此楼
20楼2011-12-09 21:40:17
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

daicong

木虫 (小有名气)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
20楼: Originally posted by saladin983 at 2011-12-09 01:40:17:
线性规划的解法比如单纯形法或许能给出解，不过如果是给出范围的话，恐怕需要去看看运筹学的书了，印象当中可以画割线图求解，毕竟只有二维。最大的问题在于，这里的c到底是常量还是变量。如果是常量，就有矛盾的 ...

因为是范围，所以你的推荐是使用“画个线图求解”是吗？
c其实本来不存在的，因为原来的约束条件是大于等于和小于等于，所以为了转换成标准的形式，加入了c，即c是大于等于0的，是一个范围。
赞一下(2人) 回复此楼
21楼2011-12-10 02:36:18
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

saladin983

铁杆木虫 (正式写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
21楼: Originally posted by daicong at 2011-12-09 20:36:18:
因为是范围，所以你的推荐是使用“画个线图求解”是吗？
c其实本来不存在的，因为原来的约束条件是大于等于和小于等于，所以为了转换成标准的形式，加入了c，即c是大于等于0的，是一个范围。

c是松弛变量的话，运筹学的教材中应该有对应的例子了，拿线性规划的方法姐就是了。手头没有运筹的书，你可以翻一下看。
赞一下(2人) 回复此楼
22楼2011-12-10 07:21:44
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

小巫巫

新虫 (初入文坛)
★
小木虫(金币+0.5):给个红包，谢谢回帖
如果你使用的matlab的话，循环次数很花费时间的，你不妨将循环文件用Ｃ语言写，然后做一个接口，用ｍａｔｌａｂ进行调用，这样子会快很多的
赞一下 回复此楼
23楼2012-03-11 13:45:55
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

chaogumath

铜虫 (小有名气)
送鲜花一朵
兄弟的计算机水平不行，做不来调用的事情。呵呵
赞一下 回复此楼
24楼2012-03-13 19:44:19
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
简单回复
zyxme11楼
2011-09-04 05:41   回复  
chaogumath(金币+2):谢谢参与
nono2009: 专业区讨论贴请勿灌水赚金币！ 2011-09-05 21:34:08
祝福
scx110914楼
2011-09-05 16:04   回复  
chaogumath(金币+2):谢谢参与
nono2009: 专业区讨论贴请勿灌水赚金币！ 2011-09-05 21:34:20
scx110915楼
2011-09-05 16:04   回复  
chaogumath(金币+2):谢谢参与
scx110916楼
2011-09-05 16:04   回复  
chaogumath(金币+2):谢谢参与
wzp18247525楼
2012-03-22 12:12   回复  
相关版块跳转 我要订阅楼主 chaogumath 的主题更新
251/1返回列表
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
信息提示
关闭
请填处理意见
关闭