24小时热门版块排行榜

返回列表

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

zdy2008

新虫 (小有名气)

应助: 4 (幼儿园)
金币: 87.4
散金: 135
帖子: 260
在线: 124.4小时
虫号: 2788226
注册: 2013-11-08
性别: GG
专业: 运筹学

[求助] 一个约束规划问题求解已有5人参与

求解这类约束规划问题有没有运算速度比较快的算法？我这里的X是6200维的向量，A是7000*6200的矩阵，lb和ub都是6200维的向量。用matlab自带的规划算法计算速度非常慢！

1W(V{2MA2$BM_GU]DI2R5WY.jpg

回复此楼

» 猜你喜欢

职称评审没过，求安慰已经有56人回复
最近几年招的学生写论文不引自己组发的文章已经有5人回复
26申博自荐已经有3人回复
A期刊撤稿已经有4人回复

1楼 2014-07-05 13:06:26

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

suntree4152

铁虫 (正式写手)

应助: 31 (小学生)
金币: 1861.3
红花: 11
帖子: 378
在线: 150.9小时
虫号: 3100182
注册: 2014-03-30
专业: 信号理论与信号处理

【答案】应助回帖

感谢参与，应助指数 +1

你的目标函数是什么？假设你的目标函数为f(x), 如果以下几个条件满足，那么高效的算法是存在的（以下我给你描述的是内点法--interior point method or Nestrov-Todd method 在matlab里面的优化函数中也有这个option.）：
1. f(x)是凸函数，且它的Hessian矩阵H之逆易于算出（如对角矩阵，傅里叶变换矩阵等）。
2. A 满足一定的结构如低秩序(low-rank),那么增广Hessian矩阵 H^= [H, A'; A, 0]之逆就可以通过Schur分解快速求解，在你的描述中A是7000*6200矩阵，这是一个超定矩阵显然不符合low-rank的要求，其实你提供的这个A矩阵是包含冗余信息的， AX=b要么没解,要么有唯一解，要么可以再简化为k*6200矩阵，其中k<6200, 我怀疑你打错了，应该比如是700*6200之类。
3.最后的bound-constraints lb<X<ub，可以把该constrait替换为log-barrier penalty function: 如 x<ub 替换为 theta*log(|ub-x|).这样你原来的问题：
min f(x) s.t Ax = b, lb<x<ub (1)
可以theta-approximated by 如下问题：
min f(x) + theta*[log(|x-lb|)+log(|ub-x|), s.t. Ax=b (2)
在内点法运行的过程中，参数theta (theta > 0) 逐步减少，但theta足够小时，（1）和（2）可视为等价。规划（2）也是一个凸规划，可以用newton法来解决。