| Bản hiện tại |
Nội dung bạn nhập |
| Dòng 49: |
Dòng 49: |
| | {{NumBlk|:|<math>f((1 - t)x + ty) \le (1 - t)f(x) + tf(y), \forall x, y \in \mathbb{R}^n, \forall t \in (0, 1).</math>|{{EquationRef|2}}}} | | {{NumBlk|:|<math>f((1 - t)x + ty) \le (1 - t)f(x) + tf(y), \forall x, y \in \mathbb{R}^n, \forall t \in (0, 1).</math>|{{EquationRef|2}}}} |
| | | | |
| − | Tổng quát hơn, một hàm <math>f : \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}</math> là lồi khi và chỉ khi | + | Tổng quát hơn, một hàm f : Rn → R ∪ {+∞} là lồi khi và chỉ khi |
| | | | |
| − | :<math>f(\lambda _1 x_1 + ... + \lambda _k x_k) \le \lambda _1 f(x_1) + ... + \lambda _k f(x_k) \qquad \text{(bất đẳng thức Jensen)}</math>
| + | f(λ1x1 + · · · + λkxk) ≤ λ1f(x1) + · · · + λkf(xk) (bất đẳng thức Jensen) |
| | | | |
| − | với mọi <math>x_1, ... , x_k \in \mathbb{R}^n</math> và <math>\lambda _1 \ge 0, ... , \lambda _kk \ge 0, \lambda _1 + ... + \lambda _k = 1</math>. (Xem Rockafellar (1970), Định lý 4.3.) | + | với mọi x1, . . . , xk ∈ Rn và λ1 ≥ 0, . . . , λk ≥ 0, λ1 + · · · + λk = 1. (Xem Rockafellar (1970), Định lý 4.3.) |
| | | | |
| | ===Hàm lồi chặt=== | | ===Hàm lồi chặt=== |
| | | | |
| − | Giả sử rằng <math>D \subset \mathbb{R}^n</math> là một tập lồi. Nếu bất đẳng thức trong ({{EquationNote|2}}) đúng với mọi <math>x, y \in D</math> và với mọi <math>t \in (0, 1)</math>, thì ta nói <math>f</math> là lồi trên <math>D</math>. Nếu bất đẳng thức trong ({{EquationNote|2}}) nghiệm đúng như một bất đẳng thức chặt với mọi <math>x, y \in D</math> mà <math>x \ne y</math> và với mọi <math>t \in (0, 1)</math>, thì ta nói <math>f</math> là lồi chặt trên <math>D</math>. | + | Giả sử rằng D ⊂ Rn là một tập lồi. Nếu bất đẳng thức trong (2) đúng với mọi x, y ∈ D và với mọi t ∈ (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 ∈ D mà x 6= y và với mọi t ∈ (0, 1), thì ta nói f là lồi chặt trên D. |
| | | | |
| | ===Bài toán quy hoạch lồi=== | | ===Bài toán quy hoạch lồi=== |
| | | | |
| − | Ta nói rằng <math>(P)</math> là bài toán quy hoạch lồi nếu <math>D</math> là tập lồi và <math>f</math> là hàm lồi. Nếu <math>(P)</math> bài toán quy hoạch lồi, thì | + | 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ì |
| | | | |
| − | {{NumBlk|:|<math>\text{Sol}(P) = \text{loc}(P).</math>|{{EquationRef|3}}}}
| + | Sol(P) = loc(P). (3) |
| | | | |
| | ===Bài toán quy hoạch không lồi=== | | ===Bài toán quy hoạch không lồi=== |
| | | | |
| − | Nếu <math>D</math> là tập không lồi hoặc <math>f</math> là hàm không lồi, thì ta nói <math>(P)</math> là ''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 | | Xét bài toán |
| | | | |
| − | {{NumBlk|:|<math>\text{min}\{f(x) = (x_1 - c_1)^2 + (x_2 - c_2)^2 : x \in D\},</math>|{{EquationRef|4}}}}
| + | min{f(x) = (x1 − c1)2 + (x2 − c2)2: x ∈ D}, (4) |
| | | | |
| − | ở đó <math>D = {x = (x_1, x_2) \in \mathbb{R}^2 : x_1 \ge 0} \cup {x = (x_1, x_2) : x_2 \ge 0}</math> và <math>c = (c_1, c_2) = (-2, -1)</math>. Nhận xét rằng <math>f</math> là lồi, trong khi <math>D</math> là không lồi. Rõ ràng rằng ({{EquationNote|4}}) là tương đương với bài toán sau đây: | + | ở đó D = {x = (x1, x2) ∈ R2 : x1 ≥ 0} ∪ {x = (x1, x2) : x2 ≥ 0} và c = (c1, c2) = (−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: |
| | | | |
| − | {{NumBlk|:|<math>\text{min}\{\lVert x - c \rVert : x \in D\}.</math>|{{EquationRef|5}}}}
| + | min{kx − ck : x ∈ D}. (5) |
| | | | |
| − | Có thể thấy rằng tập nghiệm của ({{EquationNote|4}}) và ({{EquationNote|5}}) chỉ gồm một điểm <math>(-2, 0)</math>, còn tập nghiệm địa phương gồm hai điểm: <math>(-2, 0)</math> và <math>(0, -1)</math>. Điều này chứng tỏ rằng đẳng thức ({{EquationNote|3}}) nói chung không đúng với các bài toán quy hoạch không lồi. | + | 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 <math>f_1(x) = -x + 2, f_2(x) = x + \frac{3}{2}</math> với mọi <math>x \in \mathbb{R}</math>. Định nghĩa <math>f(x) = \text{min}{f_1(x), f_2(x)}</math> và chọn <math>D = [0, 2] \subset R</math>. Với hàm <math>f</math> và tập <math>D</math> đó, chúng ta có | + | Đặt f1(x) = −x + 2, f2(x) = x + 32 với mọi x ∈ R. Định nghĩa f(x) = min{f1(x), f2(x)} và chọn D = [0, 2] ⊂ R. Với hàm f và tập D đó, chúng ta có |
| | | | |
| − | :<math>\text{Sol}(P) =\{2\},\quad \text{loc}(P) = \{0, 2\};</math>
| + | Sol(P) = {2}, loc(P) = {0, 2}; |
| | | | |
| − | tức là đẳng thức ({{EquationNote|3}}) không đúng cho bài toán trong ví dụ này. Ở đây, <math>f</math> là hàm không lồi và <math>D</math> là tập lồi. | + | 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 đó. | | 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 đó. |
| Dòng 89: |
Dòng 90: |
| | ===Miền hữu hiệu=== | | ===Miền hữu hiệu=== |
| | | | |
| − | Đối với mỗi hàm số <math>f : \mathbb{R}^n \to \bar{\mathbb{R}}</math>, tập hợp | + | Đối với mỗi hàm số f : Rn → R, tập hợp |
| | | | |
| − | :<math>\text{dom}f := \{x \in \mathbb{R}^n: -\infty < f(x) < +\infty\}</math>
| + | domf := {x ∈ Rn: −∞ < f(x) < +∞} |
| | | | |
| − | được gọi là ''miền hữu hiệu'' của f. | + | được gọi là miền hữu hiệu của f. |
| | | | |
| | ===Đạo hàm theo hướng=== | | ===Đạo hàm theo hướng=== |
| | | | |
| − | Đối với một điểm <math>\bar{x} \in \text{dom}f</math> và một véctơ <math>v \in \mathbb{R}^n</math>, nếu giới hạn | + | Đối với một điểm x¯ ∈ domf và một véctơ v ∈ Rn, nếu giới hạn |
| | | | |
| − | :<math>f'(\bar{x}; v) := \lim_{t \downarrow 0} \frac{f(\bar{x} + tv) - f(\bar{x})}{t}</math>
| + | f0(¯x; v) := limt↓0f(¯x + tv) − f(¯x)t |
| | | | |
| − | (có thể nhận các giá trị <math>+\infty</math> và <math>-\infty</math>) tồn tại, thì <math>f</math> được gọi là khả vi theo hướng tại <math>\bar{x}</math> theo hướng <math>v</math> và giá trị <math>f'(\bar{x}; v)</math> được gọi là đạo hàm theo hướng của <math>f</math> tại <math>\bar{x}</math> theo hướng <math>v</math>. Nếu <math>f'(\bar{x}; v)</math> tồn tại với mọi <math>v \in \mathbb{R}^n</math>, thì <math>f</math> được gọi là ''khả vi theo hướng'' tại <math>\bar{x}</math>. | + | (có thể nhận các giá trị +∞ và −∞) tồn tại, thì f được gọi là khả vi theo hướng tại x¯ theo hướng v và giá trị f0 (¯x; v) được gọi là đạo hàm theo hướng của f tại x¯ theo hướng v. Nếu f0(¯x; v) tồn tại với mọi v ∈ Rn, thì f được gọi là khả vi theo hướng tại x¯. |
| | | | |
| − | Trong hai định lý tiếp theo đây, <math>f : \mathbb{R}n \to \mathbb{R} \cup \{+\infty\}</math> là một hàm lồi và chính thường. | + | Trong hai định lý tiếp theo đây, f : Rn → R ∪ {+∞} 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 <math>\bar{x} \in \mathbb{R}^n</math> và <math>\delta > 0</math> là điểm và số thực sao cho hình cầu mở <math>B(\bar{x}, \delta)</math> chứa trong <math>\text{dom}f</math>, thì phần hạn chế của <math>f</math> trên <math>B(\bar{x}, \delta)</math> là một hàm số thực liên tục.
| + | Định lý 0.0.1. (Xem Rockafellar (1970), Định lý 10.1) Nếu x¯ ∈ Rn và δ > 0 là điểm và số thực sao cho hình cầu mở B(¯x, δ) chứa trong domf, thì phần hạn chế của f trên B(¯x, δ) 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 <math>\bar{x} \in \text{dom}f</math>, thì với mỗi <math>v \in \mathbb{R}^n</math> giới hạn
| + | Định lý 0.0.2. (Xem Rockafellar (1970), Định lý 23.1) Nếu x¯ ∈ domf, thì với mỗi v ∈ Rn giới hạn |
| | | | |
| − | :<math>f'(\bar{x};\ v) := \lim_{t \downarrow 0} \frac{f(\bar{x} + tv) - f(\bar{x})}{t}</math>
| + | f0(¯x; v) := limt↓0f(¯x + tv) − f(¯x)t |
| | | | |
| | tồn tại, và ta có | | tồn tại, và ta có |
| | | | |
| − | :<math>f'(\bar{x};\ v) = \inf_{t > 0} \frac{f(\bar{x} + tv) - f(\bar{x})}{t}.</math>
| + | f0(¯x; v) = inft>0f(¯x + tv) − f(¯x)t. |
| | | | |
| | ===Nón pháp tuyến=== | | ===Nón pháp tuyến=== |
| | | | |
| − | ''Nón pháp tuyến'' <math>N_D(\bar{x})</math> của tập lồi <math>D \subset \mathbb{R}^n</math> tại một điểm <math>\bar{x} \in \mathbb{R}^n</math> được cho bởi công thức
| + | Nón pháp tuyến ND(¯x) của tập lồi D ⊂ R |
| | + | n tại một điểm x¯ ∈ Rn được cho bởi công thức |
| | | | |
| − | <math>
| + | ND(¯x) = |
| − | N_D(\bar{x}) =
| + | {x∗ ∈ Rn: hx∗, x − x¯i ≤ 0 với mọi x ∈ D} nếu x¯ ∈ D |
| − | \begin{cases}
| + | ∅ nếu x / ¯ ∈ D. |
| − | \{ x^* \in R^n : \langle x^*, x - \bar{x} \rangle \le 0 \text{ với mọi } x \in D\} & \text{nếu } \bar{x} \in D\\
| |
| − | \empty & \text{nếu } \bar{x} \notin D.
| |
| − | \end{cases}
| |
| − | </math>
| |
| | | | |
| | ===Dưới vi phân=== | | ===Dưới vi phân=== |
| | | | |
| − | Dưới vi phân <math>\partial f(\bar{x})</math> của một hàm lồi <math>f : R^n \to \mathbb{R}</math> tại một điểm <math>\bar{x} \in \mathbb{R}n</math> được định nghĩa bằng công thức | + | Dưới vi phân ∂f(¯x) của một hàm lồi f : Rn → R tại một điểm x¯ ∈ Rn được định nghĩa bằng công thức |
| | | | |
| − | :<math>\partial f(\bar{x}) = \{ x^* \in \mathbb{R}^n : f(\bar{x}) + \langle x^*, x - \bar{x} \rangle \le f(x) \text{ với mọi } x \in \mathbb{R}^n</math>
| + | ∂f(¯x) = {x∗ ∈ Rn: f(¯x) + hx∗, x − x¯i ≤ f(x) với mọi x ∈ Rn}. |
| | | | |
| | ===Phần trong tương đối=== | | ===Phần trong tương đối=== |
| | | | |
| − | Tập con <math>M \subset \mathbb{R}^n</math> được gọi là một ''tập affine'' (a-phin) nếu <math>tx + (1 - t)y \in M</math> với mọi <math>x \in M, y \in M</math> và <math>t \in R</math>. Đối với một <math>D \subset \mathbb{R}^n</math>, ''bao affine'' aff<math>D of D</math> là tập affine nhỏ nhất chứa <math>D</math>. Phần trong tương đối của <math>D</math> được xác định bởi công thức | + | Tập con M ⊂ Rn được gọi là một tập affine (a-phin) nếu tx + (1 − t)y ∈ M với mọi x ∈ M, y ∈ M và t ∈ R. Đối với một D ⊂ Rn, bao affine affD of D 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 |
| | | | |
| − | :<math>\text{ri}D := \{ x \in D : \exists \partial > 0 \text{ sao cho } B(x, \partial) \cap \text{aff}D \subset D \}</math>
| + | riD := {x ∈ D : ∃δ > 0 sao cho B(x, δ) ∩ affD ⊂ 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ý 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 <math>f</math> là một hàm lồi trên <math>R^n</math>. Nếu <math>x \notin \text{dom}f</math>, thì <math>\partial f(x)</math> là rỗng. Nếu <math>x \in \text{ri}(\text{dom}f)</math>, thì <math>\partial f(x)</math> là khác rỗng và
| + | Định lý 0.0.3. (Xem Rockafellar (1970), Định lý 23.4) Cho f là một hàm lồi trên Rn. Nếu x /∈ domf, thì ∂f(x) là rỗng. Nếu x ∈ ri(domf), thì ∂f(x) là khác rỗng và |
| | | | |
| − | :<math>f'(x;v) = \sup \{ \langle x^*, v \rangle : x^* \in \partial f(x) \}, \quad \forall v \in R^n. </math>
| + | f0(x; v) = sup{hx ∗ , vi : x ∗ ∈ ∂f(x)}, ∀v ∈ Rn. |
| | | | |
| − | Ngoài ra, <math>\partial f(x)</math> là tập khác rỗng và giới nội khi và chỉ khi | + | Ngoài ra, ∂f(x) là tập khác rỗng và giới nội khi và chỉ khi |
| | | | |
| − | :<math>x \in \text{int}(\text{dom} f);</math>
| + | x ∈ int(domf); |
| | | | |
| − | trong trường hợp đó, <math>f'(x; v)</math> là hữu hạn với mỗi <math>v \in \mathbb{R}^n</math>. | + | trong trường hợp đó, f0(x; v) là hữu hạn với mỗi v ∈ Rn. |
| | | | |
| | Kết quả sau đây được gọi là Định lý Moreau-Rockafellar. | | 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 <math>f = f_1 + ... + f_k</math>, ở đó <math>f_1 + ... + f_k</math> là các hàm lồi, chính thường trên <math>\mathbb{R}^n</math>. Nếu
| + | Định lý 0.0.4. (Xem Rockafellar (1970), Định lý 23.8) Cho f = f1 + · · · + fk, ở đó f1, . . . , fk là các hàm lồi, chính thường trên Rn. Nếu |
| | | | |
| − | :<math>\bigcap_{i = 1}^{k}\text{ri}(\text{dom} f_i) \ne \empty,</math>
| + | ki=1 ri(domfi) 6= ∅, |
| | | | |
| | thì | | thì |
| | | | |
| − | :<math>\partial f(x) = \partial f_1 (x) + ... + \partial f_k (x), \quad \forall x \in R^n.</math>
| + | ∂f(x) = ∂f1(x) + · · · + ∂fk(x), ∀x ∈ Rn. |
| | | | |
| | Đ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. | | Đ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 <math>f</math> là một hàm lồi, chính thường trên <math>\mathbb{R}^n</math> và <math>D \subset \mathbb{R}^n</math> là một tập lồi. Nếu bao hàm thức
| + | Đị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 Rn và D ⊂ Rn là một tập lồi. Nếu bao hàm thức |
| | | | |
| − | {{NumBlk|:|<math>0 \in \partial f(\bar{x}) + N_D(\bar{x})</math>|{{EquationRef|6}}}}
| + | 0 ∈ ∂f(¯x) + ND(¯x) (6) |
| | | | |
| − | nghiệm đúng với <math>\bar{x} \in \mathbb{R}^n</math>, thì <math>\bar{x}</math> là nghiệm của <math>(P)</math>. Ngược lại, nếu | + | nghiệm đúng với x¯ ∈ Rn, thì x¯ là nghiệm của (P). Ngược lại, nếu |
| | | | |
| − | {{NumBlk|:|<math>\text{ri}(\text{dom} f) \cap \text{ri}D \ne \empty ,</math>|{{EquationRef|7}}}}
| + | ri(domf) ∩ riD 6= ∅, (7) |
| | | | |
| − | thì ({{EquationNote|6}}) là điều kiện cần và đủ cho <math>\bar{x} \in \mathbb{R}^n</math> là nghiệm của <math>(P)</math>. Nói riêng ra, nếu <math>D = \mathbb{R}^n</math>, thì <math>\bar{x}</math> là một nghiệm của <math>(P)</math> khi và chỉ khi <math>0 \in \partial f(\bar{x})</math>. | + | thì (6) là điều kiện cần và đủ cho x¯ ∈ Rn là nghiệm của (P). Nói riêng ra, nếu D = Rn, thì x¯ là một nghiệm của (P) khi và chỉ khi 0 ∈ ∂f(¯x). |
| | | | |
| − | Bao hàm thức ({{EquationNote|6}}) có nghĩa là tồn tại <math>x^* \in \partial f (\bar{x})</math> và <math>u^* \in N_D(\bar{x})</math> sao cho 0 = x<sup>∗</sup> + u<sup>∗</sup>. Nhận xét rằng ({{EquationNote|7}}) là một điều kiện chính quy cho bài toán quy hạch lồi có dạng <math>(P)</math>. | + | Bao hàm thức (6) có nghĩa là tồn tại x∗ ∈ ∂f(¯x) và u∗ ∈ ND(¯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. | | Đị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. |
| Dòng 179: |
Dòng 177: |
| | ===Điểm Fermat=== | | ===Điểm Fermat=== |
| | | | |
| − | Cho <math>A, B, C</math> là ba điểm trong không gian hai chiều <math>\mathbb{R}^2</math> với các tọa độ tương ứng là | + | Cho A, B, C là ba điểm trong không gian hai chiều R2 với các tọa độ tương ứng là |
| | | | |
| − | :<math>a = (a_1, a_2), b = (b_1, b_2), c = (c_1, c_2).</math>
| + | a = (a1, a2), b = (b1, b2), c = (c1, c2). |
| | | | |
| − | 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 <math>M</math> trong <math>\mathbb{R}^2</math> với các tọa độ <math>\bar{x} = (\bar{x}_1, \bar{x}_2)</math> sao cho tổng khoảng cách từ <math>M</math> tới <math>A, B</math> và <math>C</math> là tối thiểu. Điều đó có nghĩa rằng <math>\bar{x}</math> là một nghiệm của bài toán quy hoạch lồi không có ràng buộc sau: | + | 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 R2 với các tọa độ x¯ = (¯x1, 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 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: |
| | | | |
| − | {{NumBlk|:|<math>\text{min} \{ f(x) := \lVert x - a \rVert + \lVert x - b \rVert + \lVert x - c \rVert : x \in \mathbb{R}^2 \}.</math>|{{EquationRef|8}}}}
| + | min{f(x) := kx − ak + kx − bk + kx − ck : x ∈ R2}. (8) |
| | | | |
| − | Sử dụng định lý Weierstrass và tính lồi chặt của <math>f(x)</math> trên <math>\mathbb{R}^2</math>, ta có thể chứng tỏ rằng ({{EquationNote|8}}) có duy nhất nghiệm; xem Lee, Tam, Yen (2005), tr. 11–13. Để ý rằng <math>f = f_1 + f_2 + f_3</math>, ở đó <math>f_1(x) = \lVert x - a \rVert, f_2(x) = \lVert x - b \rVert, f_3(x) = \lVert x - c \rVert</math>. Theo Định lý 0.0.5, <math>\bar{x}</math> là nghiệm của ({{EquationNote|8}}) khi và chỉ khi <math>0 \in \partial f(\bar{x})</math>. Vì <math>\text{dom} f_i = \mathbb{R}^2 (i = 1, 2 ,3)</math>, sử dụng Định lý 0.0.4 ta có thể viết bao hàm thức cuối dưới dạng | + | 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 |
| | | | |
| − | :<math>0 \in \partial f_1 (\bar{x}) + f_2 (\bar{x}) + f_3 (\bar{x})</math>.
| + | 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 <math>\bar{x}</math> 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: | + | 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: |
| | | | |
| − | # Nếu một trong ba góc của tam giác <math>ABC</math>, ví dụ như góc <math>\hat{A}</math>, là lớn hơn hoặc bằng 120°, thì <math>M \equiv A</math> là nghiệm duy nhất của bài toán đang được xét.
| + | (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. |
| − | # Nếu tất cả các góc của tam giác <math>ABC</math> đều nhỏ hơn 120°, thì nghiệm duy nhất của bài toán là điểm <math>M</math> nhìn các cạnh <math>BC</math>, <math>AC</math> và <math>AB</math> của tam giác <math>ABC</math> dưới cùng một góc 120°(Điểm <math>M</math> đặ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 <math>ABC</math>.)
| |
| | | | |
| − | Trong bài toán <math>(P)</math>, nếu <math>D</math> 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.
| + | (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 |
| | | | |
| − | Chúng ta hãy xét bài toán <math>(P)</math> dưới các giả thiết <math>f : \mathbb{R}^n \to \mathbb{R}</math> là một hàm lồi,
| + | * (Đ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.) |
| | | | |
| − | {{NumBlk|:|<math>D = \{x \in \mathbb{R}^n : g_1(x) \le, ..., g_m(x) \le 0, h_1(x) = 0, ..., h_s(x) = 0\}</math>|{{EquationRef|9}}}}
| + | 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. |
| | | | |
| − | ở đó <math>g_i: \mathbb{R}^n \to \mathbb{R}, i = 1, . . . , m</math>, là các hàm lồi, <math>h_j: \mathbb{R}^n \to \mathbb{R}, j = 1, . . . , s</math> là các hàm affine, nghĩa là tồn tại <math>a_j \in \mathbb{R}^n</math> và <math>\alpha _j \in \mathbb{R}</math> sao cho <math>h_j(x) = \langle a_j, x \rangle + \alpha _j</math> với mọi <math>x \in \mathbb{R}^n</math>. 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 ({{EquationNote|9}}). Để cho gọn, chúng ta sử dụng cách viết hình thức <math>m = 0</math> (tương ứng, <math>s = 0</math>) để 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 ({{EquationNote|9}}).
| + | 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, |
| | | | |
| − | '''Đị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 <math>(P)</math> là bài toán quy hoạch lồi với <math>D</math> được cho bởi ({{EquationNote|9}}). Giả sử rằng các giả thiết đặt lên <math>f, g_i (i = 1, ... , m)</math> và <math>h_j (j = 1, ... s)</math> như đã nói ở trên được thỏa mãn. Giả sử rằng tồn tại véctơ <math>z \in \mathbb{R}^n</math> sao cho
| + | D = {x ∈ Rn: g1(x) ≤ 0, . . . , gm(x) ≤ 0, h1(x) = 0, . . . , hs(x) = 0}, (9) |
| | | | |
| − | {{NumBlk|:|<math>g_i(z) < 0 \text{ với } i = 1, ..., m \quad \text{và} \quad h_j (z) = 0 \text{ với } j = 1, ..., s</math>|{{EquationRef|10}}}}
| + | ở đó 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). |
| | | | |
| − | Khi đó, <math>\bar{x}</math> là một nghiệm của <math>(P)</math> khi và chỉ khi tồn tại <math>m + s</math> số thực <math>\lambda _1, ... , \lambda _m, \mu _1, ... , \mu _s,</math> được gọi là các nhân tử Langrange tương ứng với <math>\bar{x}</math>, sao cho các điều skiện Kuhn-Tucker sau đây được thỏa mãn:
| + | Đị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 |
| | | | |
| − | # <math>\lambda _i \ge 0, g_i(\bar{x}) \le 0 \text{ và } \lambda _i f _i(\bar{x}) = 0 \text{ với } i = 1, ... , m,</math>
| + | gi(z) < 0 với i = 1, . . . , m và hj (z) = 0 với j = 1, . . . , s. (10) |
| − | # <math>h _j (\bar{x}) = 0 \text{ với } j = 1, ... , s,</math>
| |
| − | # <math>0 \in \partial f(\bar{x}) + \sum_{i = 1}^{m} \lambda _i \partial g _i(\bar{x}) + \sum_{j = 1}^{s} \mu _j a_j.</math>
| |
| | | | |
| − | Nhận xét rằng ({{EquationNote|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 <math>s = 0</math> thì nó trở thành
| + | 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: |
| | | | |
| − | :<math> \exists z \in \mathbb{R}^n \text{ s.t. } g_i(z) < 0 \text{ với } i = 1, ..., m \quad \text{(Điều kiện Slater)}</math>
| + | (a) λi ≥ 0, gi(¯x) ≤ 0 và λifi(¯x) = 0 với i = 1, . . . , m, |
| | | | |
| − | Nếu <math>m = 0</math> thì ({{EquationNote|10}}) tương đương với đòi hỏi rằng <math>D</math> là khác rỗng. Trên thực tế, trong trường hợp đó, có thể bỏ qua điều kiện ({{EquationNote|10}}) trong phát biểu của Định lý 0.0.6. | + | (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== | | ==Trơn và không trơn== |
| | ===Định nghĩa=== | | ===Định nghĩa=== |
| − | Để cho gọn, nếu <math>f : \mathbb{R}^n \to R</math> là hàm khả vi Fréchet liên tục, thì ta nói rằng <math>f</math> là một <math>\text{hàm } C^1</math> (tức là hàm thuộc lớp <math>C^1</math>). | + | Để 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 <math>(P)</math> là bài toán quy hoạch toán học trơn nếu <math>f : \mathbb{R}^n \to \mathbb{R}</math> là hàm <math>C^1</math> và <math>D</math> biểu diễn được dưới dạng ({{EquationNote|9}}), ở đó <math>g_i: \mathbb{R}^n \to \mathbb{R} (i = 1, . . . , m)</math> và <math>h_j : \mathbb{R}^n \to \mathbb{R} (j = 1, . . . , s)</math> là các hàm <math>C^1</math>. Ngược lại, <math>(P)</math> được gọi là bài toán quy hoạch toán học không trơn. | + | 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=== | | ===Hàm Lipschitz địa phương=== |
| | | | |
| − | Một hàm <math>f : \mathbb{R}^n \to \mathbb{R}</math> được gọi là Lipschitz địa phương tại <math>\bar{x} \in \mathbb{R}^n</math> nếu tồn tại hằng số <math>l \ge 0</math> và lân cận <math>U</math> của <math>\bar{x}</math> sao cho | + | 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 |
| | | | |
| − | {{NumBlk|:|<math>\lVert f(x') - f(x) \rVert \le l \lVert x' - x \rVert \quad \text{ với mọi } x, x' \in U</math>|{{EquationRef|11}}}}
| + | |f(x0) − f(x)| ≤ `kx0 − xk với mọi x, x0 thuộc U. (11) |
| | | | |
| − | Nếu <math>f</math> là Lipschitz địa phương tại mỗi điểm thuộc <math>\mathbb{R}^n</math>, thì <math>f</math> được gọi là hàm số Lipschitz địa phương trên <math>\mathbb{R}^n</math>. | + | 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 ({{EquationNote|11}}) đúng với mọi <math>x, x' /in C</math>, ở đó <math>C</math> là một tập con của <math>\mathbb{R}^n</math>, thì ta nói <math>f</math> là Lipschitz trên <math>C</math> với hệ số Lipschitz <math>l</math>. | + | 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=== | | ===Đạo hàm theo hướng suy rộng theo nghĩa Clarke=== |
| | | | |
| − | Nếu <math>f</math> là Lipschitz địa phương tại <math>\bar{x}</math>, thì đạo hàm theo hướng suy rộng theo nghĩa Clarke của <math>f</math> tại <math>\bar{x}</math> theo hướng <math>v \in \mathbb{R}^n</math> được định nghĩa bằng công thức | + | 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 |
| | | | |
| − | :<math>f^0(\bar{x}; v) := \lim_{x \to \bar{x}} \sup_{t \downarrow 0} \frac{f(x + tv) - f(x)}{t}</math>
| + | 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. |
| − | | |
| − | :<math>\qquad \qquad = sup \Bigl\{ \xi \in \mathbb{R} : \forall \text{ các dãy } x_k \to \bar{x} \text{ và } t_k \to 0+ \text{ sao cho } \xi = \lim_{k \to + \infty} \frac{f(x_k + t_kv) - f(x_k)}{t_k} \Bigr\}.</math>
| |
| | | | |
| | ===Dưới vi phân Clarke=== | | ===Dưới vi phân Clarke=== |
| | | | |
| − | ''Dưới vi phân Clarke'' của <math>f</math> tại <math>\bar{x}</math> được cho bởi công thức
| + | Dưới vi phân Clarke của f tại x¯ được cho bởi công thức |
| − | | |
| − | :<math>\partial f (\bar{x}) := \{ x^* \in \mathbb{R}^n : f^0 (\bar{x}; v) \ge \langle x^*, v \rangle \text{ với mọi } v \in \mathbb{R}^n \}</math>
| |
| − | | |
| − | '''Đị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 <math>f : \mathbb{R}^n \to \mathbb{R}</math> là một hàm số thực. Khi đó, các khẳng định sau đây nghiệm đúng:
| + | ∂f(¯x) := {x∗ ∈ Rn: f0(¯x; v) ≥ hx∗, vi với mọi v ∈ Rn}. |
| | | | |
| − | ''(a) Nếu <math>f</math> là Lipschitz địa phương tại <math>\bar{x} \in \mathbb{R}^n</math>, thì
| + | Đị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: |
| | | | |
| − | :<math>f^0(\bar{x};v) = \max \{ \langle x^*, v \rangle : x^* \in \partial f (\bar{x}) \}</math>
| + | (a) Nếu f là Lipschitz địa phương tại x¯ ∈ Rn, thì |
| | | | |
| − | ''với mọi v ∈ Rn.
| + | f0(¯x; v) = max{hx∗, vi : x∗ ∈ ∂f(¯x)} |
| | | | |
| − | ''(b) Nếu <math>f</math> là hàm <math>C^1</math>, thì <math>f</math> là hàm số Lipschitz địa phương và
| + | với mọi v ∈ Rn. |
| | | | |
| − | :<math>\partial f (\bar{x}) = \{ \nabla f(\bar{x}) \}, f^0 (\bar{x};v) = \langle \nabla f(\bar{x}), v \rangle \text{ với mọi } \bar{x} \in \mathbb{R}^n \text{ và } v \in \mathbb{R}^n.</math>
| + | (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 <math>f</math> là lồi, thì <math>f</math> là hàm số Lipschitz địa phương và, với mỗi <math>\bar{x} \in \mathbb{R}^n</math>, dưới vi phân Clarke <math>\partial f(\bar{x})</math> trùng với dưới vi phân của <math>f</math> tại <math>\bar{x}</math> 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, <math>f^0(\bar{x}; v) = f^\prime (\bar{x}; v) \text{ với mỗi } v \in \mathbb{R}^n</math>
| + | (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 <math>f^0 (\bar{x};v)</math> tồn tại (xem Định lý 0.0.2). | + | 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=== | | ===Nón tiếp tuyến Clarke=== |
| | | | |
| − | Cho <math>C \subset \mathbb{R}^n</math> là tập con khác rỗng. Nón tiếp tuyến Clarke <math>T_C(x)</math> của <math>C</math> tại <math>x \in C</math> là tập hợp tất cả các véctơ <math>v \in \mathbb{R}^n</math> thỏa mãn <math>d^0_C (x;v) = 0</math>, ở đó <math>d^0_C (x;v)</math> ký hiệu đạo hàm theo hướng suy rộng theo nghĩa Clarke của hàm số Lipschitz | + | 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 |
| | | | |
| − | :<math>d_C(z) := \text{inf} \{ \lVert y - z \rVert : y \in C \}</math>
| + | dC(z) := inf{ky − zk : y ∈ C} |
| | | | |
| − | tại <math>x</math> theo hướng <math>v</math>. | + | tại x theo hướng v. |
| | | | |
| | ===Nón pháp tuyến Clarke=== | | ===Nón pháp tuyến Clarke=== |
| | | | |
| − | ''Nón pháp tuyến Clarke'' <math>N_C(x)</math> của <math>C</math> tại <math>x</math> được định nghĩa là nón đối ngẫu của <math>T_C(x)</math>, tức là
| + | 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à |
| | | | |
| − | :<math>N_C(x) = \{ x^* \in \mathbb{R}^n : \langle x^*, v \rangle \le 0 \text{ với mọi } v \in T_C(x) \}.</math>
| + | 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:
| + | Đị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. | | (a) NC(x) = n∪t≥0 t∂dC(x)o. |