标签: mathematical-optimization

我希望学生在任务中解决一个二次方程,而不必安装额外的软件,如cvxopt等.是否有可用的python实现只依赖于NumPy/SciPy？

方法1:
C(n,r)= n!/(nr)!r!

方法2:
在wilf的" 组合算法 "一书中,我发现:
C(n,r)可以写成C(n-1,r) + C(n-1,r-1).

例如

C(7,4) = C(6,4) + C(6,3) 
       = C(5,4) + C(5,3) + C(5,3) + C(5,2)
       .   .
       .   .
       .   .
       .   .
       After solving
       = C(4,4) + C(4,1) + 3*C(3,3) + 3*C(3,1) + 6*C(2,1) + 6*C(2,2)

如您所见,最终解决方案不需要任何乘法.在每种形式C(n,r)中,n == r或r == 1.

这是我实现的示例代码:

int foo(int n,int r)
{
     if(n==r) return 1;
     if(r==1) return n;
     return foo(n-1,r) + foo(n-1,r-1);
}

请参见此处的输出

在方法2中,存在重叠的子问题,我们正在调用递归来再次解决相同的子问题.我们可以通过使用动态编程来避免它.

我想知道哪个是计算C(n,r)的更好方法？

我正在尝试建立一个线性程序,其中目标函数max为决策变量中的各个系数增加额外的权重.

考虑到这一点,是有办法使用的方式min或max运营商内部线性规划的目标函数？

例:

Minimize
    (c1 * x1) + (c2 * x2) + (c3 * x3) + (c4 * max(c1*x1, c2*x2, c3*x3)) 
subject to
    #some arbitrary integer constraints:
    x1 >= ...
    x1 + 2*x2 <= ... 
    x3 >= ...
    x1 + x3 == ...

请注意,这(c4 * max(c1*x1, c2*x2, c3*x3))是我关注的"额外重量"一词.我们让c4表示"额外重量"系数.另外,还要注意x1,x2和x3是整数,在这个特殊的例子.

我认为上述内容可能超出了线性编程提供的范围.但是,也许有办法将其破解/重新格式化为有效的线性程序？

如果这个问题完全超出了线性规划的范围,也许有人可以推荐一种更适合这类问题的优化范例？(任何允许我避免手动枚举和检查所有可能的解决方案的东西都会有所帮助.)

我正在寻找scipy/numpy中的优化例程,它可以解决非线性最小二乘类型问题(例如,将参数函数拟合到大数据集),但包括边界和约束(例如参数的最小值和最大值)优化).目前我使用的是pyfit版本的mpfit(从idl翻译过来......):虽然效果很好,但显然不是最佳选择.

python/scipy/etc中的高效例程可能很棒!这里非常欢迎任何输入:-)

谢谢!

我刚才问了这个问题.我不确定是否应将此作为答案或新问题发布.我没有答案但是我通过nls.lm在R中应用Levenberg-Marquardt算法"解决"了这个问题,当解决方案在边界时,我运行信任区域反射算法(TRR,在R中实现)来执行远离它.现在我有了新的问题.

根据我的经验,以这种方式,程序达到最佳状态,并且对起始值不那么敏感.但这只是一种实用的方法,可以解决我遇到的问题nls.lm以及R中的其他优化函数.我想知道为什么nls.lm这种方式对于边界约束的优化问题以及如何nls.lm在实践中使用时处理边界约束.

下面我举例说明使用的两个问题nls.lm.

1. 它对起始值很敏感.
2. 当某个参数到达边界时停止.

可重复的示例:焦点数据集D.

library(devtools)
install_github("KineticEval","zhenglei-gao")
library(KineticEval)
data(FOCUS2006D)
km <- mkinmod.full(parent=list(type="SFO",M0 = list(ini   = 0.1,fixed = 0,lower = 0.0,upper =Inf),to="m1"),m1=list(type="SFO"),data=FOCUS2006D)
system.time(Fit.TRR <- KinEval(km,evalMethod = 'NLLS',optimMethod = 'TRR'))
system.time(Fit.LM <- KinEval(km,evalMethod = 'NLLS',optimMethod = 'LM',ctr=kingui.control(runTRR=FALSE)))
compare_multi_kinmod(km,rbind(Fit.TRR$par,Fit.LM$par))
dev.print(jpeg,"LMvsTRR.jpeg",width=480)

描述模型/系统的微分方程是:

"d_parent = - k_parent * parent"                                                 
"d_m1 = - k_m1 * m1 + k_parent * f_parent_to_m1 * parent" 

在左边的图中是带有初始值的模型,中间是使用"TRR"的拟合模型(类似于Matlab lsqnonlin函数中的算法),右边是使用"LM"的拟合模型nls.lm.查看拟合参数(Fit.LM$par),您会发现一个拟合参数(f_parent_to_m1)位于边界处1.如果我将一个参数的起始值 …

我想在Tensorflow上为我的网络编写一个新的优化算法.我希望实现Levenberg Marquardt优化算法,该算法现在被排除在TF API之外.我发现关于如何编写自定义优化器的文档很差,所以我问是否有人可以给我任何建议.谢谢.

我正在研究一个可以简化为图优化问题的问题,如下所示.

• 给出了一组彩色节点.它们都是未连接的,即图中没有边缘.

• 边缘将插入节点之间.

• 一个节点最多只能有4个边.

• 表格提供了边缘利润贡献的规则.

  例如.,

  • 连接红色到红色的边缘:利润为10

  • 连接红色到蓝色的边缘:利润是20

• 节点总数约为100.

• 颜色总数通常在20到30左右,但它可以高达50个.相应地,利润表(边缘)将是一个很长的列表,但它不会列出所有可能的组合.表中未指定的边的利润假定为零.

问题是优化连接(边缘),以使总利润最大化.

我想知道这个问题,或许是以某种其他方式,是已知的.如果是这样,请提供可能有帮助的任何指示.谢谢.

计算机如何对2个数字进行乘法运算,比如100*55.

我的猜测是计算机重复添加以实现乘法.当然,这可能是整数的情况.但是对于浮点数,必须有一些其他逻辑.

注意:这在面试中被问到了.

快速搜索"python线性编程"会产生大量的点击(例如这一点).通过它们,我看到了相当多的关于过时的依赖关系,糟糕的文档等的抱怨.

任何人都可以为python推荐一个没有头痛的(例如快速,文档齐全,易于安装,干净的API)线性编程库吗？

我的问题在概念上类似于解决字谜,除了我不能只使用字典查找.我试图找到合理的词而不是真实的词.

我已经基于一堆文本中的字母创建了一个N-gram模型(现在,N = 2).现在,给定一个随机的字母序列,我想根据转移概率将它们置于最可能的序列中.我认为在开始时我需要维特比算法,但随着我看起来更深入,维特比算法根据观察到的输出优化了一系列隐藏的随机变量.我正在尝试优化输出序列.

有没有一个众所周知的算法,我可以阅读？或者我是否与Viterbi走在正确的轨道上,我只是没有看到如何应用它？

更新

我已经添加了一笔赏金来要求更深入地了解这个问题.(分析解释为什么不能采用有效的方法,除模拟退火之外的其他启发式/近似等)