Bài giảng Tối ưu hóa nâng cao - Bài 2: Các kiến thức cơ sở - Hoàng Nam Dũng

Các kiến thức cơ sở
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
Tập lồi
Định nghĩa
Tập hợp S C Rn /à một tập lồi nếu
Àx + (1 — À)y 2 S; VÀ 2 [0; 1]; x; y 2 S.
Nói một cách khác đoạn thẳng nối hai điểm hoàn toàn nằm trong tập hợp nếu hai đầu mút công thuộc tập hợp.
Tập lồi
Định nghĩa
Tập hợp S C Rn /à một tập lồi nếu
Àx + (1 — À)y 2 S; VÀ 2 [0; 1]; x; y 2 S.
Nói một cách khác đoạn thẳng nối hai điểm hoàn toàn nằm trong tập hợp nếu hai đầu mút công thuộc tập hợp.
Tập không lồi
Ví dụ tạp lồi
I Tập rỗng, điểm, đường thắng, toàn bộ không gian Rn.
I Hình cầu {x 2 Rn I ||xII < r} với chuẩn II ■ II và bán kín r cho trước.
I Siêu phắng (hyperplane) {x 2 Rn I aTx = b} với a 2 Rn, b 2 R cho trước.
I Nửa không gian (halfspace) {x 2 Rn I aTx < b} với a 2 Rn, b 2 R cho trước.
I {x 2 Rn I Ax = b} với A 2 Rmxn, b 2 Rm cho trước.
I Da diện {x 2 Rn I Ax < b} với A 2 Rmxn, b 2 Rm cho trước.
I ...
Tổ hợp lồi và bao lồi
Định nghĩa
Một tổ hợp lồi của X1; x2;...; xk 2 Rn là một tô hợp tuyến tính
A1X1 + A2 X2 + • • • + AkXk
với các hệ số A1; A2;... ;Ak > 0 thỏa mãn
A1 + A2 + • • • + Ak = 1.
Tổ hợp lồi và bao lồi
Định nghĩa
Một tổ hợp lồi của X1; x2;...; xk 2 Rn là một tô hợp tuyến tính
A1X1 + A2 X2 + • • • + AkXk
với các hệ số A1; A2;... ;Ak > 0 thỏa mãn
A1 + A2 + • • • + Ak = 1.
Định nghĩa
Bao lồi của một tập hợp S, conv(S), là tập hợp của tất cả các tô hợp lểi của các phan tử thuộc S.
Tổ hợp lồi và bao lồi
Định nghĩa
Một tổ hợp lồi của X1; x2;...; xk 2 Rn là một tô hợp tuyến tính
A1X1 + A2 X2 + • • • + AkXk
với các hệ số A1; A2;... ;Ak > 0 thỏa mãn
A1 + A2 + • • • + Ak = 1.
Định nghĩa
Bao lồi của một tập hợp S, conv(S), là tập hợp của tất cả các tô hợp lểi của các phan tử thuộc S.
conv(S) là một tập lồi và là tập lồi bé nhất chứa S.
Tổ hợp lồi và bao lồi
Định nghĩa
Một tổ hợp lồi của X1; x2;...; xk 2 Rn là một tô hợp tuyến tính
A1X1 + A2 X2 + • • • + AkXk
với các hệ số A1; A2;... ;Ak > 0 thỏa mãn
A1 + A2 + • • • + Ak = 1.
Định nghĩa
Bao lồi của một tập hợp S, conv(S), là tập hợp của tất cả các tô hợp lểi của các phan tử thuộc S.
conv(S) là một tập lồi và là tập lồi bé nhất chứa S.
Hàm lồi
Đinh nghĩa
Một hàm so f : S ! R, S C Rn, được gọi là một hàm lồi nếu
I Miền định nghĩa S là một tập loi.
I Hàm f thỏa mãn
f(Ax + (1 — A)y) < Af(x) + (1 — A)f(y), VA 2 [0,1],x,y 2 S.
Hàm lồi
Đinh nghĩa
Một hàm so f : S ! R, S C Rn, được gọi là một hàm lồi nếu
I Miền định nghĩa S là một tập loi.
I Hàm f thỏa mãn
f(Ax + (1 — A)y) < Af(x) + (1 — A)f(y), VA 2 [0,1],x,y 2 S.
Hàm lõm
Định nghĩa
Một hàm so f : S ! R, S C Rn, được gọi là một hà m lõm nếu
I Miền định nghĩa S là một tập loi.
I Hàm f thỏa mãn
f(Ax + (1 — A)y) > Af(x) + (1 — A)f(y); VA 2 [0; 1];x;y 2 S.
f là hà m lõm o —f là một hà m lồi.
Hàm lồi ngặt và hàm lồi mạnh
Định nghĩa
Một hàm lồi f : S ! R được gọi là
I lồi ngặt nếu ta có với mọi X 2 (0; 1); x; y 2 S; x = y f(Xx + (1 - X)y) < Xf(x) + (1 - X)f(y).
Tức là độ cong của nó lớn hơn độ cong của 1 hàm tuyến tính.
Hàm lồi ngặt và hàm lồi mạnh
Định nghĩa
Một hàm lồi f : S ! R được gọi là
I lồi ngặt nếu ta có với mọi X 2 (0; 1); x; y 2 S; x = y
f(Xx + (1 - X)y) < Xf(x) + (1 - X)f(y).
Tức là độ cong của nó lớn hơn độ cong của 1 hàm tuyến tính.
I lồi mạnh nếu tồn tại m > 0 sao cho f — m||x112 là một hàm lồi hay tương đương với
tồn tại m > 0 sao cho ta có với mọi X 2 [0; 1]; x; y 2 S
f(Xx + (1 - X)y) < Xf(x) + (1 - X)f(y) -1 mX(1 - X)|x-y 112.
Hàm lồi ngặt và hàm lồi mạnh
Định nghĩa
Một hàm lồi f : S ! R được gọi là
I lồi ngặt nếu ta có với mọi X 2 (0; 1); x; y 2 S; x = y
f(Xx + (1 - X)y) < Xf(x) + (1 - X)f(y).
Tức là độ cong của nó lớn hơn độ cong của 1 hàm tuyến tính.
I lồi mạnh nếu tồn tại m > 0 sao cho f — m||x112 là một hàm lồi hay tương đương với
tồn tại m > 0 sao cho ta có với mọi X 2 [0; 1]; x; y 2 S
f(Xx + (1 - X)y) < Xf(x) + (1 - X)f(y) -1 mX(1 - X)|x-y 112.
Mối quan hệ:
Lồi mạnh =) lồi ngặt =) lồi.
Ví dụ hà m lồi
I Hàm đơn biến
eax trên R với a 2 R
xa trên R>0 với a 2 (0; 1)
—xa trên R>0 với a 2 [0; 1]
— logx trên R>0
I Hàm affine: aTx + b đồng thời vừa là hàm lồi, vừa là hàm lõm
I Hàm bậc 2: 2xTAx + bTx + c với A nửa xác định dương
(A	0)
I Least square lost: ky — AxII2
I Chuẩn I|xII bất kì, ví dụ chuẩn Lp
I Hàm max: f(x) = max{xi;x2;...;xng
I ...
Đặc trưng của hàm lồi
I Epigraph:
epi(f) = {(x; t) 2 dom(f) X RI f (x) < t}
Đặc trưng của hàm lồi
I Epigraph:
epi(f) = {(x; t) 2 dom(f) X RI f (x) < t}
Đặc trưng của hàm lồi
I Epigraph:
epi(f) = {(x; t) 2 dom(f) X RI f (x) < t}
f là hàm lồi o epi(f) là một tập lồi.
Đặc trưng của hàm lồi
I Epigraph:
epi(f) = {(x; t) 2 dom(f) X RI f (x) < t}
f là hàm lồi o epi(f) là một tập lồi.
I Tập mức dưới: Nếu f lồi thì tập mức dưới
{x 2 dom(f) I f(x) < a}
là lồi với mọi a 2 R. Tuy nhiên điều ngược lại không đúng.
Đặc trưng của hàm lồi
Định lý (Đặc trưng bậc nhất)
Neu f khả vi thì f là hàm loi khi và chỉ khi dom(f) là một tập loi và
f(y) > f(x) + Vf(x)T(y — x); 8x;y 2 dom(f).
Đặc trưng của hàm lồi
Định lý (Đặc trưng bậc nhất)
Neu f khả vi thì f là hàm loi khi và chỉ khi dom(f) là một tập loi và
f(y) > f(x) + Vf(x)T(y — x); 8x;y 2 dom(f).
Định lý (Đặc trưng bậc hai)
Neu f khả vi hai lần thì hàm loi khi và chỉ khi dom(f) là một tập loi và
V2f(x) >2 0; 8x 2 dom(f).
Đặc trưng của hàm lồi
Định lý (Đặc trưng bậc nhất)
Neu f khả vi thì f là hàm loi khi và chỉ khi dom(f) là một tập loi và
f(y) > f(x) + Vf(x)T(y — x); 8x;y 2 dom(f).
Định lý (Đặc trưng bậc hai)
Neu f khả vi hai lần thì hàm loi khi và chỉ khi dom(f) là một tập loi và
V2f(x) >2 0; 8x 2 dom(f).
Định lý (Bất đẳng thức Jenssen)
Neu f là một hàm loi và X là một biến ngẫu nhiên trên dom(f) thì
f(E[X]) < E[f(X)].
Operations preserving convexity
Nonnegative linear combination:	convex implies
af + ... + amfm convex for any a1,... am > 0
Pointwise maximization: if fs is convex for any s e S, then f (x) = maxseS fs(x) is convex. Note that the set S here
(number of functions fs) can be infinite
Partial minimization: if g(x,y) is convex in x,y, and C is convex, then f (x) = mill,, C g(x, y) is convex
Example: distances to a set
Let C be an arbitrary set, and consider the maximum distance to C under an arbitrary norm II • II:
f (x) = max ||x - y\\
y&C
Let's check convexity: fy(x) = ||x — y\\ is convex in x for any fixed y, so by pointwise maximization rule, f is convex
Now let C be convex, and consider the minimum distance to C:
f(x) = min Hx — y||
yeC
Let's check convexity: g(x,y) = ||x — y\\ is convex in x,y jointly, and C is assumed convex, so apply partial minimization rule
More operations preserving convexity
Affine composition: if f is convex, then g(x) = f (Ax + b) is convex
General composition: suppose f = h o g, where g : Rn	R,
h : R	R, f : Rn R. Then:
f is convex if h is convex and nondecreasing, g is convex
f is convex if h is convex and nonincreasing, g is concave
f is concave if h is concave and nondecreasing, g concave
f is concave if h is concave and nonincreasing, g convex
How to remember these? Think of the chain rule when n = 1:
f"(x) = h"(g(x))g'(x)2 + h'(g(x))g"(x)
• Vector composition: suppose that
f (x) = h{g(x) = h(gi(x),. ..gk(x))
where g : Rn Rk, h : Rk	R, f : Rn	R. Then:
f is convex if h is convex and nondecreasing in each argument, g is convex
f is convex if h is convex and nonincreasing in each argument, g is concave
f is concave if h is concave and nondecreasing in each argument, g is concave
f is concave if h is concave and nonincreasing in each argument, g is convex
Example: log-sum-exp function
Log-sum-exp function: g(x) = log(£k=1 eaTx+bi), for fixed ữi,bị, Ỉ = 1,... k. Often called “soft max”, as it smoothly approximates maxi=i;...fc (aTx + bi)
How to show convexity? First, note it suffices to prove convexity of f (x) = logQ2Z=i exi) (affine composition rule)
Now use second-order characterization. Calculate
Vif(x)
= E”=1
vjf(x) = £11 e3*1{i = j} — (£11 e3*)2
Write v2f(x) = diag(z) — zzT, where zi = eXi/(£11 exe). This matrix is diagonally dominant, hence positive semidefinite
Bà i toán tối ưu
Một bài toán tối ưu hóa gồm có
x vectơ của các biến
I hàm mục tiêu f là một hàm (vô hướng) mà chúng ta muốn cực đại hóa hay cực tiếu hóa
Các hàm điều kiện gi, hi là các hàm (vô hướng) của x định nghĩa các đắng thức hay bất đắng thức mà x phải thỏa mãn.
Bà i toán tối ưu
Một bài toán tối ưu hóa gồm có
x vectơ của các biến
I hàm mục tiêu f là một hàm (vô hướng) mà chúng ta muốn cực đại hóa hay cực tiếu hóa
Các hàm điều kiện gi, hi là các hàm (vô hướng) của x định nghĩa các đắng thức hay bất đắng thức mà x phải thỏa mãn.
Bài toán tối ưu có thể viết dưới dạng
min f (x)
s.t. gi (x) < 0;	i = 1; 2; . . . ; k
hj (x) = 0; j = 1; 2;... ; l .
max min:
max f(x)	min	— f(x)
s.t. gi (x)	<	0;	i = 1; . . . ; k	o s.t. gi (x)	<	0;	i = 1; . . . ; k
hj (x)	=	0;	j = 1; . . . ; l .	hj (x)	=	0;	j = 1; . . . ; l .
max min:
max f(x)	min	— f(x)
s.t. gi (x)	<	0;	i = 1; . . . ; k	o s.t. gi (x)	<	0;	i = 1; . . . ; k
hj (x)	=	0;	j = 1; . . . ; l .	hj (x)	=	0;	j = 1; . . . ; l .
Vế phải khác 0:
max f(x)	min — f(x)
s.t. gi (x)	<	bị ;	i =	1;	.	. . ; k	o s.t. gi (x)	< 0;	i = 1;...; k
hj (x)	=	Cj ;	j =	1;	.	. . ; l .	hj (x)	= 0;	j = 1; . . . ; l .
với gi = gi - bi, hị = hj - Cj.
max min:
max
f (x )
min
-f (x )
s.t.
gi (x ) < 0;
i = 1;
• ••; k (
) s.t.
gi (x) < 0;
i = 1,, •
•;k
hj (x) = 0;
j = 1;
• •• ; l •
hj(x) =0;
j = 1; • •
..; l •
Vế phải khác 0:
max
f (x)
min
-f (x )
s.t.
gi (x ) < bi ;
i = 1;
k (
s.t.
ghi (x) < 0;
i = 1; •
••;k
hj (x ) = Cj ;
j = 1
,•••; l •
hhj (x) = 0;
j = 1; •
• • ; l •
với gi
= gi - bi, hj
= hj -
cj .
min
f(x)
min
f (x )
s.t.
gi (x ) > 0;
i = 1; •
• •; k (=
s.t.
-gi (x ) < 0;
i = 1; •
••;k
hj (x ) = 0;
j = 1; •
• • ; l •
hj (x) = 0;
j = 1; •
•• ; l^	11
min	f (x)	min	f (x)
s.t.	gị (x)	< 0; i = 1; . . . ; k s.t.	gi (x)	< 0; i = 1;	. . . ; k
hj (x) = 0; j = 1; . . . ; l .	hj (x) < 0; j = 1; . . . ; l
-hj (x ) < 0; j = 1;...; l .
min	f (x)
s.t. gì(x) < 0;	i = 1;...; k
hj (x ) = 0; j = 1; . . . ; l .
min f(x)
s.t. gi(x)	<	0;	i =	1;...; k
hj (x)	<	0;	j =	1;	.	. . ; l
-hj (x ) < 0; j = 1;...; l .
< —! =: Thêm biến bù
min	f (x )
s.t. gì(x) < 0;	i = 1;...; k
hj (x ) = 0; j = 1; . . . ; l .
min f (x )
s.t. gì (x) + Sì = 0;	i = 1; . . . ; k
hj (x )= 0;	j = 1;...; l
Sì > 0;	i = 1; . . . ; k .
min f(x)
s.t. gỉ (x) < 0; i = 1; 2; . . . ; k
hj (x) = 0; j = 1; 2;... ; l
I gi(x) < 0 gọi là ràng buộc bất đẳng thức, hj(x) = 0 gọi là ràng buộc đẳng thức.
min f(x)
s.t. gỉ (x) < 0; i = 1; 2; . . . ; k
hj (x) = 0; j = 1; 2;... ; l
I gi(x) < 0 gọi là ràng buộc bất đẳng thức, hj(x) = 0 gọi là ràng buộc đẳng thức.
I x thỏa mãn các điều kiện được gọi là một nghiệm chấp nhận được (feasible solution).
min f(x)
s.t. gỉ (x) < 0; i = 1; 2; . . . ; k
hj (x) = 0; j = 1; 2;... ; l
I gi(x) < 0 gọi là ràng buộc bất đẳng thức, hj(x) = 0 gọi là ràng buộc đẳng thức.
I x thỏa mãn các điều kiện được gọi là một nghiệm chấp nhận được (feasible solution).
I Tập hợp các nghiệm CND được gọi là mien CND (feasible region).
min f(x)
s.t. gỉ (x) < 0; i = 1; 2; . . . ; k
hj (x) = 0; j = 1; 2;... ; l
I gi(x) < 0 gọi là ràng buộc bất đẳng thức, hj(x) = 0 gọi là ràng buộc đẳng thức.
I x thỏa mãn các điều kiện được gọi là một nghiệm chấp nhận được (feasible solution).
I Tập hợp các nghiệm CND được gọi là mien CND (feasible region).
I Neu miền CND bằng rỗng ta nói bài toán không có nghiệm CND (infeasible), ngược lại là có nghiệm chấp nhận được (feasible).
min f (x)
s.t. gỉ (x) < 0;	i = 1; 2; . . . ; k
hj (x) = 0; j = 1; 2;... ; l .
I Với một nghiệm CND x, nếu
gi(x) = 0 ta nói gi active tại x.
min f (x)
s.t. gỉ (x) < 0;	i = 1; 2; . . . ; k
hj (x) = 0; j = 1; 2;... ; l .
I Với một nghiệm CND x, nếu gi(x) = 0 ta nói gi active tại x.
I Giá trị nhỏ nhất của f(x) trên miền CND gọi là giá trị tối ưu (optimal value), kí hiệu f*.
min f (x)
s.t. gỉ (x) < 0;	i = 1; 2; . . . ; k
hj (x) = 0; j = 1; 2;... ; l .
I Với một nghiệm CND x, nếu gi(x) = 0 ta nói gi active tại x.
I Giá trị nhỏ nhất của f(x) trên miền CND gọi là giá trị tối ưu (optimal value), kí hiệu f*.
I Nếu x là một nghiệm CND và f(x) = f* thì ta gọi x là một nghiệm tối ưu (optimal solution).
min f (x)
s.t. gỉ (x) < 0;	i = 1; 2; . . . ; k
hj (x) = 0; j = 1; 2;... ; l .
I Với một nghiệm CND x, nếu gi(x) = 0 ta nói gi active tại x.
I Giá trị nhỏ nhất của f(x) trên miền CND gọi là giá trị tối ưu (optimal value), kí hiệu f*.
I Nếu x là một nghiệm CND và f(x) = f* thì ta gọi x là một nghiệm tối ưu (optimal solution).
I Nếu x là một nghiệm CND và f(x) < f * + " thì ta gọi x là e-suboptimal.
Example: lasso
Given y G Rn, X G RnXp, consider the lasso problem:
min \\y - XII2 subject to IIBII1 < s
Is this convex? What is the criterion function? The inequality and
equality constraints? Feasible set? Is the solution unique, when:
n > p and X has full column rank?
p > n (“high-dimensional” case)?
How do our answers change if we changed criterion to Huber loss:
y p(y - xTBY p(z)= / 2z2 , „ |z| < ỏ ?
y iP	pu	Ụ|z|- 1Ỗ2 else ■
Example: support vector machines
Given y e {-1,1}n, X e RnXp with rows xi,... xn, consider the support vector machine or SVM problem:
1	n
min	2||p||2 + ơ^£i
P,P0,£	2	“1
subject to pi > 0, i = 1,...n
yi(xT p + Pop > 1 - pi, i = 1,...n
Is this convex? What is the criterion, constraints, feasible set? Is the solution (p,po, p) unique? What if changed the criterion to
2IIPII2 + 2 Po2 + cẺ£'01?
2	2	i=i
For original criterion, what about p component, at the solution?
I Khi không có điều kiện ràng buộc thì ta có bài toán tối ưu hóa không ràng buộc.
I Ngược lại ta có bài toán tối ưu hóa có ràng buộc.
I Khi không có điều kiện ràng buộc thì ta có bài toán tối ưu hóa không ràng buộc.
I Ngược lại ta có bài toán tối ưu hóa có ràng buộc.
Tiếp theo ta xét các loại bài toán tối ưu hóa
I tuyến tính
I lồi
I rời rạc.
Bà i toán tối ưu tuyến tính
Dạng chính tắc
min c Tx
s.t. Ax = b
x > 0.
Dạng chuẩn tắc
min
s.t.
c T x
Ax > b
Dạng tổng quát
min
s.t.
x > 0.
c Tx + d Ty Ax + By = a Cx + Dy > b x > 0.
Bài toán tối ưu
min f (x)
s.t. gỉ (x) < 0; i = 1; 2; . . . k
được gọi là là bài toán toi ưu loi nếu f và gi là các hàm lồi.
Bài toán tối ưu
min f (x)
s.t. gỉ (x) < 0; i = 1; 2; . . . k
được gọi là là bài toán toi ưu loi nếu f và gi là các hàm lồi.
Khi đó mỗi điều kiện ứng với một tập mức dưới lồi nên miền chấp nhận được là giao của chúng cũng là một tập lồi.
Bài toán tối ưu
min f (x)
s.t. gỉ (x) < 0; i = 1; 2; . . . k
được gọi là là bài toán toi ưu loi nếu f và gi là các hàm lồi.
Khi đó mỗi điều kiện ứng với một tập mức dưới lồi nên miền chấp nhận được là giao của chúng cũng là một tập lồi.
Bài toán tối ưu
min f(x)
s.t. gi(x) < 0; i = 1;...; k
hj(x) = 0; j = 1;---; 1.
là lồi nếu
Bài toán tối ưu
min f (x)
s.t. gỉ (x) < 0; i = 1; 2; . . . k
được gọi là là bài toán toi ưu loi nếu f và gi là các hàm lồi.
Khi đó mỗi điều kiện ứng với một tập mức dưới lồi nên miền chấp nhận được là giao của chúng cũng là một tập lồi.
Bài toán tối ưu
min f(x)
s.t. gi(x) < 0; i = 1;...; k
hj(x) = 0; j = 1;...; f và gi là các hàm lồi
I hj vừa là hàm lồi vừa là hàm lõm.
.
là lồi nếu
min f(x)
s.t. gi(x) < 0;	i = 1;...; k
hj(x) < 0;	j = 1;...; 1
-hj(x) < 0; j = 1;...; 1
Bài toán tối ưu lồi
Bổ đề
f : Rn —> R là hàm vừa loi vừa lõm khi và chỉ khi f là hàm affine.
Bài toán tối ưu lồi
Bổ đề
f : Rn —> R là hàm vừa loi vừa lõm khi và chỉ khi f là hàm affine.
Chứng minh.
f vừa là hàm lồi vừa là hàm lõm thì ta có
f(Ax + (1 — A)y) = Af(x) + (1 — A)f(y); VA 2 [0; 1];x; y 2 Rn.
Bài toán tối ưu lồi
Bổ đề
f : Rn ! R là hàm vừa loi vừa lõm khi và chỉ khi f là hàm affine.
Chứng minh.
f vừa là hàm lồi vừa là hàm lõm thì ta có
f(Ax + (1 — A)y) = Af(x) + (1 — A)f(y); VA 2 [0; 1];x; y 2 Rn.
Suy ra với mọi A 2 [0; 1] ta có
f (Ax) = f (Ax + (1 — A)0) = Af (x) + (1 — A)f (0);
Bài toán tối ưu lồi
Bổ đề
f : Rn —> R là hàm vừa loi vừa lõm khi và chỉ khi f là hàm affine.
Chứng minh.
f vừa là hàm lồi vừa là hàm lõm thì ta có
f(Ax + (1 — A)y) = Af(x) + (1 — A)f(y); VA 2 [0; 1];x; y 2 Rn. Suy ra với mọi A 2 [0; 1] ta có
f (Ax) = f (Ax + (1 — A)0) = Af (x) + (1 — A)f (0);
hay
g (Ax) = Ag (x)
với g(x) := f(x) - f(0).
Bổ đề
f : Rn ! R là hàm vừa loi vừa lõm khi và chỉ khi f là hàm affine.
Chứng minh.
f vừa là hàm lồi vừa là hàm lõm thì ta có
f(Ax + (1 — A)y) = Af(x) + (1 — A)f(y); VA 2 [0; 1];x; y 2 Rn.
Suy ra với mọi A 2 [0; 1] ta có
f (Ax) = f (Ax + (1 — A)0) = Af (x) + (1 — A)f (0);
hay
g (Ax) = Ag (x)
với g(x) := f(x) — f(0). Từ đó ta cũng suy ra với mọi A > 1 ta có
g(x) = g ( A(Axộ = A g(Ax) hay
18
Ag (x) = g (Ax).
Chứng minh.
Ta có
g(x + y) =	2x + 1 y) = 2f Qx + 2y) - 2f(0)
□
Chứng minh.
Ta có
g(x + y) =	2x + 1 y) = 2f Qx + 2y) - 2f(0)
= 2(1 f(x) +1 f(y)) - 2f(0)
□
Chứng minh.
Ta có
g(x + y) =	2x + 1 y) = 2f Qx + 2y) - 2f(0)
= 2(1 f(x) +1 f(y)} - 2f(0)
= f (x) +f (y) - 2f (0) = g(x) + g (y)-
□
Chứng minh.
Ta có
g(x + y) = 2g(^2x + 1 y) = 2f Qx + 2y) - 2f(0)
= 2(1 f(x) +1 f(y)} - 2f(0)
= f (x) +f (y) - 2f (0) = g(x) + g (y)-
Suy ra g là hàm tuyến tính và do đó f là hàm affine.	□
Chứng minh.
Ta có
g(x + y) = Như vậy bài toán tối ưu lồi sẽ có dạng min f(x)
s.t. gi(x) < 0; i = 1;...; k
Ax = b
với f và gi, i = 1; 2;... k, là các hàm lồi.
g(^2x + 1 y) = 2f Qx + 2y) - 2f(0)
= 2(1 f(x) +1 f(y)} - 2f(0)
= f (x) +f (y) - 2f (0) = g(x) + g (y).
19
Suy ra g là hàm tuyến tính và do đó f là hàm affine.	□
Tối ưu liên tục vs. tối ưu rời rạc
Dôi khi chúng ta đòi hỏi biến phải là số nguyên hay nhị phân. Ví dụ như khi biến của chúng ta là số ôtô cần để vận chuyển, số nhân lực, hay biến quyết định có làm một việc gì đó không.
Khi đó ta sẽ có bài toán tối ưu hóa nguyên hoặc tối ưu hóa nhị phân.
Trong nội dung môn học này chúng ta sẽ không xét đến dạng bài toán trên.
Xét bài toán tối ưu
min f (x)
s.t. gỉ (x) < 0; i = 1; 2; . . . ; k hj (x) = 0; j = 1; 2;... ; l .
Kí hiệu X là miền CND.
Xét bài toán tối ưu
min
f (x)
s.t.
gi (x) < 0; i = 1; 2; k hj (x)= 0; j = 1; 2;...; l .
Kí hiệu X là miền CND.
x 2 X được gọi là nghiệm tối ưu địa phương (locally optimal) nếu tồn tại R > 0 sao cho
f(x) < f(x); 8x 2 X : ||x — x||2 < R.
Xét bài toán tối ưu
min f (x)
s.t. gỉ (x) < 0; i = 1; 2; . . . ; k hj (x) = 0; j = 1; 2;... ; l .
Kí hiệu X là miền CND.
x 2 X được gọi là nghiệm tối ưu địa phương (locally optimal) nếu tồn tại R > 0 sao cho
f(x) < f(x); 8x 2 X : ||x — x||2 < R.
De phân biệt với nghiệm tối ưu địa phương với nghiệm tối ưu, ta còn gọi nghiệm tối ưu là nghiệm tối ưu toàn cục (globally optimal).
Cực tiểu địa phương của bài toán tối ưu lồi
Định lý
Nghiệm toi ưu địa phương của một bài toán toi ưu loi công là nghiệm tèi ưu toàn cục.
Chứng minh.
Chứng minh phản chứng dựa trên tính lồi của miền CND và hàm mục tiêu.	□
Điểm dừng (stationary point) x của một hàm khả vi f là một điểm tại đó Vf(x) = 0.
Điểm dừng (stationary point) x của một hàm khả vi f là một điểm tại đó Vf(x) = 0.
Ta sẽ thấy mỗi điểm cực trị địa phưong là một điểm dừng.
Điểm dừng (stationary point) x của một hàm khả vi f là một điểm tại đó Vf(x) = 0.
Ta sẽ thấy mỗi điểm cực trị địa phưong là một điểm dừng. Tuy nhiên cần lưu ý rằng không phải mọi điểm dừng đều là cực trị địa phưong.
Điểm dừng (stationary point) x của một hàm khả vi f là một điểm tại đó Vf(x) = 0.
Ta sẽ thấy mỗi điểm cực trị địa phưong là một điểm dừng. Tuy nhiên cần lưu ý rằng không phải mọi điểm dừng đều là cực trị địa phưong.
Ví dụ: f(x) = x3
f'(0) = 0 nhưng 0 không phải là một điểm cực trị.
Dường mức của một hàm so f : Rn ! R là một tập hợp có dạng
Lc (f) = {x I f (x) = c }:
Dường mức của một hàm so f : Rn ! R là một tập hợp có dạng
Lc(f) = {x I f(x) = c}.
f (x; y) = (x2 + y - 11)2 + (x + y2 - 7)2
Log-spaced level curve
Với hàm f khả vi, gradient tại một điểm hoặc bằng 0 hoặc vuông góc với đường mức tại điểm đó.
Với hàm f khả vi, gradient tại một điểm hoặc bằng 0 hoặc vuông góc với đường mức tại điểm đó.
Ví dụ: f(x; y) = x3 - 3x - 2y2
Tà i liệu tham khảo
n Chương 2 và chương 3, S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press.
n Chương 1, J. Nocedal and S. Wright, Numerical Optimization, Springer.