IWCMC14/argmin.tex

   1 The approach detailed previously requires to compute
   2 the variable that minimizes four convex functions
   3 on constraint domains, one
   4 for each primal variable $q_i$, $P_{sh}$, $R_h$, and $x_{hl}$,
   5 Among state of the art for this optimization step, there is
   6 the  L-BFGS-B algorithm~\cite{byrd1995limited},
   7 the truncated Newton algorithm,
   8 the Constrained Optimization BY Linear Approximation (COBYLA) method~\cite{ANU:1770520}.
   9 However, all these methods suffer from being iterative approaches
  10 each iteration including  many steps of computation to obtain an approximation
  11 of the minimal value.
  12 This approach is dramatic since the objective is to
  13 reduce all the computation steps to increase the network lifetime.
  14
  15 A closer look to each function that has to be minimized shows that it is
  16 differentiable and the minimal value can be computed in only one step.
  17 The table~\ref{table:min} presents these minimal value for each primal
  18 variable.
  19 Thanks to this formal calculus, computing the
  20 new iterate of each primal variable  only requires
  21 one computation step.
  22
  23 \begin{table*}[t]
  24 $$
  25 \begin{array}{|l|l|l|}
  26 \hline
  27 q_i^{(k+1)} &
  28  \arg\min_{q>0}
  29 \left(
  30 q^2 + q.
  31 \left(
  32 \sum_{l \in L } a_{il}w_l^{(k)}-
  33 \lambda_i^{(k)}B_i
  34 \right)
  35 \right)
  36  &
  37 \max \left\{\epsilon,\dfrac{\sum_{l \in L } a_{il}w_l^{(k)}-
  38 \lambda_i^{(k)}B_i}{2}\right\} \\
  39 \hline
  40 P_{sh}^{(k+1)}&
  41 \arg \min_{p > 0}
  42 \left(
  43 v_h^{(k)}.\dfrac{\ln(\sigma^2/D_h)}{\gamma p^{2/3}} + \lambda_h^{(k)}p
  44 + \delta_p p^{8/3}
  45 \right)
  46 &
  47 \max \left\{\epsilon,
  48 \left(
  49 \dfrac{
  50 -3\lambda_h^{(k)} + \sqrt{(3\lambda_h^{(k)})^2 + 64\delta_p/\gamma.\ln(\sigma^2/D_h)}
  51 }{16\delta_p}
  52 \right)^{\frac{3}{5}}
  53 \right\} \\
  54 \hline
  55 R_h^{(k+1)}
  56 &
  57 \arg \min_{r \geq 0 }
  58 \left(
  59 \delta_r r^2
  60 -v_h^{(k)}.r - \sum_{i \in N} u_{hi}^{(k)} \eta_{hi}
  61 \right) &
  62 \max\left\{0,\dfrac{v_h^{(k)}}{2\delta_r}\right\}
  63 \\
  64 \hline
  65 x_{hl}^{(k+1)} &
  66 \begin{array}{l}
  67 \arg \min_{x \geq 0}
  68 \left(
  69 \delta_x.x^2  \right.\\
  70 \qquad \qquad + x.
  71 \sum_{i \in N} \left(
  72 \lambda_{i}^{(k)}.(c^s_l.a_{il}^{+} +
  73 c^r. a_{il}^{-} ) \right.\\
  74 \qquad \qquad\qquad \qquad +
  75 \left.\left. u_{hi}^{(k)} a_{il}
  76 \right)
  77 \right)
  78 \end{array}
  79 &
  80 \max\left\{0,\dfrac{-\sum_{i \in N} \left(
  81 \lambda_{i}^{(k)}.(c^s_l.a_{il}^{+} +
  82 c^r. a_{il}^{-} ) + u_{hi}^{(k)} a_{il}
  83 \right)}{2\delta_x}\right\}
  84 \\
  85 \hline
  86 \end{array}
  87 $$
  88 \caption{Primal Variables: Argmin and Direct Calculus}\label{table:min}
  89 \end{table*}
  90
  91
  92 This improvment has been evaluated on a set of experiments.
  93 For 10 tresholds $t$, such that $1E-5 \le t \le 1E-3$, we have
  94 executed 10 times the aproach detailled before either with the new
  95 gradient calculus or with the original argmin one.
  96 The Table~\ref{Table:argmin:time} summarizes the averages of these
  97 excution times, given in seconds. We remark time spent with the gradient
  98 approach is about 37 times smaller than the one of the argmin one.
  99 Among implementations of argmin aproaches, we have retained
 100 the COBYLA one since it does not require any gradient to be executed.
 101
 102 \begin{table*}
 103 \begin{scriptsize}
 104 $$
 105 \begin{array}{|l|l|l|l|l|l|l|l|l|l|l|}
 106 \hline
 107 \textrm{Convergence Treshold} &
 108 10^{-5} &
 109 1.67.10^{-5} &
 110 2.78.10^{-5} &
 111 4.64.10^{-5} &
 112 7.74.10^{-5} &
 113 1.29.10^{-4} &
 114 2.15.10^{-4} &
 115 3.59.10^{-4} &
 116 5.99.10^{-4} &
 117 0.001 \\
 118 \hline
 119 \textrm{Gradient Calculus} &
 120 56.29 &
 121 29.17 &
 122 37.05 &
 123 6.05 &
 124 5.47 &
 125 3.82 &
 126 1.91 &
 127 2.37 &
 128 0.87 &
 129 0.65 \\
 130 \hline
 131 \textrm{Argmin Method} &
 132 2224.27 &
 133 1158.37 &
 134 1125.21&
 135 216.82&
 136 162.26&
 137 126.99&
 138 58.044&
 139 74.204&
 140 23.99&
 141 15.85\\
 142 \hline
 143 \end{array}
 144 $$
 145 \caption{Convergence Times for Gradient and Argmin Methods}\label{Table:argmin:time}
 146 \end{scriptsize}
 147 \end{table*}
 148
 149