寻找函数的最大值

Question

4

我需要找到以下函数的最大值：

a1^x1 * const1 + a2^x2 * const2 +....+ ak^xk * constk = qaulity

其中 xk>0 并且 xk 是整数。ak 是常数。

约束条件： a1^x1 * const1*func(x1) + a2^x2 * const2*func(x2) +....+ ak^xk * constk*func(xk) < Budget

其中 func 是离散函数：

func(x)
{
    switch(x)
    {
        case 1: return 423;
        case 2: return 544;
        ...
        etc
    }
}

k可能很大（超过1000）。x小于100。什么是最好的方法？

- Neir0

你有一个超过1000个变量的函数吗？ - Matti Virkkunen

是的，几千个变量... - Neir0

这不就是伪装成背包问题了吗？ - 9000

1

这被称为整数规划，解决整数规划的方法之一是分支定界搜索。 - Yaroslav Bulatov

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Foo Bah · Accepted Answer

有一些技术，比如Nelder-Mead优化（我相信GSL实现了这个技术），但大多数技术都假设某种特殊结构（即凸性或连续性）。根据函数的值，可能不存在唯一的最优解，甚至正常的下降方法也无法找到最优解。