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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle (-2, 0)} , còn tập nghiệm địa phương gồm hai điểm: $(-2,0)$ và Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle (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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f_1(x) = -x + 2, f_2(x) = x + \frac{3}{2}} với mọi $x\in \mathbb {R}$. Định nghĩa Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f(x) = \text{min}{f_1(x), f_2(x)}} và chọn Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle D = [0, 2] \subset R} . Với hàm Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} và tập Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle D} đó, chúng ta có

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \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, Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} là hàm không lồi và Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 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ố Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f : \mathbb{R}^n \to \bar{\mathbb{R}}} , tập hợp

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x} \in \text{dom}f} và một véctơ Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle v \in \mathbb{R}^n} , nếu giới hạn

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 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ị Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle +\infty} và Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle -\infty} ) tồn tại, thì Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} được gọi là khả vi theo hướng tại Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x}} theo hướng Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle v} và giá trị Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f'(\bar{x}; v)} được gọi là đạo hàm theo hướng của Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} tại Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x}} theo hướng Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle v} . Nếu Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f'(\bar{x}; v)} tồn tại với mọi Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle v \in \mathbb{R}^n} , thì Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} được gọi là khả vi theo hướng tại Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x}} .

Trong hai định lý tiếp theo đây, Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x} \in \mathbb{R}^n} và Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \delta > 0} là điểm và số thực sao cho hình cầu mở Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle B(\bar{x}, \delta)} chứa trong Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \text{dom}f} , thì phần hạn chế của Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} trên Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x} \in \text{dom}f} , thì với mỗi Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle v \in \mathbb{R}^n} giới hạn

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f'(\bar{x};\ v) := \lim_{t \downarrow 0} \frac{f(\bar{x} + tv) - f(\bar{x})}{t}}

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

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle N_D(\bar{x})} của tập lồi Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle D \subset \mathbb{R}^n} tại một điểm Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x} \in \mathbb{R}^n} được cho bởi công thức

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle N_D(\bar{x}) = \begin{cases} \{ 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} }

Dưới vi phân

Dưới vi phân Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \partial f(\bar{x})} của một hàm lồi Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f : R^n \to \mathbb{R}} tại một điểm Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x} \in \mathbb{R}n} được định nghĩa bằng công thức

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \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}

Phần trong tương đối

Tập con Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle M \subset \mathbb{R}^n} được gọi là một tập affine (a-phin) nếu Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle tx + (1 - t)y \in M} với mọi Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle x \in M, y \in M} và Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle t \in R} . Đối với một Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle D \subset \mathbb{R}^n} , bao affine affKhông thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle D of D} là tập affine nhỏ nhất chứa Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle D} . Phần trong tương đối của Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle D} được xác định bởi công thức

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} là một hàm lồi trên Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle R^n} . Nếu Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle x \notin \text{dom}f} , thì Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \partial f(x)} là rỗng. Nếu Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle x \in \text{ri}(\text{dom}f)} , thì Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \partial f(x)} là khác rỗng và

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f'(x;v) = \sup \{ \langle x^*, v \rangle : x^* \in \partial f(x) \}, \quad \forall v \in R^n. }

Ngoài ra, Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \partial f(x)} là tập khác rỗng và giới nội khi và chỉ khi

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle x \in \text{int}(\text{dom} f);}

trong trường hợp đó, Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f'(x; v)} là hữu hạn với mỗi Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f = f_1 + ... + f_k} , ở đó Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f_1 + ... + f_k} là các hàm lồi, chính thường trên Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \mathbb{R}^n} . Nếu

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bigcap_{i = 1}^{k}\text{ri}(\text{dom} f_i) \ne \empty,}

thì

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} là một hàm lồi, chính thường trên Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \mathbb{R}^n} và Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle D \subset \mathbb{R}^n} là một tập lồi. Nếu bao hàm thức

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 0 \in \partial f(\bar{x}) + N_D(\bar{x})}

(6)

nghiệm đúng với Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x} \in \mathbb{R}^n} , thì Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x}} là nghiệm của Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle (P)} . Ngược lại, nếu

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \text{ri}(\text{dom} f) \cap \text{ri}D \ne \empty ,}

(7)

thì (6) là điều kiện cần và đủ cho Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x} \in \mathbb{R}^n} là nghiệm của Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle (P)} . Nói riêng ra, nếu Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle D = \mathbb{R}^n} , thì Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x}} là một nghiệm của Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle (P)} khi và chỉ khi Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 0 \in \partial f(\bar{x})} .

