Tối ưu hóa trong toán học

Trong toán học, thuật ngữ tối ưu hóa ám chỉ việc nghiên cứu các bài toán có cấu trúc

Cho: một hàm f: A $\to <!--\; \to \; -->$ R từ tập hợp A đến tập số thực

Tìm: một phần tử x₀ thuộc A sao cho f(x₀) ≤ f(x) với mọi x thuộc A ('cực tiểu hóa') hoặc sao cho f(x₀) ≥ f(x) với mọi x thuộc A ('cực đại hóa').

Một bài toán như vậy thường được gọi là quy hoạch toán học (mathematical program). Nhiều bài toán thực tiễn và lý thuyết có thể được diễn tả theo cách này.

Miền xác định A của hàm f được gọi là không gian tìm kiếm. Thường thì, A là một tập con của không gian Euclid R, và được xác định bởi một tập các ràng buộc như các đẳng thức hoặc bất đẳng thức mà các phần tử của A phải thỏa mãn. Các phần tử trong A được gọi là các lời giải khả thi. Hàm f là hàm mục tiêu hoặc hàm chi phí. Một lời giải khả thi tối ưu hóa hàm mục tiêu (hoặc tối đa hóa nếu đó là mục tiêu) được gọi là lời giải tối ưu.

Thông thường, có nhiều điểm cực tiểu và cực đại địa phương, trong đó một cực tiểu địa phương x được xác định bởi điều kiện sau:

với một giá trị δ > 0 nào đó và cho mọi giá trị x sao cho

$\Vert <!--\; \Vert \; -->x-<!--\; -\; -->x^{\ast <!--\; \ast \; -->}\Vert <!--\; \Vert \; -->\le <!--\; \le \; -->\mathrm{\delta <!--\; \delta \; -->}$;

thì công thức dưới đây luôn đúng

$f\left(x^{\ast <!--\; \ast \; -->}\right)\le <!--\; \le \; -->f\left(x\right)$

Điều này có nghĩa là, trong khu vực quanh điểm x, mọi giá trị của hàm đều không nhỏ hơn giá trị tại điểm x. Cực đại địa phương được xác định theo cách tương tự. Thông thường, việc tìm các cực tiểu địa phương là đơn giản hơn – cần thêm thông tin về bài toán (ví dụ, nếu hàm mục tiêu là hàm lồi) để đảm bảo rằng lời giải tìm được là cực tiểu toàn cục.

Ký hiệu

Các bài toán tối ưu hóa thường được thể hiện qua các ký hiệu đặc biệt. Dưới đây là một số ví dụ:

Giá trị cực đại và cực tiểu của hàm số

Xem xét các ký hiệu sau đây:

$\underset{x\in <!--\; \in \; -->R}{min}{x}^2+1$

Đây là ký hiệu để chỉ giá trị nhỏ nhất của hàm mục tiêu $x^2+1$, với $x$ thuộc tập số thực $R$. Giá trị nhỏ nhất trong trường hợp này là $1$, đạt được khi $x=0$.

Tương tự, ký hiệu

$\underset{x\in <!--\; \in \; -->R}{max}2x$

chỉ ra giá trị lớn nhất của hàm mục tiêu $2x$, với $x$ là một số thực. Trong trường hợp này, không có giá trị lớn nhất vì biểu thức không bị giới hạn trên, do đó kết quả là 'vô cùng' hoặc 'không xác định'.

Đối số tối ưu

Xem xét ký hiệu sau đây:

$\underset{x\in <!--\; \in \; -->(-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->},-<!--\; -\; -->1]}{argmin}{x}^2+$

1 , {\displaystyle {\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,}

hoặc có thể viết dưới dạng

$\underset{x}{argmin}{x}^2+1,\text{với điều kiện:}x\in <!--\; \in \; -->(-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->},-<!--\; -\; -->1].$

Ký hiệu này chỉ ra một hoặc nhiều giá trị của biến $x$ trong khoảng $(-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->},-<!--\; -\; -->1]$ để hàm mục tiêu $x^2+1$ đạt giá trị nhỏ nhất (không yêu cầu tìm giá trị nhỏ nhất đó). Kết quả là $x=-<!--\; -\; -->1$, vì $x=0$ không nằm trong phạm vi hợp lệ.

Tương tự như vậy,

$\underset{x\in <!--\; \in \; -->[-<!--\; -\; -->5,5],y\in <!--\; \in \; -->R}{argmax}x\cos <!--\; \; -->\left(y\right),$

hoặc có thể được viết như sau

$\underset{x,y}{argmax}x\cos <!--\; \; -->\left(y\right),\text{với điều kiện:}x\in <!--\; \in \; -->[-<!--\; -\; -->5,5],y\in <!--\; \in \; -->R,$

