b****u
发帖数: 1130 | 1 目标函数 f(x1, x2, x3.....). 1000个变量，二次型目标函数
约束 xi>=0
x1+x2+x3.....=1
但最多只能有30个变量大于0，其余都是0 （这个最麻烦了，没这就好搞多了）
我本来想把L1约束加到目标函数中，但担心结果很不稳定。
现在打算用非传统的方法搞，比如遗传算法，模拟退火或集群算法。
大家有没有啥推荐的方法？ |
g****t
发帖数: 31659 | 2 （log barrier etc） 牛顿法试验过了？不工作？
启发式方法的缺点是缺乏预测性。
忙两个月，结果可能是0。
梯度based method忙两个月，一般结果可以是正贡献，就是比啥也不干的好。
【在 b****u 的大作中提到】
: 目标函数 f(x1, x2, x3.....). 1000个变量，二次型目标函数
: 约束 xi>=0
: x1+x2+x3.....=1
: 但最多只能有30个变量大于0，其余都是0 （这个最麻烦了，没这就好搞多了）
: 我本来想把L1约束加到目标函数中，但担心结果很不稳定。
: 现在打算用非传统的方法搞，比如遗传算法，模拟退火或集群算法。
: 大家有没有啥推荐的方法？
|
b****u
发帖数: 1130 | 3 最麻烦的就是 正的变量个数不能超过30个。
这个比较麻烦，其实是个混合整数规划。
而且数值最优化，你要我自己实现内点法，甚至最基本的牛顿法，我还是相当头疼的。
这方面我和你的差距估计得用光年来计算。
【在 g****t 的大作中提到】
: （log barrier etc） 牛顿法试验过了？不工作？
: 启发式方法的缺点是缺乏预测性。
: 忙两个月，结果可能是0。
: 梯度based method忙两个月，一般结果可以是正贡献，就是比啥也不干的好。
|
g****t
发帖数: 31659 | 4 你是做产品还是写论文？
如果做产品，我干半年差不多。不是一句话能说清楚。
需要边试边走。还需要改问题的定义。
这个问题从算法角度来讲，
显然是没有通用办法，而且可能是ill conditional,NP hard. 所以
技术这边要压榨business那边给更合适的问题定义。
这类似于从股市挑30个股票买，跑个什么马尔科维兹优化,难
度可想而知。
如果写论文，那就找个大学课程抄一下logbarrier吧。反正你做启发式一般最后还是要
比较优劣。
for example:
https://www.cv-foundation.org/openaccess/content_cvpr_2014/papers/Yuan_
Newton_Greedy_Pursuit_2014_CVPR_paper.pdf
www.cv-foundation.org/openaccess/content_cvpr_2014/papers/Yuan_Newton_Greedy
_Pursuit_2014_CVPR_paper.pdf
: 最麻烦的就是 正的变量个数不能超过30个。
: 这个比较麻烦，其实是个混合整数规划。
: 而且数值最优化，你要我自己实现内点法，甚至最基本的牛顿法，我还是
相当头
疼的。
: 这方面我和你的差距估计得用光年来计算。
【在 b****u 的大作中提到】
: 最麻烦的就是 正的变量个数不能超过30个。
: 这个比较麻烦，其实是个混合整数规划。
: 而且数值最优化，你要我自己实现内点法，甚至最基本的牛顿法，我还是相当头疼的。
: 这方面我和你的差距估计得用光年来计算。
|
s*******g
发帖数: 187 | 5 Sparsity optimization 用l1是王道啊，有现成的toolbox
http://cvxopt.org/applications/nucnrm/
【在 b****u 的大作中提到】
: 目标函数 f(x1, x2, x3.....). 1000个变量，二次型目标函数
: 约束 xi>=0
: x1+x2+x3.....=1
: 但最多只能有30个变量大于0，其余都是0 （这个最麻烦了，没这就好搞多了）
: 我本来想把L1约束加到目标函数中，但担心结果很不稳定。
: 现在打算用非传统的方法搞，比如遗传算法，模拟退火或集群算法。
: 大家有没有啥推荐的方法？
|
N*****r
发帖数: 94 | 6
这个不可以直接上L0正则吗， 现在L0也是有办法做的
【在 b****u 的大作中提到】
: 目标函数 f(x1, x2, x3.....). 1000个变量，二次型目标函数
: 约束 xi>=0
: x1+x2+x3.....=1
: 但最多只能有30个变量大于0，其余都是0 （这个最麻烦了，没这就好搞多了）
: 我本来想把L1约束加到目标函数中，但担心结果很不稳定。
: 现在打算用非传统的方法搞，比如遗传算法，模拟退火或集群算法。
: 大家有没有啥推荐的方法？
|
L****8
发帖数: 3938 | 7 gurobi solver 这个小意思了
【在 b****u 的大作中提到】
: 目标函数 f(x1, x2, x3.....). 1000个变量，二次型目标函数
: 约束 xi>=0
: x1+x2+x3.....=1
: 但最多只能有30个变量大于0，其余都是0 （这个最麻烦了，没这就好搞多了）
: 我本来想把L1约束加到目标函数中，但担心结果很不稳定。
: 现在打算用非传统的方法搞，比如遗传算法，模拟退火或集群算法。
: 大家有没有啥推荐的方法？
|
g****t
发帖数: 31659 | 8 你们这都是纸上谈兵。他这个问题类似于1块钱，从1000个股票里分散买30个股票。不
能short。二次型portfolio 优化什么的。
处理实际问题是很难的。
: gurobi solver 这个小意思了
【在 L****8 的大作中提到】
: gurobi solver 这个小意思了
|
L****8
发帖数: 3938 | 9 gurobi solver 找个解 易如反掌
至于是不是处理实际问题 那是lz的建模问题
【在 g****t 的大作中提到】
: 你们这都是纸上谈兵。他这个问题类似于1块钱，从1000个股票里分散买30个股票。不
: 能short。二次型portfolio 优化什么的。
: 处理实际问题是很难的。
:
:
: gurobi solver 这个小意思了
:
|
g****t
发帖数: 31659 | 10 你找出来的解是什么解？软件打印个数字就叫解吗？
: gurobi solver 找个解 易如反掌
: 至于是不是处理实际问题 那是lz的建模问题
【在 L****8 的大作中提到】
: gurobi solver 找个解 易如反掌
: 至于是不是处理实际问题 那是lz的建模问题
|
|
|
w***g
发帖数: 5958 | 11 难道现在NP难的问题都可以易如反掌地求解了，科技发展真是日新月异。
【在 L****8 的大作中提到】
: gurobi solver 找个解 易如反掌
: 至于是不是处理实际问题 那是lz的建模问题
|
N*****r
发帖数: 94 | 12
问题是NP， 并不代表彻底不能求解啊
单纯形法也是NP吧， 大家曾经也用的很high啊
【在 w***g 的大作中提到】
: 难道现在NP难的问题都可以易如反掌地求解了，科技发展真是日新月异。
|
b****u
发帖数: 1130 | 13 目标函数 f(x1, x2, x3.....). 1000个变量，二次型目标函数
约束 xi>=0
x1+x2+x3.....=1
但最多只能有30个变量大于0，其余都是0 （这个最麻烦了，没这就好搞多了）
我本来想把L1约束加到目标函数中，但担心结果很不稳定。
现在打算用非传统的方法搞，比如遗传算法，模拟退火或集群算法。
大家有没有啥推荐的方法？ |
g****t
发帖数: 31659 | 14 （log barrier etc） 牛顿法试验过了？不工作？
启发式方法的缺点是缺乏预测性。
忙两个月，结果可能是0。
梯度based method忙两个月，一般结果可以是正贡献，就是比啥也不干的好。
【在 b****u 的大作中提到】
: 目标函数 f(x1, x2, x3.....). 1000个变量，二次型目标函数
: 约束 xi>=0
: x1+x2+x3.....=1
: 但最多只能有30个变量大于0，其余都是0 （这个最麻烦了，没这就好搞多了）
: 我本来想把L1约束加到目标函数中，但担心结果很不稳定。
: 现在打算用非传统的方法搞，比如遗传算法，模拟退火或集群算法。
: 大家有没有啥推荐的方法？
|
b****u
发帖数: 1130 | 15 最麻烦的就是 正的变量个数不能超过30个。
这个比较麻烦，其实是个混合整数规划。
而且数值最优化，你要我自己实现内点法，甚至最基本的牛顿法，我还是相当头疼的。
这方面我和你的差距估计得用光年来计算。
【在 g****t 的大作中提到】
: （log barrier etc） 牛顿法试验过了？不工作？
: 启发式方法的缺点是缺乏预测性。
: 忙两个月，结果可能是0。
: 梯度based method忙两个月，一般结果可以是正贡献，就是比啥也不干的好。
|
g****t
发帖数: 31659 | 16 你是做产品还是写论文？
如果做产品，我干半年差不多。不是一句话能说清楚。
需要边试边走。还需要改问题的定义。
这个问题从算法角度来讲，
显然是没有通用办法，而且可能是ill conditional,NP hard. 所以
技术这边要压榨business那边给更合适的问题定义。
这类似于从股市挑30个股票买，跑个什么马尔科维兹优化,难
度可想而知。
如果写论文，那就找个大学课程抄一下logbarrier吧。反正你做启发式一般最后还是要
比较优劣。
for example:
https://www.cv-foundation.org/openaccess/content_cvpr_2014/papers/Yuan_
Newton_Greedy_Pursuit_2014_CVPR_paper.pdf
www.cv-foundation.org/openaccess/content_cvpr_2014/papers/Yuan_Newton_Greedy
_Pursuit_2014_CVPR_paper.pdf
: 最麻烦的就是 正的变量个数不能超过30个。
: 这个比较麻烦，其实是个混合整数规划。
: 而且数值最优化，你要我自己实现内点法，甚至最基本的牛顿法，我还是
相当头
疼的。
: 这方面我和你的差距估计得用光年来计算。
【在 b****u 的大作中提到】
: 最麻烦的就是 正的变量个数不能超过30个。
: 这个比较麻烦，其实是个混合整数规划。
: 而且数值最优化，你要我自己实现内点法，甚至最基本的牛顿法，我还是相当头疼的。
: 这方面我和你的差距估计得用光年来计算。
|
s*******g
发帖数: 187 | 17 Sparsity optimization 用l1是王道啊，有现成的toolbox
http://cvxopt.org/applications/nucnrm/
【在 b****u 的大作中提到】
: 目标函数 f(x1, x2, x3.....). 1000个变量，二次型目标函数
: 约束 xi>=0
: x1+x2+x3.....=1
: 但最多只能有30个变量大于0，其余都是0 （这个最麻烦了，没这就好搞多了）
: 我本来想把L1约束加到目标函数中，但担心结果很不稳定。
: 现在打算用非传统的方法搞，比如遗传算法，模拟退火或集群算法。
: 大家有没有啥推荐的方法？
|
N*****r
发帖数: 94 | 18
这个不可以直接上L0正则吗， 现在L0也是有办法做的
【在 b****u 的大作中提到】
: 目标函数 f(x1, x2, x3.....). 1000个变量，二次型目标函数
: 约束 xi>=0
: x1+x2+x3.....=1
: 但最多只能有30个变量大于0，其余都是0 （这个最麻烦了，没这就好搞多了）
: 我本来想把L1约束加到目标函数中，但担心结果很不稳定。
: 现在打算用非传统的方法搞，比如遗传算法，模拟退火或集群算法。
: 大家有没有啥推荐的方法？
|
L****8
发帖数: 3938 | 19 gurobi solver 这个小意思了
【在 b****u 的大作中提到】
: 目标函数 f(x1, x2, x3.....). 1000个变量，二次型目标函数
: 约束 xi>=0
: x1+x2+x3.....=1
: 但最多只能有30个变量大于0，其余都是0 （这个最麻烦了，没这就好搞多了）
: 我本来想把L1约束加到目标函数中，但担心结果很不稳定。
: 现在打算用非传统的方法搞，比如遗传算法，模拟退火或集群算法。
: 大家有没有啥推荐的方法？
|
g****t
发帖数: 31659 | 20 你们这都是纸上谈兵。他这个问题类似于1块钱，从1000个股票里分散买30个股票。不
能short。二次型portfolio 优化什么的。
处理实际问题是很难的。
: gurobi solver 这个小意思了
【在 L****8 的大作中提到】
: gurobi solver 这个小意思了
|
|
|
L****8
发帖数: 3938 | 21 gurobi solver 找个解 易如反掌
至于是不是处理实际问题 那是lz的建模问题
【在 g****t 的大作中提到】
: 你们这都是纸上谈兵。他这个问题类似于1块钱，从1000个股票里分散买30个股票。不
: 能short。二次型portfolio 优化什么的。
: 处理实际问题是很难的。
:
:
: gurobi solver 这个小意思了
:
|
g****t
发帖数: 31659 | 22 你找出来的解是什么解？软件打印个数字就叫解吗？
: gurobi solver 找个解 易如反掌
: 至于是不是处理实际问题 那是lz的建模问题
【在 L****8 的大作中提到】
: gurobi solver 找个解 易如反掌
: 至于是不是处理实际问题 那是lz的建模问题
|
w***g
发帖数: 5958 | 23 难道现在NP难的问题都可以易如反掌地求解了，科技发展真是日新月异。
【在 L****8 的大作中提到】
: gurobi solver 找个解 易如反掌
: 至于是不是处理实际问题 那是lz的建模问题
|
N*****r
发帖数: 94 | 24
问题是NP， 并不代表彻底不能求解啊
单纯形法也是NP吧， 大家曾经也用的很high啊
【在 w***g 的大作中提到】
: 难道现在NP难的问题都可以易如反掌地求解了，科技发展真是日新月异。
|
l*******m
发帖数: 1096 | 25 先用L1好了，lasso的本质就是greedy, 根据改变惩罚系数，来改变为零的变量。所以
如果greedy 产生的为零变量的序列比较稳定，你的结果就会稳定
：目标函数 f(x1, x2, x3.....). 1000个变量，二次型目标函数
：约束 xi>=0 |
w***g
发帖数: 5958 | 26 线性规划是多项式难度
整数线性规划是np难
问题难度不一样，和算法无关
单纯形法最差情况下是指数，
但是有研究表明平均意义下是多项式时间的。楼主的问题，要么用次优解，
要么尽量重新定义问题。
比如弄成网络流啥的形式，就可以解了。
：
：【 在 wdong (万事休) 的大作中提到: 】 |
b****u
发帖数: 1130 | 27 其实这个就是在选股。刚刚把程序调通，现在的方案是二次型优化嵌入到遗传优化当中
去。
小范围（100 选3）的结果还不错。明天多搞点数据，跑一跑。
其实我们需要很多次优解，然后再加入人工分析做最后选择。
【在 g****t 的大作中提到】
: 你是做产品还是写论文？
: 如果做产品，我干半年差不多。不是一句话能说清楚。
: 需要边试边走。还需要改问题的定义。
: 这个问题从算法角度来讲，
: 显然是没有通用办法，而且可能是ill conditional,NP hard. 所以
: 技术这边要压榨business那边给更合适的问题定义。
: 这类似于从股市挑30个股票买，跑个什么马尔科维兹优化,难
: 度可想而知。
: 如果写论文，那就找个大学课程抄一下logbarrier吧。反正你做启发式一般最后还是要
: 比较优劣。
|
g****t
发帖数: 31659 | 28 （1）
如你所知，实现梯度为基础的办法，成本颇高。不是老司机的话，软件质量存疑。
但是我认为今后ANN的成熟tool chain会在使用中代替各种乱七八糟的梯度，牛顿，海
赛矩阵的应用。
所以第一推荐你可以试下整数线性规划用ANN，BP等来求解。
也许你很容易就可以和tensorflow等接起来。
本质上就相当于绕过自己实现梯度和伪梯度计算。
这是我第一推荐的办法。tool齐备。
把整数规划什么的modeling成神经网络的文献应该是90年代就有了。
缺点是现在dl不算海塞矩阵。用adams等估计来代替。
3000变量也许海塞阵速度会好一些。但你有GPU的话。。。
（2）
你用什么写的程序？tool chain方便说一下吗？
回头我也要写个遗传算法。
（3）
wdong说的网络流也可以试一下。
尽管改定义改优化指标不一定能改出来。
【在 b****u 的大作中提到】
: 其实这个就是在选股。刚刚把程序调通，现在的方案是二次型优化嵌入到遗传优化当中
: 去。
: 小范围（100 选3）的结果还不错。明天多搞点数据，跑一跑。
: 其实我们需要很多次优解，然后再加入人工分析做最后选择。
|
w***g
发帖数: 5958 | 29 选股就不用纠结最优解了啊，你很可能有系统性问题，最优也没用。
：其实这个就是在选股。刚刚把程序调通，现在的方案是二次型优化嵌入到遗传优化当
中去。
：小范围（100 选3）的结果还不错。明天多搞点数据，跑一跑。 |
b****u
发帖数: 1130 | 30 我现在就用用python包。 二次型优化就用CVXOPT，还行，不过要把初值和精度弄好了
，否则会给出很搞笑的结果。
遗传算法就套用DEAP包。我这个不用上生产线，内部用，估计就是给几个还行的次优解
，然后调调参数，再打打嘴炮。
其实基本就是个玩具。
【在 g****t 的大作中提到】
: （1）
: 如你所知，实现梯度为基础的办法，成本颇高。不是老司机的话，软件质量存疑。
: 但是我认为今后ANN的成熟tool chain会在使用中代替各种乱七八糟的梯度，牛顿，海
: 赛矩阵的应用。
: 所以第一推荐你可以试下整数线性规划用ANN，BP等来求解。
: 也许你很容易就可以和tensorflow等接起来。
: 本质上就相当于绕过自己实现梯度和伪梯度计算。
: 这是我第一推荐的办法。tool齐备。
: 把整数规划什么的modeling成神经网络的文献应该是90年代就有了。
: 缺点是现在dl不算海塞矩阵。用adams等估计来代替。
|
|
|
g****t
发帖数: 31659 | 31 你们的组织，two language dilemma怎么办？
R/matlab/Python cpp/c 吗？
我们是不同的组。matlab. Python Etc 加上C.
算法和developer分开。但是
developer不是算法的developer。算法的人
又开发的不是可以做developing的算法。
经常崩溃。
一崩溃我就休息半年。
: 我现在就用用python包。 二次型优化就用CVXOPT，还行，不过要把初值
和精度
弄好了
: ，否则会给出很搞笑的结果。
: 遗传算法就套用DEAP包。我这个不用上生产线，内部用，估计就是给几个
还行的
次优解
: ，然后调调参数，再打打嘴炮。
: 其实基本就是个玩具。
【在 b****u 的大作中提到】
: 我现在就用用python包。 二次型优化就用CVXOPT，还行，不过要把初值和精度弄好了
: ，否则会给出很搞笑的结果。
: 遗传算法就套用DEAP包。我这个不用上生产线，内部用，估计就是给几个还行的次优解
: ，然后调调参数，再打打嘴炮。
: 其实基本就是个玩具。
|
b****u
发帖数: 1130 | 32 我们R/matlab／vbs/python/java/scala/go/js 都有。
一团糟，我现在让他们尽可能多用python，这样维护或者需要上production的时候都会
比较方便。
【在 g****t 的大作中提到】
: 你们的组织，two language dilemma怎么办？
: R/matlab/Python cpp/c 吗？
: 我们是不同的组。matlab. Python Etc 加上C.
: 算法和developer分开。但是
: developer不是算法的developer。算法的人
: 又开发的不是可以做developing的算法。
: 经常崩溃。
: 一崩溃我就休息半年。
:
:
: 我现在就用用python包。 二次型优化就用CVXOPT，还行，不过要把初值
|
