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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 数学 » 数学综合 » 全局最优解
101/1返回列表
查看: 2507  |  回复: 9
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

chuhongyun

金虫 (小有名气)

[求助] 全局最优解

刚接触数学优化算法，学得不够系统所以存在许多漏洞，在这想请教牛人一些问题，我不要具体的证明过程，只要大致的思想和物理意义，谢谢：
1、怎样证明一个目标函数一定有可行解呢？一定有全局最优解？
2、具备怎样条件的优化问题才会得到全局最优解？
3、得到可行解后，怎样证明是全局最优解?
谢谢
回复此楼

» 猜你喜欢
1楼 2012-06-30 18:47:04
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

whyhow

铁杆木虫 (著名写手)

带你飞翔

【答案】应助回帖

★ ★
感谢参与，应助指数 +1
soliton923: 金币+1, 谢谢参与讨论~~~ 2012-06-30 20:30:13
chuhongyun: 金币+1, ★有帮助, 谢谢 2012-07-01 10:40:10
我觉得这么泛泛的问很难回答, 这个要看具体的函数性质, 以及解空间的情况.

例如函数如果有凸性, 空间有紧性问题就比较容易解决了. 通常有限维的问题要比无穷维容易很多.
赞一下 回复此楼
青春有千万种，却没有一种可以重来
2楼2012-06-30 19:27:33
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

liuanan

专家顾问 (著名写手)
楼主，你提问方式有问题哦
赞一下 回复此楼
3楼2012-06-30 22:04:13
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

locustzhang

木虫 (著名写手)

【答案】应助回帖

★ ★ ★
感谢参与，应助指数 +1
chuhongyun: 金币+3, ★★★很有帮助, 谢谢 2012-07-01 10:41:28
1、怎样证明一个目标函数一定有可行解呢？一定有全局最优解？
2、具备怎样条件的优化问题才会得到全局最优解？
3、得到可行解后，怎样证明是全局最优解?
回答：
1、基本上无法证明，如果没有可行解说明你的优化问题是完全错误的，毫无意义的。全局最优解可以说都有的，如果没有那么去近似他。没有的情况很少，意义不大！
2、只要优化模型不错误，约束函数为闭就有全局，至于如何得到？太难了，现在可解的仅仅是极少一部分特殊优化问题，基本上都是近似解！
3、基本上无法证明，除非是特殊优化。迭代算法基本上就是近似。
赞一下 回复此楼
4楼2012-07-01 08:10:20
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

chuhongyun

金虫 (小有名气)
引用回帖:
3楼: Originally posted by liuanan at 2012-06-30 22:04:13
楼主，你提问方式有问题哦

谢谢您的指教
回复此楼
5楼2012-07-01 10:40:36
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

chuhongyun

金虫 (小有名气)
引用回帖:
4楼: Originally posted by locustzhang at 2012-07-01 08:10:20
1、怎样证明一个目标函数一定有可行解呢？一定有全局最优解？
2、具备怎样条件的优化问题才会得到全局最优解？
3、得到可行解后，怎样证明是全局最优解?
回答：
1、基本上无法证明，如果没有可行解说明你的优化 ...

首先非常感谢您的回答，
但是我觉得从数学严谨的证明逻辑上来考虑，要想求一个目标函数的全局最优解的步骤应该是：
1、证明有可行解，其中可行是有严格定义的，不是说看一下目标函数及其约束条件就能看出来的；
2、在说明确实存在可行解的前提下，在开始求解，因为数学问题用在工科应用中，无解的情况是有特殊含义的，并不是代表无意义，比如目标函数无解可以表示某点是孤立节点，从而对其获取的信息进行有别于其他节点的处理；
3、在求出最优解后，需要验证结果是否是全局最优或者是满足应用需求获得的最优解，因为很多迭代算法需要给出初始值，但是初始值选取不当可能造成局部最优，所以我想知道除了证明目标函数是凸函数外，还有什么方法可以证明只要求出了最优解就一定能够证明其是全局最优的呢？
谢谢
赞一下 回复此楼
6楼2012-07-01 10:51:44
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

allenjcn

木虫 (小有名气)

【答案】应助回帖

★ ★
感谢参与，应助指数 +1
chuhongyun: 金币+2, ★★★很有帮助, 谢谢 2012-07-01 22:06:53
数学的严格性从来就没有标准，而对于确定是否为全局最优解，作为专业数学软件，matlab在其优化工具箱中提供了一个让人印象深刻的解决办法，即对可行域划分为若干个区间，然后每个区间求取局部最优，最后将若干个局部最优简单比较大小，便得到全局最优。目前，matlab能自行划分区间，数目也可选系统计算或手动控制。该方法的原理相信懂得分蛋糕的人和专业数学人士都非常面熟。
赞一下 回复此楼
7楼2012-07-01 17:44:45
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

rainbowguy

银虫 (正式写手)

【答案】应助回帖

★ ★
感谢参与，应助指数 +1
chuhongyun: 金币+2, ★★★很有帮助, 谢谢 2012-07-01 22:06:35
引用回帖:
6楼: Originally posted by chuhongyun at 2012-07-01 10:51:44
首先非常感谢您的回答，
但是我觉得从数学严谨的证明逻辑上来考虑，要想求一个目标函数的全局最优解的步骤应该是：
1、证明有可行解，其中可行是有严格定义的，不是说看一下目标函数及其约束条件就能看出来的；
...

目前，除了凸函数优化问题中可以证明其局部最优解就是全局最优外，其他优化问题无法严格证明你求得的是不是全局最优解，很可能你得到的局部最优或近似全局最优。可以像allenjcn  说的，将可行域分几块，然后再比较，但这也不是严格证明求的最优解就是全局最优解。
如果lz非要求出全局最优，可以尝试将优化问题转变成凸规划问题，这样就一定可以获得全局最优解。
赞一下 回复此楼
8楼2012-07-01 21:09:36
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

locustzhang

木虫 (著名写手)

【答案】应助回帖

★ ★
chuhongyun: 金币+2, ★★★很有帮助 2012-07-02 09:16:53
引用回帖:
6楼: Originally posted by chuhongyun at 2012-07-01 10:51:44
首先非常感谢您的回答，
但是我觉得从数学严谨的证明逻辑上来考虑，要想求一个目标函数的全局最优解的步骤应该是：
1、证明有可行解，其中可行是有严格定义的，不是说看一下目标函数及其约束条件就能看出来的；
...

其实即使对于凸函数来说，寻找一个可行解也是非常难的（非常非常难）。有两种办法：1、通过不可行的解去逼近可行解，得到后看误差是多少，满足要求即可。
2、人工办法使得某个解可行（通过扰动原问题或者自对偶办法），但是维数增加太大（一倍或者更多，如果上十万维的话可想而知）。
至于你的回复我认为：优化问题在最初的产生就是一个模型，任何模型不可行就意味着该模型不能反映正常的现象，属于错误的模型，是无意义的。另外：如果该优化问题目标函数根本就不是凸函数，你怎么去证明呢？对于工程中的优化问题最难的1、证明是凸优化问题2、寻找可行解3、寻找有效算法。
赞一下 回复此楼
9楼2012-07-02 06:25:00
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

juwan

木虫 (知名作家)
必须是凸的问题
回复此楼
10楼2012-08-15 09:30:41
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 chuhongyun 的主题更新
101/1返回列表
普通表情 龙 兔 虎 猫
信息提示
关闭
请填处理意见
关闭