From a53c28eebf8926d02a835dc55a903b6528c8e784 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Thu, 4 Jul 2013 11:58:04 -0700
Subject: added lower bound in proof, some wording changed

---
 appendix.tex | 19 +++++--------------
 1 file changed, 5 insertions(+), 14 deletions(-)

(limited to 'appendix.tex')

diff --git a/appendix.tex b/appendix.tex
index e964a40..682fce2 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -176,7 +176,7 @@ the proof of the lemma. \qed
 %     and $F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})$.
 %\end{lemma}
 \subsection{Proof of Lemma~\ref{lemma:rounding}}\label{proofoflemmarounding}
-\begin{proof}
+%\begin{proof}
     We give a rounding procedure which, given a feasible $\lambda$ with at least
     two fractional components, returns some feasible $\lambda'$ with one less fractional
     component such that $F(\lambda) \leq F(\lambda')$.
@@ -215,10 +215,10 @@ the proof of the lemma. \qed
     which is positive by submodularity of $V$. Hence, the maximum of
     $F_\lambda$ over the interval given in \eqref{eq:convex-interval} is
     attained at one of its limit, at which either the $i$-th or $j$-th component of
-    $\lambda_\varepsilon$ becomes integral.
-\end{proof}
+    $\lambda_\varepsilon$ becomes integral. \qed
+%\end{proof}
 \subsection{Proof of Proposition~\ref{prop:relaxation}}\label{proofofproprelaxation}
-Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that
+The lower bound on $L^*_c$ follows immediately from the fact that $L$ extends $V$ to $[0,1]^n$. For the upper bound, let us consider a feasible point $\lambda^*\in \dom_c$ such that
 $L(\lambda^*) = L^*_c$. By applying Lemma~\ref{lemma:relaxation-ratio} and
 Lemma~\ref{lemma:rounding} we get a feasible point $\bar{\lambda}$ with at most
 one fractional component such that
@@ -276,48 +276,39 @@ Proposition~\ref{prop:monotonicity}.
         A(S) \defeq I_d + \sum_{i\in S} x_i\T{x_i}
     \end{displaymath}
     Let us also define $A_k\defeq A(\{x_1,\ldots,x_k\})$.
-
     We have $\partial_i L(\lambda) = \T{x_i}\tilde{A}(\lambda)^{-1}x_i$. Since
     $\tilde{A}(\lambda)\succeq I_d$, $\partial_i L(\lambda)\leq \T{x_i}x_i \leq 1$, which
     is the right-hand side  of the lemma.
-
     For the left-hand side, note that $\tilde{A}(\lambda) \preceq A_n$. Hence
     $\partial_iL(\lambda)\geq \T{x_i}A_n^{-1}x_i$.
-
     Using the Sherman-Morrison formula, for all $k\geq 1$:
     \begin{displaymath}
         \T{x_i}A_k^{-1} x_i = \T{x_i}A_{k-1}^{-1}x_i 
         - \frac{(\T{x_i}A_{k-1}^{-1}x_k)^2}{1+\T{x_k}A_{k-1}^{-1}x_k}
     \end{displaymath}
-
     By the Cauchy-Schwarz inequality:
     \begin{displaymath}
         (\T{x_i}A_{k-1}^{-1}x_k)^2 \leq \T{x_i}A_{k-1}^{-1}x_i\;\T{x_k}A_{k-1}^{-1}x_k
     \end{displaymath}
-
     Hence:
     \begin{displaymath}
         \T{x_i}A_k^{-1} x_i \geq \T{x_i}A_{k-1}^{-1}x_i 
         - \T{x_i}A_{k-1}^{-1}x_i\frac{\T{x_k}A_{k-1}^{-1}x_k}{1+\T{x_k}A_{k-1}^{-1}x_k}
     \end{displaymath}
-
     But $\T{x_k}A_{k-1}^{-1}x_k\leq 1$ and $\frac{a}{1+a}\leq \frac{1}{2}$ if
     $0\leq a\leq 1$, so:
     \begin{displaymath}
         \T{x_i}A_{k}^{-1}x_i \geq \T{x_i}A_{k-1}^{-1}x_i
         - \frac{1}{2}\T{x_i}A_{k-1}^{-1}x_i\geq \frac{\T{x_i}A_{k-1}^{-1}x_i}{2}
     \end{displaymath}
-
     By induction:
     \begin{displaymath}
         \T{x_i}A_n^{-1} x_i \geq \frac{\T{x_i}x_i}{2^n}
     \end{displaymath}
-    
     Using that $\T{x_i}{x_i}\geq b$ concludes the proof of the left-hand side
     of the lemma's inequality.
 \end{proof}
-
-Let us introduce the Lagrangian of problem, \eqref{eq:perturbed-primal}:
+Let us introduce the Lagrangian of problem \eqref{eq:perturbed-primal}:
 
 \begin{displaymath}
     \mathcal{L}_{c, \alpha}(\lambda, \mu, \nu, \xi) \defeq L(\lambda) 
-- 
cgit v1.2.3-70-g09d2

