Bài giảng Tối ưu hóa trong thiết kế cơ khí - Chương I: Những khái niệm cơ bản

Trường Đại học Công nghiệp thành phố Hồ Chí Minh Khoa Công nghệ Cơ khí CHƯƠNG I: NHỮNG KHÁI NIỆM CƠ BẢN Thời lượng: 6 tiết (2 buổi) 2 Các tình huống tối ưu hóa trong thiết kế Cơ khí 31 dm minV S   h a a 3 Các tình huống tối ưu hóa trong thiết kế Cơ khí Cho dầm với mặt cắt hình tròn đặc với đường kính d, được làm từ vật liệu có khối lượng riêng ρ. Chiều dài dầm là L. Tìm đường kính d để khối lượng dầm là tối thiểu, biết tần số dao động riêng thứ nhất của nó không được vượt quá giá trị f 4 Các tình huống tối ưu hóa trong thiết kế Cơ khí Tìm d, D, N để lò xo nhẹ nhất mà vẫn đảm bảo các điều kiện: - Về độ cứng - Về độ bền - Về tần số dao động 5 Phân dạng các vấn đề tối ưu hóa Tối ưu hóa Không ràng buộc Có ràng buộc Phát biểu của một vấn đề tối ưu hóa 1 2 n x x x                XTìm Để hàm f(X) nhỏ nhất 1 2 n x x x                XTìm Để hàm f(X) nhỏ nhất và phải thỏa mãn các điều kiện ràng buộc 6 Phát biểu của một vấn đề tối ưu hóa 7 Phát biểu của một vấn đề tối ưu hóa - Thường là: • Kích thước của các kết cấu (dài, góc) • Các thuộc tính vật liệu (khối lượng, nhiệt độ, ) - Giá trị của các tham biến thường nằm trong 1 khoảng giới hạn - Tham biến có thể là một số thực, rời rạc, số nhị phân, số nguyên 8 Phát biểu của một vấn đề tối ưu hóa - Thường là: • Khối lượng của một vật hay chi tiết, cụm vật, v.v • Ứng suất, độ bền • Chuyển vị, độ cứng • Giá thành, chi phí • Hiệu suất, công suất, năng suất 9 Phát biểu của một vấn đề tối ưu hóa Thường là các điều kiện liên quan đến: - ngưỡng giới hạn của một hiện tượng vật l{ nào đó - ngưỡng giới hạn của yêu cầu kỹ thuật về kích thước, khối lượng, ứng suất, biến dạng, tần số dao động, năng suất, độ nhám bề mặt, sai số, v.v 10 Tính lồi lõm (Convexity) Tập hợp lồi Tập hợp không lồi 11 Tính lồi lõm (Convexity) 12 Tính lồi lõm (Convexity) Khái niệm lồi – lõm quan trọng để xác định hàm số chỉ có 1 giá trị cực tiểu. Một hàm lồi sẽ có 1 cực tiểu toàn cục. Nếu hàm không lồi thì cực trị có thể chỉ là địa phương. Cực trị địa phương Cực trị toàn cục Hàm số có nhiều hơn 1 cực đại và cực tiểu gọi là hàm đa phương thức (Multimodal function) 13 Cực tiểu toàn cục chặt chẽ Không có cực tiểu toàn cục chặt chẽ Cực tiểu toàn cục không chặt chẽ Cực tiểu cục bộ chặt chẽ (toàn cục) Cực tiểu cục bộ chặt chẽ Cực tiểu cục bộ không chặt chẽ Cực tiểu cục bộ chặt chẽ 14 Tính lồi lõm (Convexity) Các kỹ sư không chỉ quan tâm đến cực trị toàn cục (Global Optimum) mà còn cần quan tâm đến các cực trị địa phương và các cực trị trong điều kiện ràng buộc. Vì không phải lúc nào cũng có thể sử dụng thiết kế theo cực trị toàn cục do bị các ràng buộc kỹ thuật khác từ chối. 15 Tính lồi lõm (Convexity) Nếu f(x) là hàm lồi thì –f(x) sẽ là hàm lõm Chính vì vậy ta có:    min maxf x f x    16 Đạo hàm (độ dốc) của hàm số f(x) Tiếp tuyến Phương của độ dốc thể hiện sự thay đổi giá trị của hàm số một cách lớn nhất. Độ dốc cung cấp thông tin cần thiết về phương hướng tìm kiếm cực trị (cực đại hoặc cực tiểu) địa phương của hàm số. Trong hầu hết các bài toán tối ưu, khi mà hàm số f(x) là phi tuyến thì đạo hàm (độ dốc) thường được tính bằng phương pháp số. Đối với hàm 1 biến số thì tiếp tuyến tại mọi điểm của đồ thị và độ dốc của nó là như nhau. 17 Phương pháp số để tính đạo hàm 18 Phân định cực đại hay cực tiểu Cực đại Cực tiểu   0f x    0f x    0f x  Điểm uốn   0f x  19 Độ dốc của hàm nhiều biến   1 2, , , , nf x x xx x   1 2 n f x f xf f x                       x 20 Tiếp tuyến và độ dốc của hàm 2 biến    3 1 2 1 2, sinx f x x x x   Giao tuyến giữa các mặt phẳng song song với mặt phẳng x1x2 với bề mặt hàm số sẽ tạo ra các đường đồng mức, mà ở đó giá trị của hàm số tại mọi điểm trên những đường này đều bằng nhau. 21 Tiếp tuyến và độ dốc của hàm 2 biến    3 1 2 1 2, sinx f x x x x   Chiều của mũi tên là chiều mà giá trị hàm f tăng 22 Tiếp tuyến và độ dốc của hàm 2 biến Độ dốc vuông góc với các tiếp tuyến với các đường đồng mức của hàm số. Hay nói cách khác: Độ dốc chính là véctơ Pháp tuyến với đường cong 23 Ma trận Jacobian Xét m hàm số n biến:      1 1 2 2 1 2 1 2, , , , , , , , , , , ,n n m nf x x x f x x x f x x x Độ dốc của những hàm này có thể được đặt trong 1 ma trận Jacobian:   1 1 1 1 2 2 2 2 1 2 x 1 2 n n m n m m m n f f f x x x f f f x x x f f f x x x                                  J Đối với các bài toán tối ưu hóa có ràng buộc, có thể việc di chuyển theo hướng độ dốc sẽ dẫn đến việc di chuyển vào vùng không hợp lệ (infeasible region). Trong trường hợp như vậy, người ta có thể di chuyển theo một số hướng tìm kiếm khác, và khi đó ta sẽ cần biết tốc độ thay đổi giá trị của hàm số theo những hướng đó. Đạo hàm định hướng (The directional derivative) sẽ cung cấp thông tin về vận tốc thay đổi giá trị tức thời của hàm số theo một hướng nhất định. Nếu u là một véc tơ đơn vị, thì đạo hàm định hướng của hàm f(x) theo hướng của u được tính bởi công thức:   T f   x u 24 Ý nghĩa của đạo hàm định hướng MAX e  f x u   T f   x u Rào cản ràng buộc 25 Ma trận Hessian Xét hàm số n biến:    1 2, , , nf f x x xx Ma trận Hessian được định nghĩa:   2 2 2 2 1 1 2 1 2 2 2 2 2 1 2 2 2 2 2 2 1 2 n n n n n f f f x x x x x f f f x x x x x f f f x x x x x                                         H 1. Ma trận Hessian là một ma trận đối xứng 2. Ma trận Hessian phải dương tại điểm cực tiểu của hàm số 3. Ma trận Hessian phải âm tại điểm cực đại của hàm số 26 Bài tập ví dụ 1 Cho hàm 3 biến số:     2 2 21 2 3 1 1 2 2 3 2 3, , 2 3 4 5f f x x x x x x x x x x     x Yêu cầu: 1. Tìm Gradient và ma trận Hessian của hàm số 2. Tìm đạo hàm định hướng của hàm f tại điểm (1,1,1) theo hướng của véctơ d=[1,2,3]T Gradient: Hessian: Véctơ đơn vị của d: tại điểm (1,1,1) Đạo hàm định hướng: 27 Xấp xỉ tuyến tính và bậc 2 Dãy Taylor được dùng để xấp xỉ hóa hàm số n biến:           1 2 T Tf f f f               0 0 0 0x x Δx x x Δx Δx H x Δx     0 0x x Δx Δx x xVới: Xấp xỉ tuyến tính (The Linear Approximation):           T f l f f       0 0 0x x x x x x Xấp xỉ bậc hai (The Quadratic Approximation):                 1 2 T T f q f f                 0 0 0 0 0 0x x x x x x x x H x x x Để tính toán cần tính sẵn các véctơ và ma trận sau đây:             f f f           0 0 0 0 x x x x x H x H x Chú {, dĩ nhiên là f(x)≈l(x)≈q(x) khi x≈x0 28 Ý nghĩa của việc xấp xỉ                   1 2 T T l q f f f                0 0 0 0 0 0 x x x x x x x x x H x x x 0 0x  29 Bài tập ví dụ 2 Hãy xây dựng xấp xỉ tuyến tính và xấp xỉ bậc 2 của hàm số sau tại điểm (2,1) và kiểm tra lại giá trị của hàm số, giá trị của các xấp xỉ tại điểm lân cận của nó là (1.9,1.1)   12 2 3 x f x x  x Dựa theo quy trình tính, ta có:                 1 2 1 2 2 1 2 2 2 2 1 2 3 2 2 2 1 ; 2 1 1 1 1 5 3 1 0 0 1 2 1 41 T T x x x x f x f f x x x x x x                                                          0 0 0 0 0 x x x x x x x H x H x 30 Bài tập ví dụ 2 (tiếp) Xấp xỉ tuyến tính và xấp xỉ bậc 2 sau khi rút gọn có dạng: 2 1 2 2 1 22 2 7 2x x x x x           1.9,1.1 1.9, 1.572727 11.1 1.9,1. .6 1 1.57 f l q    Xấp xỉ bậc 2 chính xác hơn xấp xỉ tuyến tính 31                                 0.1 1 1 5 1 1 0.1 5 0.1 1.6 0.1 0 1 0.11 1 1.6 0.1 0.1 1 4 0.12 2 0.11 1.6 0.1 0.5 0.12 1 1.6 0.01 0.05 1.57 2 T T l f f q l                                                                       0 0 0 0 0 0 x x x x x x x x x H x x x                 2 1 2 2 2 2 1 2 3 2 2 2 1 1.9 2 0.1 1.1 1 0.11.9 1.1 1 1 1 5 3 1 0 0 1 2 1 41 T T f x f f x x x x x x                                                                  0 0 0 0 0 x x x x x x x H x H x   12 2 3 x f x x  x 32 Phép khử Gauss và phần tử cơ sở (Gaussian Elimination and Pivot Elements) 0 . . . 0 0 . . . 0 0 . 0 0 0 0 0 . . . 0 0 . . . 0 0 . 0 0 . . . 0 0 . . . 0 0 . . . 0 Sau i=1 Sau i=2 Sau i=3 Sau i=n-1 Dạng bậc thang (Row Echelon Form) 0 . . . 0 0 . . . 0 0 . 0 0 0 0 Phần tử cơ sở ≠ 0 (Pivot Elements) 33 Hạng (Rank) của ma trận Nếu B là một ma trận bậc thang thì hạng (rank) của B bằng số hàng khác 0 của nó Các phép biến đổi sơ cấp không làm thay đổi hạng của ma trận  Ta sẽ đưa ma trận bất kz A về ma trận bậc thang B. Từ đó hạng của A cũng sẽ là hạng của B: rank(A)=rank(B) 34     1 1 2 2 1 3 3 1 4 4 1 2 2 1 23 5 4 3 8 2 5 1 0 3 32 5 3 2 5 0 1 0 8 11 3 3 0 1 2 4 7 1 3 32 4 7 1 5 2 6 3 4 43 5 2 6 3 0 3 3 34 3 1 2 4 3 1 2 17 17 0 2 3 3 2 1 R R R R R R R R R R R R R A                                                                   3 3 2 3 3 4 4 2 4 2 3 25 17 3 5 2 52 5 0 1 01 0 3 3 3 33 3 11 3 11 311 3 0 1 0 10 1 8 8 8 88 8 4 43 125 5 0 3 0 0 10 0 3 3 52 2 17 3317 17 17 33 0 00 2 0 0 8 83 3 8 8 R R R R R R R R                                                                       4 4 3 17 8 2 5 1 0 3 3 11 3 0 1 8 8 1 0 0 1 5 37 0 0 0 10 R R R                                               Tìm hạng của ma trận A: 4 hàng khác 0  Rank(A) = 4 35 REDUCED ROW ECHELON FORM       1 1 2 1 2 3 1 3 2 2 3 3 1 12 1 2 2 5 3 7 1 3 7 1 1 1 1 1 2 2 22 3 2 7 1 2 2 2 1 13 11 1 1 1 3 6 1 1 1 3 6 0 2 2 2 2 1 1 1 5 4 1 1 1 5 4 5 17 7 0 2 2 2 2 3 7 1 1 2 2 0 1 4 13 4 1 0 1 5 R R R R R R R R R R R R A                                                                  3 2 3 3 3 2 3 2 1 3 1 1 5 416 1 3 7 1 1 1 2 2 2 2 11 0 1 4 13 11 7 7 16 48 48 0 0 5 5 5 5 5 3 7 1 3 7 1 1 1 1 1 2 2 2 2 2 2 0 1 4 13 11 0 1 0 1 1 0 0 1 3 3 0 0 1 3 3 R R R R R R R R R R R                                                                               1 2 1 3 2 3 1 7 1 0 1 0 0 1 22 2 2 0 1 0 1 1 0 1 0 1 1 0 0 1 3 3 0 0 1 3 3 R R R                                 36 REDUCED ROW ECHELON FORM 7 2 5 4 1 3 6 7 2 8 2 4 2 9 4 A             3711 1 0 0 4812 31 7 0 1 0 24 48 0 0 1 1 15 16 A                    37 Giá trị riêng (Eigenvalues) và Véctơ riêng (Eigenvector) Cho ma trận vuông [A] kích thước (n x n). λ là giá trị riêng, và là véctơ riêng của ma trận [A], nếu thỏa mãn điều kiện sau:     x1 x1x 1 n nn n   A v v Giá trị riêng λ là nghiệm của phương trình sau:         x x x det det 0; 2 n n n n n n                     Δ A I Trong đó:       x x xn n n n n n            Δ A I - Là ma trận đặc trưng (Characteristic Matrix) - Là phương trình đặc trưng (Characteristic Equation) Phương trình (2) có n nghiệm: λ1,λ2,, λn. Mỗi nghiệm λi có véctơ riêng . 38 Giá trị riêng (Eigenvalues) và Véctơ riêng (Eigenvector) 1 2 x1n n                L - Là ma trận (của) véctơ riêng 1 2 x x1 x1 x1 n n n n n n            V v v v - Là véc tơ (của) giá trị riêng Có nghĩa là chúng ta sẽ có n đẳng thức sau:     1 1 1 x1 x1x x1 x1x n nn n n n n n nn n         A v v A v v 39 Giá trị riêng (Eigenvalues) và Véctơ riêng (Eigenvector) Khi có λi ta làm như sau để tìm véctơ riêng :       x1 x1 x1x x x x x1 i i i i i n n nn n n n n n n n n                    Δ A v v A I v 0 Δ 0 Dùng phép khử Gauss để đưa về dạng bậc thang (Reduced Row Echelon Form) 40 Giá trị riêng (Eigenvalues) và Véctơ riêng (Eigenvector) 3x3 1 3 3 3 5 3 6 6 4               A Tìm giá trị riêng và véctơ riêng của ma trận sau: 1. Tính ma trận đặc trưng (Characteristic Matrix)       3x3 3x3 3x3 1 3 3 3 5 3 6 6 4                          Δ A I 2. Tính phương trình đặc trưng (Characteristic Equation)      23 3x3 det 12 16 4 2 0                     Δ 3. Giải phương trình đặc trưng ta có 3 nghiệm λ, từ đó có véctơ giá trị riêng:   3x1 4 2 2 T   L 41 4.1. Tìm véctơ riêng của giá trị riêng λ1 = 4:     1 1 2 3x143x3 3x3 3 3 3 3 0 3 9 3 0 6 6 0 0 R R R                   A I 0 1 3x1 1 2 1 2 1             v 42 4.2. Tìm véctơ riêng và của giá trị riêng λ2 = λ3 = -2:     1 2 2 3x123x3 3x3 3 3 3 3 0 3 3 3 0 6 6 6 0 R R R                    A I 0 2 3 3x1 3x1 1 1 0 ; 1 1 0                     v v 1 2 3x3 3x1 3x1 3x1 1 1 1 2 1 0 1 2 1 1 0 n                      V v v v - ma trận (của) véctơ riêng 43 Ma trận Hessian xác định dương (Positive Definite Hessian Matrix) Ma trận Hessian sẽ là xác định dương nếu toàn bộ giá trị riêng của nó mang dấu +   3 2 2 1 0 1 2 1 det 6 10 4 0 0 1 2 2 0 0.585786438 0 3.414213562 0 Eiv                                                      A I Ma trận xác định dương 2 1 0 1 2 1 0 1 2 A            Ma trận đối xứng Chú {: Do ma trận Hessian là ma trận đối xứng nên các giá trị riêng λi của nó luôn là các số thực chứ không phải số phức. 44 Ma trận Hessian xác định dương (Positive Definite Hessian Matrix) Ma trận Hessian sẽ là xác định dương nếu toàn bộ giá trị của các phần tử cơ sở (pivot) của nó đều dương Toàn bộ các phần tử cơ sở >0 nên ma trận này xác định dương 2 2 1 3 3 2 1 2 3 2 3 2 1 0 1 2 1 0 1 2 2 1 0 0 3 2 0 1 2 2 1 0 0 3 2 0 0 4 R R R R R R R A R R                                      Ma trận đối xứng 45 Ma trận Hessian xác định dương (Positive Definite Hessian Matrix) Ma trận Hessian sẽ là xác định dương nếu toàn bộ định thức của các ma trận thành phần tính từ điểm bên trái trên cùng lớn hơn 0 11 12 13 14 21 22 23 24 31 32 33 34 41 42 43 44 a a a a a a a a A a a a a a a a a  1 11 11 12 2 21 22 11 12 13 3 21 22 23 31 32 33 11 12 13 14 21 22 23 24 4 31 32 33 34 41 42 43 44 0 0 0 0 A a a a A a a a a a A a a a a a a a a a a a a a a A a a a a a a a a         46 Ma trận Hessian xác định dương (Positive Definite Hessian Matrix) 2 1 0 1 2 1 0 1 2 A            Ma trận đối xứng 1 2 3 2 0 2 1 3 0 1 2 2 1 0 2 1 1 1 1 2 1 2 1 2 1 0 4 0 1 2 0 2 0 1 0 1 2 A A A                        Toàn bộ các định thức thành phần >0 nên ma trận này xác định dương Cách này vất vả trong tính toán 47 Tính lồi lõm (Convexity)   1 2, , , , nf x x xx xHàm nhiều biến là hàm lồi nếu với mọi cặp điểm                1 1 1 1 2 2 2 2 1 2 1 2; T T n nx x x x x x        x x và λ thuộc khoảng 0 1  thỏa mãn điều kiện sau:              2 1 2 11 1f f f         x x x x  1 x  2 x      2 11x x     1f x   2f x      2 11f x x            2 11f x f x   48 Tính lồi lõm (Convexity)   1 2, , , , nf x x xx xHàm nhiều biến là hàm lõm nếu với mọi cặp điểm                1 1 1 1 2 2 2 2 1 2 1 2; T T n nx x x x x x        x x và λ thuộc khoảng 0 1  thỏa mãn điều kiện sau:              2 1 2 11 1f f f         x x x x  1 x  2 x      2 11x x     1f x   2f x      2 11f x x            2 11f x f x   49 Tính lồi lõm (Convexity)   1 2, , , , nf x x xx xHàm nhiều biến là hàm lồi nếu ma trận Hessian của nó [H] là bán xác định dương (positive semidefinite) Bất cứ một cực tiểu địa phương (Local minimum) nào của một hàm số lồi f(x) đều là cực tiểu toàn cục (Global minimum) 50 Tính lồi lõm (Convexity) Xác định tính lồi – lõm của các hàm số sau: a)   2 2 16 0 d f x dx            H   2 2 0x d f e x dx           H Hàm số lồi chặt chẽ b) Hàm số lõm chặt chẽ c)   2 2 2 1 1 2 1 2 2 2 2 1 2 18 0 0 12 f f x x x x f f x x x                          H Theo định nghĩa 2 của ma trận xác định dương, do -12<0, nên ma trận này không thể dương. Nếu x1 < 0 thì ma trận này xác định âm  Hàm lõm 51 Tính lồi lõm (Convexity) d)   2 1 2 3 2 3 3 1 3 2 2 2 2 1 1 2 1 3 2 2 2 2 2 1 2 2 3 2 2 2 2 3 1 3 2 3 3 1 4 2 1 8 8 6 1 6 6 0 1 0 10 8 6 18 6 1 3 3 3 0 0 2 4 3 79 0 4 8 R R R R R R R R R f f f x x x x x f f f x x x x x f f f x x x x x                                                                      H 3 2 4 19 0 0 2                     Đưa về dạng bậc thang bằng phép khử Gauss để xét dấu các pivot Các phần tử cơ sở đều dương do đó ma trận Hessian xác định dương Hàm f lồi trên toàn miền số thực của x1, x2, x3 52 Ôn tập về đạo hàm