Điều kiện bậc nhất so sánh hàm với các tiếp tuyến của nó, và để dùng được, ta vẫn phải xét từng cặp điểm $x,y$. Nếu hàm có đạo hàm bậc hai, câu chuyện gọn hơn nhiều. Tính lồi trở thành một phép kiểm tra tại từng điểm: Tại mỗi $x$, phải . Đây là công cụ được dùng nhiều nhất khi cần nhận diện một cụ thể.

Nhưng còn cho biết nhiều hơn một câu trả lời có hoặc không. Nó đo độ cong của hàm theo từng hướng, cho biết hàm có dạng cái bát, cái máng hay cái yên ngựa quanh mỗi điểm, và các trị riêng của nó quyết định một thuật toán như phương pháp chạy nhanh hay chậm. Lần lượt từng vai trò ấy sẽ được làm rõ dưới đây.

1. Phát biểu

Định lý. Giả sử $f$ khả vi hai lần, nghĩa là $\mathrm{dom}f$ mở và ${\mathrm{\nabla }}^{2}f$ tồn tại tại mọi điểm của nó. Khi đó $f$ lồi khi và chỉ khi $\mathrm{dom}f$ lồi và

$${\mathrm{\nabla }}^{2}f(x)⪰0\mathrm{\forall }x\in \mathrm{dom}f.$$

Với hàm một biến, điều kiện là $f^{″}(x)\ge 0$ trên một khoảng, tức đạo hàm $f^{\prime }$ không giảm. Điều kiện này không mới: Nó là tính đơn điệu của ở chủ đề trước, phát biểu lại qua đạo hàm của đạo hàm. Dưới góc nhìn hình học, điều kiện ${\mathrm{\nabla }}^{2}f(x)⪰0$ phản ánh việc đồ thị luôn có độ cong hướng lên tại $x$. Tương tự, $f$ lõm khi và chỉ khi miền xác định lồi và ${\mathrm{\nabla }}^{2}f(x)⪯0$ tại mọi điểm.

Hai cụm từ "mọi điểm" và "miền lồi" đều có ý nghĩa tiên quyết. Hàm $1/x^2$ có $f^{″}(x)=6/x^4>0$ tại mọi điểm thuộc miền xác định, nhưng miền xác định gồm hai khoảng mở rời nhau $(-\mathrm{\infty },0)\cup (0,\mathrm{\infty })$, không phải là một , nên không lồi. Ở chiều ngược lại, một hàm có gần như khắp nơi, chỉ cần vi phạm trên một dải hẹp, cũng đủ làm mất tính lồi toàn cục, như mô phỏng ở mục 2 sẽ làm sáng tỏ.

2. Độ cong theo một hướng

Đặt $g(t)=f(x+tv)$, hàm hạn chế của $f$ lên đường thẳng qua $x$ theo hướng $v$. Áp dụng quy tắc dây chuyền hai lần:

$$g^{\prime }(t)=\mathrm{\nabla }f(x+tv{)}^{T}v,g^{″}(t)=v^T{\mathrm{\nabla }}^{2}f(x+tv)v.$$

Tại $t=0$, ta được $g^{″}(0)=v^T{\mathrm{\nabla }}^{2}f(x)v$. Vậy dạng toàn phương của đo độ cong của đồ thị khi đi qua $x$ theo hướng $v$. Điều kiện ${\mathrm{\nabla }}^{2}f(x)⪰0$ nói rằng không có đường thẳng nào qua $x$ mà dọc theo nó đồ thị cong xuống.

Phân tích phổ cho thấy độ cong thay đổi thế nào khi xoay hướng. Theo định lý phổ cho đối xứng thực, ta có thể khai triển tường minh thành:

$${\mathrm{\nabla }}^{2}f(x)=\sum _{i=1}^n{\lambda }_i{q}_i{q}_i^T={\lambda }_1{q}_1{q}_1^T+{\lambda }_2{q}_2{q}_2^T+\cdots +{\lambda }_n{q}_n{q}_n^T$$

