Thuật toán nhánh-giảm đơn hình giải bài toán quy hoạch lồi chứa ràng buộc tích

: 09h00, ngày 26/04/2014 (Thứ Bảy)

: Bộ môn Toán ứng dụng

: Seminar Tối ưu

: NCS Trần Ngọc Thăng

: Toán tin

Tóm tắt báo cáo

Abstract. Optimization problems that involve products of convex functions in the objective function or in the constraints arise in a variety of applications. These problems are difficult global optimization problems. During the past 15 years, however, a number of practical algorithms have been proposed for globally solving these types of problems. In this article, we present and validate a branch-and-reduce algorithm for finding a global optimal solution to a convex program that contains an additional constraint on the product of several convex functions. To globally solve this problem, the algorithm instead globally solves an equivalent master problem. At any stage of the algorithm, a disconnected set consisting of a union of simplices is constructed. This set is guaranteed to contain a portion of the boundary of the feasible region of the master problem where a global optimal solution lies. The algorithm uses a new branch-and-reduce scheme to iteratively reduce the sizes of these sets until a global optimal solution is found. Several potential computational advantages of the algorithm are explained, and a numerical example is solved.

 

Tóm tắt. Các bài toán tối ưu liên quan đến tích của các hàm lồi trên hàm mục tiêu hay trong các ràng buộc được nảy sinh từ nhiều ứng dụng. Đây là các bài toán tối ưu toàn cục khó. Tuy nhiên, trong 15 năm qua, một số thuật toán đã được đề xuất để giải toàn cục các lớp bài toán này. Trong bài báo này, chúng tôi đưa ra một thuật toán nhánh-giảm để tìm nghiệm tối ưu toàn cục của một bài toán quy hoạch lồi có chứa thêm một ràng buộc là tích của các hàm lồi. Thay vì giải toàn cục bài toán ban đầu, thuật toán sẽ giải một bài toán tương đương. Tại mỗi bước của thuật toán, một tập không liên thông gồm hợp của các đơn hình được xây dựng. Tập này đảm bảo chứa một phần biên của tập chấp nhận được của bài toán tương đương mà nghiệm tối ưu toàn cục nằm trong đó. Thuật toán sử dụng một lược đồ nhánh-giảm để giảm kích cỡ của các tập này cho đến khi một nghiệm tối ưu toàn cục được xác định. Một vài ưu điểm tính toán của thuật toán được phân tích và một ví dụ số được đưa ra.


Đánh giá bài viết


Xem thêm