Bao hàm thức (6) có nghĩa là tồn tại Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle x^* \in \partial f (\bar{x})} và Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle (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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle A, B, C} là ba điểm trong không gian hai chiều Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \mathbb{R}^2} với các tọa độ tương ứng là

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle M} trong $\mathbb {R} ^{2}$ với các tọa độ Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x} = (\bar{x}_1, \bar{x}_2)} sao cho tổng khoảng cách từ Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle M} tới $A,B$ và Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle C} là tối thiểu. Điều đó có nghĩa rằng Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f(x)} trên Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \mathbb{R}^2} , 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=f_{1}+f_{2}+f_{3}$, ở đó $f_{1}(x)=\lVert x-a\rVert ,f_{2}(x)=\lVert x-b\rVert ,f_{3}(x)=\lVert x-c\rVert$. Theo Định lý 0.0.5, Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x}} là nghiệm của (8) khi và chỉ khi Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 0 \in \partial f(\bar{x})} . Vì Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \text{dom} f_i = \mathbb{R}^2 (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

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 0 \in \partial f_1 (\bar{x}) + f_2 (\bar{x}) + f_3 (\bar{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 ${\bar {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:

1. Nếu một trong ba góc của tam giác Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle ABC} , ví dụ như góc Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \hat{A}} , là lớn hơn hoặc bằng 120°, thì Không thể phân tích cú pháp (Lỗi chuyển đổi. Máy chủ (“https://en.wikipedia.org/api/rest_”) phản hồi: “Cannot get mml. Server problem.”): {\displaystyle M\equiv A} là nghiệm duy nhất của bài toán đang được xét.
2. Nếu tất cả các góc của tam giác Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle ABC} đều nhỏ hơn 120°, thì nghiệm duy nhất của bài toán là điểm Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle M} nhìn các cạnh $BC$, Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle AC} và Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle AB} của tam giác $ABC$ dưới cùng một góc 120°(Điểm Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle ABC} .)

Trong bài toán $(P)$, nếu Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle (P)} dưới các giả thiết $f:\mathbb {R} ^{n}\to \mathbb {R}$ là một hàm lồi,

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle D = \{x \in \mathbb{R}^n : g_1(x) \le, ..., g_m(x) \le 0, h_1(x) = 0, ..., h_s(x) = 0\}}

(9)

ở đó Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle g_i: \mathbb{R}^n \to \mathbb{R}, i = 1, . . . , m} , là các hàm lồi, $h_{j}:\mathbb {R} ^{n}\to \mathbb {R} ,j=1,...,s$ là các hàm affine, nghĩa là tồn tại $a_{j}\in \mathbb {R} ^{n}$ và Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \alpha _j \in \mathbb{R}} sao cho Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle h_j(x) = \langle a_j, x \rangle + \alpha _j} với mọi Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle x \in \mathbb{R}^n} . 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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle m = 0} (tương ứng, Không thể phân tích cú pháp (Lỗi chuyển đổi. Máy chủ (“https://en.wikipedia.org/api/rest_”) phản hồi: “Cannot get mml. Server problem.”): {\displaystyle 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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle (P)} là bài toán quy hoạch lồi với Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle D} được cho bởi (9). Giả sử rằng các giả thiết đặt lên $f,g_{i}(i=1,...,m)$ và Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle h_j (j = 1, ... s)} như đã nói ở trên được thỏa mãn. Giả sử rằng tồn tại véctơ Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle z \in \mathbb{R}^n} sao cho

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle g_i(z) < 0 \text{ với } i = 1, ..., m \quad \text{và} \quad h_j (z) = 0 \text{ với } j = 1, ..., s}

(10)

Khi đó, Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x}} là một nghiệm của Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle (P)} khi và chỉ khi tồn tại Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle m + s} số thực Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \lambda _1, ... , \lambda _m, \mu _1, ... , \mu _s,} được gọi là các nhân tử Langrange tương ứng với Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x}} , sao cho các điều skiện Kuhn-Tucker sau đây được thỏa mãn:

1. Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \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,}
2. $h_{j}({\bar {x}})=0{\text{ với }}j=1,...,s,$
3. Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 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.}

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

$\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)}}$

Nếu Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle m = 0} thì (10) tương đương với đòi hỏi rằng Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle 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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f : \mathbb{R}^n \to R} là hàm khả vi Fréchet liên tục, thì ta nói rằng $f$ là một ${\text{hàm }}C^{1}$ (tức là hàm thuộc lớp $C^{1}$).