với $\{q_1,q_2,\dots ,q_n\}$ là hệ riêng trực chuẩn ứng với các trị riêng ${\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n$. Với vector hướng đơn vị $\parallel v{\parallel }_2=1$, ta biểu diễn $v$ qua cơ sở trực chuẩn $v=\sum _{i=1}^n(q_i^{T}v)q_i$. Khi đó dạng toàn phương trở thành:

$$\begin{array}{rl}{v}^T{\mathrm{\nabla }}^{2}f(x)v& =\sum _{i=1}^n{\lambda }_i(q_i^{T}v{)}^2={\lambda }_1(q_1^{T}v{)}^2+\cdots +{\lambda }_n(q_n^{T}v{)}^2,\\ \sum _{i=1}^n(q_i^{T}v{)}^2& =(q_1^{T}v{)}^2+\cdots +(q_n^{T}v{)}^2=\parallel v{\parallel }_2^2=1.\end{array}$$

Độ cong theo hướng $v$ chính là một (trung bình có trọng số) của các trị riêng với các trọng số không âm $(q_i^{T}v{)}^2\ge 0$ có tổng bằng 1. Vì vậy, độ cong luôn nằm giữa trị riêng nhỏ nhất ${\lambda }_1$ và trị riêng lớn nhất ${\lambda }_n$, đồng thời đạt hai giá trị biên đó đúng khi $v$ là riêng tương ứng. khi và chỉ khi trị riêng nhỏ nhất không âm (${\lambda }_{min}\ge 0$), tức hướng "cong ít nhất" cũng không hề cong xuống.

Với hàm hai biến, dấu của hai trị riêng cho ta bốn hình dạng cơ bản của đồ thị quanh một điểm:

Hai trị riêng	Hình dạng quanh $x$	Tương thích với tính lồi
cùng dương	cái bát, cong lên theo mọi hướng	có
một dương, một bằng 0	cái máng, phẳng dọc một hướng	có
một dương, một âm	cái yên ngựa	không
cùng âm	cái bát úp	không

Tính lồi hỏng ở đâu: bản đồ Hessian

vùng Hessian có trị riêng âmhướng cong lênhướng có độ cong 0

Hàm f = x₁² + x₁x₂ + 2x₂²log(e^x₁ + e^x₂)x₁²/x₂ (x₂ > 0)(x₁² − 1)² + x₂²0.4(x₁² + x₂²) + cos(2x₁)x₁² + 3x₁x₂ + x₂²

Tại x = (0.30, 1.00): ∇²f(x) = [[−2.92, 0.00], [0.00, 2.00]], hai trị riêng 2.000 và −2.920.

Hessian không xác định: cong lên theo hướng (0.00, 1.00), cong xuống theo hướng (−1.00, 0.00), như một cái yên ngựa.

Trong khung nhìn có những điểm mà Hessian có trị riêng âm (vùng đỏ). Chỉ cần một điểm như vậy, hàm đã không lồi.

Gợi ý thao tác

1. Với (x₁² − 1)² + x₂², dải đỏ nằm giữa hai đường thẳng đứng nào? Tính 12x₁² − 4 để kiểm tra.
2. Với x₁²/x₂, kéo x đi khắp nửa mặt phẳng trên. Hướng có độ cong bằng 0 luôn chỉ về đâu so với gốc tọa độ?
3. Với log(e^x₁ + e^x₂), hướng có độ cong bằng 0 là hướng nào? Kết quả này khớp với điều gì đã thấy ở chủ đề hàm lồi?
4. Với x₁² + 3x₁x₂ + x₂², vì sao cả khung đều đỏ dù hai phần tử trên đường chéo của Hessian đều dương?

Mô phỏng tô đỏ những điểm mà có trị riêng âm. Với $(x_1^2-1{)}^2+x_2^2$, Hessian là $\mathrm{diag}(12x_1^2-4,2)$, nên vùng đỏ đúng là dải $|x_1|<1/\sqrt{3}\approx 0.577$. Ngoài dải ấy hàm cong lên theo mọi hướng, vậy mà chỉ dải hẹp này thôi đã đủ làm hàm mất tính lồi. Với $0.4(x_1^2+x_2^2)+\cos (2x_1)$, vùng đỏ gồm dải giữa $|x_1|<0.685$ và hai mép $|x_1|>2.457$ của khung nhìn. Hàm $x_1^2+3x_1{x}_2+x_2^2$ thì đỏ khắp khung, dù cả hai phần tử trên đường chéo của Hessian đều dương: $\left[\begin{array}{cc}2& 3\\ 3& 2\end{array}\right]$ có trị riêng $5$ và $-1$, và theo hướng $(1,-1)$ đồ thị cong xuống.

Hai hàm còn lại, $\log (e^{x_1}+e^{x_2})$ và $x_1^2/x_2$, không có điểm đỏ nào, nhưng mỗi điểm đều có một hướng với độ cong bằng 0. Ta sẽ trở lại với chúng ở mục 5.

3. Vì sao điều kiện đúng

Để chứng minh định lý này một cách chặt chẽ, ý tưởng trung tâm là quy bài toán nhiều biến về bài toán một biến quen thuộc thông qua kỹ thuật hạn chế lên đường thẳng. Phép chứng minh gồm hai mắt xích sau:

Một biến. Với hàm $g$ khả vi hai lần trên một khoảng, $g^{″}\ge 0$ tương đương với $g^{\prime }$ không giảm. Mà $g^{\prime }$ không giảm thì $g$ lồi: Lập luận trong bài tập về hàm softplus ở chủ đề trước áp dụng nguyên vẹn, vì nó chỉ dùng tính đơn điệu của đạo hàm để suy ra điều kiện bậc nhất. Ngược lại, $g$ lồi thì $g^{\prime }$ không giảm theo tính đơn điệu của , nên $g^{″}\ge 0$.

Nhiều biến. $f$ lồi khi và chỉ khi mọi hàm hạn chế $g(t)=f(x+tv)$ lồi. Theo trường hợp một biến, điều này tương đương với $g^{″}(t)=v^T{\mathrm{\nabla }}^{2}f(x+tv)v\ge 0$ với mọi $x$, mọi $v$ và mọi $t$ hợp lệ. Vì mỗi điểm $z$ của miền xác định đều có dạng $x+tv$ với $x=z$ và $t=0$, điều kiện đó chính là $v^T{\mathrm{\nabla }}^{2}f(z)v\ge 0$ với mọi $z$ và mọi $v$, tức ${\mathrm{\nabla }}^{2}f(z)⪰0$ tại mọi điểm.

4. Hàm bậc hai và bình phương tối thiểu

Với hàm bậc hai tổng quát $f(x)=\frac{1}{2}{x}^{T}Px+q^{T}x+r$, trong đó $P$ đối xứng, bằng $P$ tại mọi điểm. Do đó $f$ lồi khi và chỉ khi $P⪰0$, và lồi nghiêm ngặt khi và chỉ khi $P\succ 0$. Với hàm bậc hai, điều kiện bậc hai chính xác theo cả hai chiều, kể cả ở phần "nghiêm ngặt".

Hàm mất mát là trường hợp then chốt trong học máy. Khai triển

$$\parallel Aw-b{\parallel }_2^2=w^T{A}^{T}Aw-2b^{T}Aw+b^{T}b,$$

ta thấy bằng $2A^{T}A$. này luôn vì $v^T{A}^{T}Av=\parallel Av{\parallel }_2^2\ge 0$, nên luôn là bài toán lồi. Nó lồi nghiêm ngặt khi và chỉ khi $Av\ne 0$ với mọi $v\ne 0$, tức các cột của $A$ độc lập tuyến tính. Khi hai đặc trưng tỉ lệ với nhau, điều này không còn đúng, và hệ quả nhìn thấy được ngay trên nghiệm.

Ví dụ: Hai đặc trưng cộng tuyến và tác dụng của điều chuẩn ridge

Lấy $A=\left[\begin{array}{cc}1& 2\\ 2& 4\\ 3& 6\end{array}\right]$, trong đó cột thứ hai gấp đôi cột thứ nhất, và $b=(1,2,2)$. Ta có $A^{T}A=\left[\begin{array}{cc}14& 28\\ 28& 56\end{array}\right]$ với trị riêng $70$ và $0$. Hướng có độ cong bằng 0 là $(2,-1)$, vì $A(2,-1)=0$: Tăng $w_1$ thêm 2 và giảm $w_2$ đi 1 không làm thay đổi dự đoán.

Hàm mất mát là một cái máng. Phương trình chuẩn $A^{T}Aw=A^{T}b=(11,22)$ rút về một phương trình $w_1+2w_2=11/14$, nên mọi điểm trên đường thẳng này đều tối ưu, với cùng tổng bình phương sai số $5/14\approx 0.357$. Bộ giải trả về điểm nào là tùy cách nó được cài đặt, và các hệ số riêng lẻ không còn ý nghĩa diễn giải.

Thêm điều chuẩn ridge $\lambda \parallel w{\parallel }_2^2$, trở thành $2(A^{T}A+\lambda I)$ với trị riêng $2(70+\lambda )$ và $2\lambda$, cả hai dương. Cái máng được uốn thành cái bát, và nghiệm trở nên duy nhất. Với $\lambda =1$, giải $(A^{T}A+I)w=A^{T}b$ được $w=(11/71,22/71)\approx (0.155,0.310)$. Khi $\lambda$ giảm dần về 0, nghiệm ridge tiến về $(11/70,22/70)$, điểm có chuẩn nhỏ nhất trên đường nghiệm.

5. Cái máng xoay quanh gốc: Hàm $x^2/y$

Hàm hai biến $f(x,y)=x^2/y$ trên nửa mặt phẳng $y>0$ đem lại một hình ảnh trực quan rõ nét về suy biến. Tính trực tiếp,

$${\mathrm{\nabla }}^{2}f(x,y)=\frac{2}{y^3}\left[\begin{array}{cc}{y}^2& -xy\\ -xy& x^2\end{array}\right]=\frac{2}{y^3}\left[\begin{array}{c}y\\ -x\end{array}\right]{\left[\begin{array}{c}y\\ -x\end{array}\right]}^T⪰0.$$

có dạng $cu{u}^T$ với $c>0$, nên , và . Nhưng hạng của nó bằng 1, và hướng có độ cong bằng 0 là $(x,y)$, vuông góc với $u=(y,-x)$. Hướng $(x,y)$ chính là hướng của tia đi từ gốc qua điểm đang xét. Lý do hình học: Ta có $f(tx,ty)=tf(x,y)$ với mọi $t>0$, nên dọc mỗi tia xuất phát từ gốc tọa độ, tăng tuyến tính và hoàn toàn không cong. Đồ thị là một cái máng mà đáy máng xoay quanh gốc tọa độ. Trong mô phỏng ở mục 2, chọn hàm $x_1^2/x_2$ và kéo điểm $x$ đi khắp nửa mặt phẳng trên để thấy vạch nét đứt luôn chỉ thẳng về gốc.

Hàm $\log (e^{x_1}+e^{x_2})$ có hiện tượng tương tự theo một kiểu khác. Dọc hướng $(1,1)$, ta có $f(x+t(1,1))=f(x)+t$, tăng tuyến tính, nên luôn suy biến theo hướng đó. Trong bài tiếp theo, ta sẽ tính ma trận Hessian của hàm log-sum-exp ở dạng tổng quát.

6. Lồi nghiêm ngặt và những điều điều kiện bậc hai không nói

Nếu ${\mathrm{\nabla }}^{2}f(x)\succ 0$ tại mọi $x$ thì $f$ lồi nghiêm ngặt. Chiều ngược lại không đúng: Chẳng hạn hàm $f(x)=x^4$ lồi nghiêm ngặt nhưng $f^{″}(0)=0$. Lồi nghiêm ngặt chỉ cấm đồ thị chứa một đoạn thẳng, và một hàm có đạo hàm bậc hai bằng 0 tại vài điểm rời rạc vẫn không chứa đoạn thẳng nào. Với $x^4$, dây cung nối $(-1,1)$ và $(1,1)$ nằm ở độ cao 1, còn đồ thị tại 0 có độ cao 0.

Điều kiện bậc hai cũng im lặng trước những hàm không khả vi hai lần, và trong học máy có không ít hàm như vậy: $|x|$, $max\{x_1,\dots ,x_n\}$, ReLU, chuẩn ${\ell }_1$. Với chúng, ta phải dùng định nghĩa, điều kiện bậc nhất với dưới đạo hàm, hoặc các phép toán giữ tính lồi ở chủ đề sau. Ngay cả $\parallel x{\parallel }_2$ cũng không khả vi tại gốc, dù ở mọi điểm khác của nó , như Bài tập 3 sẽ cho thấy.

7. Độ cong cho biết bài toán dễ hay khó

Ngoài câu trả lời định tính lồi hay không, còn cung cấp thông tin định lượng thực tế: Độ lớn của các trị riêng trực tiếp quyết định tốc độ hội tụ của thuật toán tối ưu.

Lồi mạnh: Ta định nghĩa $f$ là lồi mạnh (strongly convex) trên tập $S$ nếu tồn tại hằng số $m>0$ sao cho:

$${\mathrm{\nabla }}^{2}f(x)⪰mI\mathrm{\forall }x\in S.$$

Khai triển Taylor bậc hai kèm phần dư khi đó đem lại một hàm chặn dưới tốt hơn hẳn tiếp diện bậc nhất:

$$f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^T(y-x)+\frac{m}{2}\parallel y-x{\parallel }_2^2.$$

Về mặt hình học, tựa phía dưới đồ thị tại mỗi điểm $x$ giờ đây là cả một mặt paraboloit tròn xoay có độ cong $m$, tạo nên một chặn dưới chặt chẽ hơn nhiều so với mặt phẳng tiếp xúc. Cực tiểu hóa vế phải theo biến $y$ bằng cách giải điều kiện đạo hàm triệt tiêu $\mathrm{\nabla }f(x)+m(y-x)=0$, tức chọn $y=x-\frac{1}{m}\mathrm{\nabla }f(x)$, ta thu được bất đẳng thức chặn dưới giá trị tối ưu toàn cục $p^{\star }$:

$$p^{\star }\ge f(x)-\frac{1}{2m}\parallel \mathrm{\nabla }f(x){\parallel }_2^2.$$

Ý nghĩa thực tiễn của chặn dưới này rất sâu sắc: Với mạnh, bất cứ khi nào độ lớn $\parallel \mathrm{\nabla }f(x){\parallel }_2$ nhỏ, điểm hiện tại chắc chắn đã nằm rất gần nghiệm tối ưu toàn cục $p^{\star }$. Đây là bảo chứng mà tính lồi thông thường không thể mang lại. Chẳng hạn hàm $e^x$ lồi nghiêm ngặt nhưng không lồi mạnh trên toàn bộ $\mathbb{R}$, bởi vì $f^{″}(x)=e^x\to 0$ khi $x\to -\mathrm{\infty }$. Tại miền đó gradient tiến sát về 0 nhưng bài toán thậm chí không hề đạt cực tiểu tại bất kỳ điểm hữu hạn nào.

Số điều kiện: Khi vừa lồi mạnh vừa có bị chặn trên bởi $M$ (tức ${\mathrm{\nabla }}^{2}f(x)⪯MI$ với $M\ge m>0$), tỉ số $\kappa =M/m\ge 1$ được gọi là số điều kiện (condition number). Đại lượng này đo lường độ lệch cong giữa các hướng, hay mức độ dẹt của các tập mức: Đường mức của một hàm bậc hai với hai trị riêng $m$ và $M$ là hình ellipse có tỉ số độ dài hai bán trục chính là $\sqrt{\kappa }$.

Xét mô hình tối ưu hàm bậc hai $f(x)=\frac{1}{2}(x_1^2+\gamma x_2^2)$ bằng phương pháp descent với bước nhảy tìm kiếm chính xác theo tia (exact line search). Khi xuất phát từ $(\gamma ,1)$, sau mỗi bước lặp $k$, khoảng cách sai số giá trị mục tiêu $f(x^{(k)})-p^{\star }$ bị thu hẹp đúng một hệ số không đổi $((\gamma -1)/(\gamma +1){)}^2$:

$\gamma$	Hệ số giảm sai số mỗi bước	Số bước để sai số giảm ${10}^6$ lần
10	0.669	35
100	0.961	346

Cùng là một cái bát, nhưng bát càng dẹt thì phương pháp càng đi zíc zắc và càng chậm. Đây là một trong những lý do người ta chuẩn hóa thang đo của các đặc trưng trước khi huấn luyện mô hình: Đưa các đặc trưng về cùng thang đo thường làm của hàm mất mát bớt lệch giữa các hướng.

8. Những câu hỏi để đào sâu

Câu 1. Hàm $f(x)=\frac{1}{2}{x}^{T}Px$ với $P=\left[\begin{array}{cc}1& 2\\ 2& 1\end{array}\right]$ có mọi phần tử của $P$ đều dương. Hàm có lồi không?

Xem lời giải thích

Không. Phần tử dương không có nghĩa là . $P$ có trị riêng $3$ và $-1$, với riêng ứng với $-1$ là $(1,-1)/\sqrt{2}$. Theo hướng đó, $v^{T}Pv=\frac{1}{2}(1-4+1)=-1<0$, đồ thị cong xuống, và $f$ là một cái yên ngựa. Điều ngược lại cũng đúng: $\left[\begin{array}{cc}2& -1\\ -1& 2\end{array}\right]$ có phần tử âm nhưng xác định dương.

Câu 2. Xét quy trình kiểm tra đối xứng $2\times 2$ dạng $\left[\begin{array}{cc}a& b\\ b& c\end{array}\right]$ bằng hai điều kiện $a\ge 0$ và $ac-b^2\ge 0$, rồi kết luận . Cách kiểm tra này tồn tại lỗ hổng nào?

Xem lời giải thích

Lỗ hổng xuất hiện khi $a=0$. Xét $\left[\begin{array}{cc}0& 0\\ 0& -1\end{array}\right]$, ma trận này thỏa mãn $a=0\ge 0$ và $ac-b^2=0\ge 0$, nhưng với $v=(0,1)$ thì $v^{T}Xv=-1<0$. Đối với ma trận đối xứng cỡ $2\times 2$, điều kiện cần và đủ để là cả ba bất đẳng thức $a\ge 0$, $c\ge 0$ và $ac-b^2\ge 0$. Khi chỉ cần ma trận xác định dương ($X\succ 0$) thì hai điều kiện $a>0$ và $ac-b^2>0$ là đủ, bởi vì khi đó $c>b^2/a\ge 0$ là hệ quả tất yếu. Sự khác biệt giữa "nửa xác định" và "xác định" ở đây là một cái bẫy kinh điển mà người học rất dễ mắc phải.

Câu 3. Hàm $e^x$ lồi nghiêm ngặt trên $\mathbb{R}$. Nó có lồi mạnh không, và câu trả lời liên quan gì tới chuyện phương pháp có thể "dừng" ở đâu?

Xem lời giải thích

Không lồi mạnh, vì không có $m>0$ nào để $e^x\ge m$ với mọi $x$. Cận $p^{\star }\ge f(x)-\parallel \mathrm{\nabla }f(x){\parallel }^2/(2m)$ vì thế không áp dụng được. Với $e^x$, tại $x=-10$ đạo hàm chỉ khoảng $4.5\times {10}^{-5}$, nhỏ đến mức một tiêu chí dừng kiểu " đủ nhỏ" sẽ cho dừng, dù bài toán không có nghiệm và hàm vẫn còn giảm được nữa. Lồi mạnh là điều kiện bảo đảm rằng gradient nhỏ thật sự có nghĩa là gần tối ưu.

Câu 4. Trong ví dụ hai đặc trưng cộng tuyến ở mục 4, nếu chỉ cần dự đoán tốt trên dữ liệu đã có, việc nghiệm không duy nhất có gây hại gì không? Còn khi cần đọc ý nghĩa của từng hệ số thì sao?

Xem lời giải thích

Về dự đoán thì không hại: Mọi nghiệm trên đường $w_1+2w_2=11/14$ cho cùng dự đoán $Aw=\frac{11}{14}(1,2,3)$, nên cùng sai số. Nhưng khi đọc hệ số thì có vấn đề lớn. Nghiệm $(11/14,0)$ nói chỉ đặc trưng thứ nhất quan trọng, nghiệm $(0,11/28)$ nói chỉ đặc trưng thứ hai quan trọng, và cả hai đều tối ưu như nhau. Một thay đổi nhỏ trong dữ liệu có thể đẩy bộ giải từ nghiệm này sang nghiệm kia. suy biến báo trước điều đó, và điều chuẩn ridge là một cách chọn ra một nghiệm ổn định.

9. Bài tập tự luyện

Bài tập 1: Kiểm tra bằng Hessian

Hàm $f(x,y)=x^2-2xy+4y^2+e^x$ có lồi trên ${\mathbb{R}}^2$ không? Có lồi nghiêm ngặt không?

Lời giải

${\mathrm{\nabla }}^{2}f=\left[\begin{array}{cc}2+e^x& -2\\ -2& 8\end{array}\right]$. Phần tử đầu dương, và định thức bằng $8(2+e^x)-4=12+8e^x>0$. Hai điều kiện $a>0$ và định thức dương cho xác định dương tại mọi điểm, nên $f$ lồi nghiêm ngặt.

Bài tập 2: Một hàm không lồi với hai cực tiểu toàn cục

Cho $f(x,y)=x^4+y^4-4xy$. (a) Tính và tìm tập điểm mà Hessian . Tập đó có lồi không? (b) Tìm mọi điểm dừng và phân loại chúng. (c) Chỉ ra trực tiếp một dây cung vi phạm định nghĩa .

Lời giải

(a) ${\mathrm{\nabla }}^{2}f=\left[\begin{array}{cc}12x^2& -4\\ -4& 12y^2\end{array}\right]$. Hai phần tử đường chéo luôn không âm, nên khi và chỉ khi $144x^2{y}^2\ge 16$, tức $|xy|\ge 1/3$. Tập này gồm bốn miền nằm ngoài các nhánh hyperbol $xy=\pm 1/3$, không lồi, và không chứa gốc tọa độ. Vậy $f$ không lồi.

(b) $\mathrm{\nabla }f=(4x^3-4y,4y^3-4x)=0$ cho $y=x^3$ và $x=y^3=x^9$, nên $x\in \{0,1,-1\}$. Ba điểm dừng là $(0,0)$, $(1,1)$ và $(-1,-1)$. Tại gốc, $\left[\begin{array}{cc}0& -4\\ -4& 0\end{array}\right]$ có trị riêng $\pm 4$, đó là điểm yên ngựa. Tại $(\pm 1,\pm 1)$, Hessian $\left[\begin{array}{cc}12& -4\\ -4& 12\end{array}\right]$ có trị riêng $8$ và $16$, đó là cực tiểu cục bộ với $f=-2$. Vì $f\to \mathrm{\infty }$ khi $\parallel (x,y)\parallel \to \mathrm{\infty }$, cực tiểu toàn cục tồn tại và phải là một điểm dừng, nên cả hai điểm $(1,1)$ và $(-1,-1)$ đều là cực tiểu toàn cục.

(c) Trung điểm của hai cực tiểu là gốc tọa độ, với $f(0,0)=0$, trong khi trung bình của hai giá trị là $-2$. Đồ thị tại trung điểm nằm trên dây cung, trái với định nghĩa. Một không thể có hai cực tiểu toàn cục tách rời với một "bướu" ở giữa, vì tập các cực tiểu của hàm lồi là một .

Bài tập 3: Hessian của chuẩn Euclid

Cho $f(x)=\parallel x{\parallel }_2$ trên ${\mathbb{R}}^n$. (a) Với $x\ne 0$, chứng minh $\mathrm{\nabla }f(x)=x/\parallel x{\parallel }_2$ và ${\mathrm{\nabla }}^{2}f(x)=(I-u{u}^T)/\parallel x{\parallel }_2$ với $u=x/\parallel x{\parallel }_2$. (b) Tìm các trị riêng của và hướng có độ cong bằng 0. Giải thích hướng đó bằng hình học. (c) Vì sao điều kiện bậc hai không đủ để kết luận $f$ lồi trên ${\mathbb{R}}^n$, và ta kết luận bằng cách nào?

Lời giải

(a) $\partial \parallel x{\parallel }_2/\partial x_i=x_i/\parallel x{\parallel }_2$. Đạo hàm tiếp theo $x_j$ cho ${\delta }_{ij}/\parallel x{\parallel }_2-x_i{x}_j/\parallel x{\parallel }_2^3$, tức ${\mathrm{\nabla }}^{2}f(x)=(I-x{x}^T/\parallel x{\parallel }_2^2)/\parallel x{\parallel }_2$. (b) $I-u{u}^T$ là phép chiếu lên siêu phẳng vuông góc với $u$, có trị riêng 1 (bội $n-1$) và 0 (theo hướng $u$). Vậy có trị riêng $1/\parallel x{\parallel }_2$ bội $n-1$ và trị riêng 0 theo hướng $x$. Lý do tương tự hàm $x^2/y$: Ta có $f(tx)=tf(x)$ với $t>0$, nên dọc theo tia từ gốc tọa độ qua điểm $x$, hàm chuẩn tăng tuyến tính và hoàn toàn không cong. Đồ thị của $\parallel x{\parallel }_2$ là một mặt nón tròn xoay. (c) Gốc tọa độ thuộc miền xác định nhưng $f$ không khả vi tại đó, nên định lý không áp dụng trên toàn ${\mathbb{R}}^n$. Ta kết luận bằng định nghĩa: Bất đẳng thức tam giác và tính thuần nhất cho

$$\parallel \theta x+(1-\theta )y{\parallel }_2\le \theta \parallel x{\parallel }_2+(1-\theta )\parallel y{\parallel }_2,$$

như đã thực hiện ở chủ đề về chuẩn.

Tóm tắt

Hàm khả vi hai lần trên miền lồi là lồi khi và chỉ khi tại mọi điểm. Dạng toàn phương $v^T{\mathrm{\nabla }}^{2}f(x)v$ là độ cong của đồ thị khi đi qua $x$ theo hướng $v$, và nó là trung bình có trọng số của các trị riêng. Dấu các trị riêng cho biết quanh $x$ đồ thị là cái bát, cái máng, cái yên ngựa hay cái bát úp, và chỉ cần một vùng nhỏ có trị riêng âm là hàm mất tính lồi.

luôn lồi vì $2A^{T}A⪰0$, nhưng chỉ lồi nghiêm ngặt khi các cột của $A$ độc lập. Đặc trưng cộng tuyến tạo ra cái máng và vô số nghiệm, còn điều chuẩn ridge uốn nó thành cái bát. Hessian xác định dương suy ra lồi nghiêm ngặt nhưng không ngược lại, như $x^4$ cho thấy. Cuối cùng, lồi mạnh và số điều kiện $M/m$ cho biết nhỏ có nghĩa là gần tối ưu hay không, và phương pháp gradient chạy nhanh hay chậm.

Tài liệu tham khảo

• Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press.