\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath, amsfonts, amsthm}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\input{definitions}

\begin{document}
Let $c$ be a cost vector in $[0,1]^n$, and $x_1,\ldots,x_n$, $n$ vectors in
$\mathbf{R}^d$ such that for all $i\in\{1,\ldots,n\}$, $b\leq \T{x_i}{x_i}\leq
1$ for some $b\in(0,1]$. Let us consider the following convex optimization
problem:
\begin{equation}\tag{$P_c$}\label{eq:primal}
    \begin{split}
    \mathrm{maximize}\quad & L(\lambda) \defeq\log\det\left(I_d + \sum_{i=1}^n
    \lambda_i x_i x_i^T\right)\\
    \textrm{subject to}\quad & c^T\lambda \leq 1 \;;\; 0\leq\lambda\leq \mathbf{1}
\end{split}
\end{equation}
We denote by $L^*_c$ its optimal value.

Let $\alpha\in\mathbf{R}^+$, consider the perturbed optimization problem:
\begin{equation}\tag{$P_{c, \alpha}$}\label{eq:perturbed-primal}
    \begin{split}
        \mathrm{maximize}\quad & L(\lambda) \defeq\log\det\left(I_d + \sum_{i=1}^n
    \lambda_i x_i x_i^T\right)\\
    \textrm{subject to}\quad & c^T\lambda \leq 1 \;;\; \alpha\leq\lambda\leq \mathbf{1}
\end{split}
\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
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)
\end{displaymath}
so that:
\begin{displaymath}
    L^*_c(\alpha) = \min_{\mu, \nu, \xi\geq 0}\max_\lambda \mathcal{L}_{c, \alpha}(\lambda, \mu, \nu, \xi)
\end{displaymath}
Similarly, we define $\mathcal{L}_{c}\defeq\mathcal{L}_{c, 0}$ the lagrangian of \eqref{eq:primal}.

Let $\lambda^*$ be primal optimal for \eqref{eq:perturbed-primal}, and $(\mu^*,
\nu^*, \xi^*)$ be dual optimal for the same problem. In addition to primal and
dual feasibility, the KKT conditions give $\forall i\in\{1, \ldots, n\}$:
\begin{gather*}
    \partial_i L(\lambda^*) + \mu_i^* - \nu_i^* - \xi^* c_i = 0\\
    \mu_i^*(\lambda_i^* - \alpha) = 0\\
    \nu_i^*(1 - \lambda_i^*) = 0
\end{gather*}

\begin{lemma}\label{lemma:derivative-bounds}
    Let $\partial_i L(\lambda)$ denote the $i$-th derivative of $L$, for $i\in\{1,\ldots, n\}$, then:
    \begin{displaymath}
        \forall\lambda\in[0, 1]^n,\;\frac{b}{2^n} \leq \partial_i L(\lambda) \leq 1
    \end{displaymath}
\end{lemma}

\begin{proof}
    Let us define:
    \begin{displaymath}
        S(\lambda)\defeq I_d + \sum_{i=1}^n \lambda_i x_i\T{x_i}
        \quad\mathrm{and}\quad
        S_k \defeq I_d + \sum_{i=1}^n x_i\T{x_i}
    \end{displaymath}

    We have $\partial_i L(\lambda) = \T{x_i}S(\lambda)^{-1}x_i$. Since
    $S(\lambda)\geq 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 $S(\lambda) \leq S_n$. Hence
    $\partial_iL(\lambda)\geq \T{x_i}S_n^{-1}x_i$.

    Using the Sherman-Morrison formula, for all $k\geq 1$:
    \begin{displaymath}
        \T{x_i}S_k^{-1} x_i = \T{x_i}S_{k-1}^{-1}x_i 
        - \frac{(\T{x_i}S_{k-1}^{-1}x_k)^2}{1+\T{x_k}S_{k-1}^{-1}x_k}
    \end{displaymath}

    By the Cauchy-Schwarz inequality:
    \begin{displaymath}
        (\T{x_i}S_{k-1}^{-1}x_k)^2 \leq \T{x_i}S_{k-1}^{-1}x_i\;\T{x_k}S_{k-1}^{-1}x_k
    \end{displaymath}

    Hence:
    \begin{displaymath}
        \T{x_i}S_k^{-1} x_i \geq \T{x_i}S_{k-1}^{-1}x_i 
        - \T{x_i}S_{k-1}^{-1}x_i\frac{\T{x_k}S_{k-1}^{-1}x_k}{1+\T{x_k}S_{k-1}^{-1}x_k}
    \end{displaymath}

    But $\T{x_k}S_{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}S_{k}^{-1}x_i \geq \T{x_i}S_{k-1}^{-1}x_i
        - \frac{1}{2}\T{x_i}S_{k-1}^{-1}x_i\geq \frac{\T{x_i}S_{k-1}^{-1}x_i}{2}
    \end{displaymath}

    By induction:
    \begin{displaymath}
        \T{x_i}S_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}