Tìm các cặp $(x,y)$để hàm mục tiêu $x\cos <!--\; \; -->\left(y\right)$đạt giá trị cao nhất, với điều kiện là x nằm trong khoảng $[-<!--\; -\; -->5,5]$. (Lưu ý, giá trị tối ưu của hàm mục tiêu không quan trọng, hàm $\arg <!--\; \; -->max$chỉ xác định cặp $(x,y)$thỏa mãn điều kiện này.) Kết quả là các cặp có dạng $(5,2k\mathrm{\pi <!--\; \pi \; -->})$và $(-<!--\; -\; -->5,(2k+1\left)\mathrm{\pi <!--\; \pi \; -->}\right)$, với $k$là số nguyên tùy ý.

Các lĩnh vực chính

• Quy hoạch lồi (Convex programming) phân tích trường hợp hàm mục tiêu là hàm lồi (cực đại hóa) hoặc hàm lõm (cực tiểu hóa) với tập khả thi là lồi. Đây được xem là một dạng đặc biệt của quy hoạch phi tuyến hoặc là trường hợp tổng quát của quy hoạch tuyến tính và quy hoạch lồi bậc hai.
  • Quy hoạch tuyến tính (Linear programming) tìm hiểu các tình huống khi hàm mục tiêu f là hàm tuyến tính và các ràng buộc là các đẳng thức và bất đẳng thức tuyến tính (gọi tập ràng buộc như vậy là một polytope).
  • Second-order cone programming (SOCP) bao gồm một số dạng cụ thể trong quy hoạch bậc hai.
  • Semidefinite programming (SDP) là lĩnh vực con của tối ưu lồi tương tự quy hoạch tuyến tính, nhưng thay vì các ràng buộc với đối số thực, ta có các ràng buộc với ma trận bán xác định.
  • Conic programming mở rộng quy hoạch lồi. Quy hoạch tuyến tính, SOCP và SDP đều thuộc conic programming với loại nón (cone) xác định.
  • Geometric programming là bài toán tối ưu với hàm mục tiêu và ràng buộc được viết dưới dạng đa thức đa biến và có thể chuyển đổi thành quy hoạch lồi.
• Quy hoạch số nguyên (Integer programming) nghiên cứu các quy hoạch tuyến tính với một số hoặc tất cả các biến là số nguyên.
• Quy hoạch bậc hai (Quadratic programming) cho phép hàm mục tiêu có các toán hạng bậc hai, trong khi tập A phải được mô tả bằng các đẳng thức và bất đẳng thức tuyến tính (gọi là khúc lồi).
• Quy hoạch phi tuyến (Nonlinear programming) phân tích các tình huống tổng quát khi hàm mục tiêu hoặc các ràng buộc chứa các thành phần không tuyến tính.
• Quy hoạch ngẫu nhiên (Stochastic programming) nghiên cứu các trường hợp khi một số ràng buộc phụ thuộc vào các biến ngẫu nhiên.
• Quy hoạch động (Dynamic programming) tập trung vào các chiến lược tối ưu hóa bằng cách chia bài toán thành các bài toán con nhỏ hơn (nguyên lý quy hoạch động).
• Tối ưu hóa tổ hợp (Combinatorial optimization) giải quyết các bài toán trong đó tập các lời giải khả thi là rời rạc hoặc có thể thu gọn về một tập rời rạc.
• Infinite-dimensional optimization nghiên cứu các bài toán khi tập các lời giải khả thi là một tập con của không gian vô số chiều, chẳng hạn như không gian các hàm số (ví dụ: bài toán điều khiển tối ưu).
• Constraint satisfaction nghiên cứu các tình huống khi hàm mục tiêu f là hằng số – đây là một vấn đề quan trọng trong trí tuệ nhân tạo, đặc biệt là lĩnh vực Suy luận tự động (Automated reasoning).

Các phương pháp

Đối với các hàm khả vi hai lần (twice-differentiable), có thể giải các bài toán không ràng buộc bằng cách xác định các điểm mà tại đó đạo hàm của hàm mục tiêu bằng 0 (điểm dừng) và áp dụng ma trận Hesse để phân tích xem đó là cực tiểu, cực đại, hay điểm yên ngựa.

Chúng ta có thể xác định các điểm dừng bằng cách bắt đầu từ một điểm dự đoán và sau đó tiếp cận điểm dừng thông qua việc lặp lại các phương pháp như

• Phương pháp Gradient (gradient descent)
• Phương pháp Newton
• Phương pháp Gradient liên hợp (conjugate gradient)
• Line search

Khi hàm mục tiêu là hàm lồi trong vùng quan tâm, thì cực tiểu địa phương sẽ đồng thời là cực tiểu toàn cục. Có những phương pháp số nhanh và hiệu quả để tối ưu hóa các hàm lồi khả vi hai lần.

