Định lýĐã chứng minh

Cực tiểu địa phương của hàm lồi là cực tiểu toàn cục

Phát biểu

Cho $f : C \to \mathbb{R}$ là hàm lồi trên tập lồi $C \subseteq \mathbb{R}^n$ . Nếu $x^* \in C$ là cực tiểu địa phương của $f$ thì $x^*$ cũng là cực tiểu toàn cục của $f$ trên $C$ . Nếu $f$ lồi chặt thì cực tiểu toàn cục, khi tồn tại, là duy nhất.

Vì sao đúng?

Đồ thị hàm lồi không bao giờ nằm dưới đoạn thẳng nối hai điểm bất kỳ trên nó, nên không có 'thung lũng' tách biệt — toàn bộ đồ thị cong lên như một cái bát duy nhất. Nếu bạn đứng ở đáy một chỗ trũng nhỏ, tính lồi buộc mọi hướng rời khỏi đó đều đi lên, và vì điều này đúng dọc theo cả đoạn thẳng nối tới bất kỳ điểm nào khác trong $C$ , nên không điểm xa nào có thể thấp hơn.

Phác thảo chứng minh

Giả sử $x^*$ là cực tiểu địa phương nhưng không toàn cục: tồn tại $y \in C$ với $f(y) < f(x^*)$ . Với $t \in (0,1)$ đủ nhỏ, tính lồi cho $f((1-t)x^* + ty) \le (1-t)f(x^*) + t f(y) < f(x^*)$ . Nhưng các điểm $(1-t)x^* + ty$ nằm gần $x^*$ tùy ý khi $t$ nhỏ, mâu thuẫn với việc $x^*$ là cực tiểu địa phương. Vậy không tồn tại $y$ như thế.

Chủ đề chứa định lý này

Tối ưu lồi

Định lý liên quan

Điều kiện Karush–Kuhn–Tucker Định lý đối ngẫu mạnh trong quy hoạch tuyến tính

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

Stephen Boyd, Lieven Vandenberghe (2004). Convex Optimization
R. Tyrrell Rockafellar (1970). Convex Analysis