Bài giảng Tối ưu hóa nâng cao - Bài 1: Giới thiệu về tối ưu hóa - Hoàng Nam Dũng

Giới thiệu về tối ưu hóa
Hoà ng Nam Dũng
Khoa Toán - Cơ - Tin học, Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội
Copyright 1997 Randy Glasbergon. www.glasborgon.com
“Algebra class will be important to you later in life because there’s going to be a test six weeks from now.”
Bill Gates nói về toán học
America's young people must come to see science and math degrees as key to opportunity. If we fail at this, we won't be able to compete in the global economy.
— Bill Gates, 2007
Speaking to LinkedIn Executive Editor Daniel Roth, Mr Gates said: “I do think of basic knowledge of the sciences, math skills, economics — a lot of careers in the future will be very demanding on those things.”
— Bill Gates, 2016
Toán học - kính hiển vi của vạn vạt
Mathematics Is Biology's Next Microscope, Only Better; Biology Is
Mathematics' Next Physics, Only Betterhttps://doi.org/10.1371/journal.pbio.0020439
— Joel E. Cohen, 2004
Mô hình hóa
Mô hình hóa toán học là gì?
Modeling is a process that uses math to represent, analyze, make predictions, or otherwise provide insight into real-world phenomena.SIAM: What is math modeling?
Thales of Miletus (624 BC - 546 BC)
1/2 LEntqrh of basE
ksiqhT of srick shadow of srick
IdEiqldT of pyramid
1/2 of basE + shadow of pyramid
Đường đi ngắn nhất
Đường đi ngắn nhất
Dồ thị có hưóng D gồm có
Tập hợp V các đỉnh.
Tập hợp các cạnh có hưóng A, la tập chứa các cặp có thứ tự của các đỉnh thuộc V.
Mỗi cạnh có một trọng số không âm. Ham trọng so c : A ! R+.
Dự báo thời tiết  NWP_LecturesFall2013.pdf
Dự báo thời tiết
Sử dụng các phương trình toán học để mô tả trạng thái vật lí của khí quyển và dự đoán về sự biến đổi của nó.
Equations of motion (ECWMF model)
+ w* l’cos0f}+	East-west wind
+Vcos0»+ “8(C,;+y2)}+^	North-south wind
*+ dak®4 v“‘el}4 ’’sd ?	Temperature
I = dak®+V“s9R = d = P^K’	Humidity
Kb)+vdb> +5^b) = 0	Continuity of mass
= _Jv.(vH^dn	Surface pressure
Siêu máy tính sẽ được sử dụng đế giải các phương trình này.
Tối ưu hóa trong tự nhiên
Bà i toán tối ưu
minimize
x
subject to
Bà i toán tối ưu
minimize	f (x)
x
subject to x 2 X.
Biến x = (xi,x2,..., xn) là gì?
Hàm mục tiêu f là gì?
Diều kiện x 2 X (tập hợp nghiệm chấp nhận được X) là gì?
Bà i toán tối ưu
minimize	f (x)
x
subject to x 2 X.
Biến x = (xi,x2,..., xn) là gì?
I Hàm mục tiêu f là gì?
Diều kiện x 2 X (tập hợp nghiệm chấp nhận được X) là gì?
x, f, X của các bài toán thực tế đến từ quá trình mô hình hóa (modeling).
Tự nhiên "luôn" tối ưu
Whether by design or accident, nature optimizes. The motions of stars, planets, and rays of light through the universe are governed by an optimization principle: the principle of least action. The shapes and functions of proteins -the building blocks of living organisms - are determined by a minimum-energy configuration of the molecule. Balls come to rest in valleys rather than on hillsides, because they seek a state of optimal potential energy. a
awid.wisc.edu/the-natural-order-and-divine-law-of-optimization/
— M. Ferris and S. Wright, 2015
Ánh sáng - kẻ tiết kiệm thời gian
Hiện tượng phản xạ: Theo nguyên lý thời gian tối thiểu của Fermat ta có
Ớ1 = Ớ2-
Ong - kiến trúc sư đại tài
3https://en.wikipedia.org/wiki/Honeycomb_structure
Ong - kiến trúc sư đại tài
Cấu trúc to ong cho phép sử dụng ít nguyên liệu nhất, nhẹ nhất, đồng thòi có tỉ lệ sức ben vật liệu/trọng lượng cao.https://en.wikipedia.org/wiki/Honeycomb_structure
Tại sao bong bóng xà phòng có hình cầu?
Tại sao bong bóng xà phòng có hình cầu?
Lực căng sẽ khiến bong bóng chuyển dần sang hình dạng có chu vi nhỏ nhất (để còng chứa một lượng không khí bị giữ bên trong) và đó chính là hình cầu.
Quả bóng cũng biết tối ưu
Một và i ứng dụng của toán học
ứng dụng của toán học4
4https://mathigon.org/applications
ứng dụng của toán học4
4https://mathigon.org/applications
Automatic guided vehicle (AGV) https://www.youtube.com/watch?v=zm_rlLyelQo
Amazon robot https://www.youtube.com/watch?v=3eQAFVetNGI
Môn học toi ưu hóa nâng cao
Môn học tối hóa nâng cao
Trang chủ: 
I Thông tin môn học
I Slides bài giảng
I Bài tập
Diểm thành phần
I Bài tập về nhà, bài tập lập trình: 20%.
I Giữa kì 20%
I Cuối kì 60%
Tà i liệu tham khảo
Download sách: 
Sách tham khảo
I J. Nocedal and S. Wright, Numerical Optimization, Springer.
I S. Boyd and L. Vandenberghe, Convex Optimization,
Cambridge University Press, 
I R. Tyrrell Rockafellar, Convex Analysis, Princeton University Press
Slide bà i giảng
I Optimization Methods for Large-Scale Systems, UCLA: 
I Convex Optimization, CMU:
	19