10

制約のある非線形最適化の問題があります。ソルバー アドインを使用して Microsoft Excel で解決できますが、C# で再現するのに問題があります。

私の問題は、次のスプレッドシートに示されています。私は古典的なA x = b問題を解いていますが、 xのすべての成分が非負でなければならないという警告があります。したがって、標準の線形代数を使用する代わりに、非負の制約を持つソルバーを使用して、差の二乗和を最小化し、妥当な解を得ます。Microsoft Solver FoundationまたはSolver SDKを使用して、これを C# で複製しようとしました。ただし、MSFでは目標を定義する方法がわからず、Solver SDKでは常にステータスが「最適」であり、ローカルではないすべて0のソリューションが返されるため、どこにも行けないようです。最小。

Solver SDK のコードは次のとおりです。

static double[][] A = new double[][] { new double[] { 1, 0, 0, 0, 0 }, new double[] { 0.760652602, 1, 0, 0, 0 }, new double[] { 0.373419404, 0.760537565, 1, 0, 0 }, new double[] { 0.136996731, 0.373331934, 0.760422587, 1, 0 }, new double[] { 0.040625222, 0.136953801, 0.373244464, 0.76030755, 1 } };
static double[][] b = new double[][] { new double[] { 2017159 }, new double[] { 1609660 }, new double[] { 837732.8125 }, new double[] { 330977.3125 }, new double[] { 87528.38281 } };

static void Main(string[] args)
{
    using(Problem problem = new Problem(Solver_Type.Minimize, 5, 0))
    {
        problem.VarDecision.LowerBound.Array = new double[] { 0.0, 0.0, 0.0, 0.0, 0.0 };
        problem.VarDecision.UpperBound.Array = new double[] { Constants.PINF, Constants.PINF, Constants.PINF, Constants.PINF, Constants.PINF };

        problem.Evaluators[Eval_Type.Function].OnEvaluate += new EvaluateEventHandler(SumOfSquaredErrors);

        problem.ProblemType = Problem_Type.OptNLP;

        problem.Solver.Optimize();

        Optimize_Status status = problem.Solver.OptimizeStatus;

        Console.WriteLine(status.ToString());
        foreach(double x in problem.VarDecision.FinalValue.Array)
        {
            Console.WriteLine(x);
        }
    }
}

static Engine_Action SumOfSquaredErrors(Evaluator evaluator)
{
    double[][] x = new double[evaluator.Problem.Variables[0].Value.Array.Length][];
    for(int i = 0; i < x.Length; i++)
    {
        x[i] = new double[1] { evaluator.Problem.Variables[0].Value.Array[i] };
    }

    double[][] b_calculated = MatrixMultiply(A, x);

    double sum_sq = 0.0;
    for(int i = 0; i < b_calculated.Length; i++)
    {
        sum_sq += Math.Pow(b_calculated[i][0] - b[i][0], 2);
    }
    evaluator.Problem.FcnObjective.Value[0] = sum_sq;

    return Engine_Action.Continue;
}

static double[][] MatrixMultiply(double[][] left, double[][] right)
{
    if(left[0].Length != right.Length)
    {
        throw new ArgumentException();
    }

    double[][] sum = new double[left.Length][];
    for(int i = sum.GetLowerBound(0); i <= sum.GetUpperBound(0); i++)
    {
        sum[i] = new double[right[i].Length];
    }

    for(int i = 0; i < sum.Length; i++)
    {
        for(int j = 0; j < sum[0].Length; j++)
        {
            for(int k = 0; k < right.Length; k++)
            {
                sum[i][j] += left[i][k] * right[k][j];
            }
        }
    }

    return sum;
}

Microsoft Solver Foundation のコードはありません。ゴール関数を 1 行で記述できるとは思えず、Solver SDK のようにデリゲートを使用できないためです。

4

1 に答える 1

3

代替案の 1 つは、これを LP 問題として定式化することです。

xの要素の合計を最小化する

Ax >= bの対象

これは、LP サンプルの 1 つに基づいて、Solver Foundation を使用して定式化するのはかなり簡単です。

7月5日更新

上記のアプローチも非常に複雑に見えますが、これはおそらく Frontline Solver API によるものです。Microsoft Solver Foundation を使用して、差の二乗和を最小化すると、次のプログラムが実行されます。

private static void Main(string[] args)
{
    var solver = SolverContext.GetContext();
    var model = solver.CreateModel();

    var A = new[,]
        {
            { 1, 0, 0, 0, 0 }, 
            { 0.760652602, 1, 0, 0, 0 }, 
            { 0.373419404, 0.760537565, 1, 0, 0 },
            { 0.136996731, 0.373331934, 0.760422587, 1, 0 },
            { 0.040625222, 0.136953801, 0.373244464, 0.76030755, 1 }
        };
    var b = new[] { 2017159, 1609660, 837732.8125, 330977.3125, 87528.38281 };

    var n = A.GetLength(1);
    var x = new Decision[n];
    for (var i = 0; i < n; ++i)
        model.AddDecision(x[i] = new Decision(Domain.RealNonnegative, null));

    // START NLP SECTION
    var m = A.GetLength(0);
    Term goal = 0.0;
    for (var j = 0; j < m; ++j)
    {
        Term Ax = 0.0;
        for (var i = 0; i < n; ++i) Ax += A[j, i] * x[i];
        goal += Model.Power(Ax - b[j], 2.0);
    }
    model.AddGoal(null, GoalKind.Minimize, goal);
    // END NLP SECTION

    var solution = solver.Solve();
    Console.WriteLine("f = {0}", solution.Goals.First().ToDouble());
    for (var i = 0; i < n; ++i) Console.WriteLine("x[{0}] = {1}", i, x[i].GetDouble());
}

次のソリューションが生成されます。これは、リンクされた Excel シートのソリューションと一致している必要があります。

f = 254184688.179922
x[0] = 2017027.31820845
x[1] = 76226.6063397686
x[2] = 26007.3375581303
x[3] = 1.00650383558278E-07
x[4] = 4.18546775823669E-09

私が間違っていなければ、GRG とは異なり、Solver Foundation はすぐに使用できる一般的な非線形制約をサポートできません。これらを処理するには、追加のプラグインが必要になると思います。あなたの問題については、これはもちろん問題ではありません。

完全を期すために、代わりに LP 問題を定式化するには、START NLP SECTIONとEND NLP SECTIONの間のコードを次のコードと交換します。

    var m = A.GetLength(0);
    var constraints = new Term[m];
    for (var j = 0; j < m; ++j)
    {
        Term Ax = 0.0;
        for (var i = 0; i < n; ++i) Ax += A[j, i] * x[i];
        model.AddConstraint(null, constraints[j] = Model.GreaterEqual(Ax, b[j]));
    }
    model.AddGoal(null, GoalKind.Minimize, Model.Sum(x));

これにより、次の出力が得られます (目的関数が 2 つのケースで異なることに注意してください。したがって、大きな違いがありますf)。

f = 2125502.27815564
x[0] = 2017159
x[1] = 75302.7580022821
x[2] = 27215.9247379241
x[3] = 5824.5954154355
x[4] = 0
于 2012-07-03T19:52:59.330 に答える