Moreau Decomposition cho hàm nonconvex
Đối với bất kỳ hàm lồi, thích hợp và đóng $f$ và cho bất kỳ $x$, sự phân hủy Moreau nói rằng
$$Prox_f(x)+Prox_{f^*}(x)=x,$$ Ở đâu $f^*$ là hàm liên hợp của $f$ và $Prox_f$ là toán tử gần của $f$ định nghĩa là $$Prox_f(x)=\underset{v}{\arg\min}\;\frac{1}{2}||x-v||^2+f(v).$$ Câu hỏi của tôi là liệu sự phân hủy này có diễn ra ngay cả khi $f$là không lồi , giả định rằng$Prox_f(x)$được xác định rõ. tôi biết điều đó$f^*$ là lồi bất kể độ lồi của $f$, do đó, nó sẽ giữ $$Prox_{f^{**}}(x)+Prox_{f^*}(x)=x,$$ Ở đâu $f^{**}$ là lưỡng hợp của $f$. Do đó, câu hỏi của tôi giảm xuống liệu$Prox_f=Prox_{f^{**}}$ khi nào $f$ là không lồi?
Cảm ơn bạn.
Trả lời
Hấp dẫn. $\newcommand{\prox}{\mathrm{prox}}\newcommand\inner[1]{\left\langle #1 \right\rangle}$
Lưu ý rằng nếu $f$ sau đó không lồi $\prox_f(x)$có thể không phải là singleton, do đó câu hỏi được quan tâm là liệu những thứ sau có đúng hay không: \ begin {method} x \ in \ prox_f (x) + \ prox_ {f ^ *} (x). \ tag {*} \ label { moreau} \ end {method} Với một số giả định khác về$f$ (và $x$), câu trả lời là khẳng định.
Chứng tỏ $d_x(y) = \frac{1}{2}\|y-x\|^2$. Chúng tôi có (xem \ eqref {Optimality} bên dưới):$$z\in \prox_f(x) \iff z\in \arg\min_{y} \left\{f(y) + d_x(y)\right\} \iff 0\in\partial(f + d_x)(z).$$ Từ $f$ là không lồi, bao gồm $\partial f(z) + \partial d_x(z) \subset \partial(f + d_x)(z)$ có thể thích hợp, ví dụ: khi $\partial f(z) = \emptyset$. Rõ ràng, cho bất kỳ$z\in \prox_f(x)$, bộ $\partial(f + d_x)(z)$ không trống vì nó chứa $0$. Bây giờ, nếu chúng ta giả định rằng có tồn tại$z$ sao cho phần tử $0$ thuộc tập hợp con $\partial f(z) + \partial d_x(z)$, sau đó \ eqref {moreau} giữ lại. Lưu ý rằng giả định này đúng nếu$f$ là lồi.
Kết quả có thể được chứng minh bằng cách nhận thấy rằng một số kết quả phân tích lồi có thể được mở rộng cho các hàm không lồi, như sau.
Sự thật 1. Điều kiện tối ưu bậc nhất cũng phù hợp với một hàm không lồi: \ begin {method} x ^ * \ in \ arg \ min_x f (x) \ iff 0 \ in \ part f (x ^ *). \ tag {1} \ nhãn {tối ưu} \ end {phương trình}
Điều này theo trực tiếp từ định nghĩa của subgradient.
Sự thật 2. Bất đẳng thức Fenchel – Young cũng áp dụng cho một hàm không lồi: \ begin {method} f (x) + f ^ * (u) \ ge \ internal {u, x} \ \ forall x, u. \ tag {2} \ label {fenchel} \ end {method}
Điều này theo sau trực tiếp từ định nghĩa của liên từ.
Sự thật 3. Trường hợp đẳng thức trong bất đẳng thức Fenchel – Young cũng giống như đối với một hàm không lồi: \ begin {method} f (x) + f ^ * (u) = \ internal {x, u} \ Longleftrightarrow u \ in \ một phần f (x). \ tag {3} \ label {fenchel-equal} \ end {method}
Xem ở đây để có bằng chứng.
Bây giờ trở lại kết quả chính. Để cho$z$ được như vậy $0\in\partial f(z) + \partial d_x(z)$. Bởi vì$\partial f(z) + \partial d_x(z) \subset \partial(f + d_x)(z)$ chúng ta có $0 \in \partial(f + d_x)(z)$ và như vậy $z\in\prox_f(x)$ theo \ eqref {tối ưu}.
Chứng tỏ $u=x-z$. Thông báo rằng$\partial d_x(z) = \{z - x\}$, chúng ta có $0\in\partial f(z) + z-x$, I E $\boxed{u \in \partial f(z)}$và do đó theo \ eqref {fenchel-Equity} chúng ta có \ begin {method} \ internal { z, u} = f (z) + f ^ * (u). \ tag {4} \ label {zu} \ end { method } Mặt khác, theo \ eqref {fenchel}: \ begin { method } f (z) + f ^ * (v) \ ge \ internal {v , z} \ \ forall v. \ tag {5} \ label {zv} \ end { method } Tính tổng \ eqref {zu} và \ eqref {zv} chúng ta thu được: \ begin { method } f ^ * (v) \ ge f ^ * (u) + \ internal {z, vu} \ \ forall v, \ end {method} có nghĩa là$\boxed{z\in\partial f^*(u)}$, ngụ ý \begin{align} x-u \in\partial f^*(u) \implies &0\in\partial f^*(u) + u-x \\ \implies &0 \in\partial f^*(u) + \partial d_x(u) \\ \implies &0\in \partial (f^* + d_x) (u) \\ \implies &u = \prox_{f^*}(x). \end{align} Do đó chúng tôi đã chứng minh rằng $x=z+u \in \prox_f(x) + \prox_{f^*}(x)$. QED
Tôi muốn nói rằng ở trên là khá đơn giản. Một câu trả lời đầy đủ phải cung cấp một ví dụ ngược lại cho \ eqref {moreau} (nếu ví dụ đó tồn tại) hoặc ít nhất cung cấp thêm thông tin chi tiết về giả định$\exists z: 0\in\partial f(z) + \partial d_x(z)$. Mặc dù tôi nghĩ rằng giả định này khá yếu nhưng tôi không thể nói nhiều hơn.
P / s: Từ minh chứng, chúng ta có những điều sau đây.
Sự thật 4. Hàm ý sau đây phù hợp với một hàm không lồi: \ begin {method} u \ in \ part f (z) \ ngụ ý z \ in \ part f ^ * (u). \ end {method} Nếu$f$ là lồi thì converse cũng giữ.
Cập nhật
Ở phần trên, tôi đã ngay lập tức tổng quát hóa sự phân hủy Moreau thành bao gồm \ eqref {moreau} vì sự không lồi lõm của $f$. Tuy nhiên, vì Regev cho rằng mọi thứ đều được xác định rõ ràng trong câu hỏi của mình, nên một quan điểm khác hạn chế hơn sẽ cho rằng$\prox_f(x)$là một singleton (như được xác nhận bởi Regev trong nhận xét gần đây của anh ấy / cô ấy) để bình đẳng được giữ thay vì bao gồm: \ begin {method} x = \ prox_f (x) + \ prox_ {f ^ *} (x). \ tag {**} \ label {moreau-equal} \ end {method}
Nếu chúng ta giả định thêm rằng vi sai phụ $\partial f(z)$ không rỗng (đây là một giả định rất nhẹ nhàng), thì \ eqref {moreau-equal} thực sự giữ nguyên.
Hệ quả. Nếu$\prox_f(x)$ là một singleton và vi phân con $\partial f(\prox_f(x))$ là khác rỗng, thì phân tách Moreau \ eqref {moreau-Equity} giữ.
Bằng chứng. Chứng tỏ$z = \prox_f(x)$. Bởi vì$\prox_f(x)$ là một singleton, theo suy luận trên, chúng ta có $\partial(f + d_x)(z) = 0$(với một chút lạm dụng ký hiệu, chúng tôi biểu thị singleton được đặt bởi chính phần tử). Do đó, bởi vì$\partial f(z) \neq \emptyset$ và $\partial f(z) + \partial d_x(z) \subset \partial(f + d_x)(z) = 0$, vi sai phụ $\partial f(z)$ cũng phải là một singleton, và hơn nữa $\partial f(z) + \partial d_x(z) = 0$. Điều này rõ ràng thỏa mãn giả thiết được đưa ra trong phần trước và do đó chúng ta thu được \ eqref {moreau-Equal}.
Câu trả lời bây giờ đã hoàn thành.