Công thức số/Tìm kiếm gốc đa chiều (sử dụng newt): Cách giảm thiểu lỗi tối đa

Question

Câu hỏi này liên quan đến sách "công thức số trong C++", vì vậy nó sẽ được dành riêng cho những người biết một chút về nó cũng như về tối ưu hóa đa chiều.

Tôi đang viết một chương trình cần tìm kiếm một gốc đa chiều và để giải quyết nó, tôi đang sử dụng phương pháp tìm kiếm gốc newton đa chiều, cụ thể là thủ tục "newt".

Đối với những người quan tâm đến chi tiết, tôi đang cố gắng để phù hợp với một mô hình 3D biến dạng để một cái nhìn vô hình của một đối tượng, dựa trên một vài điểm đặc trưng (điểm đặc trưng mà hai máy ảnh nhìn thấy).

Đối với điều này, tôi đang sử dụng các thủ tục sa giông như sau:

• 11 thông số đầu vào: mô hình biến dạng của tôi có thể được mô hình với 11 thông số (gồm 5 thông số hình học và 6 deegres tự do cho vị trí đối tượng 3D):
• 14 Thông số đầu ra mà tôi cần tìm gốc: dựa trên các điểm tính năng được máy ảnh xác định và được đặt trên "thông số đầu vào", tôi có thể tính toán tập hợp khoảng cách giữa các điểm đặc trưng mà máy ảnh nhìn thấy và cation. Tôi có 7 trong số những điểm đó, do đó cung cấp cho tôi 14 tham số (khoảng cách 7 lần 2, vì tôi tính toán khoảng cách trên cả hai máy ảnh)

Vấn đề của tôi là tôi có nhiều tham số đầu ra hơn (14) so ​​với tham số đầu vào (11): bất cứ khi nào tôi gọi "newt", thuật toán luôn hội tụ, tuy nhiên nó sẽ tìm ra giải pháp giảm thiểu gần như hoàn toàn 11 tham số đầu ra đầu tiên, nhưng có rất nhiều lỗi trên 3 tham số còn lại.

Tuy nhiên, tôi muốn các lỗi được phân chia đồng đều giữa các tham số đầu ra.

Tôi đã thử các cách tiếp cận mô tả dưới đây:

1. Cố gắng kết hợp các thông số đầu ra 14 thành 11 thông số (ví Ví dụ, bạn lấy trung bình của một số khoảng cách, thay vì sử dụng cả khoảng cách). Tuy nhiên tôi không phải là 100% hài lòng với cách tiếp cận này
2. Mix một số giải pháp với các nguyên tắc sau đây:
   • Gọi mnewt và ghi nhớ gốc tìm thấy
   • Thay đổi thứ tự của các tham số 14 ngõ ra
   • Calling mnewt một lần nữa và nhớ gốc tìm thấy
   • Tính một giải pháp là mức trung bình của hai rễ tìm thấy

Có ai biết một cách tiếp cận chung chung hơn, trong đó thuật toán tìm gốc sẽ ưu tiên một lỗi được phân chia đồng đều giữa các tham số đầu ra, thay vì ưu tiên các thông số đầu tiên?

Answer 1

Bạn cố gắng thu nhỏ F(x) bằng cách giải quyết f(x)=0 trong đó x là một vector m và f ánh xạ bản đồ này tới vectơ n chiều.Vấn đề tối ưu hoá của bạn là chưa xác định được nếu m < n (trong trường hợp của bạn là 11 < 14).

Đối với các hệ thống như vậy, cách chung để giải quyết chúng là giảm thiểu một vector chỉ tiêu trên x. Bạn có thể thực hiện việc này bằng cách thu nhỏ hệ thống x^T A x + c f(x)^T f(x) đối với cả hai số x và Lagrange-multiplierc. Nếu không có thêm thông tin, bạn có thể lấy A là nxn ma trận nhận dạng. Điều này sẽ tìm thấy các x mà giải quyết f(x)=0 trong khi có định mức nhỏ nhất.

Để biết thêm chi tiết về cách thực hiện điều này với phương pháp Newton, xem ví dụ: này paper.