Giải phương trình phi tuyến số

Question

Tôi cần giải quyết các vấn đề giảm thiểu phi tuyến (ít nhất là ô vuông còn lại của N chưa biết) trong chương trình Java của tôi. Cách thông thường để giải quyết chúng là thuật toán Levenberg-Marquardt. Tôi có một vài câu hỏi

• Có ai có kinh nghiệm về các triển khai LM khác nhau không? Có tồn tại hơi hương vị khác nhau của LM, và tôi đã nghe nói rằng việc thực hiện chính xác của thuật toán có ảnh hưởng lớn đến sự ổn định số của nó. Chức năng của tôi khá tốt, vì vậy điều này có thể không phải là một vấn đề, nhưng tất nhiên tôi muốn chọn một trong những lựa chọn thay thế tốt hơn. Dưới đây là một số lựa chọn thay thế tôi đã tìm thấy:

  • FPL Statistics Group's Nonlinear Optimization Java Package. Điều này bao gồm một bản dịch Java của các thói quen Fortran MINPACK cổ điển.

  • JLAPACK, một bản dịch khác của Fortran.

  • Optimization Algorithm Toolkit.

  • Javanumerics.

  • Một số triển khai Python. Pure Python sẽ ổn, vì nó có thể được biên dịch sang Java với jythonc.

• Có bất kỳ chẩn đoán thường được sử dụng nào để thực hiện dự đoán ban đầu mà LM yêu cầu không? Trong ứng dụng của tôi, tôi cần phải thiết lập một số ràng buộc về giải pháp, nhưng may mắn là chúng đơn giản: tôi chỉ yêu cầu các giải pháp (để trở thành giải pháp vật lý) không mang tính âm tính. Các giải pháp tiêu cực hơi là kết quả đo lường sự thiếu chính xác trong dữ liệu và rõ ràng là bằng không. Tôi đã suy nghĩ để sử dụng "thường xuyên" LM nhưng lặp lại để nếu một số ẩn số trở thành tiêu cực, tôi đặt nó bằng không và giải quyết phần còn lại từ đó. Nhà toán học thực sự có thể sẽ cười tôi, nhưng bạn có nghĩ rằng điều này có thể làm việc?

Cảm ơn mọi ý kiến!

Cập nhật: Đây không phải là khoa học tên lửa, số lượng tham số để giải quyết (N) tối đa là 5 và tập dữ liệu đủ lớn để giải quyết khả thi, vì vậy tôi tin rằng Java khá hiệu quả. điều này. Và tôi tin rằng vấn đề này đã được giải quyết nhiều lần bởi các nhà toán học được áp dụng thông minh, vì vậy tôi chỉ tìm kiếm một số giải pháp sẵn sàng hơn là tự nấu ăn của mình. Ví dụ. Scipy.optimize.minpack.leastsq có lẽ sẽ ổn nếu nó là tinh khiết Python ..

Answer 1

Tôi chưa thực sự sử dụng bất kỳ thư viện Java nào để lấy điều này với một hạt muối: dựa trên các phụ trợ mà tôi có thể sẽ xem tại JLAPACK trước. Tôi tin rằng LAPACK là phụ trợ của Numpy, về cơ bản là tiêu chuẩn để thực hiện các phép toán đại số/toán học tuyến tính bằng Python. Ít nhất, bạn chắc chắn nên sử dụng một thư viện C hoặc Fortran được tối ưu hóa tốt hơn là Java thuần túy, bởi vì đối với các tập dữ liệu lớn, các nhiệm vụ này có thể trở nên cực kỳ tốn thời gian.

Để tạo dự đoán ban đầu, nó thực sự phụ thuộc vào loại chức năng bạn đang cố gắng phù hợp (và loại dữ liệu bạn có). Về cơ bản, chỉ cần tìm một số tính toán tương đối nhanh (có lẽ là O (N) hoặc tốt hơn) sẽ cung cấp một giá trị gần đúng cho tham số bạn muốn.(Gần đây tôi đã làm điều này với một phân bố Gaussian trong Numpy và tôi ước tính giá trị trung bình chỉ là average(values, weights = counts) - nghĩa là, một mức trung bình trọng số của biểu đồ trong biểu đồ, đó là giá trị trung bình thực của tập dữ liệu. của đỉnh tôi đang tìm kiếm, nhưng nó đã đủ gần, và thuật toán đi phần còn lại của con đường.)

