Ý nghĩa của học phần phương pháp tối ưu

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

Đây là ký hiệu cho giá trị nhỏ nhất của hàm mục tiêu x 2 + 1 {\displaystyle x^{2}+1} , với x {\displaystyle x} nằm trong tập số thực R {\textstyle \mathbb {R} } . Giá trị nhỏ nhất trong trường hợp này là 1 {\displaystyle 1} , xảy ra tại x = 0 {\displaystyle x=0} .

Tương tự thì ký hiệu

max x ∈ R 2 x {\displaystyle \max _{x\in \mathbb {R} }\;2x}

chỉ ra giá trị lớn nhất cho hàm mục tiêu 2 x {\displaystyle 2x} , với x {\displaystyle x} là một số thực. Trong trường hợp này, không có giá trị đó 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".

Đối số tối ưuSửa đổi

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

a r g m i n x ∈ [ − ∞ , − 1 ] x 2 + 1 , {\displaystyle {\underset {x\in [-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,}

hay tương đương là

a r g m i n x x 2 + 1 , subject to: x ∈ [ − ∞ , − 1 ] . {\displaystyle {\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{subject to:}}\;x\in [-\infty ,-1].}

Ký hiệu này biểu diễn một hoặc nhiều giá trị của đối số x {\displaystyle x} trong đoạn [ − ∞ , − 1 ] {\textstyle [-\infty ,-1]} sao cho hàm mục tiêu x 2 + 1 {\textstyle x^{2}+1} đạt giá trị nhỏ nhất [chứ không yêu cầu tìm giá trị nhỏ nhất đó]. Kết quả là x = − 1 {\displaystyle x=-1} , do không như ví dụ đầu tiên, x = 0 {\displaystyle x=0} không nằm trong tập khả thi.

Tương tự,

a r g m a x x ∈ [ − 5 , 5 ] , y ∈ R x cos ⁡ [ y ] , {\displaystyle {\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos[y],}

hay ký hiệu tương đương

a r g m a x x , y x cos ⁡ [ y ] , subject to: x ∈ [ − 5 , 5 ] , y ∈ R , {\displaystyle {\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos[y],\;{\text{subject to:}}\;x\in [-5,5],\;y\in \mathbb {R} ,}

Biểu diễn một hay nhiều cặp [ x , y ] {\displaystyle [x,y]} làm cho hàm mục tiêu x cos ⁡ [ y ] {\displaystyle x\cos[y]} đạt giá trị lớn nhất, với ràng buộc là x nằm trong đoạn [ − 5 , 5 ] {\textstyle [-5,5]} . [Một lần nữa, giá trị tối ưu của hàm mục tiêu không quan trọng, hàm arg ⁡ max {\displaystyle \arg \max } chỉ cho ra cặp [ x , y ] {\displaystyle [x,y]} 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 [ 5 , 2 k π ] {\textstyle [5,\,2k\pi ]} và [ − 5 , [ 2 k + 1 ] π ] {\textstyle [-5,\,[2k+1]\pi ]} , với k {\displaystyle k} là số nguyên tùy ý.

• Quy hoạch lồi [Convex programming] nghiên cứu trường hợp khi 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à tập khả thi là lồi. Đây có thể xem như trường hợp đặc biệt của quy hoạch phi tuyến hoặc 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] nghiên cứu các trường hợp khi hàm mục tiêu f là hàm tuyến tính và các ràng buộc có dạng các đẳng thức và bấ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].

Đố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 tìm 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à sử dụng ma trận Hesse để xác định xem đó là cực tiểu, cực đại, hay điểm yên ngựa.

Ta có thể tìm các điểm dừng bằng cách bắt đầu từ một điểm dự đoán là điểm dừng rồi tiến về điểm dừng bằng cách lặp đi 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

Nếu 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ẽ là cực tiểu toàn cục. Có các phương pháp số nhanh chóng và hiệu quả cho việc tối ưu hóa các hàm lồi khả vi hai lần.

Các bài toán ràng buộc thường có thể được biến đổi thành một bài toán không có ràng buộc bằng phương pháp nhân tử Lagrange [Lagrange multiplier].

Dưới đây là một số phương pháp thông dụng:

• random-restart hill climbing [leo đồi lặp ngẫu nhiên]
• phương pháp luyện thép [simulated annealing]
• stochastic tunneling [dò tìm ngẫu nhiên]
• giải thuật di truyền
• chiến lược tiến hóa
• differential evolution
• particle swarm optimization [tối ưu bầy đàn]

Các bài toán trong động lực học vật rắn [cụ thể là động lực học vật rắn chính xác] thường đòi hỏi các kỹ thuật quy hoạch toán học, do ta có thể coi động lực học vật rắn như là 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 ràng buộc [constraint manifold]; các ràng buộc là các ràng buộc hình học không tuyến tính đa dạng, chẳng hạn "hai điểm này phải luôn trùng nhau", "bề mặt này không được xuyên qua các bề mặt khác", hoặc "điểm này phải nằm đâu đó trên đường cong này". Ngoài ra, vấn đề 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 một bài toán bù tuyến tính [linear complementarity problem]. Dạng bài nài cũng có thể được coi là bài toán quy hoạch bậc hai.

Nhiều bài toán thiết kế cũng có thể được biểu diễn dưới dạng các chương trình tối ưu hóa. Áp dụng này được gọi là tối ưu hóa thiết kế. Một lĩnh vực con mới phát triển trong thời gian gần đây là multidisciplinary design optimization. Nó hữu ích cho nhiều bài toán và đã được áp dụng cho các bài toán kỹ nghệ hàng không [aerospace engineering].

Vận trù học [operations research] là lĩnh vực sử dụng rất nhiều đến 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]
• variational inequality ["Bất đẳng thức biến phân"]
• thuật toán đơn hình [simplex algorithm]
• interior point methods ["Các phương pháp điểm trong"]
• Bài toán cân bằng ["Equilbrium problems"]
• Các ấn bản quan trọng về ngành tối ưu hóa

• Stephen Boyd and Lieven Vandenberghe [2004]. Convex Optimization, 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.

• 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 — include optimization in industry solutions [free trial license available];
• Xpress-MP – Optimization software free to students