3

我有五个值，A、B、C、D 和 E。

给定约束 A + B + C + D + E = 1，以及五个函数 F(A)、F(B)、F(C)、F(D)、F(E)，我需要通过E 使得 F(A) = F(B) = F(C) = F(D) = F(E)。

为此使用的最佳算法/方法是什么？我不在乎是否必须自己写，我只想知道在哪里看。

编辑：这些是非线性函数。除此之外，它们无法表征。其中一些最终可能是从数据表中插入的。

4

8 回答 8

4

这个问题没有一般的答案。不存在求解任何方程的求解器。正如 Lance Roberts 已经说过的，你必须更多地了解函数。仅举几个例子

  • 如果函数是两次可微的，并且您可以计算一阶导数，您可以尝试Newton-Raphson的变体
  • 查看用于实现约束的拉格朗日乘数法。
  • 如果函数 F 是连续的（如果它是插值，它可能是连续的），您还可以尝试二分法，这很像二分搜索。

在解决问题之前，您确实需要更多地了解您正在研究的功能。

于 2009-08-21T06:15:44.950 回答
2

As others have already posted, we do need some more information on the functions. However, given that, we can still try to solve the following relaxation with a standard non-linear programming toolbox.

min k
st.
A + B + C + D + E = 1
F1(A) - k = 0
F2(B) - k = 0
F3(C) -k = 0
F4(D) - k = 0
F5(E) -k = 0

Now we can solve this in any manner we wish, such as penalty method

min k + mu*sum(Fi(x_i) - k)^2 st
A+B+C+D+E = 1

or a straightforward SQP or interior-point method.

More details and I can help advise as to a good method.

m

于 2009-09-01T00:29:59.147 回答
2

The functions are all monotonically increasing with their argument. Beyond that, they can't be characterized. The approach that worked turned out to be:

1) Start with A = B = C = D = E = 1/5
2) Compute F1(A) through F5(E), and recalculate A through E such that each function equals that sum divided by 5 (the average).
3) Rescale the new A through E so that they all sum to 1, and recompute F1 through F5.
4) Repeat until satisfied.

It converges surprisingly fast - just a few iterations. Of course, each iteration requires 5 root finds for step 2.

于 2009-09-12T04:39:59.103 回答
1

方程的一种解

A + B + C + D + E = 1
F(A) = F(B) = F(C) = F(D) = F(E)

就是取A、B、C、D、E都等于1/5。不知道这是否是你想要的......

在约翰的评论之后添加（谢谢！）

Assuming the second equation should read F1(A) = F2(B) = F3(C) = F4(D) = F5(E), I'd use the Newton-Raphson method (see Martijn's answer). You can eliminate one variable by setting E = 1 - A - B - C - D. At every step of the iteration you need to solve a 4x4 system. The biggest problem is probably where to start the iteration. One possibility is to start at a random point, do some iterations, and if you're not getting anywhere, pick another random point and start again.

Keep in mind that if you really don't know anything about the function then there need not be a solution.

于 2009-08-21T08:41:34.093 回答
0

ALGENCAN（探戈的一部分）非常好。也有 Python 绑定。

http://www.ime.usp.br/~egbirgin/tango/codes.php -“完全不使用矩阵操作的一般非线性规划，因此能够以适中的计算机时间解决极大的问题。通用算法属于增广拉格朗日类型..."

http://pypi.python.org/pypi/TANGO%20Project%20-%20ALGENCAN/1.0

于 2009-08-21T06:27:40.213 回答
0

Google OPTIF9 or ALLUNC. We use these for general optimization.

于 2009-09-01T00:34:14.280 回答
0

You could use standard search technic as the others mentioned. There are a few optimization you could make use of it while doing the search.

First of all, you only need to solve A,B,C,D because 1-E = A+B+C+D.

Second, you have F(A) = F(B) = F(C) = F(D), then you can search for A. Once you get F(A), you could solve B, C, D if that is possible. If it is not possible to solve the functions, you need to continue search each variable, but now you have a limited range to search for because A+B+C+D <= 1.

If your search is discrete and finite, the above optimizations should work reasonable well.

于 2009-09-01T00:49:31.150 回答
-1

I would try Particle Swarm Optimization first. It is very easy to implement and tweak. See the Wiki page for it.

于 2009-08-24T18:23:28.430 回答