\begin{lemma}\label{lemma:proximity}
We have:
\begin{displaymath}
    L^*_c - \alpha n\leq L^*_c(\alpha) \leq L^*_c
\end{displaymath}
In particular, $|L^*_c - L^*_c(\alpha)| \leq \alpha n$.
\end{lemma}

\begin{proof}
    $\alpha\mapsto L^*_c(\alpha)$ is a decreasing function as it is the
    maximum value of the $L$ function over a set-decreasing domain, which gives
    the rightmost inequality.

    Let $\mu^*, \nu^*, \xi^*$ be dual optimal for $(P_{c, \alpha})$, that is:
    \begin{displaymath}
        L^*_{c}(\alpha) = \max_\lambda \mathcal{L}_{c, \alpha}(\lambda, \mu^*, \nu^*, \xi^*)
    \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,
    \begin{displaymath}
        L^*_{c}(\alpha) \geq \mathcal{L}_{c}(\lambda, \mu^*, \nu^*, \xi^*) - \T{\alpha}\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^*
    \end{equation}

    Note that from the KKT conditions, we cannot have both $\mu_i^*$ and $\nu_i^*$ different from zero, hence:
    \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
    \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.
\end{proof} 

\begin{lemma}\label{lemma:monotonicity}
    If $c'$ = $(c_i', c_{-i})$, with $c_i'\leq c_i - \delta$, we have:
    \begin{displaymath}
        L^*_{c'}(\alpha) \geq L^*_c(\alpha) + \frac{\alpha\delta b}{2^n}
    \end{displaymath}
\end{lemma}

\begin{proof}
    Let $\mu^*, \nu^*, \xi^*$ be dual optimal for $(P_{c', \alpha})$. Noting that, $\mathcal{L}_{c', \alpha}(\lambda, \mu^*, \nu^*, \xi^*) \geq
    \mathcal{L}_{c, \alpha}(\lambda, \mu^*, \nu^*, \xi^*) + \lambda_i\xi^*\delta$, we get similarly to Lemma~\ref{lemma:proximity}:
    \begin{displaymath}
        L^*_{c'}(\alpha) \geq L(\lambda) + \lambda_i\xi^*\delta
    \end{displaymath}
    for any $\lambda$ feasible for \eqref{eq:perturbed-primal}. In particular, for $\lambda^*$ primal optimal for \eqref{eq:perturbed-primal}:
    \begin{displaymath}
        L^*_{c'}(\alpha) \geq L^*_{c}(\alpha) + \alpha\xi^*\delta
    \end{displaymath}
    since $\lambda_i^*\geq \alpha$.

    Using the KKT conditions for $(P_{c', \alpha})$, we can write:
    \begin{displaymath}
        \xi^* = \inf_{i:\lambda^{'*}_i>\alpha} \frac{\T{x_i}S(\lambda^{'*})^{-1}x_i}{c_i'}
    \end{displaymath}
    with $\lambda^{'*}$ optimal for $(P_{c', \alpha})$. Since $c_i'\leq 1$, using Lemma~\ref{lemma:derivative-bounds}, we get that $\xi^*\geq \frac{b}{2^n}$, which concludes the proof.
\end{proof}

\begin{proposition}
    Let $\delta\in(0,1]$. For any $\varepsilon\in(0,1]$, there exists
    a routine which computes an approximate solution $\tilde{L}^*_c$ to
    \eqref{eq:primal} such that:
    \begin{enumerate}
        \item $|\tilde{L}^*_c - L^*_c| \leq \varepsilon$
        \item for all $c' = (c_i', c_{-i})$ with $c_i'\leq c_i-\delta$, $\tilde{L}^*_c \leq \tilde{L}^*_{c'}$
        \item the routine's running time is $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$
    \end{enumerate}
\end{proposition}

\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
$L^*_c(\alpha)$ with an accuracy $\frac{1}{2^{n+1}}\alpha\delta b$ computed by
a standard convex optimization algorithm

\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
\end{displaymath}

\item let $c' = (c_i', c_{-i})$ with $c_i'\leq c_i-\delta$, then:
\begin{displaymath}
    \tilde{L}^*_{c'} \geq L^*_{c'} - \frac{\alpha\delta b}{2^{n+1}} 
                     \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}.

\item the accuracy of the approximation $\tilde{L}^*_c$ is:
\begin{displaymath}
    A\defeq\frac{\varepsilon\delta b}{2^{n+1}(\delta + n)}
\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
\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}