Thuật toán DCA cho một mô hình tối ưu danh mục đầu tư với ràng buộc về lực lượng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

19
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết trình bày việc xét một mô hình tối ưu danh mục đầu tư với độ đo rủi ro là giá trị rủi ro có điều kiện (CVaR). Trên thực tế khi tối ưu danh mục đầu tư thì số lượng tài sản cần có trong danh mục là ràng buộc rất quan trọng (về mặt toán học ta có thể gọi đây là các ràng buộc về lực lượng). Ràng buộc này giúp cho danh mục đầu tư được đa dạng và góp phần hạn chế rủi ro trong tương lai.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Thuật toán DCA cho một mô hình tối ưu danh mục đầu tư với ràng buộc về lực lượng

Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), Nha Trang, ngày 8-9/10/2020 DOI: 10.15625/vap.2020.00216 THUẬT TOÁN DCA CHO MỘT MÔ HÌNH TỐI ƯU DANH MỤC ĐẦU TƯ VỚI RÀNG BUỘC VỀ LỰC LƯỢNG Trần Đức Quỳnh1, Nguyễn Thị Lụa2 1 Khoa Quốc tế, Đại học Quốc gia Hà Nội 2 Viện Toán ứng dụng và Tin học, Trường Đại học Bách khoa Hà Nội quynhtd@isvnu.vn, luanguyen.hn@gmail.com TÓM TẮT: Bài toán tối ưu danh mục đầu tư là bài toán xác định phương án đầu tư hiệu quả nhất, mang về lợi nhuận cao nhất với mức rủi ro thấp nhất. Trong nghiên cứu này chúng tôi xét một mô hình tối ưu danh mục đầu tư với độ đo rủi ro là giá trị rủi ro có điều kiện (CVaR). Trên thực tế khi tối ưu danh mục đầu tư thì số lượng tài sản cần có trong danh mục là ràng buộc rất quan trọng (về mặt toán học ta có thể gọi đây là các ràng buộc về lực lượng). Ràng buộc này giúp cho danh mục đầu tư được đa dạng và góp phần hạn chế rủi ro trong tương lai. Do đó chúng tôi đề xuất mô hình tối ưu có xét đến các ràng buộc về lực lượng và độ đo rủi ro CVaR. Bài toán được mô hình hóa dưới dạng một bài toán tối ưu hỗn hợp nguyên với ràng buộc bậc hai lồi (MIQCP). Đây là lớp bài toán tối ưu rời rạc nên khá khó để tìm được nghiệm tối ưu toàn cục. Do đó các tiếp cận địa phương cho lớp bài toán này là các nghiên cứu cần thiết để tăng tốc độ giải bài toán trong trường hợp số chiều lớn. Trong phương pháp tiếp cận của mình, chúng tôi sử dụng kỹ thuật hàm phạt đưa bài toán về dạng một bài toán tối ưu DC (difference of convex functions - hàm mục tiêu là hiệu hai hàm lồi) rồi áp dụng thuật toán DCA (thuật toán hiệu hai hàm lồi) để giải bài toán thu được. Kết quả thu được trên các bộ dữ liệu thử nghiệm khác nhau cho thấy mặc dù là thuật toán địa phương nhưng DCA cho nghiệm rất gần nghiệm tối ưu toàn cục trong thời gian tính toán chấp nhận được. Từ khóa: Thuật toán DCA, danh mục đầu tư, ràng buộc về lực lượng, tối ưu hỗn hợp nguyên. I. GIỚI THIỆU Trong đầu tư, để đưa ra quyết định đầu tư vào các tài sản, các nhà đầu tư thường quan tâm đến hai yếu tố quan trọng: lợi nhuận dự kiến thu được và mức độ rủi ro. Thông thường, các tài sản có lợi nhuận càng cao thì rủi ro càng lớn, và dĩ nhiên các nhà đầu tư luôn muốn hạn chế các rủi ro ấy. Ở các quốc gia có thị trường chứng khoán phát triển, từ rất lâu các nhà đầu tư đã biết áp dụng nguyên tắc “không để tất cả trứng vào cùng một giỏ”, thông qua việc kết hợp các loại tài sản khác nhau để hạn chế rủi ro. Danh mục đầu tư chính là sự kết hợp nắm giữ các loại chứng khoán, hàng hóa, bất động sản, các công cụ tương đương tiền mặt hay các tài sản khác bởi một cá nhân hay một tổ chức đầu tư; mục đích của danh mục đầu tư là làm giảm thiểu rủi ro bằng việc đa dạng hóa đầu tư. Bài toán tối ưu danh mục đầu tư là bài toán có ý nghĩa quan trọng và nhận được sự quan tâm của các nhà đầu tư trên toàn thế giới. Lý thuyết tối ưu hóa danh mục đầu tư được khởi nguồn từ những nghiên cứu đầu tiên của Harry Markowitz năm 1952 [1]. Từ đó, rất nhiều các nghiên cứu tiếp tục được đưa ra, nhằm giải quyết hai vấn đề chính: (1) mô hình một cách đầy đủ bài toán lựa chọn danh mục đầu tư trong thực tế với các rủi ro và các ràng buộc; (2) tính hiệu quả, cụ thể là khả năng giải quyết bài toán cỡ lớn, khi số lượng tài sản và kịch bản đầu tư cần xem xét là rất nhiều. Trong quản trị rủi ro tài chính, giá trị rủi ro (Value at Risk – VaR) là một thước đo rủi ro được sử dụng rộng rãi, VaR của tài sản hoặc một danh mục thể hiện nguy cơ tổn thất lớn nhất có thể xảy ra trong một khoảng thời gian với một mức độ tin cậy nhất định, trong điều kiện thị trường hoạt động bình thường. Mặc dù được sử dụng khá phổ biến, VaR vẫn có những hạn chế nhất định. VaR chỉ giúp ta trả lời câu hỏi “có thể mất tối đa bao nhiêu trong phần lớn các tình huống”. Tuy nhiên, VaR chưa trả lời được câu hỏi: trong phần nhỏ các tình huống (1 % hay 5 % tình huống xấu nhất ứng với các diễn biến bất thường của thị trường) khi xảy ra, mức tổn thất có thể là bao nhiêu. Do đó nếu tiếp tục sử dụng VaR như công cụ quản trị rủi ro có thể gặp hậu quả: tổn thất thực tế lớn hơn nhiều so với ước tính theo VaR. Để khắc phục hạn chế của VaR, Uryasev và Rockafellar [2] đã giới thiệu giá trị rủi ro có điều kiện (Conditional Value at Risk – CVaR). CVaR cho biết giá trị trung bình của các mức tổn thất vượt ngưỡng VaR. Trong bài báo này chúng tôi nghiên cứu một mô hình lựa chọn danh mục đầu tư dựa trên thước đo rủi ro CVaR. Để có thể đưa ra các phương án hợp lý, phù hợp với thực tế và đáp ứng nhu cầu đa dạng hóa danh mục đầu tư của các nhà đầu tư, chúng tôi xem xét đưa vào mô hình các ràng buộc về lực lượng, bao gồm các giới hạn về mức đầu tư vào mỗi tài sản và giới hạn số lượng tài sản trong danh mục. Bài toán được mô hình hóa dưới dạng một bài toán tối ưu hỗn hợp nguyên với ràng buộc bậc hai lồi (MIQCP). Để giải bài toán trên chúng tôi biểu diễn ràng buộc biến nguyên dưới dạng một ràng buộc lõm không âm sau đó sử dụng phương pháp hàm phạt để đưa về dạng bài toán tối ưu DC (hàm mục tiêu là hiệu hai hàm lồi với ràng buộc lồi). Sau đó chúng tôi áp dụng thuật toán DCA (một thuật toán địa phương để giải bài toán tối ưu DC) để giải bài toán thu được. Ý tưởng cơ bản của thuật toán DCA khá đơn giản là xấp xỉ hàm DC bởi một dãy các hàm lồi, ở mỗi bước ta sẽ đi giải bài toán lồi xấp xỉ đến khi điều kiện dừng được thỏa mãn. Thuật toán DCA được đưa ra lần đầu tiên năm 1985 bởi nhà toán học Phạm Đình Tào. Khoảng 20 năm vừa qua thuật toán này đã cho thấy là một trong những thuật toán địa phương hiệu quả, đã giải quyết được nhiều lớp bài toán khó, kể cả những bài toán cỡ lớn trong nhiều lĩnh vực khác nhau từ quản lý sản xuất, quản lý danh mục đầu tư, khoa học dữ liệu [3], [8], [9]. Phần còn lại của bài báo được cấu trúc như sau: mục II trình bày mô hình bài toán lựa chọn danh mục đầu tư dựa trên CVaR với các ràng buộc về lực lượng. Mục III đề xuất phương pháp giải sử dụng thuật toán DCA. Mục IV sẽ trình bày kết quả thử nghiệm phương pháp đề xuất trên một số bộ dữ liệu và cuối cùng là một số kết luận.
588 THUẬT TOÁN DCA CHO MỘT MÔ HÌNH TỐI ƯU DANH MỤC ĐẦU TƯ VỚI RÀNG BUỘC VỀ LỰC LƯỢNG II. MÔ HÌNH Trong mục này chúng tôi sẽ trình bày về mô hình toán học sử dụng trong bài báo này. Phần giới thiệu về mô hình tối ưu danh mục đầu tư với giá trị rủi ro có điều kiện được tham khảo trong [5]. Xét một danh sách tài sản trên thị trường. Tại thời điểm đầu tư nhà đầu tư phân bổ vốn bằng cách chia một phần vốn cho mỗi tài sản. Phần vốn cho tài sản thứ là , là tỉ lệ phần trăm vốn đầu tư cho tài sản trên tổng số vốn đầu tư. Giả sử nhà đầu tư sẽ đầu tư toàn bộ số vốn và không bán khống. Để biểu diễn các giả thiết này về mặt toán học, ta định nghĩa tập các phương án đầu tư ∑ Lợi nhuận của tài sản được ký hiệu là . Ở đây là một biến ngẫu nhiên chưa biết phân phối. Giá trị kỳ vọng của được ký hiệu là , được ước lượng bởi trung bình lợi nhuận của tài sản qua thời kỳ trong quá khứ: ∑ với là lợi nhuận của tài sản trong thời kỳ . Từ đó, lợi nhuận kỳ vọng của danh mục đầu tư là (2.1) {∑ } ∑ { } ∑ Rủi ro của danh mục đầu tư được định nghĩa như sau [4] [5] { }, (2.2) trong đó, là một hằng số để điều chỉnh mức độ rủi ro, là trung bình độ lệch chuẩn của tất cả tài sản rủi ro trong danh mục: ∑ (2.3) với là độ lệch chuẩn của lợi nhuận của tài sản , được tính bằng dữ liệu lịch sử. Để tìm được danh mục đầu tư tối đa lợi nhuận kỳ vọng và tối thiểu rủi ro, bài toán lựa chọn danh mục đầu tư có thể được phát biểu như một bài toán tối ưu hai mục tiêu như sau: (2.4a) ( ( )∑ ) (2.4b) với ( ) { }. Có thể giải quyết mục tiêu maximin trong (2.4a) bằng cách thêm biến và ràng buộc, bài toán trở thành: ( ∑ ) (2.5a) ( ) (2.5b) (2.5c) với ( ) là ràng buộc xác suất thứ . Do quá trình tối ưu sẽ đẩy giá trị của y về bằng ( ) nên bài toán tối ưu (2.5) tương đương với bài toán tối ưu (2.4). Theo định nghĩa ( ) là một xác suất, nên y nằm trong khoảng từ 0 đến 1. Nếu ta chọn y là một số thực cố định bất kỳ nằm trong khoảng này, bài toán (2.5) trở thành bài toán tối ưu một mục tiêu sau: (2.6a) ∑ ( ) (2.6b)
Trần Đức Quỳnh, Nguyễn Thị Lụa 589 (2.6c) Đến đây, trọng tâm vấn đề nằm ở (2.6b), giá trị của { }. Rủi ro sụt giá theo xác suất này không thể tính trực tiếp khi không có giả thiết về phân phối của . Tuy nhiên, bằng mối quan hệ giữa các ràng buộc ngẫu nhiên và các giới hạn của CVaR, ta có thể xấp xỉ các ràng buộc ngẫu nhiên (2.6b) bằng tập các ràng buộc bất đẳng thức thông thường. Viết lại các ràng buộc (2.6b) như sau: (2.7) { } trong đó và . Với mỗi , ràng buộc (2.7) là một ràng buộc VaR, là ràng buộc không lồi. Ta thay thế nó bằng một ràng buộc CVaR, là xấp xỉ lồi tốt nhất của (2.7). Với mỗi , ( ) hay (2.8) { } với là một biến được thêm vào. Giả sử là một biến ngẫu nhiên có trung bình không và phương sai dương. Khi đó, theo [6]: (2.9) √ Đặt , và , ta được ( ) ( ) √ với là phương sai của . Do vậy, (2.8) đúng nếu [ ( ) √ ] là đúng. Do đó, bài toán xấp xỉ có thể phát biểu như sau: ∑ (2.10a) (2.10b) v.đ.k. √( ) , (2.10c) Trong thực tế, khi quyết định lựa chọn tài sản đầu tư, nhà đầu tư thường gặp tình huống sau: Đối với tài sản , hoặc là không đầu tư, hoặc là nếu đầu tư thì khoản đầu tư phải không ít hơn và không quá , tức . Như vậy, ta gặp phải điều kiện “hoặc là , hoặc ”. Đặt { Khi đó, ràng buộc logic “hoặc là , hoặc ” được đưa về hệ ràng buộc tương đương sau: Tổng số tài sản có trong danh mục đầu tư là ∑ . Giả sử nhà đầu tư muốn giới hạn tổng số lượng tài sản trong danh mục đầu tư trong khoảng từ đến tài sản, ta thêm ràng buộc: ∑
590 THUẬT TOÁN DCA CHO MỘT MÔ HÌNH TỐI ƯU DANH MỤC ĐẦU TƯ VỚI RÀNG BUỘC VỀ LỰC LƯỢNG Bài toán lựa chọn danh mục đầu tư tối ưu dựa trên CVaR với các ràng buộc về lực lượng có thể được mô hình hóa như sau: ∑ (2.11a) v.đ.k. √( ) , (2.11b) (2.11c) (2.11d) , (2.11e) ∑ (2.11f) (2.11g) Nhận xét: Ràng buộc (2.11b) thực chất là ràng buộc bậc hai lồi. Do đó bài toán trên là bài toán tối ưu hỗn hợp nguyên với ràng buộc bậc hai lồi. III. PHƯƠNG PHÁP GIẢI 3.1. Thuật toán DCA cho bài toán DC tổng quát [7] Cho là tập tất cả các hàm lồi hoàn toàn nửa liên tục dưới trên Hàm liên hợp của thuộc và được xác định như sau: 〈 〉 Chú ý rằng . Cho một hàm . Miền hữu hiệu của , ký hiệu là , là Một bài toán tối ưu DC có dạng , (P) trong đó , được gọi là hàm DC và là hai hàm thành phần của . Bài toán đối ngẫu của (P) có dạng: (D) Điểm được gọi là điểm cực tiểu địa phương của nếu là hữu hạn và tồn tại một lân cận của sao cho: Một điểm được gọi là điểm tới hạn của nếu Trong đó, với là một hàm lồi và , được gọi là dưới vi phân của tại và xác định như sau: 〈 〉 Trong một bài toán DC , điều kiện tối ưu địa phương dưới đây thường được sử dụng: , (3.1) . (3.2) Thuật toán DCA được giới thiệu bởi giáo sư Phạm Đình Tảo vào năm 1985 là một phương pháp để giải bài toán DC tổng quát theo hướng tiếp cận địa phương [3]. Ý tưởng chính của thuật toán là chúng ta sẽ đi tìm cách thay thế thành phần không lồi trong hàm mục tiêu bằng cách xấp xỉ nó bởi một hàm tuyến tính ̃ . Thuật toán cho phép ta đi xây dựng 2 dãy và trong đó (tương ứng ) là nghiệm của bài toán (tương ứng , là bài toán thu được từ (tương ứng ) bằng cách thay hàm (tương ứng ) bởi xấp xỉ tuyến tính của nó ̃ (tương ứng ̃ ): ̃ 〈 〉 〈 〉 với . Bằng cách đó, hai dãy { } và sẽ thỏa mãn các điều kiện sau: Hai dãy và là các dãy giảm. Mỗi điểm giới hạn của dãy { } đều là một điểm tới hạn của . Thuật toán DCA giải bài toán (P)
Trần Đức Quỳnh, Nguyễn Thị Lụa 591 Khởi tạo: Lấy đủ nhỏ và ban đầu, đặt Bước 1: Tính Bước 2: Tính 〈 〉 Bước 3: Cập nhật Bước 4: Nếu thì dừng thuật toán, kết luận là nghiệm thu được bởi DCA. Ngược lại thì gán và quay lại bước 1. 3.2. Biến đổi bài toán tối ưu (2.11) về bài toán tối ưu DC (3.3) Đặt { } Tập chấp nhận được của (2.11) có thể được biểu diễn như sau Xét hàm được định nghĩa như sau ∑ Rõ ràng là hàm lõm, hữu hạn trên K và Do đó, Bài toán (2.11) có thể viết lại như sau ∑ Sử dụng kỹ thuật hàm phạt, khi , bài toán (3.3) có nghiệm hội tụ đến nghiệm tối ưu của bài toán (2.11) ∑ ∑ ( ) (3.3) 3.3. Thuật toán DCA cho bài toán (3.3) Xét bài toán (3.3) với các biến được ký hiệu bởi Đặt ∑ ∑ ∑ Khi đó, với với K là tập lồi, g là hàm lồi, h là hàm lồi, (3.3) có dạng một bài toán quy hoạch DC: Thuật toán DCA cho bài toán (3.3) được mô tả như sau: Thuật toán DCA cho bài toán (3.3) Khởi tạo: Lấy đủ nhỏ, đặt và . Bước 1: Tính : { Bước 2: Tính 〈 〉 . Bước 3: Cập nhật | |. Bước 4: Nếu thì dừng thuật toán, kết luận là nghiệm thu được bởi DCA. Ngược lại thì gán và quay lại bước 1.
592 THUẬT TOÁN DCA CHO MỘT MÔ HÌNH TỐI ƯU DANH MỤC ĐẦU TƯ VỚI RÀNG BUỘC VỀ LỰC LƯỢNG IV. KẾT QUẢ THỬ NGHIỆM Để đánh giá hiệu quả của thuật toán, chúng tôi cài đặt thuật toán DCA cho bài toán (3.3) và thử nghiệm trên các tập dữ liệu khác nhau, là dữ liệu chỉ số chứng khoán từ các thị trường trên thế giới. Cụ thể: Tập dữ liệu DAX (Đức): dữ liệu giá chứng khoán hàng tuần từ tháng 3/1992 đến tháng 9/1997 (291 tuần) của 85 mã chứng khoán. Tập dữ liệu NIKKEI 225 (Nhật Bản): dữ liệu giá chứng khoán hàng tuần từ tháng 3/1992 đến tháng 9/1997 (291 tuần) của 225 mã chứng khoán. Tập dữ liệu NASDAQ (Mỹ): dữ liệu chứng khoán hàng tuần từ tháng 3/2003 đến tháng 3/2008 của 2196 mã chứng khoán. Ngoài việc thay đổi bộ dữ liệu thì chúng tôi còn thay đổi các tham số h, k liên quan đến ràng buộc về lực lượng để làm đa dạng hóa dữ liệu và đánh giá sự thay đổi của nghiệm thu được bởi các thuật toán. Thuật toán được cài đặt bằng C++, sử dụng phần mềm tối ưu hóa CPLEX 12.10.0 để giải các bài toán quy hoạch lồi với ràng buộc bậc hai. Thử nghiệm tiến hành trên máy tính Windows với cấu hình như sau: CPU Core i5- 6200U 2.30GHz, 4.0GB RAM. Kết quả của DCA được so sánh với kết quả của bộ giải bài toán hỗn hợp nguyên với ràng buộc bậc hai lồi (MIQCP) của CPLEX. Đối với bài toán MIQCP, CPLEX có hai phương pháp giải, ta sẽ so sánh kết quả của DCA với cả hai phương pháp này. Kết quả được tổng hợp trong Bảng 1, Bảng 2 và Bảng 3. Trong các bảng này, với mỗi tham số Card tương ứng với số lượng tài sản trong danh mục, thời gian chạy (tính bằng giây) và giá trị hàm mục tiêu của DCA và CPLEX được trình bày. Trong đó: Card: ràng buộc về số lượng tài sản trong danh mục. TimeCPLEX_1: Thời gian chạy của CPLEX_1. ObjCPLEX_1: Giá trị hàm mục tiêu thu được bởi CPLEX_1. TimeCPLEX_2: Thời gian chạy của CPLEX_2. ObjCPLEX_2: Giá trị hàm mục tiêu thu được bởi CPLEX_2. TimeDCA: Thời gian chạy thuật DCA. ObjDCA: Giá trị hàm mục tiêu thu được bởi DCA. Gap được tính như sau với . h, k lần lượt là số tài sản tối thiểu và tối đa yêu cầu cần có trong danh mục đầu tư. Bảng 1. Kết quả thử nghiệm DCA trên bộ dữ liệu DAX, với CPLEX DCA Card TimeCPLEX_1 ObjCPLEX_1 TimeCPLEX_2 ObjCPLEX_2 TimeDCA ObjDCA Gap h=k=5 0,165303 0,007489 0,050017 0,007489 0,094851 0,007489 0,00 % h=k=10 0,117304 0,007408 0,046632 0,007408 0,101635 0,007408 0,00 % h=k=15 0,118517 0,007296 0,050213 0,007296 0,106470 0,007296 0,00 % h=k=20 0,164977 0,007168 0,061990 0,007168 0,106271 0,007168 0,00 % h=k=25 0,114434 0,007025 0,056047 0,007025 0,114651 0,007024 0,01 % h=k=30 0,156426 0,006870 0,050695 0,006870 0,107503 0,006870 0,00 % h=k=35 0,158464 0,006702 0,067825 0,006702 0,110051 0,006702 0,01 % h=5, k=20 0,118677 0,007489 0,079593 0,007489 0,098786 0,007489 0,00 % h=10, k=25 0,123115 0,007408 0,052666 0,007408 0,109339 0,007408 0,00 % h=15, k=30 0,123864 0,007296 0,050610 0,007296 0,107949 0,007296 0,00 % h=20, k=35 0,167149 0,007168 0,045438 0,007168 0,136086 0,007168 0,00 % Bảng 2. Kết quả thử nghiệm DCA trên bộ dữ liệu NIKKEI, với CPLEX DCA Card TimeCPLEX_1 ObjCPLEX_1 TimeCPLEX_2 ObjCPLEX_2 TimeDCA ObjDCA Gap h=k=10 0,254736 0,003633 0,100155 0,003633 0,179870 0,003633 0,00 % h=k=20 0,249618 0,003477 0,068917 0,003477 0,169005 0,003477 0,00 % h=k=30 0,212449 0,003236 0,067850 0,003235 0,169872 0,003235 0,03 % h=k=40 0,353298 0,002926 0,092195 0,002925 0,178948 0,002926 0,03 % h=k=50 0,294351 0,002576 0,101084 0,002576 0,163387 0,002576 0,00 % h=k=60 0,207297 0,002193 0,100759 0,002193 0,159470 0,002192 0,05 % h=k=70 0,290304 0,001775 0,066381 0,001775 0,162672 0,001775 0,00 %
Trần Đức Quỳnh, Nguyễn Thị Lụa 593 CPLEX DCA Card TimeCPLEX_1 ObjCPLEX_1 TimeCPLEX_2 ObjCPLEX_2 TimeDCA ObjDCA Gap h=k=80 0,210000 0,001323 0,105406 0,001323 0,154815 0,001323 0,00 % h=k=90 0,222403 0,000837 0,072367 0,000836 0,162346 0,000837 0,01 % h=10, k=50 0,182593 0,003633 0,073133 0,003633 0,202118 0,003633 0,00 % h=20, k=60 0,203529 0,003477 0,080245 0,003477 0,186596 0,003477 0,00 % h=30, k=70 0,349755 0,003236 0,080726 0,003235 0,174799 0,003236 0,00 % h=40, k=80 0,286846 0,002926 0,069537 0,002926 0,232427 0,002926 0,02 % h=50, k=90 0,309258 0,002576 0,086648 0,002576 0,183074 0,002576 0,00 % Bảng 3. Kết quả thử nghiệm DCA trên bộ dữ liệu NASDAQ, với CPLEX DCA Card TimeCPLEX_1 ObjCPLEX_1 TimeCPLEX_2 ObjCPLEX_2 TimeDCA ObjDCA Gap h=k=50 5,770739 0,020984 1,626120 0,020983 2,241465 0,020984 0,00 % h=k=100 17,445118 0,020607 0,601009 0,020604 2,219649 0,020606 0,00 % h=k=200 4,960819 0,019635 0,706037 0,019635 2,083302 0,019634 0,01 % h=k=300 5,170924 0,018519 0,592876 0,018519 2,678953 0,018516 0,01 % h=k=400 4,221476 0,017232 0,600560 0,017237 2,575112 0,017236 0,01 % h=k=500 4,242997 0,015865 0,685428 0,015865 2,745739 0,015864 0,00 % h=50, k=100 5,430128 0,020984 0,790025 0,020983 2,391426 0,020984 0,00 % h=100, k=200 16,229370 0,020607 0,605430 0,020607 2,308237 0,020607 0,00 % h=200, k=300 5,247118 0,019635 0,716321 0,019635 2,257334 0,019635 0,00 % h=300, k=400 4,627873 0,018513 0,617494 0,018519 2,879001 0,018519 0,00 % h=400, k=500 4,584729 0,017237 0,687806 0,017237 2,647017 0,017236 0,01 % Từ các kết quả số thu được ta rút ra một số nhận xét sau: Thuật toán DCA tìm được lời giải với độ chính xác cao trong tất cả các trường hợp (xem giá trị Gap). Mặc dù DCA là thuật toán tìm nghiệm tối ưu địa phương, kết quả thu được trong các thử nghiệm gần như trùng khớp với nghiệm tối ưu toàn cục tìm được bởi CPLEX; nghiệm thu được thỏa mãn ràng buộc nguyên. DCA khá nhanh: trong khoảng thời gian chưa đến 3 giây, DCA tìm được lời giải cho bài toán với kích thước tương đối lớn. Trong hầu hết các trường hợp DCA nhanh hơn CPLEX_1, điều này rõ ràng hơn khi kích thước bài toán tăng lên. Tuy nhiên, DCA chậm hơn CPLEX_2. V. KẾT LUẬN Trong bài báo này, chúng tôi đã đề xuất mô hình tối ưu danh mục đầu tư có sự kết hợp của hai ràng buộc quan trọng là CVaR và ràng buộc về lực lượng. Với các ràng buộc này, mô hình trở nên khó giải, việc đề xuất các thuật giải cho mô hình này là cần thiết. Chúng tôi đã đề xuất thuật toán DCA cho mô hình. Thử nghiệm phương pháp đề xuất trên các bộ dữ liệu cho kết quả tốt, DCA có thể tìm được nghiệm tối ưu toàn cục trong thời gian rất nhanh. TÀI LIỆU THAM KHẢO [1] H. M. Markowitz, "Portfolio Selection", Journal of Finance, vol. 7, pp. 77-91, 1952. [2] R. RT and U. S, "Optimization of Conditional Value-at-Risk", Journal of Risk, vol. 2, pp. 21-41, 2000. [3] H. A. Le Thi and T. Pham Dinh, "DC programming and DCA: thirty years of developments," Math. Program., vol. 169, pp. 5-68, 2018. [4] Y. Sun, G. Aw, K. L. Teo and G. Zhou, "Portfolio optimization using a new probabilistic risk measure", Journal of Industrial and Management Optimization, pp. 1275-1283, 2015. [5] Y. Sun, E. L. G. Aw, B. Li, K. L. Teo and J. Sun, "CVaR-based robust models for portfolio selection," Journal of Industrial & Management Optimization, pp. 1861-1871, 2020. [6] W. Chen, M. Sim, J. Sun and C.-P. Teo, "From CVaR to uncertain set: Implications in joint chance-constrained optimization," Operations Research, pp. 470-485, 2010. [7] H.A. Le Thi and D. Q. Tran, "Solving a continuous minmax problem for single period portfolio selection with discrete constraints by DCA", Optimization, pp. 1025-1038, Vol. 62, 2012. [8] H.A. Le Thi, T. Pham Dinh, D. Q. Tran, "A DC programming approach for a class of bilevel programming problems and application in portfolio selection", Numerical Algebra, Control and Optimization (NACO), Vol 2, pp. 167-185, 2012. [9] H.A. Le Thi, D. Q. Tran, H.A. Kondo, "A difference of convex functions algorithm for optimal scheduling and real- time assignment of preventive maintenance jobs on parallel processors", to appear in Journal of Industry and Management Optimization (JIMO), pp. 243 - 258, Volume 10, Issue 1, January 2014.
594 THUẬT TOÁN DCA CHO MỘT MÔ HÌNH TỐI ƯU DANH MỤC ĐẦU TƯ VỚI RÀNG BUỘC VỀ LỰC LƯỢNG SOLVING A PORTFOIO SELECTION MODEL WITH CARDINALITY CONSTRAINTS BY DCA Tran Duc Quynh, Nguyen Thi Lua ABSTRACT: Portfolio selection is an important problem. It aims to maximizing the return and minimizing the risk. In this work, we consider an optimization model for portfolio selection problem where the risk measurement is the conditional value at risk (CVaR). Because cardinality constraints play an crucial role in optimizing portfolios, these constraints help diversify the portfolio and then reduce the risk. Therefore, we propose an optimization model that considers both CvaR and cardinality constraints. The proposed model is a mixed integer quadratic constraint optimization problem (MIQCP), it is closer to reality but more difficult to solve. Global solution methods for solving the proposed problem are computationally expensive. Hence, developing local methods is significant and necessary, it help reduce the executing time, particularly for large scale problem. Our approach is to reformulate the problem into a DC optimization problem (the objective function is a difference of convex functions) and then use DC algorithm (DCA) to solve the resulting problem. The numerical results on some dataset show that the solution furnished by DCA is very close to the global solution although DCA is a local method and the executing time is acceptable.