Có nhiều cách để phân loại các bài toán quy hoạch toán học:

• Lồi đối lập với Không lồi
• Trơn đối lập với Không trơn
• Tuyến tính đối lập với Phi tuyến.

Lồi và không lồi

Tập lồi

Chúng ta nói rằng $D\subset \mathbb {R} ^{n}$ là một tập lồi nếu

$(1-t)x+ty\in D{\text{ với mọi }}x\in D,y\in D{\text{ và }}t\in (0,1)$.

Bao lồi

Tập lồi nhỏ nhất chứa $\Omega \subset \mathbb {R} ^{n}$ được gọi là bao lồi của $\Omega$ và được ký hiệu bởi ${\text{co}}\Omega$.

Hàm lồi

Một hàm $f:R^{n}\to \mathbb {\bar {R}}$ được gọi là lồi nếu tập trên đồ thị của nó,

${\text{epi}}f:=\{(x,\alpha ):x\in \mathbb {R} ,\alpha \in \mathbb {R} ,\alpha \geq f(x)$

(1)

là một tập lồi trong không gian tích $\mathbb {R} ^{n}\times \mathbb {R}$.

Hàm chính thường

Hàm $f$ được gọi là chính thường nếu $f(x)<+\infty$ với ít nhất một phần tử $x\in \mathbb {R} ^{n}$ và $f(x)>-\infty$ với mọi $x\in \mathbb {R} ^{n}$. Hàm $f:\mathbb {R} ^{n}\to \mathbb {\bar {R}}$ được gọi là lõm nếu hàm $-f$ được xác định bởi công thức $(-f)(x)=-f(x)$ là lồi.

Theo các quy ước thường dùng (xem Rockafellar (1970), tr. 24),

$\alpha +(+\infty )=(+\infty )+\alpha =+\infty {\text{ với }}-\infty <\alpha \leq +\infty$

$\alpha +(-\infty )=(-\infty )+\alpha =-\infty {\text{ với }}-\infty \leq \alpha <+\infty$

$\alpha (+\infty )=(+\infty )\alpha =+\infty ,\alpha (-\infty )=(-\infty )\alpha =-\infty ,{\text{ với }}0<\alpha \leq +\infty$

$\alpha (+\infty )=(+\infty )\alpha =-\infty ,\alpha (-\infty )=(-\infty )\alpha =+\infty ,{\text{ với }}-\infty \leq \alpha <0$

$0(+\infty )=(+\infty )0=0=0(-\infty )=(-\infty )0,\ -(-\infty )=+\infty ,\ {\text{inf}}\emptyset =+\infty ,\ {\text{sup}}\emptyset =-\infty$.

Các tổ hợp $(+\infty )+(-\infty )$ và $(-\infty )+(+\infty )$ là vô nghĩa và sẽ được tránh sử dụng.

Bất đẳng thức Jensen

Từ định nghĩa hàm lồi và công thức (1) ta suy ra rằng hàm số $f:\mathbb {R} ^{n}\to \mathbb {R} \cup \{+\infty \}$ là lồi khi và chỉ khi

$f((1-t)x+ty)\leq (1-t)f(x)+tf(y),\forall x,y\in \mathbb {R} ^{n},\forall t\in (0,1).$

(2)

Tổng quát hơn, một hàm $f:\mathbb {R} ^{n}\to \mathbb {R} \cup \{+\infty \}$ là lồi khi và chỉ khi

$f(\lambda _{1}x_{1}+...+\lambda _{k}x_{k})\leq \lambda _{1}f(x_{1})+...+\lambda _{k}f(x_{k})\qquad {\text{(bất đẳng thức Jensen)}}$

với mọi $x_{1},...,x_{k}\in \mathbb {R} ^{n}$ và $\lambda _{1}\geq 0,...,\lambda _{k}k\geq 0,\lambda _{1}+...+\lambda _{k}=1$. (Xem Rockafellar (1970), Định lý 4.3.)

Hàm lồi chặt

Giả sử rằng $D\subset \mathbb {R} ^{n}$ là một tập lồi. Nếu bất đẳng thức trong (2) đúng với mọi $x,y\in D$ và với mọi $t\in (0,1)$, thì ta nói $f$ là lồi trên $D$. Nếu bất đẳng thức trong (2) nghiệm đúng như một bất đẳng thức chặt với mọi $x,y\in D$ mà $x\neq y$ và với mọi $t\in (0,1)$, thì ta nói $f$ là lồi chặt trên $D$.

Bài toán quy hoạch lồi

Ta nói rằng $(P)$ là bài toán quy hoạch lồi nếu $D$ là tập lồi và $f$ là hàm lồi. Nếu $(P)$ bài toán quy hoạch lồi, thì

${\text{Sol}}(P)={\text{loc}}(P).$

(3)

Bài toán quy hoạch không lồi

Nếu $D$ là tập không lồi hoặc $f$ là hàm không lồi, thì ta nói $(P)$ là bài toán quy hoạch không lồi.

Xét bài toán

${\text{min}}\{f(x)=(x_{1}-c_{1})^{2}+(x_{2}-c_{2})^{2}:x\in D\},$

(4)

ở đó $D={x=(x_{1},x_{2})\in \mathbb {R} ^{2}:x_{1}\geq 0}\cup {x=(x_{1},x_{2}):x_{2}\geq 0}$ và $c=(c_{1},c_{2})=(-2,-1)$. Nhận xét rằng $f$ là lồi, trong khi $D$ là không lồi. Rõ ràng rằng (4) là tương đương với bài toán sau đây:

${\text{min}}\{\lVert x-c\rVert :x\in D\}.$

(5)

Có thể thấy rằng tập nghiệm của (4) và (5) chỉ gồm một điểm $(-2,0)$, còn tập nghiệm địa phương gồm hai điểm: $(-2,0)$ và $(0,-1)$. Điều này chứng tỏ rằng đẳng thức (3) nói chung không đúng với các bài toán quy hoạch không lồi.

Đặt $f_{1}(x)=-x+2,f_{2}(x)=x+{\frac {3}{2}}$ với mọi $x\in \mathbb {R}$. Định nghĩa $f(x)={\text{min}}{f_{1}(x),f_{2}(x)}$ và chọn $D=[0,2]\subset R$. Với hàm $f$ và tập $D$ đó, chúng ta có

${\text{Sol}}(P)=\{2\},\quad {\text{loc}}(P)=\{0,2\};$

tức là đẳng thức (3) không đúng cho bài toán trong ví dụ này. Ở đây, $f$ là hàm không lồi và $D$ là tập lồi.

Các hàm lồi có nhiều tính chất thú vị. Chẳng hạn, hàm lồi là liên tục tại mỗi điểm trong của miền hữu hiệu của nó và nó là khả vi theo hướng tại mỗi điểm thuộc miền đó.

Miền hữu hiệu

Đối với mỗi hàm số $f:\mathbb {R} ^{n}\to {\bar {\mathbb {R} }}$, tập hợp

${\text{dom}}f:=\{x\in \mathbb {R} ^{n}:-\infty <f(x)<+\infty \}$

được gọi là miền hữu hiệu của f.

Đạo hàm theo hướng

Đối với một điểm ${\bar {x}}\in {\text{dom}}f$ và một véctơ $v\in \mathbb {R} ^{n}$, nếu giới hạn

$f'({\bar {x}};v):=\lim _{t\downarrow 0}{\frac {f({\bar {x}}+tv)-f({\bar {x}})}{t}}$

(có thể nhận các giá trị $+\infty$ và $-\infty$) tồn tại, thì $f$ được gọi là khả vi theo hướng tại ${\bar {x}}$ theo hướng $v$ và giá trị $f'({\bar {x}};v)$ được gọi là đạo hàm theo hướng của $f$ tại ${\bar {x}}$ theo hướng $v$. Nếu $f'({\bar {x}};v)$ tồn tại với mọi $v\in \mathbb {R} ^{n}$, thì $f$ được gọi là khả vi theo hướng tại ${\bar {x}}$.

Trong hai định lý tiếp theo đây, $f:\mathbb {R} n\to \mathbb {R} \cup \{+\infty \}$ là một hàm lồi và chính thường.

Định lý 0.0.1. (Xem Rockafellar (1970), Định lý 10.1) Nếu ${\bar {x}}\in \mathbb {R} ^{n}$ và $\delta >0$ là điểm và số thực sao cho hình cầu mở $B({\bar {x}},\delta )$ chứa trong ${\text{dom}}f$, thì phần hạn chế của $f$ trên $B({\bar {x}},\delta )$ là một hàm số thực liên tục.

Định lý 0.0.2. (Xem Rockafellar (1970), Định lý 23.1) Nếu ${\bar {x}}\in {\text{dom}}f$, thì với mỗi $v\in \mathbb {R} ^{n}$ giới hạn

$f'({\bar {x}};\ v):=\lim _{t\downarrow 0}{\frac {f({\bar {x}}+tv)-f({\bar {x}})}{t}}$

tồn tại, và ta có

$f'({\bar {x}};\ v)=\inf _{t>0}{\frac {f({\bar {x}}+tv)-f({\bar {x}})}{t}}.$

Nón pháp tuyến

Nón pháp tuyến $N_{D}({\bar {x}})$ của tập lồi $D\subset \mathbb {R} ^{n}$ tại một điểm ${\bar {x}}\in \mathbb {R} ^{n}$ được cho bởi công thức

$N_{D}({\bar {x}})={\begin{cases}\{x^{*}\in R^{n}:\langle x^{*},x-{\bar {x}}\rangle \leq 0{\text{ với mọi }}x\in D\}&{\text{nếu }}{\bar {x}}\in D\\\emptyset &{\text{nếu }}{\bar {x}}\notin D.\end{cases}}$

Dưới vi phân

Dưới vi phân $\partial f({\bar {x}})$ của một hàm lồi $f:R^{n}\to \mathbb {R}$ tại một điểm ${\bar {x}}\in \mathbb {R} n$ được định nghĩa bằng công thức

$\partial f({\bar {x}})=\{x^{*}\in \mathbb {R} ^{n}:f({\bar {x}})+\langle x^{*},x-{\bar {x}}\rangle \leq f(x){\text{ với mọi }}x\in \mathbb {R} ^{n}$

Phần trong tương đối

Tập con $M\subset \mathbb {R} ^{n}$ được gọi là một tập affine (a-phin) nếu $tx+(1-t)y\in M$ với mọi $x\in M,y\in M$ và $t\in R$. Đối với một $D\subset \mathbb {R} ^{n}$, bao affine aff$DofD$ là tập affine nhỏ nhất chứa $D$. Phần trong tương đối của $D$ được xác định bởi công thức

${\text{ri}}D:=\{x\in D:\exists \partial >0{\text{ sao cho }}B(x,\partial )\cap {\text{aff}}D\subset D\}$

Định lý sau đây mô tả mối quan hệ giữa đạo hàm theo hướng và dưới vi phân của các hàm lồi.

Định lý 0.0.3. (Xem Rockafellar (1970), Định lý 23.4) Cho $f$ là một hàm lồi trên $R^{n}$. Nếu $x\notin {\text{dom}}f$, thì $\partial f(x)$ là rỗng. Nếu $x\in {\text{ri}}({\text{dom}}f)$, thì $\partial f(x)$ là khác rỗng và

$f'(x;v)=\sup\{\langle x^{*},v\rangle :x^{*}\in \partial f(x)\},\quad \forall v\in R^{n}.$

Ngoài ra, $\partial f(x)$ là tập khác rỗng và giới nội khi và chỉ khi

$x\in {\text{int}}({\text{dom}}f);$

trong trường hợp đó, $f'(x;v)$ là hữu hạn với mỗi $v\in \mathbb {R} ^{n}$.

Kết quả sau đây được gọi là Định lý Moreau-Rockafellar.

Định lý 0.0.4. (Xem Rockafellar (1970), Định lý 23.8) Cho $f=f_{1}+...+f_{k}$, ở đó $f_{1}+...+f_{k}$ là các hàm lồi, chính thường trên $\mathbb {R} ^{n}$. Nếu

$\bigcap _{i=1}^{k}{\text{ri}}({\text{dom}}f_{i})\neq \emptyset ,$

thì

$\partial f(x)=\partial f_{1}(x)+...+\partial f_{k}(x),\quad \forall x\in R^{n}.$

Điều kiện cần và đủ tối ưu cho các bài toán quy hoạch lồi được phát biểu như sau.

Định lý 0.0.5. (Xem Rockafellar (1970), Định lý 27.4) Giả sử rằng $f$ là một hàm lồi, chính thường trên $\mathbb {R} ^{n}$ và $D\subset \mathbb {R} ^{n}$ là một tập lồi. Nếu bao hàm thức

$0\in \partial f({\bar {x}})+N_{D}({\bar {x}})$

(6)

nghiệm đúng với ${\bar {x}}\in \mathbb {R} ^{n}$, thì ${\bar {x}}$ là nghiệm của $(P)$. Ngược lại, nếu

${\text{ri}}({\text{dom}}f)\cap {\text{ri}}D\neq \emptyset ,$

(7)

thì (6) là điều kiện cần và đủ cho ${\bar {x}}\in \mathbb {R} ^{n}$ là nghiệm của $(P)$. Nói riêng ra, nếu $D=\mathbb {R} ^{n}$, thì ${\bar {x}}$ là một nghiệm của $(P)$ khi và chỉ khi $0\in \partial f({\bar {x}})$.

Bao hàm thức (6) có nghĩa là tồn tại $x^{*}\in \partial f({\bar {x}})$ và $u^{*}\in N_{D}({\bar {x}})$ sao cho 0 = x^∗ + u^∗. Nhận xét rằng (7) là một điều kiện chính quy cho bài toán quy hạch lồi có dạng $(P)$.

Định lý 0.0.5 là công cụ hiệu quả để giải nhiều bài toán quy hoạch lồi. Chúng ta có thể minh họa điều đó bằng cách xét ví dụ sau đây.

Điểm Fermat

Cho $A,B,C$ là ba điểm trong không gian hai chiều $\mathbb {R} ^{2}$ với các tọa độ tương ứng là

$a=(a_{1},a_{2}),b=(b_{1},b_{2}),c=(c_{1},c_{2}).$

Giả sử rằng không tồn tại đường thẳng nào chứa tất cả ba điểm đó. Bài toán đặt ra là tìm một điểm $M$ trong $\mathbb {R} ^{2}$ với các tọa độ ${\bar {x}}=({\bar {x}}_{1},{\bar {x}}_{2})$ sao cho tổng khoảng cách từ $M$ tới $A,B$ và $C$ là tối thiểu. Điều đó có nghĩa rằng ${\bar {x}}$ là một nghiệm của bài toán quy hoạch lồi không có ràng buộc sau:

${\text{min}}\{f(x):=\lVert x-a\rVert +\lVert x-b\rVert +\lVert x-c\rVert :x\in \mathbb {R} ^{2}\}.$

(8)

Sử dụng định lý Weierstrass và tính lồi chặt của f(x) trên R2, ta có thể chứng tỏ rằng (8) có duy nhất nghiệm; xem Lee, Tam, Yen (2005), tr. 11–13. Để ý rằng f = f1+f2+f3, ở đó f1(x) = kx−ak, f2(x) = kx−bk, f3(x) = kx−ck. Theo Định lý 0.0.5, x¯ là nghiệm của (8) khi và chỉ khi 0 ∈ ∂f(¯x). Vì domfi = R2 (i = 1, 2, 3), sử dụng Định lý 0.0.4 ta có thể viết bao hàm thức cuối dưới dạng

0 ∈ ∂f1(¯x) + ∂f2(¯x) + ∂f3(¯x).

Tiếp theo, bằng cách tính toán các dưới vi phân (xem Lee, Tam, Yen (2005), tr. 10), ta có thể xác định được điểm x¯ là nghiệm duy nhất của bao hàm thức này. Trong ngôn ngữ của Hình học Euclide, ta có các kết luận sau:

(i) Nếu một trong ba góc của tam giác ABC, ví dụ như góc Aˆ, là lớn hơn hoặc bằng 120o, thì M ≡ A là nghiệm duy nhất của bài toán đang được xét.

(ii) Nếu tất cả các góc của tam giác ABC đều nhỏ hơn 120o, thì nghiệm duy nhất của bài toán là điểm M nhìn các cạnh BC, AC và AB của tam giác ABC dưới cùng một góc 120o

• (Điểm M đặc biệt này được gọi là điểm Fermat hay điểm Torricelli (xem Weisstein (1999)). Có thể chứng tỏ rằng điểm Fermat thuộc phần trong của tam giác ABC.)

Trong bài toán (P), nếu D là tập nhiệm của một hệ các phương trình và bất phương trình, thì điều kiện tối ưu bậc nhất có thể viết được ở dạng có sử dụng các nhân tử Lagrange.

Chúng ta hãy xét bài toán (P) dưới các giả thiết f : Rn → R là một hàm lồi,

D = {x ∈ Rn: g1(x) ≤ 0, . . . , gm(x) ≤ 0, h1(x) = 0, . . . , hs(x) = 0}, (9)

ở đó gi: Rn → R, i = 1, . . . , m, là các hàm lồi, hj: Rn → R, j = 1, . . . , s là các hàm affine, nghĩa là tồn tại aj ∈ Rn và αj ∈ R sao cho hj (x) = haj, xi + αj với mọi x ∈ Rn. Chúng ta chấp nhận rằng các ràng buộc bất đẳng thức (tươngứng, các ràng buộc bất đẳng thức) có thể không có mặt trong (9). Để cho gọn, chúng ta sử dụng cách viết hình thức m = 0 (tương ứng, s = 0) để chỉ rằng các ràng buộc bất đẳng thức (tương ứng, các ràng buộc bất đẳng thức) không có mặt trong (9).

Định lý 0.0.6. (Định lý Kuhn-Tucker cho các bài toán quy hoạch lồi; xem Rockafellar (1970), tr. 283) Giả sử rằng (P) là bài toán quy hoạch lồi với D được cho bởi (9). Giả sử rằng các giả thiết đặt lên f, gi (i = 1, . . . , m) và hj (j = 1, . . . s) như đã nói ở trên được thỏa mãn. Giả sử rằng tồn tại véctơ z ∈ Rn sao cho

gi(z) < 0 với i = 1, . . . , m và hj (z) = 0 với j = 1, . . . , s. (10)

Khi đó, x¯ là một nghiệm của (P) khi và chỉ khi tồn tại m + s số thực λ1, . . . , λm, µ1, . . . , µs, được gọi là các nhân tử Langrange tương ứng với x¯, sao cho các điều kiện Kuhn-Tucker sau đây được thỏa mãn:

(a) λi ≥ 0, gi(¯x) ≤ 0 và λifi(¯x) = 0 với i = 1, . . . , m,

(b) hj (¯x) = 0 với j = 1, . . . , s,

(c) 0 ∈ ∂f(¯x) + Xmi=1λi∂gi(¯x) +Xsj=1µjaj.

Nhận xét rằng (10) là một điều kiện chuẩn hóa ràng buộc (còn được gọi là điều kiện chính quy ràng buộc, hay đơn giản là điều kiện chính quy) cho các bài toán hoạch lồi. Nếu s = 0 thì nó trở thành

∃z ∈ Rns.t. gi(z) < 0 với i = 1, . . . , m. (Điều kiện Slater)

Nếu m = 0 thì (10) tương đương với đòi hỏi rằng D là khác rỗng. Trên thực tế, trong trường hợp đó, có thể bỏ qua điều kiện (10) trong phát biểu của Định lý 0.0.6.

Trơn và không trơn

Định nghĩa

Để cho gọn, nếu f : Rn → R là hàm khả vi Fréchet liên tục, thì ta nói rằng f là một hàm C1 (tức là hàm thuộc lớp C1).

Ta gọi (P) là bài toán quy hoạch toán học trơn nếu f : Rn → R là hàm C1 và D biểu diễn được dưới dạng (9), ở đó gi: Rn → R (i = 1, . . . , m) và hj: Rn → R (j = 1, . . . , s) là các hàm C1. Ngược lại, (P) được gọi là bài toán quy hoạch toán học không trơn.

Hàm Lipschitz địa phương

Một hàm f : Rn → R được gọi là Lipschitz địa phương tại x¯ ∈ Rn nếu tồn tại hằng số ` ≥ 0 và lân cận U của x¯ sao cho

|f(x0) − f(x)| ≤ `kx0 − xk với mọi x, x0 thuộc U. (11)

Nếu f là Lipschitz địa phương tại mỗi điểm thuộc Rn, thì f được gọi là hàm số Lipschitz địa phương trên Rn.

Nếu bất đẳng thức trong (11) đúng với mọi x, x0 ∈ C, ở đó C là một tập con của Rn, thì ta nói f là Lipschitz trên C với hệ số Lipschitz `.

Đạo hàm theo hướng suy rộng theo nghĩa Clarke

Nếu f là Lipschitz địa phương tại x¯, thì đạo hàm theo hướng suy rộng theo nghĩa Clarke của f tại x¯ theo hướng v ∈ Rn được định nghĩa bằng công thức

f0(¯x; v) := lim sup x→x, t ¯ ↓0 f(x + tv) − f(x))t = sup n ξ ∈ R : ∃ các dãy xk → x¯ và tk → 0+ sao cho ξ = limk→+∞f(xk + tkv) − f(xk)tko.

Dưới vi phân Clarke

Dưới vi phân Clarke của f tại x¯ được cho bởi công thức

∂f(¯x) := {x∗ ∈ Rn: f0(¯x; v) ≥ hx∗, vi với mọi v ∈ Rn}.

Định lý 0.0.7. ( Xem Clarke (1983), các Mệnh đề 2.1.2, 2.2.4, 2.2.6 và 2.2.7)Cho f : Rn → R là một hàm số thực. Khi đó, các khẳng định sau đây nghiệm đúng:

(a) Nếu f là Lipschitz địa phương tại x¯ ∈ Rn, thì

f0(¯x; v) = max{hx∗, vi : x∗ ∈ ∂f(¯x)}

với mọi v ∈ Rn.

(b) Nếu f là hàm C1, thì f là hàm số Lipschitz địa phương và ∂f(¯x) = {∇f(¯x)}, f0(¯x; v) = h∇f(¯x), vi với mọi x¯ ∈ Rn và v ∈ Rn.

(c) Nếu f là lồi, thì f là hàm số Lipschitz địa phương và, với mỗi x¯ ∈ Rn, dưới vi phân Clarke ∂f(¯x) trùng với dưới vi phân của f tại x¯theo nghĩa Giải tích lồi, tức là dưới vi phân được định nghĩa bởi . Ngoài ra, f0 (¯x; v) = f0 (¯x; v) với mỗi v ∈ Rn.

Liên quan đến khẳng định (c) ở trên, chúng ta lưu ý rằng, đạo hàm theo hướng f0(¯x; v) tồn tại (xem Định lý 0.0.2).

Nón tiếp tuyến Clarke

Cho C ⊂ Rn là tập con khác rỗng. Nón tiếp tuyến Clarke TC(x) của C tại x ∈ C là tập hợp tất cả các véctơ v ∈ Rn thỏa mãn d0 C(x; v) = 0, ở đó d0 C(x; v) ký hiệu đạo hàm theo hướng suy rộng theo nghĩa Clarke của hàm số Lipschitz

dC(z) := inf{ky − zk : y ∈ C}

tại x theo hướng v.

Nón pháp tuyến Clarke

Nón pháp tuyến Clarke NC(x) của C tại x được định nghĩa là nón đối ngẫu của TC(x), tức là

NC(x) = {x∗ ∈ Rn: hx∗, vi ≤ 0 với mọi v ∈ TC(x)}.

Định lý 0.0.8. (Xem Clarke (1983), các Mệnh đề 2.4.3, 2.4.4 và 2.4.5) Với mỗi tập con khác rỗng C ⊂ Rn và với mỗi điểm x ∈ C, các khẳng định sau nghiệm đúng:

(a) NC(x) = n∪t≥0 t∂dC(x)o.

(b) Nếu C là lồi, thì NC(x) trùng với nón pháp tuyến của C tại x được định nghĩa bởi công thức , và TC(x) trùng với bao đóng tôpô của hình nón

cone(C − x) := {tz : t ≥ 0, z ∈ C − x}.

(c) Bao hàm thức v ∈ TC(x) nghiệm đúng khi và chỉ khi với mỗi dãy điểm xk trong C hội tụ đến x và dãy số tk trong (0, +∞) hội tụ đến 0, tồn tại dãy véctơ vk trong Rn hội tụ đến v sao cho xk + tkvk ∈ C với mọi k.

Xét bài toán (P) dưới các giả thiết f : Rn → R là hàm Lipschitz địa phương,

D = {x ∈ C : g1(x) ≤ 0, . . . , gm(x) ≤ 0, h1(x) = 0, . . . , hs(x) = 0}, (12)

với C ⊂ Rn là tập khác rỗng, gi: Rn → R (i = 1, . . . , m) và hj: Rn → R(j = 1, . . . , s) là các hàm Lipschitz địa phương.

Định lý 0.0.9. (Xem Clarke (1983), Định lý 6.1.1 và Nhận xét 6.1.2) Nếu x¯ là nghiệm địa phương của (P), thì tồn tại m + s + 1 số thực λ0 ≥ 0, λ1 ≥ 0, . . . , λm ≥ 0, µ1, . . . , µs, không đồng thời bằng 0, sao cho

0 ∈ λ0∂f(¯x) +Xm i=1 λi∂gi(¯x) +Xs j=1 µj∂hj (¯x) + NC(¯x) (13)

và

λigi(¯x) = 0 với mọi i = 1, 2, . . . , m. (14)

Điều kiện cần tối ưu bậc nhất ở dạng Fritz-John

Định lý trên phát biểu điều kiện cần tối ưu bậc nhất ở dạng Fritz-John cho một lớp bài toán không trơn. Dưới những điều kiện chính quy ràng buộc thích hợp, nhân tử λ0 tương ứng với hàm mục tiêu f là dương. Trong trường hợp đó, bằng cách chia cả hai vế của bao hàm thức trong (13) và các đẳng thức trong (14) cho λ0, và đặt λei = λi/λ0 cho mỗi i = 1, . . . , m, µej = µj/λ0 cho mỗi j = 1, . . . , s, chúng ta thu được

0 ∈ ∂f(¯x) +Xmi=1λei∂gi(¯x) +X s j=1 µej∂hj (¯x) + NC(¯x) (15)

và

λeigi(¯x) = 0 với mọi i = 1, 2, . . . , m. (16)

Tương tự như trong trường hợp các bài toán quy hoạch lồi (Định lý 1.6), nếu x¯ ∈ D và (15), (16) nhiệm đúng, thì các số λe1 ≥ 0, . . . , λem ≥ 0, µe1 ∈ R, . . . , µes ∈ R được gọi là các nhân tử Lagrange tương ứng với x¯.

Hai quy tắc nhân tử Lagrange sau đây suy ra từ Định lý 0.0.9 (xem Clarke(1983), tr. 234–236).

Hệ quả 0.0.1. Nếu x¯ là một nghiệm địa phương của (P) và nếu điều kiện chuẩn hóa ràng buộc

h0 ∈Xmi=1λi∂gi(¯x) +Xsj=1µj∂hj (¯x) + NC(¯x),

λ1 ≥ 0, . . . , λm ≥ 0, µ1 ∈ R, . . . , µs ∈ R;

λigi(¯x) = 0 với i = 1, . . . , mi

=⇒[λ1 = · · · = λm = 0, µ1 = · · · = µs = 0i]

được thỏa mãn, thì tồn tại các nhân tử Lagrange λ1 ≥ 0, . . . , λm ≥ 0, µ1 ∈ R, . . . , µs ∈ R sao cho λigi(¯x) = 0 với i = 1, 2, . . . , m, và

0 ∈ ∂f(¯x) +X m i=1 λi∂gi(¯x) +X s j=1 µj∂hj (¯x) + NC(¯x).

Hệ quả 0.0.2. Giả sử rằng x¯ là một nghiệm địa phương của bài toán quy hoạch trơn (P), ở đó D được cho bởi công thức (9). Nếu điều kiện chuẩn hóa ràng buộc Mangasarian-Fromovitz (viết tắt: (MFCQ))

Các véctơ {∇hj (¯x) : j = 1, . . . , s} là độc lập tuyến tính,

và tồn tại v ∈ Rn sao cho h∇hj (¯x), vi = 0

với mỗi j = 1, . . . , s, và h∇gi(¯x), vi < 0

với mỗi i = 1, . . . , m thỏa mãn gi(¯x) = 0

được thỏa mãn, thì tồn tại các nhân tử Lagrange λ1 ≥ 0, . . . , λm ≥ 0, µ1 ∈ R, . . . , µs ∈ R sao cho λigi(¯x) = 0 với i = 1, 2, . . . , m, và

0 = ∇f(¯x) +X m i=1 λi∇gi(¯x) +X s j=1 µj∇hj (¯x).

Sử dụng Định lý 0.0.9 ta dễ dàng chứng minh được quy tắc nhân tử Lagrange cho các bài toán quy hoạch lồi đã được phát biểu trong Định lý 0.0.6 (xem Lee, Tam, Yen (2005), tr. 18–19).

Tuyến tính và phi tuyến

Tập lồi đa diện

Tập hợp D ⊂ Rn được gọi là tập lồi đa diện nếu như ta có thể biểu diễn D dưới dạng giao của một số hữu hạn các nửa không gian đóng của R n; nghĩa là tồn tại các véctơ khác không a1, . . . , am ∈ Rn và các số thực β1, . . . , βm sao cho

D = {x ∈ Rn : hai , xi ≥ βi với i = 1, . . . , m}. (17)

Nói một cách khác, D là tập nghiệm của một hệ gồm hữu hạn các bất đẳng thức tuyến tính. (Chúng ta quy ước rằng giao của một họ rỗng của các nửa không gian đóng của Rn là Rn. Vì thế, D = Rn cũng là một tập lồi đa diện.)

Điểm cực biên

Một điểm x ∈ D được gọi là điểm cực biên của D nếu như không thể nào biểu diễn x dưới dạng x = (1 − t)y + tz, ở đó y ∈ D, z ∈ D, y 6= z, và t ∈ (0, 1). Tập hợp tất cả các điểm cực biên của D được ký hiệu bởi extrD. Ký hiệu bởi A ma trận cấp m × n với các phần tử aij (i = 1, . . . , m, j = 1, . . . , n), ở đó aij là thành phần thứ j của véctơ ai. Đặt b = (β1, . . . , βm) ∈ Rm. Khi đó, ta có thể viết lại (17) như sau:

D = {x ∈ Rn: Ax ≥ b}.

Từ đây về sau, đối với hai véctơ tùy ý y = (y1, . . . , ym) ∈ Rm và z = (z1, . . . , zm) ∈ R m, ta viết y ≥ z nếu yi ≥ zi với i = 1, . . . , m. Ta sẽ viết y > z nếu yi > zi với mọi i = 1, . . . , m. Vì

{x ∈ Rn: Ax = b} = {x ∈ Rn: Ax ≥ b, (−A)x ≥ −b},

ta suy ra rằng {x ∈ Rn: Ax = b} là một tập lồi đa diện.

Bài toán quy hoạch tuyến tính

Bài toán (P) được gọi là bài toán quy hoạch tuyến tính nếu D là tập lồi đa diện và f(x) là phiếm hàm tuyến tính. Ngược lại, (P) được gọi là bài toán quy hoạch phi tuyến.

Có ba dạng điển hình của bài toán quy hoạch tuyến:

min{f(x) = hc, xi : x ∈ Rn, Ax ≥ b},

min{f(x) = hc, xi : x ∈ Rn, Ax = b, x ≥ 0},

min{f(x) = hc, xi : x ∈ Rn, Ax ≥ b, Cx = d};

chúng được gọi tương ứng là dạng chuẩn, dạng chính tắc, và dạng tổng quát. Ở đây, A ∈ Rm×n, C ∈ Rs×n là các ma trận cho trước, c ∈ Rn, b ∈ Rm và d ∈ Rs là các véctơ cho trước.

Xét bài toán quy hoạch tuyến tính dạng chuẩn:

min nx1 +12x2 : x = (x1, x2), x1 + x2 ≥ 1, x1 ≥ 0, x2 ≥ 0o.

Dễ kiểm tra rằng Sol(P) = {(0, 1)}. Nhận xét rằng tập ràng buộc

D = {x ∈ R2: x1 + x2 ≥ 1, x1 ≥ 0, x2 ≥ 0}

có hai điểm cực biên, cụ thể là extr = {(1, 0), (0, 1)}. Một trong hai điểm đó là nghiệm của bài toán được xét.

Bài toán đối ngẫu

Bài toán đối ngẫu của các bài toán quy hoạch tuyến tính dạng chuẩn, dạng chính tắc, và dạng tổng quát, tương ứng là:

max{hb, yi : y ∈ Rm, ATy = c, y ≥ 0},

max{hb, yi : y ∈ Rm, ATy ≤ c},

max{hb, yi + hd, zi : (y, z) ∈ Rm × Rs, ATy + CTz = c, y ≥ 0}.

Vì bài toán quy hoạch tuyến tính cũng là một bài toán quy hoạch lồi, nên nó có tất cả các tính chất của bài toán quy hạch lồi. Ngoài ra, bài toán quy hoạch tuyến tính còn có những tính chất đặc biệt khác.

Định lý 0.0.10. (Xem Dantzig (1963)) Cho (P) là bài toán quy hoạch tuyến tính ở một trong các dạng điển hình. Các tính chất sau đây nghiệm đúng:

(i) Nếu tập ràng buộc là khác rỗng và nếu v(P) > −∞, thì Sol(P) là tập lồi đa diện khác rỗng.

(ii) Nếu cả hai tập extrD và Sol(P) đều khác rỗng, thì giao extrD ∩ Sol(P) cũng là khác rỗng.

(iii) Nếu rankA = n và tập D := {x ∈ Rn: Ax = b, x ≥ 0} là khác rỗng, thì D phải có ít nhất một điểm cực biên.

(iv) Giá trị tối ưu v(P) của (P) và giá trị tối ưu v(P0) of của bài toán đối ngẫu(P0) của (P) là bằng nhau, nếu như tập ràng buộc của ít nhất là một trong hai bài toán là khác rỗng.

Tham khảo

• Lee, Tam, Yen (2005), Chương 1.