Add the argument about the faces of the hypercube

1 files changed, 17 insertions, 10 deletions

diff --git a/main.tex b/main.tex
index 1de8ac4..31d0a94 100644
--- a/main.tex
+++ b/main.tex
@@ -420,15 +420,24 @@ i\leq |\mathcal{N}|} \lambda_i c_i \leq B$.
     a critical point of the ratio
     $F_\mathcal{N}(\lambda)/L_\mathcal{N}(\lambda)$. Such a critical point is
     characterized by:
-    \begin{displaymath}
+    \begin{equation}\label{eq:lhopital}
         \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)}
         = \frac{\partial_i F_\mathcal{N}(\lambda)}{\partial_i
         L_\mathcal{N}(\lambda)} \geq \frac{1}{2}
-    \end{displaymath}
-    
-    The case of the faces of the hypercube can be dealt with by induction
-    (TODO).
-
+    \end{equation}
+    Finally, if the minimum is attained on a face of the hypercube (a face is
+    defined as a subset of the hypercube where one of the variable is fixed to
+    0 or 1), without loss of generality, we can assume that the minimum is
+    attained on the face where the $|\mathcal{N}|$-th variable has been fixed
+    to 0 or 1. Then, either the minimum is attained at a point interior to the
+    face or on a boundary of the face. In the first case, relation
+    \eqref{eq:lhopital} still characterizes the minimum for $i< |\mathcal{N}|$.
+    In the second case, by repeating the argument again by induction, we see
+    that all is left to do is to show that the bound holds for the vertices of
+    the cube (the faces of dimension 1).  The vertices are exactly the binary
+    points, for which we know that both relaxations are equal to the value
+    function $V$. Hence, the ratio is equal to 1 on the vertices.
+ 
     Let us start by computing the derivatives of $F_\mathcal{N}$ and
     $L_\mathcal{N}$ with respect to the $i$-th component.
 
@@ -442,14 +451,13 @@ i\leq |\mathcal{N}|} \lambda_i c_i \leq B$.
                 i\in \mathcal{N}\setminus S \\
             \end{aligned}\right.
     \end{displaymath}
-
     Hence:
     \begin{multline*}
         \partial_i F_\mathcal{N} =
         \sum_{\substack{S\subseteq\mathcal{N}\\ i\in S}}
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})V(S)\\
         - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in \mathcal{N}\setminus S}}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S)\\
+        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S)
     \end{multline*}
 
     Now, using that every $S$ such that $i\in S$ can be uniquely written as
@@ -459,9 +467,8 @@ i\leq |\mathcal{N}|} \lambda_i c_i \leq B$.
         \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S\cup\{i\})\\
         - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in \mathcal{N}\setminus S}}
-        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S)\\
+        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S)
     \end{multline*}
-
     Finally, by using the expression for the marginal contribution of $i$ to
     $S$:
     \begin{displaymath}