diff options
Diffstat (limited to 'dual2.tex')
| -rw-r--r-- | dual2.tex | 213 |
1 files changed, 64 insertions, 149 deletions
@@ -30,13 +30,13 @@ Let $\alpha\in\mathbf{R}^+$, consider the perturbed optimization problem: \end{equation} and denote by $L^*_c(\alpha)$ its optimal value. Note that we have $L^*_c = L^*_c(0)$. -We will assume that $\alpha\leq\frac{1}{n}$ so that \eqref{eq:perturbed-primal} has at +We will assume that $\alpha<\frac{1}{n}$ so that \eqref{eq:perturbed-primal} has at least one feasible point: $(\frac{1}{n},\ldots,\frac{1}{n})$. Let us introduce the lagrangian of problem, \eqref{eq:perturbed-primal}: \begin{displaymath} \mathcal{L}_{c, \alpha}(\lambda, \mu, \nu, \xi) \defeq L(\lambda) - + \T{\mu}(\lambda-\mathbf{\alpha}) + \T{\nu}(\mathbf{1}-\lambda) + \xi(1-\T{c}\lambda) + + \T{\mu}(\lambda-\alpha\mathbf{1}) + \T{\nu}(\mathbf{1}-\lambda) + \xi(1-\T{c}\lambda) \end{displaymath} so that: \begin{displaymath} @@ -111,9 +111,9 @@ dual feasibility, the KKT conditions give $\forall i\in\{1, \ldots, n\}$: \begin{lemma}\label{lemma:proximity} We have: \begin{displaymath} - L^*_c - \alpha n\leq L^*_c(\alpha) \leq L^*_c + L^*_c - \alpha n^2(n-1)\leq L^*_c(\alpha) \leq L^*_c \end{displaymath} -In particular, $|L^*_c - L^*_c(\alpha)| \leq \alpha n$. +In particular, $|L^*_c - L^*_c(\alpha)| \leq \alpha n^2(n-1)$. \end{lemma} \begin{proof} @@ -127,27 +127,67 @@ In particular, $|L^*_c - L^*_c(\alpha)| \leq \alpha n$. \end{displaymath} Note that $\mathcal{L}_{c, \alpha}(\lambda, \mu^*, \nu^*, \xi^*) - = \mathcal{L}_{c}(\lambda, \mu^*, \nu^*, \xi^*) - \T{\alpha}\mu^*$ and that - for any $\lambda$ feasible for problem \eqref{eq:primal}, - $\mathcal{L}_{c}(\lambda, \mu^*, \nu^*, \xi^*) \geq L(\lambda)$. Hence, + = \mathcal{L}_{c}(\lambda, \mu^*, \nu^*, \xi^*) + - \alpha\T{\mathbf{1}}\mu^*$, and that for any $\lambda$ feasible for + problem \eqref{eq:primal}, $\mathcal{L}_{c}(\lambda, \mu^*, \nu^*, \xi^*) + \geq L(\lambda)$. Hence, \begin{displaymath} - L^*_{c}(\alpha) \geq \mathcal{L}_{c}(\lambda, \mu^*, \nu^*, \xi^*) - \T{\alpha}\mu^* + L^*_{c}(\alpha) \geq L(\lambda) - \alpha\T{\mathbf{1}}\mu^* \end{displaymath} for any $\lambda$ feasible for \eqref{eq:primal}. In particular, for $\lambda^*$ primal optimal for \eqref{eq:primal}: \begin{equation}\label{eq:local-1} - L^*_{c}(\alpha) \geq L^*_c - \T{\alpha}\mu^* + L^*_{c}(\alpha) \geq L^*_c - \alpha\T{\mathbf{1}}\mu^* \end{equation} - Note that from the KKT conditions, we cannot have both $\mu_i^*$ and $\nu_i^*$ different from zero, hence: + Let us denote by the $M$ the support of $\mu^*$, that is $M\defeq + \{i|\mu_i^* > 0\}$, and by $\lambda^*$ a primal optimal point for + $\eqref{eq:perturbed-primal}$. From the KKT conditions we see that: \begin{displaymath} - \sum_{i=1}^n \mu_i^* = \sum_{i=1}^n \xi^*c_i - \partial_i L(\lambda^*) \leq \sum_{i=1}^n\xi^*c_i + M = \{i|\lambda_i^* = \alpha\} \end{displaymath} - Using the KKT conditions again, if $\lambda_i^*>\alpha$, $\xi^*c_i \leq - \partial_i L(\lambda^*)$. In particular, using - Lemma~\ref{lemma:derivative-bounds}, $\xi^*c_i\leq 1$. As a consequence, - $\T{\alpha}\mu^*\leq\alpha n$. This, in addition to \eqref{eq:local-1} - gives the left-hand side of the lemma's inequality. + Let us first assume that, $|M|\geq 1$, then we have that $\T{c}\lambda^* + = 1$, otherwise we could increase the coordinates of $\lambda^*$ in $M$, + which would increase the value of the objective function and contradict the + optimality of $\lambda^*$. Note also, that $|M|\leq n-1$, otherwise, since + $\alpha< \frac{1}{n}$, we would have $\T{c}\lambda^*\ < 1$, which again + contradicts the optimality of $\lambda^*$. Let us write: + \begin{displaymath} + 1 = \T{c}\lambda^* = \alpha\sum_{i\in M}c_i + \sum_{i\in \bar{M}}\lambda_i^*c_i + \leq \alpha (n-1) + (n-1)\max_{i\in \bar{M}} c_i + \end{displaymath} + That is: + \begin{equation}\label{local-2} + \max_{i\in\bar{M}} c_i \geq \frac{1 - (n-1)\alpha}{n-1}> \frac{1}{n(n-1)} + \end{equation} + where the last inequality uses again that $\alpha<\frac{1}{n}$. From the + KKT conditions, we see that for $i\in M$, $\nu_i^* = 0$ and: + \begin{equation}\label{local-3} + \mu_i^* = \xi^*c_i - \partial_i L(\lambda^*)\leq \xi^*c_i\leq \xi^* + \end{equation} + since $\partial_i L(\lambda^*)\geq 0$ and $c_i\leq 1$. + + Furthermore, using the KKT conditions again, we have that: + \begin{equation}\label{local-4} + \xi^* = \inf_{i\in \bar{M}}\frac{\partial_i L(\lambda^*)}{c_i}\leq \inf_{i\in \bar{M}} \frac{1}{c_i} + = \frac{1}{\max_{i\in\bar{M}} c_i} + \end{equation} + where the inequality uses Lemma~\ref{lemma:derivative-bounds}. + + Combining \eqref{local-2}, \eqref{local-3} and \eqref{local-4}, we get that: + \begin{displaymath} + \sum_{i\in M}\mu_i^* \leq |M|\xi^* \leq n\xi^*\leq \frac{n}{\max_{i\in\bar{M}} c_i} \leq n^2(n-1) + \end{displaymath} + + Finally let us write: + \begin{displaymath} + \T{\mathbf{1}}\mu^* = \sum_{i=1}^n \mu^*_i = \sum_{i\in M}\mu_i^* + \end{displaymath} + + Either $|M|=0$, in which case $\T{\mathbf{1}}\mu^* = 0$, either $|M|\geq + 1$, in which case $\T{\mathbf{1}}\mu^*\leq n^2(n-1)$ from the inequality above. + In both cases, $\T{\mathbf{1}}\mu^* \leq n^2(n-1)$, which, in addition to + \eqref{eq:local-1} proves the lemma. \end{proof} \begin{lemma}\label{lemma:monotonicity} @@ -189,15 +229,16 @@ In particular, $|L^*_c - L^*_c(\alpha)| \leq \alpha n$. \begin{proof} Let $\varepsilon$ in $(0, 1]$. The routine works as follows: set $\alpha\defeq -\varepsilon(\delta + n)^{-1}$ and return an approximation $\tilde{L}^*_c$ of +\varepsilon(\delta + n^2(n-1))^{-1}$ and return an approximation $\tilde{L}^*_c$ of $L^*_c(\alpha)$ with an accuracy $\frac{1}{2^{n+1}}\alpha\delta b$ computed by -a standard convex optimization algorithm +a standard convex optimization algorithm. Note that this choice of $\alpha$ +implies $\alpha<\frac{1}{n}$ as requested. \begin{enumerate} \item using Lemma~\ref{lemma:proximity}: \begin{displaymath} |\tilde{L}^*_c - L^*_c| \leq |\tilde{L}^*_c - L^*_c(\alpha)| + |L^*_c(\alpha) - L^*_c| - \leq \alpha\delta + \alpha n = \varepsilon + \leq \alpha\delta + \alpha n^2(n-1) = \varepsilon \end{displaymath} \item let $c' = (c_i', c_{-i})$ with $c_i'\leq c_i-\delta$, then: @@ -206,145 +247,19 @@ a standard convex optimization algorithm \geq L^*_c + \frac{\alpha\delta b}{2^{n+1}} \geq \tilde{L}^*_c \end{displaymath} -where the first and inequality come from the accuracy of the approximation, and the inner inequality follows from Lemma~\ref{lemma:monotonicity}. +where the first and inequality come from the accuracy of the approximation, and +the inner inequality follows from Lemma~\ref{lemma:monotonicity}. \item the accuracy of the approximation $\tilde{L}^*_c$ is: \begin{displaymath} - A\defeq\frac{\varepsilon\delta b}{2^{n+1}(\delta + n)} + A\defeq\frac{\varepsilon\delta b}{2^{n+1}(\delta + n^2(n-1))} \end{displaymath} \sloppy hence, the standard convex optimization algorithm runs in time $O(poly(n, d,\log\log A^{-1}))$. Note that: \begin{displaymath} \log\log A^{-1} = O\bigg(\log n\; \log\log\frac{1}{\epsilon\delta b}\bigg) \end{displaymath} -which yields the wanted running time for the routing.\qedhere +which yields the wanted running time for the routine.\qedhere \end{enumerate} \end{proof} - -\section{Previous Junk} -\paragraph{Primal reformulation} -We define $S(\lambda) \defeq I_d + \sum_{i=1}^n \lambda_i x_i x_i^T$. We can -reformulate the primal: -\begin{align} - \mathrm{maximize}\quad & \log\det W\\ - \textrm{subject to}\quad & W = S(\lambda)\;;\;c^T\lambda \leq 1 \;;\; 0\leq\lambda\leq \mathbf{1} -\end{align} - -\paragraph{Dual} -\begin{align} - \mathrm{minimize}\quad & \log\det\big(N^{-1}\big) + \mathrm{Tr}\, N - n + \sum_{i=1}^n x_i^T N x_i \\ - & - \Bigg(\min_{1\leq i\leq n} \frac{x_i^TNx_i}{c_i}\Bigg)\Big(\sum_{i=1}^n c_i - 1\Big) \\ - \textrm{subject to}\quad & N\in \mathcal{S}_n^{++}(\mathbf{R}) -\end{align} - -Let us define: -\begin{equation} -\begin{split} - f(N, c) \defeq \log\det\big(N^{-1}\big) + \mathrm{Tr}\, N - n + \sum_{i=1}^n x_i^T N x_i \\- \Bigg(\min_{1\leq i\leq n} \frac{x_i^TNx_i}{c_i}\Bigg)\Big(\sum_{i=1}^n c_i - 1\Big) -\end{split} -\end{equation} - -So that the dual reads: -\begin{align} - \mathrm{minimize}\quad & f(N, c)\\ - \textrm{subject to}\quad & N\in \mathcal{S}_n^{++}(\mathbf{R}) -\end{align} - - -\paragraph{Duality} By duality $L^*(c)$ is equal to the optimal value of the dual optimization -problem: - -\begin{displaymath} - L^*(c) = \inf_{N\in\mathcal{S}_n(\mathbf{R})} f(N, c) = f(N^*, c) = \log\det S(\lambda^*) -\end{displaymath} - -\paragraph{KKT conditions} -Let $\xi$ denote the dual variable associated with the constraint $c^T\lambda -\leq B$. If $\xi^*$ is dual optimal and $\lambda^*$ primal optimal: -\begin{equation} - \mathrm{if}\; 0 < \lambda^*_i < 1,\; \frac{x_i^T - A(\lambda^*)^{-1}x_i}{c_i} = \xi^* -\end{equation} -\begin{equation} - \mathrm{if}\; \lambda^*_i = 1,\; \frac{x_i^T A(\lambda^*)^{-1}x_i}{c_i} > \xi^* -\end{equation} -\begin{equation} - \mathrm{if}\; \lambda^*_i = 0,\; \frac{x_i^T A(\lambda^*)^{-1}x_i}{c_i} < \xi^* -\end{equation} - -Furthermore, if $W^*\in\mathcal{M}_n(\mathbf{R})$ is primal optimal and -$N^*\in\mathcal{S}_n(\mathbf{R})$ dual optimal: - -\begin{equation} - W^* = S(\lambda^*)\;;\; N^* = (W^*)^{-1}\;;\; 0\leq\lambda^*\leq \mathbf{1} -\end{equation} - -In particular $N^* = S(\lambda^*)^{-1}$ and: -\begin{equation} - S(\mathbf{1})^{-1} \leq N^* \leq S(0)^{-1} = I_d -\end{equation} - - -\paragraph{Sensitivity analysis, first flavor} - -Let $i$ such that $0 < \lambda_i < 1$ and $c' = (c_i + \delta, c_{-i})$, we can -prove: -\begin{displaymath} -L^*(c') \leq L^*(c) - \xi^*\lambda_i^*\delta -\end{displaymath} -where $\lambda^*$ and $\xi^*$ are respectively primal and dual optimal for -$P_c$. Using the KKT conditions and \eqref{lemma:derivative-bounds}, we can bound -$\xi^*$ and get: -\begin{equation}\label{eq:sensitivity} - L^*(c) \geq L^*(c') + \delta\lambda_i^* \frac{x_i^T A(\mathbf{1})^{-1} - x_i}{c_i} -\end{equation} - - -However, note that $\lambda_i^*$ can be arbitrarily small, so even a change of -$\delta$ in the cost can lead to no variation of the optimal value. -Intuitively, it does not harm if an element $i$ that has only a small fraction -of itself in the solution sees its cost reduced. - -The problem seems to come from the fact that we can have arbitrarily small -fractions of elements in the solution : this is clearly an artifact of looking -at a continuous relaxation of the problem, because in the real life, an element -is either in or out of the solution set. - -It is probably possible to prove that if we enforce the $\lambda_i$ to be -greater than some minimal fraction $\zeta$, then we do not lose to much in -terms of the optimal value (especially after rounding). Having $\lambda_i\geq -\zeta$ will allow us to prove that if $i$ changes its cost, then the optimal -value changes by some strictly positive constant depending only on $\zeta$ (and -$\delta$ of course). - -\paragraph{Sensitivity analysis, second flavor} -Let us now assume that some user $i$ reduces its cost by $\delta$ and define $c' = (c_i + \delta, c_{-i})$. Then we have: -\begin{align} - f(N, c') - & = f(N, c) + \Bigg(\min_{1\leq i\leq n} \frac{x_i^TNx_i}{c_i}\Bigg)\Bigg(\sum_{i=1}^n c_i - 1\Bigg) - \Bigg(\min_{1\leq i\leq n} \frac{x_i^TNx_i}{c_i'}\Bigg)\Bigg(\sum_{i=1}^n c_i' - 1\Bigg)\\ - & = f(N, c) + \delta\min_{1\leq i\leq n} \frac{x_i^TNx_i}{c_i} + \Bigg(\sum_{i=1}^n c_i - 1\Bigg) \Bigg(\Bigg(\min_{1\leq i\leq n} \frac{x_i^TNx_i}{c_i}\Bigg) - \Bigg(\min_{1\leq i\leq n} \frac{x_i^TNx_i}{c_i'}\Bigg)\Bigg) -\end{align} - -\textbf{Problem:} we have no control over the third term of the last sum (the -min difference). Otherwise, when we can ignore this term (for example when the -user who changes his cost is not the one at which the min is reached), we get: - -\begin{equation} -L^*(c') \geq L^*(c) + \delta\min_{1\leq i\leq n} \frac{x_i^TNx_i}{c_i} -\end{equation} - -\paragraph{Junk:} -\begin{align*} - \mathrm{minimize}\quad & \log\det\big(N^{-1}\big) + \mathrm{Tr}\, N - n + \sum_{i=1}^n \nu_i + \xi \\ - \textrm{subject to}\quad & \nu \geq 0\; ;\; \xi \geq 0 \; ; \; N\in \mathcal{S}_n^{++}(\mathbf{R})\; ;\\ - & \forall\; 1\leq i \leq n, \; \nu_i + \xi c_i = x_i^T N x_i -\end{align*} - -\begin{align*} - \mathrm{minimize}\quad & \log\det\big(N^{-1}\big) + \mathrm{Tr}\, N - n + \sum_{i=1}^n x_i^T N x_i - \xi\Big(\sum_{i=1}^n c_i - 1\Big) \\ - \textrm{subject to}\quad & \xi \geq 0 \; ; \; N\in \mathcal{S}_n^{++}(\mathbf{R})\; ;\\ - & \forall\;1\leq i \leq n, \; \frac{x_i^T N x_i}{c_i} \geq \xi -\end{align*} - \end{document} |