Quy hoạch lồi là một lớp bài toán cơ bản của tối ưu hóa. Một đặc
điểm cơ bản nhất của lớp bài toán này là mọi điểm cực tiểu địa phương đều
là cực tiểu tuyệt đối. Tính chất quan trọng này cho phép các lý thuyết có
tính địa phương, như giới hạn, vi phân,. có thể áp dụng trực tiếp vào quy
hoạch lồi. Lý thuyết về bài toán quy hoạch lồi đã được quan tâm nghiên
cứu nhiều và đã thu được nhiều kết quả quan trọng dựa trên lý thuyết
của giải tích lồi và tối ưu hóa; về phương diện tính toán, đã có khá nhiều
phương pháp hữu hiệu cho lớp bài toán này. Các phương pháp đó đã được
giới thiệu trong cuốn sách Tối ưu lồi (Convex Optimization) của các tác
giả Stephen Boyd and Lieven Vandenberghe do nhà xuất bản Cambridge
University Press in năm 2004.
Mục đích của bản luận văn này là để trình bày một số phương pháp
cơ bản nhất cho bài toán quy hoạch lồi. Cụ thể luận văn trình bày các
phương pháp sau: các phương pháp sử dụng đạo hàm bậc nhất, phương
pháp Newton và các phương pháp hàm phạt.
Luận văn gồm có 3 chương:
• Chương 1: Giới thiệu các kiến thức cơ bản nhất về giải tích lồi, đặc
biệt chú trọng vào phép chiếu vuông góc lên một tập lồi đóng và tính dưới
vi phân của hàm lồi; chúng được sử dụng trong các chương tiếp theo.
• Chương 2: Trình bày đối ngẫu Lagrange và áp dụng Định lý Krush -Kuhn - Tucker, Định lý Kuhn - Tucker để giải bài toán quy hoạch lồi và
các định lý về sự tồn tại nghiệm tối ưu của bài toán quy hoạch lồi.
• Chương 3: Trình bày các phương pháp giải bài toán quy hoạch lồi như:
phương pháp dùng đạo hàm bậc nhất gradient, chiếu gradient và trường
hợp tổng quát của nó là chiếu dưới gradient xấp xỉ, thuật toán Frank -Wolf, phương pháp Newton dùng đạo hàm bậc hai và các phương pháp
hàm phạt
