Làm cách nào để mô phỏng chức năng Bộ giải của Microsoft Excel (GRG phi tuyến) trong C#?

Question

Tôi có một vấn đề tối ưu hóa phi tuyến tính với các ràng buộc. Nó có thể được giải quyết trong Microsoft Excel với phần bổ trợ Solver, nhưng tôi gặp sự cố khi sao chép trong C#.

Sự cố của tôi được hiển thị trong following spreadsheet. Tôi đang giải quyết vấn đề cổ điển A x = b nhưng với báo trước rằng tất cả các thành phần của x phải không âm. Vì vậy, thay vì sử dụng đại số tuyến tính chuẩn, tôi sử dụng Solver với ràng buộc không âm, giảm thiểu tổng của các khác biệt bình phương và nhận được một giải pháp hợp lý. Tôi đã cố gắng sao chép điều này trong C# bằng cách sử dụng Microsoft Solver Foundation hoặc Solver SDK. Tuy nhiên, dường như tôi không thể tìm được ở đâu với MSF vì tôi không thể tìm ra cách xác định mục tiêu và với Solver SDK, tôi luôn lấy lại trạng thái "tối ưu" và giải pháp cho tất cả 0 mà chắc chắn không phải là địa phương tối thiểu.

Đây là mã của tôi cho 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; 
} 

tôi không có bất kỳ mã cho Microsoft Solver Foundation bởi vì tôi không nghĩ rằng chức năng mục tiêu có thể được viết trong một dòng duy nhất và nó doesn' t cho phép các đại biểu như Solver SDK thực hiện.

Answer 1

Một thay thế sẽ được xây dựng này như là một vấn đề LP:

giảm thiểu tổng của các yếu tố trong x

chịu Axe> = b

này nên khá đơn giản để xây dựng bằng cách sử dụng Solver Foundation, dựa trên một trong các mẫu LP.

CẬP NHẬT 05 tháng bảy

Phương pháp trên cũng có vẻ quá phức tạp, nhưng có lẽ điều này là do các API Frontline Solver. Sử dụng Microsoft Solver Foundation, và giảm thiểu tổng số chênh lệch bình phương, các chương trình sau đây:

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()); 
} 

tạo ra các giải pháp sau đây, mà nên phù hợp với các giải pháp từ các liên kết Excel tờ:

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 

Nếu tôi không nhầm, không giống như GRG, Solver Foundation không thể hỗ trợ các ràng buộc phi tuyến tính ngoài hộp, tôi tin rằng bạn sẽ cần thêm các trình cắm thêm để xử lý chúng. Đối với vấn đề của bạn, điều này tất nhiên không phải là một vấn đề.

Để hoàn chỉnh, xây dựng các vấn đề LP thay vào đó, trao đổi mã giữa BẮT ĐẦU NLP PHẦN và END NLP PHẦN với đoạn mã sau:

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)); 

đó sẽ mang lại những điều sau đầu ra (lưu ý rằng các hàm mục tiêu khác nhau trong hai trường hợp, do đó sự khác biệt lớn trong f):

f = 2125502.27815564 
x[0] = 2017159 
x[1] = 75302.7580022821 
x[2] = 27215.9247379241 
x[3] = 5824.5954154355 
x[4] = 0