Chủ đề này có 4 trả lời

[werty]

Có bạn nào đã làm về món này không vậy? Mình đang bí một số vấn đề, nếu có người để trao đổi thì tốt quá.

[iamaguest]

Bí gì cơ? Có bí đi ấy... không? Sao bảo bí mà không post lên để mọi người có ý kiến.

[werty98]

À, hôm trước mình có dùng một chương trình giải quadratic programming (giải thuật LOQO), nhưng nó đòi hỏi ma trận Hessian phải là positive definite. Vấn đề ở chỗ trong cái của mình đang làm thì ma trận Hessian chỉ là semidefinite thôi.

[iamaguest]

Ban dung phan mem LOQO hay giai thuat LOQO. Xin loi, minh khong biet ten giai thuật này. Có thể nói rõ hơn được không.
Đúng là đối với Quadratic programming thì nếu $f=1/2x^TQx+q^Tx$ mà Q chỉ semidefine thì nghiệm có thể không duy nhất. Tuy nhiên đây là QH lồi nên cực tiểu địa phương là toàn cục.
Có 2 cách giải quyết.
1. Dùng phương pháp hiệu chỉnh: g(x) = f(x) + 1/2*epsilon*||y-x||^2. Để g lồi mạnh và giải bài toán với g, khi dó Q_g là positive define với epsilon>0.
2. Bạn sử dụng trực tiếp pp điểm trong để xây dựng thuật toán giải (nếu có ràng buộc).

[werty98]

Chào bạn iamaguest,

Trước hết xin cám ơn bạn đã trả lời câu hỏi của mình.

LOQO là một chương trình giải bài toán quadratic programming sau đây:

Minimize c^T x + 1/2 x^T H x
Subject to: Ax <= b
l <= x <= u

Mình chỉ cần tìm 1 cực tiểu toàn cục, không nhất thiết phải tìm hết các cực tiểu có thể có. Cái mình quan tâm nhất là tốc độ giải.

À còn một vấn đề khác nữa, ma trận Hessian trong bài toán mình đang giải quyết có dạng sau: H = [K -K; -K K] (K có kích thước n x n, H có kích thước 2n x 2n), trong đó K là positive definite. Với dạng ma trận Hessian cấu trúc đặc biệt như vậy thì có khả năng nào để tăng tốc độ giải không?