ĐỀ CƯƠNG CHI TIẾT HỌC PHẦN

1. Thông tin chung

- Tên học phần: THUẬT TOÁN TỐI ƯU

- Tên tiếng Anh: OPTIMIZATION ALGORITHMS

- Mã học phần: TTH703

- Ngày soạn: 15/11/2014 Phiên bản: 2

- Thuộc khối kiến thức: Cơ sở ngành

- Bộ môn – Khoa phụ trách: Tối ưu và Hệ thống

- Giảng viên phụ trách:

o TS. Võ Sĩ Trọng Long

o TS. Nguyễn Minh Tùng

- Giảng viên tham gia giảng dạy:

o TS. Võ Sĩ Trọng Long

o TS. Nguyễn Minh Tùng

o ThS. Cao Nghi Thục

- Số tín chỉ: 4

o Số tiết lý thuyết: 4

- Học phần:

o Bắt buộc: cho ngànhTối ưu và Hệ thống

o Tự chọn: cho các ngành khác

- Điều kiện đăng ký học phần:

2. Mục tiêu của học phần

Trang bị cho SV những kiến thức và phương pháp giải các bài toán tối ưu có ràng buộc và không ràng buộc.

3. Tóm tắt nội dung học phần

Tiếng Việt: Khóa học cung cấp cho sinh viên các kiến thức về:

- Các thuật toán linesearch.

- Thuật toán gradient.

- Phương pháp Newton, tựa Newton.

- Bài toán bình phương bé nhất.

- Định lý Karush-Kuhn-Tucker

- Phương pháp hàm chắn

- Phương pháp điểm trong giải quy hoạch tuyến tính

Tiếng Anh: This course provides:

- Basic concepts and properties of algorithms, linesearch methods for unconstrained optimization

- The steepert descent method, the gradient method and conjugate gradient method

- The Newton and quasi-Newton methods

- Least- square problems. Kuhn-Tucker optimality conditions

- Linear-constrained problems, sequential quasratic programming

- Primal-dual interior-point methods for LP

4. Nội dung chi tiếthọcphần

Chương 1.Tính chất cơ bản của các thuật toán

1.1 Các khái niệm cơ bản, các hướng giảm

1.2 Xoát trực tiếp và gián tiếp

1.3 Sự hội tụ và tốc độ hội tụ của phương pháp giảm

Chương 2. Phương pháp Newton

2.1 Bước Newton

2.2 Phương pháp Newton thuần túy

2.3 Phương pháp Newton giảm. Độ phức tạp

2.4 Cách tính hướng Newton

Chương 3. Phương pháp tựa Newton

3.1 Hạn chế của phương pháp Newton và thành lập công thức

3.2 Thuật toán BFGS

3.3 Phương pháp gradient liên hợp

3.4 Phương pháp gradient liên hợp tuyến tính và phương pháp tựa Newton tuyến tính

Chương 4.Điều kiện tối ưu tổng quát và bài toán bình phương nhỏ nhất

4.1 Định lý Kuhn-Tucker

4.2 Bài toán tuyến tính bình phương nhỏ nhất

4.3 Phương pháp Gauss-Newton

Chương 5.Phương pháp cực tiểu không ràng buộc

5.1 Hàm chắn Logarith

5.2 Đường trung tâm

5.3 Ước lượng nhân tử Lagrange

5.4 Điều kiện của ma trận Hessian

5.5 Phương pháp phạt toàn phương

Chương 6.Bài toán ràng buộc tuyến tính

6.1 Không gian không của bài toán ràng buộc đẳng thức

6.2 Phương pháp Newton rút gọn

6.3 Phương pháp giảm nhanh nhất

6.4 Cách tính nhân tử Lagrange

Chương 7.Phương pháp điểm trong gốc – đối ngẫu cho L^P

7.1 Phương pháp theo đường trung tâm

7.2 Giải hệ tuyến tính

7.3 Sự hội tụ của các bước lặp

7.4 Cách chọn điểm xuất phát

7.5 So sánh giữa phương pháp điểm trong và phương pháp đơnhình

Chương 8. Qui hoạch bình phương

8.1 Phương pháp Newton

8.2 Phương pháp tựa Newton

8.3 Ràng buộc đẳng thức và bất đẳng thức

5. Phương pháp dạy và học

Phương pháp truyền thống: giáng viên truyền đạt kiến thức cho sinh viên, cùng trao đổi về các nội dung bài học.

Kết hợp phương pháp điện tử: giáo án bằng slide, các bài tập qua email…

6. Phương pháp, hình thức kiểm tra, đánh giá kết quả học tập

Giữa kỳ: 30% Cuối kỳ: 70%

7. Giáo Trình:

J. J. Strodiot, Numerical Methods in Optimization, Lecturer-Notes Series, University of Namur, 2006.

8. Tài liệu tham khảo

1 D. P. Bertseleas, Nonlinear Programming, Athena Scientific, Belmont, Massachusetts, 1995.

2 E. Polak, Optimization, Algorithms and Consistent Approximations, Springer, New York, 1997.

3. B. Rustem, Algorithms for Nonlinear Programming and Multipleobjective Decisions, John Wiley and Sons, New York, 1998.