Mô-đun phụ yếu đối với các chỉ số liên tiếp
Để cho $f\colon \mathbf{R} \times \mathbf{R}^+ \rightarrow \mathbf{R}$ được xác định bởi $f(x,y) = \frac{x^2}{y}$. Để cho$X = \left\lbrace x_1, \dots, x_n\right\rbrace \subseteq \mathbf{R}$, $Y = \left\lbrace y_1, \dots, y_n\right\rbrace \subseteq \mathbf{R}^+$ được đặt hàng để $\frac{x_1}{y_1} \leq \dots \leq \frac{x_n}{y_n}$. Xác định chức năng thiết lập$F\colon 2^n \rightarrow \mathbf{R}$ bởi $F(S) = \frac{(\sum_{i \in S}x_i)^2}{\sum_{i \in S}y_i}$ cho $S \subseteq \left\lbrace 1, \dots n\right\rbrace$
$F$ có thể không theo mô-đun, ngay cả đối với $X$ tích cực - cho $X = \left\lbrace0, 7, 8, 9\right\rbrace$, $Y = \left\lbrace4, 7, 1, 1\right\rbrace$ lấy $$ \begin{align} S &= \left\lbrace 1, 3\right\rbrace \\ T &= \left\lbrace0, 2, 3\right\rbrace \\ S \cap T &= \left\lbrace 3\right\rbrace\\ S \cup T &= \left\lbrace 0, 1, 2, 3\right\rbrace \\ \end{align} $$ và $$ F(S) + F(T) \approx 80.1667 \\ F(S \cup T) + F(S \cap T) \approx 125.3077 $$
tôi nghĩ $F$ là submodular cho khoảng thời gian, tuy nhiên, nói cách khác $$ F(S) + F(T) \geq F(S \cup T) + F(S \cap T) $$
cho $S$, $T$ khoảng thời gian của biểu mẫu $\left\lbrace j, j+1, \dots k\right\rbrace$, cho $j \leq k$, cho bất kỳ thông số kỹ thuật nào của $X$, $Y$. Tôi đã không thể chứng minh điều này - có ai có thể chứng minh hoặc cung cấp một ví dụ ngược lại không?
Trả lời
Tỷ lệ phụ được giữ nguyên, với điều khoản sau: Trong OP, $F(\emptyset)$không định nghĩa được. Hãy để chúng tôi định nghĩa nó là$0$.
Để cho $$s_1:=\sum_{S\setminus T}x_i,\quad s_2:=\sum_{S\cap T}x_i,\quad s_3:=\sum_{T\setminus S}x_i,$$ $$t_1:=\sum_{S\setminus T}y_i,\quad t_2:=\sum_{S\cap T}y_i,\quad t_3:=\sum_{T\setminus S}y_i.$$ Không mất tính tổng quát (wlog), $S$ và $T$ không có giá trị nào và là điểm cuối bên trái của khoảng thời gian $S$ không lớn hơn điểm cuối bên trái của khoảng thời gian $T$. Chắc chắn,$t_1,t_2,t_3\ge0$. Giả định$t_1,t_2,t_3>0$, điều kiện $\frac{x_1}{y_1}\le\dots\le\frac{x_n}{y_n}$ ngụ ý $$\frac{s_1}{t_1}\le\frac{s_2}{t_2}\le\frac{s_3}{t_3}.\tag{1}$$
Những điều kiện này còn ngụ ý $$\frac{(s_1+s_2)^2}{t_1+t_2}+\frac{(s_2+s_3)^2}{t_2+t_3}\ge\frac{(s_1+s_2+s_3)^2}{t_1+t_2+t_3}+\frac{s_2^2}{t_2}.\tag{2}$$ Đó là, $$F(S)+F(T)\ge F(S\cup T)+F(S\cap T)$$ nếu $t_1,t_2,t_3>0$. Các trường hợp với một trong những$t_j$'s (và tương ứng $s_j$'s) bằng nhau $0$ tương tự và đơn giản hơn.
Vì vậy, $F$ là submodular.
Để chứng minh (giả sử) bất đẳng thức đầu tiên trong (1), hãy $r_i:=x_i/y_i$, $j:=\max(S\setminus T)$, và $k:=\min(S\cap T)$. Sau đó$x_i=r_i y_i$, $r_i$ không giảm trong $i$, và $j<k$. Vì thế,$s_1\le r_j t_1$, và $s_2\ge r_k t_2$, và $r_j\le r_k$. Những bất đẳng thức này bao hàm bất đẳng thức đầu tiên trong (1). Bất đẳng thức thứ hai trong (1) được chứng minh tương tự.
Để chứng minh (2), hãy thay thế vào đó $s_j$ bởi $R_jt_j$, Ở đâu $R_j:=s_j/t_j$, do đó, bởi (1), $R_1\le R_2\le R_3$. Khi đó, lưu ý rằng đạo hàm trong$R_3$ sự khác biệt giữa bên trái và bên phải của (2) (với $s_j$ thay thế bởi $R_jt_j$) Là $$\frac{2 t_1 t_3 \left(\left(R_2-R_1\right) t_2+\left(R_3-R_1\right) t_3\right)}{\left(t_2+t_3\right) \left(t_1+t_2+t_3\right)}\ge0.$$ Vì vậy, wlog $R_3=R_2$, trong trường hợp đó (2) có thể được viết lại thành $$\frac{\left(R_1-R_2\right){}^2 t_1^2 t_3}{\left(t_1+t_2\right) \left(t_1+t_2+t_3\right)}\ge0,\tag{3}$$ mà rõ ràng là đúng.
Chúng ta cũng có thể thấy rằng, với $t_1,t_2,t_3>0$, bất đẳng thức (2) là nghiêm ngặt trừ khi $R_1=R_2=R_3$.
Ngoài ra, việc chứng minh (2) trong các điều kiện tương ứng là một bài toán đơn giản của hình học đại số thực, có thể được xử lý theo thuật toán / không cần suy nghĩ, như được thấy từ hình ảnh sau đây của sổ tay Toán học (bấm vào hình để phóng to nó):
