diff options
Diffstat (limited to 'appendix.tex')
| -rw-r--r-- | appendix.tex | 19 |
1 files changed, 5 insertions, 14 deletions
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) |