Để giữ các ràng buộc tích cực, phương pháp của bạn có vẻ hợp lý. Vì bạn đang viết một chương trình để thực hiện công việc, có thể chỉ cần tạo cờ boolean cho phép bạn dễ dàng bật hoặc tắt hành vi "không mang tính tiêu cực" và chạy cả hai cách để so sánh. Chỉ khi bạn nhận được một sự khác biệt lớn (hoặc nếu một phiên bản của thuật toán mất một thời gian dài không hợp lý), nó có thể là một cái gì đó phải lo lắng. (Và các nhà toán học thực sự sẽ làm giảm thiểu tối thiểu bình phương phân tích, từ đầu; -P vì vậy tôi nghĩ rằng bạn là một trong những người có thể cười vào họ .... đùa. Có thể.)

Answer 2

Gần hơn dự đoán ban đầu của bạn là giải pháp, bạn càng hội tụ nhanh hơn.

Bạn cho biết đó là sự cố phi tuyến tính. Bạn có thể làm một giải pháp hình vuông nhỏ nhất được tuyến tính hóa. Có lẽ bạn có thể sử dụng giải pháp đó như một dự đoán đầu tiên. Một vài lần lặp phi tuyến tính sẽ cho bạn biết điều gì đó về một giả định tốt hay xấu.

Một ý tưởng khác sẽ thử một thuật toán tối ưu hóa khác. Thuật toán di truyền và kiến ​​thuộc địa có thể là một lựa chọn tốt nếu bạn có thể chạy chúng trên nhiều CPU. Chúng cũng không yêu cầu các dẫn xuất liên tục, vì vậy chúng rất tốt nếu bạn có dữ liệu rời rạc, không liên tục.

Answer 3

Bạn không nên sử dụng một người giải quyết không bị giới hạn nếu vấn đề của bạn bị hạn chế. Đối với trường hợp nếu biết rằng một số biến của bạn không phải là số âm, bạn nên thông báo cho điều này đối với người giải quyết của bạn.

Nếu bạn vui lòng sử dụng Scipy, tôi khuyên bạn nên sử dụng scipy.optimize.fmin_l_bfgs_b Bạn có thể đặt các giới hạn đơn giản lên các biến của mình bằng L-BFGS-B.

Lưu ý rằng L-BFGS-B có chức năng mục tiêu phi tuyến chung, không chỉ một vấn đề hình vuông nhỏ nhất phi tuyến.

Answer 4

Gói FPL khá đáng tin cậy nhưng có một vài quirks (truy cập mảng bắt đầu từ 1) do cách giải thích rất đúng nghĩa của mã fortran cũ. Phương pháp LM chính nó là khá đáng tin cậy nếu chức năng của bạn là tốt cư xử. Một cách đơn giản để ép buộc các ràng buộc không âm là sử dụng bình phương các tham số thay vì trực tiếp các tham số. Điều này có thể giới thiệu các giải pháp giả mạo nhưng đối với các mô hình đơn giản, các giải pháp này rất dễ sàng lọc.

Có mã sẵn có cho phương pháp LM "bị hạn chế". Nhìn ở đây http://www.physics.wisc.edu/~craigm/idl/fitting.html cho mpfit. Có một con trăn (dựa vào Numeric không may) và một phiên bản C. Phương thức LM là khoảng 1500 dòng mã, vì vậy bạn có thể có khuynh hướng chuyển C sang Java. Trong thực tế, phương pháp LM "hạn chế" không khác nhiều so với phương pháp bạn hình dung. Trong mpfit, mã điều chỉnh kích thước bước tương ứng với giới hạn trên các biến. Tôi đã có kết quả tốt với mpfit là tốt.

Tôi không có nhiều kinh nghiệm với BFGS, nhưng mã này phức tạp hơn nhiều và tôi chưa bao giờ rõ ràng về việc cấp phép mã.

Chúc may mắn.

Answer 5

Tôi đồng ý với codehippo; Tôi nghĩ rằng cách tốt nhất để giải quyết vấn đề với các ràng buộc là sử dụng các thuật toán được thiết kế đặc biệt để xử lý chúng. Thuật toán L-BFGS-B có lẽ là một giải pháp tốt trong trường hợp này.

Tuy nhiên, nếu sử dụng scipy.optimize của python.Mô-đun fmin_l_bfgs_b không phải là tùy chọn khả thi trong trường hợp của bạn (vì bạn đang sử dụng Java), bạn có thể thử sử dụng thư viện tôi đã viết: một trình bao bọc Java cho mã Fortran gốc của thuật toán L-BFGS-B. Bạn có thể tải xuống từ số http://www.mini.pw.edu.pl/~mkobos/programs/lbfgsb_wrapper và xem nó có phù hợp với nhu cầu của bạn hay không.