Tối ưu lồi

Giả sử $x^\star$ chỉ là cực tiểu địa phương và tồn tại $y \in C$ với $f(y) < f(x^\star)$. Tính lồi buộc $f$ phải nằm dưới đoạn thẳng từ $x^\star$ đến $y$ tại các điểm gần $x^\star$ tùy ý: với $\theta > 0$ nhỏ, $f(\theta y + (1-\theta) x^\star) \le \theta f(y) + (1-\theta) f(x^\star) < f(x^\star)$. Điều này mâu thuẫn với việc $x^\star$ là cực tiểu địa phương, vì các điểm $\theta y + (1-\theta)x^\star$ tiến gần $x^\star$ tùy ý.

Giả sử $x^\star \in C$ là cực tiểu địa phương, nghĩa là tồn tại bán kính $r > 0$ sao cho $f(z) \ge f(x^\star)$ với mọi $z \in C$ thỏa mãn $\|z - x^\star\| \le r$. Giả sử phản chứng rằng tồn tại điểm $y \in C$ sao cho $f(y) < f(x^\star)$.

Với mọi $\theta \in (0, 1)$, tính lồi của tập hợp và hàm số bảo đảm $z_\theta = \theta y + (1 - \theta)x^\star \in C$ và $f(z_\theta) \le \theta f(y) + (1 - \theta)f(x^\star) = f(x^\star) + \theta(f(y) - f(x^\star)) < f(x^\star)$.

Do $\|z_\theta - x^\star\| = \theta \|y - x^\star\|$, việc chọn $0 < \theta \le \dfrac{r}{\|y - x^\star\|}$ bảo đảm $\|z_\theta - x^\star\| \le r$ đồng thời $f(z_\theta) < f(x^\star)$, mâu thuẫn với giả thiết cực tiểu địa phương.

Điều kiện độ lệch bù nói rằng một ràng buộc bất đẳng thức $g_i(x) \le 0$ tại $x^\star$ hoặc không chặt ($g_i(x^\star) < 0$, nên biên không đẩy vào $x^\star$ và nhân tử của nó $\lambda_i^\star = 0$) hoặc chặt ($g_i(x^\star) = 0$, nên bức tường biên có thể đẩy lại với lực $\lambda_i^\star \ge 0$). Khi đó tính dừng phát biểu rằng $-\nabla f(x^\star)$ được cân bằng bởi một tổ hợp không âm của các pháp tuyến ngoài $\nabla g_i(x^\star)$ của những bức tường đang chặt.

Trước hết, giả sử $(x^\star, \lambda^\star, \nu^\star)$ thỏa mãn điều kiện KKT. Vì $\lambda_i^\star \ge 0$ và các hàm ràng buộc là lồi hoặc affine, hàm Lagrange $x \mapsto \mathcal{L}(x, \lambda^\star, \nu^\star)$ là hàm lồi, nên điều kiện dừng $\nabla_x \mathcal{L}(x^\star, \lambda^\star, \nu^\star) = 0$ suy ra điểm đang xét cực tiểu hóa hàm Lagrange trên toàn không gian.

Với mọi điểm khả thi $x$ thỏa $g_i(x) \le 0$ và $h_j(x) = 0$, điều kiện độ lệch bù $\lambda_i^\star g_i(x^\star) = 0$ cho chuỗi bất đẳng thức $f(x^\star) = \mathcal{L}(x^\star, \lambda^\star, \nu^\star) \le \mathcal{L}(x, \lambda^\star, \nu^\star) = f(x) + \sum_{i=1}^m \lambda_i^\star g_i(x) + \sum_{j=1}^p \nu_j^\star h_j(x) \le f(x)$, chứng minh tính tối ưu toàn cục.

Ngược lại, dưới điều kiện Slater, đối ngẫu mạnh bảo đảm tồn tại các nhân tử đối ngẫu tối ưu sao cho $f(x^\star) = g(\lambda^\star, \nu^\star) = \inf_x \mathcal{L}(x, \lambda^\star, \nu^\star) \le \mathcal{L}(x^\star, \lambda^\star, \nu^\star) = f(x^\star) + \sum_{i=1}^m \lambda_i^\star g_i(x^\star) \le f(x^\star)$. Cả hai bất đẳng thức trong chuỗi này đều phải là đẳng thức, từ đó buộc điều kiện dừng và độ lệch bù phải thỏa mãn với mọi ràng buộc.

Quy hoạch tuyến tính là bài toán lồi với tập khả thi dạng đa diện; đối với các ràng buộc đa diện thì không cần giả thiết điểm trong, và định lý siêu phẳng tách (bổ đề Farkas) bảo đảm tồn tại nhân tử đối ngẫu $y^\star$ với độ lệch đối ngẫu bằng 0. Đối với bài toán lồi tổng quát, đối ngẫu mạnh đúng bất cứ khi nào điều kiện Slater được thỏa mãn.

Với mọi vectơ khả thi nguyên thủy thỏa $Ax = b$, $x \ge 0$ và mọi vectơ khả thi đối ngẫu thỏa $A^\top y \le c$, lấy tích vô hướng cho ta bất đẳng thức đối ngẫu yếu: $b^\top y = (Ax)^\top y = x^\top(A^\top y) \le x^\top c = c^\top x$.

Lập hàm Lagrange $\mathcal{L}(x, y, s) = c^\top x + y^\top(b - Ax) - s^\top x = b^\top y + (c - A^\top y - s)^\top x$ với nhân tử $s \ge 0$. Lấy cận dưới đúng theo biến nguyên thủy không ràng buộc chỉ cho giá trị đối ngẫu hữu hạn khi $c - A^\top y - s = 0$, khôi phục ràng buộc đối ngẫu và hàm mục tiêu đối ngẫu $g(y, s) = b^\top y$.

Nếu $x^\star$ là nghiệm tối ưu nguyên thủy với giá trị $p^\star = c^\top x^\star$, bổ đề Farkas (tách siêu phẳng cho nón đa diện) bảo đảm tồn tại vectơ $y^\star$ thỏa $A^\top y^\star \le c$ và $b^\top y^\star \ge p^\star$. Kết hợp với đối ngẫu yếu buộc $b^\top y^\star = c^\top x^\star$.