|
== Ký hiệu ==
Các bài toán tối ưu hóa thường được biểu diễn bằng các ký hiệu đặc biệt. VíDưới đây là một vài ví dụ:
=== Giá trị lớn nhất và giá trị nhỏ nhất của hàm số ===
:<math>\min_{x\in\mathbb R}\; x^2 + 1</math> ▼Xét ký hiệu sau đây:
▲:<math>\min_{x\in\mathbb R}\; x^2 + 1</math>
Bài toán trên yêu cầu tìm giá trị nhỏ nhất cho biểu thức ''x<sup>2</sup>'' + 1, trong đó ''x'' chạy trên tập [[số thực]] '''R'''. Giá trị nhỏ nhất trong trường hợp này là 1, xảy ra tại ''x'' = 0. ▼
▲BàiĐây toánlà trênký yêuhiệu cầu tìmcho giá trị nhỏ nhất chocủa biểuhàm thứcmục tiêu ''x< supmath> x^2 +1</ supmath> '' + 1, trongvới đó ''<math>x ''</math> chạynằm trêntrong tập [[số thực]] '''<math display="inline">\mathbb {R '''}</math>. Giá trị nhỏ nhất trong trường hợp này là <math>1 </math>, xảy ra tại ''<math>x '' = 0 </math>.
:<math>\max_{x\in\mathbb R}\; 2x</math>
Tương tự thì ký hiệu
Bài toán trên yêu cầu tìm giá trị lớn nhất cho biểu thức 2''x'', trong đó ''x'' chạy trên tập [[số thực]]. Trong trường hợp này, không có giá trị lớn nhất do biểu thức không bị chặn trên, vậy kết quả là "[[giá trị vô cùng]]" hoặc "không xác định".
:<math>\operatorname{argmin}_max_{x\in[-\infty,-1]mathbb R}\; x^2 + 12x</math>
Bàichỉ toán trên yêu cầu tìm cácra giá trị củalớn ''x''nhất trongcho [[đoạnhàm (toánmục học)|đoạn]]tiêu [−∞<math>2x</math>, −1]với để giá trị của biểu thức ''x''<supmath>2x</supmath>là +một 1số làthực. nhỏTrong nhất.trường (Giáhợp này, không có giá trị nhỏđó nhất củado biểu thức không quanbị trọngchặn trên, quanvậy trọngkết quả là phải tìm ra "[[giá trị x)vô Trongcùng]]" trườnghoặc hợp này, kết quả là ''x''"không =xác 0định".
=== Đối số tối ưu ===
:<math>\operatorname{argmax}_{x\in[-5,5],\;y\in\mathbb R}\; x\cdot\cos(y)</math> ▼Xét ký hiệu sau đây:
<math>\underset{x\in(-\infty,-1]}{\operatorname{arg\,min}} \; x^2 + 1,</math>
Bài toán trên yêu cầu tìm cặp (''x'', ''y'') để giá trị giá trị của biểu thức ''x''·cos(''y'') là lớn nhất, với ràng buộc rằng ''x'' nằm trong đoạn [−5, 5]. (Một lần nữa, giá trị nhỏ nhất của biểu thức không quan trọng, quan trọng là phải tìm ra cặp giá trị (x,y).) Trong trường hợp này, kết quả là các cặp có dạng (5, 2[[pi|π]]''k'') và (−5, (2''k'' + 1)π), với ''k'' chạy trên tập [[số nguyên]]. ▼
hay tương đương là
<math>\underset{x}{\operatorname{arg\,min}} \; x^2 + 1, \; \text{subject to:} \; x\in(-\infty,-1].</math>
Ký hiệu này biểu diễn một hoặc nhiều giá trị của đối số <math>x</math>trong đoạn <math display="inline">(-\infty,-1]</math>sao cho hàm mục tiêu <math display="inline">x^2 + 1</math>đạt giá trị nhỏ nhất (chứ không yêu cầu tìm giá trị nhỏ nhất đó). Kết quả là <math>x=-1</math>, do không như ví dụ đầu tiên, <math>x=0</math>không nằm trong tập khả thi.
Tương tự,
▲:<math>\ operatorname{argmax}_underset{x\in[-5,5], \; y\in\mathbb R} {\operatorname{arg\,max}} \; x \cdot\cos(y) ,</math>
hay ký hiệu tương đương
<math>\underset{x, \; y}{\operatorname{arg\,max}} \; x\cos(y), \; \text{subject to:} \; x\in[-5,5], \; y\in\mathbb R,</math>
▲BàiBiểu toándiễn trênmột yêuhay cầu tìmnhiều cặp <math>( ''x '', ''y '') </math>làm đểcho giáhàm trịmục giátiêu trị<math>x của\cos biểu thức ''x''·cos( ''y '') là</math>đạt giá trị lớn nhất, với ràng buộc rằnglà ''x'' nằm trong đoạn <math display="inline">[ −5-5, 5] </math>. (Một lần nữa, giá trị nhỏtối nhấtưu của biểuhàm mục thứctiêu không quan trọng, quanhàm trọng<math>\arg là\max</math>chỉ phải tìmcho ra cặp giá trị <math>(x,y) </math>thỏa mãn yêu cầu trên.) Trong trường hợp này, kết quả là các cặp số có dạng <math display="inline">(5, 2[[\,2k\pi |π]]''k'') </math>và <math display="inline">( −5-5,\, ( 2''k'' 2k+ 1) π\pi) </math>, với ''<math>k '' chạy trên tập</math>là [[số nguyên]] tùy ý.
== Các lĩnh vực con chính ==
* [[Quy hoạch tuyến tính]]lồi (''LinearConvex programming'') nghiên cứu các trường hợp khi hàm mục tiêu ''f'' là hàm tuyếnlồi tính(cực đại hóa) hoặc hàm lõm (cực tiểu hóa) và tập ''A''khả đượcthi môlà tảlồi. chỉĐây bằngcó cácthể đẳngxem thứcnhư vàtrường bấthợp đẳngđặc thứcbiệt của quy hoạch phi tuyến tínhhoặc (Atrường đượchợp gọitổng làquát mộtcủa khúcquy hoạch tuyến tính và quy hoạch lồi) bậc hai.
** [[Quy hoạch sốtuyến nguyêntính]] (''IntegerLinear programming'') nghiên cứu các quytrường hoạchhợp tuyếnkhi tínhhàm trongmục đótiêu một''f'' số hoặclà tấthàm tuyến tính cảvà các biếnràng buộc có giớidạng hạncác làđẳng cácthức sốvà nguyênbất đẳng thức tuyến tính (Tập ràng buộc như vậy gọi là một polytope).
** ''Second-order cone programming'' (SOCP) bao gồm một số dạng nhất định 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ự như quy hoạch tuyến tính, nhưng thay thế cho các ràng buộc với đối số thực là các ràng buộc với đối số là ma trận bán xác định.
** ''Conic programming'' là dạng tổng quát của quy hoạch lồi. Quy hoạch tuyến tính, SOCP và SDP đều có thể xem là conic programming với loại nón (cone) xác định.
** ''Geometric programming'' là bài toán tối ưu có hàm mục tiêu và hàm điều kiện ràng buộc viết được dưới dạng các đa thức đa biến và chuyển đổi về được 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 trong đó một số hoặc tất cả các biến có giới hạn là các số nguyên.
* Quy hoạch bậc hai (hay [[quy hoạch toàn phương]]) (''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 mô tả được bằng các đẳng thức và bất đẳng thức tuyến tính (A được gọi là một khúc lồi).
* [[Quy hoạch phi tuyến]] (''Nonlinear programming'') nghiên cứu trường hợp tổng quát khi hàm mục tiêu hay các ràng buộc hoặc cả hai 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'') nghiên cứu các trường hợp khi chiến lược tối ưu hóa dựa trên việc 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'') quan tâm đến 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ể được rút gọn về một tập [[rời rạc]].
* [[Infinite-dimensional optimization]] nghiên cứu trường hợp khi tập các lời giải khả thi là một tập con của một không gian vô số chiều, chẳng hạn 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 trường hợp khi hàm mục tiêu ''f'' là hằng số – đây là vấn đề quan trọng của ngành [[Trí tuệ nhân tạo]], đặc biệt là lĩnh vực [[Suy luận tự động]] (''Automated reasoning'').
== Các kỹ thuật ==
| 