Các bài toán có ràng buộc thường có thể được chuyển thành bài toán không có ràng buộc nhờ phương pháp nhân tử Lagrange (Lagrange multiplier).

Dưới đây là một số phương pháp phổ biến:

• Leo đồi ngẫu nhiên (random-restart hill climbing)
• Phương pháp luyện thép (simulated annealing)
• Dò tìm ngẫu nhiên (stochastic tunneling)
• Thuật toán di truyền
• Chiến lược tiến hóa
• Tiến hóa phân tích (differential evolution)
• Tối ưu bầy đàn (particle swarm optimization)

Ứng dụng

Các bài toán trong động lực học vật rắn, đặc biệt là động lực học vật rắn chính xác, thường cần đến các kỹ thuật quy hoạch toán học. Đây là vì động lực học vật rắn có thể được hiểu như việc giải các phương trình vi phân thường (ordinary differential equation) trên một đa tạp với các ràng buộc (constraint manifold); các ràng buộc này thường là các ràng buộc hình học không tuyến tính như 'hai điểm này phải luôn trùng nhau', 'bề mặt này không được xuyên qua bề mặt khác', hoặc 'điểm này phải nằm trên đường cong này'. Ngoài ra, việc tính toán các lực tiếp xúc có thể được thực hiện bằng cách giải bài toán bù tuyến tính (linear complementarity problem). Bài toán này cũng có thể được xem như là một bài toán quy hoạch bậc hai.

Nhiều bài toán thiết kế có thể được chuyển thành các chương trình tối ưu hóa. Ứng dụng này được gọi là tối ưu hóa thiết kế. Một lĩnh vực mới nổi gần đây là tối ưu hóa thiết kế đa ngành, rất hữu ích cho nhiều bài toán và đã được áp dụng trong kỹ thuật hàng không (aerospace engineering).

Vận trù học (operations research) là một lĩnh vực rất phụ thuộc vào các kỹ thuật tối ưu hóa.

• arg max
• lý thuyết trò chơi
• vận trù học
• logic mờ
• tối ưu hóa ngẫu nhiên (random optimization)
• Bất đẳng thức biến phân (variational inequality)
• Thuật toán đơn hình (simplex algorithm)
• Các phương pháp điểm trong (interior point methods)
• Bài toán cân bằng (Equilibrium problems)
• Các tài liệu quan trọng về tối ưu hóa

• Stephen Boyd và Lieven Vandenberghe (2004). Convex Optimization Lưu trữ 2007-10-30 tại Wayback Machine, Cambridge University Press. ISBN 0-521-83378-7.
• Doãn Tam Hòe, Lý thuyết tối ưu và đồ thị, Nhà xuất bản Giáo dục 2005.

Liên kết ngoài

• NEOS Guide Lưu trữ 2009-03-01 tại Wayback Machine

Phần mềm:

• AIMMS Optimization Modeling Lưu trữ 2008-02-03 tại Wayback Machine — bao gồm giải pháp tối ưu hóa trong ngành (có giấy phép dùng thử miễn phí);
• Xpress-MP – Phần mềm tối ưu hóa miễn phí cho sinh viên

Toán học
Lịch sử Dòng thời gian Tương lai Đại cương Danh sách Ký hiệu
Nền tảng	Logic toán Lý thuyết hình thái Lý thuyết phạm trù Lý thuyết tập hợp Lý thuyết thông tin Triết học toán học
Đại số	Đa tuyến tính Đồng điều Giao hoán Lý thuyết nhóm Phổ dụng Sơ cấp Trừu tượng Tuyến tính
Giải tích	Giải tích điều hòa Giải tích hàm Giải tích phức Giải tích thực Lý thuyết độ đo Phương trình vi phân Vi tích phân
Rời rạc	Lý thuyết đồ thị Lý thuyết thứ tự Tổ hợp
Hình học	Đại số Euclid Giải tích Hữu hạn Rời rạc Số học Vi phân
Lý thuyết số	Số học Đại số Giải tích Hình học Diophantos
Tô pô	Đại số Hình học Đại cương Vi phân Lý thuyết đồng luân
Ứng dụng	Hóa học Kinh tế Lý thuyết điều khiển tự động Lý thuyết trò chơi Sinh học Tài chính Tâm lý Thống kê toán học Xác suất Thống kê Vật lý
Tính toán	Khoa học máy tính Lý thuyết tính toán Lý thuyết độ phức tạp tính toán Đại số máy tính Giải tích số Tối ưu hóa
Liên quan	Toán học giải trí Toán học và nghệ thuật Giáo dục toán học
Thể loại · Chủ đề · Commons · Dự án