Ta gọi Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle (P)} là bài toán quy hoạch toán học trơn nếu Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f : \mathbb{R}^n \to \mathbb{R}} là hàm Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle C^1} và $D$ biểu diễn được dưới dạng (9), ở đó Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle g_i: \mathbb{R}^n \to \mathbb{R} (i = 1, . . . , m)} và $h_{j}:\mathbb {R} ^{n}\to \mathbb {R} (j=1,...,s)$ là các hàm Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle C^1} . 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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f : \mathbb{R}^n \to \mathbb{R}} được gọi là Lipschitz địa phương tại ${\bar {x}}\in \mathbb {R} ^{n}$ nếu tồn tại hằng số Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle l \ge 0} và lân cận Không thể phân tích cú pháp (Lỗi chuyển đổi. Máy chủ (“https://en.wikipedia.org/api/rest_”) phản hồi: “Cannot get mml. Server problem.”): {\displaystyle U} của Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x}} sao cho

$\lVert f(x')-f(x)\rVert \leq l\lVert x'-x\rVert \quad {\text{ với mọi }}x,x'\in U$

(11)

Nếu $f$ là Lipschitz địa phương tại mỗi điểm thuộc Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \mathbb{R}^n} , thì Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} được gọi là hàm số Lipschitz địa phương trên $\mathbb {R} ^{n}$.

Nếu bất đẳng thức trong (11) đúng với mọi Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle x, x' /in C} , ở đó $C$ là một tập con của $\mathbb {R} ^{n}$, thì ta nói $f$ là Lipschitz trên $C$ với hệ số Lipschitz $l$.

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

Nếu Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} là Lipschitz địa phương tại Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x}} , thì đạo hàm theo hướng suy rộng theo nghĩa Clarke của Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} tại Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x}} theo hướng Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle v \in \mathbb{R}^n} được định nghĩa bằng công thức

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f^0(\bar{x}; v) := \lim_{x \to \bar{x}} \sup_{t \downarrow 0} \frac{f(x + tv) - f(x)}{t}}

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \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\}.}

Dưới vi phân Clarke

Dưới vi phân Clarke của Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} tại Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x}} được cho bởi công thức

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

Đị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:\mathbb {R} ^{n}\to \mathbb {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 Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x} \in \mathbb{R}^n} , thì

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f^0(\bar{x};v) = \max \{ \langle x^*, v \rangle : x^* \in \partial f (\bar{x}) \}}

với mọi v ∈ Rn.

(b) Nếu Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} là hàm Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle C^1} , thì Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} là hàm số Lipschitz địa phương và

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \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.}

(c) Nếu Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} là lồi, thì Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} là hàm số Lipschitz địa phương và, với mỗi Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \bar{x} \in \mathbb{R}^n} , dưới vi phân Clarke Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle \partial f(\bar{x})} trùng với dưới vi phân của Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle f} tại ${\bar {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, $f^{0}({\bar {x}};v)=f^{\prime }({\bar {x}};v){\text{ với mỗi }}v\in \mathbb {R} ^{n}$

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

Nón tiếp tuyến Clarke

Cho $C\subset \mathbb {R} ^{n}$ là tập con khác rỗng. Nón tiếp tuyến Clarke $T_{C}(x)$ của $C$ tại Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle x \in C} là tập hợp tất cả các véctơ Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle v \in \mathbb{R}^n} thỏa mãn Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle d^0_C (x;v) = 0} , ở đó Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle d^0_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

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle d_C(z) := \text{inf} \{ \lVert y - z \rVert : y \in C \}}

tại Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle x} theo hướng $v$.

Nón pháp tuyến Clarke

Nón pháp tuyến Clarke Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle N_C(x)} của $C$ tại Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle x} được định nghĩa là nón đối ngẫu của $T_{C}(x)$, tức là

Không thể phân tích cú pháp (MathML hoặc SVG/PNG (khuyến khích các trình duyệt và công cụ trợ năng hiện đại): Phản hồi không hợp lệ (“Math extension cannot connect to Restbase.”) từ máy chủ “https://en.wikipedia.org/api/rest_v1/”:): {\displaystyle N_C(x) = \{ x^* \in \mathbb{R}^n : \langle x^*, v \rangle \le 0 \text{ với mọi } v \in T_C(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.