## 5 Multiplicative Iterative Algorithms
Hence we rewrite Equation (51) as  
\[x_{j}\left\{-\sum_{i=1}^{n}(\
abla l_{i}(\mu_{i})^{+}\
abla_{j} \mu_{i}(\mathbf{x})^{-}+\
abla l_{i}(\mu_{i})^{-}\
abla_{j}\mu_{i}(\mathbf{x})^{+})+h [\
abla_{j}J(x)]^{+}\right\}\] \[=x_{j}\left\{\sum_{i=1}^{n}(\
abla l_{i}(\mu_{i})^{+}\
abla_{j} \mu_{i}(\mathbf{x})^{+}+\
abla l_{i}(\mu_{i})^{-}\
abla_{j}\mu_{i}(\mathbf{x})^{-})-h[ \
abla_{j}J(x)]^{-}\right\} \tag{52}\]  
This equation naturally suggests the following fixed point algorithm to update \(\mathbf{x}\):  
\[x_{j}^{(k+1/2)}=x_{j}^{(k)}\frac{\delta_{j1}^{(k)}+\epsilon}{\delta_{j2}^{(k)}+\epsilon} \tag{53}\]  
where \(\delta_{j1}^{(k)}\) and \(\delta_{j2}^{(k)}\) denote respectively the right and left hand side of Equation (52), namely,  
\[\delta_{j1}^{(k)}=\sum_{i=1}^{n}\{\
abla l_{i}(\mu_{i}^{(k)})^{+}\
abla_{j}\mu _{i}(\mathbf{x}^{(k)})^{+}+\
abla l_{i}(\mu_{i}^{(k)})^{-}\
abla_{j}\mu_{i}(\mathbf{x} ^{(k)})^{-}\}-h[\
abla_{j}J(\mathbf{x}^{(k)})]^{-} \tag{54}\]  
and  
\[\delta_{j2}^{(k)}=-\sum_{i=1}^{n}\{\
abla l_{i}(\mu_{i}^{(k)})^{+}\
abla_{j} \mu_{i}(\mathbf{x}^{(k)})^{-}+\
abla l_{i}(\mu_{i}^{(k)})^{-}\
abla_{j}\mu_{i}(\bm {x}^{(k)})^{+}\}+h[\
abla_{j}J(\mathbf{x}^{(k)})]^{+} \tag{55}\]  
and \(\epsilon\) is a small positive constant, such as \(\epsilon=10^{-5}\), used to avoid zero denominate of Equation (53). Note that the \(\epsilon\) value does not affect where the algorithm converges to. As both numerator and denominator of Equation (53) are positive, \(x_{j}^{(k+1/2)}\geq 0\) whenever \(x_{j}^{(k)}\geq 0\). In Equation (53) the updated \(x_{j}\) is denoted by \(x_{j}^{(k+1/2)}\) indicating this is not the final estimate for iteration \(k+1\). In fact, this update does not ensure monotonic increment of \(\Psi(\mathbf{x})\) and a line search step must be included to rectify this problem. We first express Equation (53) as a gradient algorithm:  
\[x_{j}^{(k+1/2)}=x_{j}^{(k)}+s_{j}^{(k)}\
abla_{j}\Psi(\mathbf{x}^{(k)}) \tag{56}\]  
where \(s_{j}^{(k)}=s_{j}(\mathbf{x}^{(k)})\) with \(s_{j}(\mathbf{x})=x_{j}/(\delta_{j2}(\mathbf{x})+\epsilon)\). Note that \(s_{j}^{(k)}>0\) when \(x_{j}^{(k)}>0\). When \(x_{j}^{(k)}=0\) we set \(s_{j}^{(k)}=0\) only if \(\
abla_{j}\Psi(\mathbf{x}^{(k)})<0\) (since \(x_{j}^{(k)}\) satisfies the KKT condition in this case); otherwise, we set \(s_{j}^{(k)}=\tilde{\epsilon}/(\delta_{j2}(\mathbf{x}^{(k)})+\epsilon)\), where \(\tilde{\epsilon}\) is another small constant such as \(10^{-2}\). Equation (56) explains that \(x_{j}^{(k+1/2)}\) emanates from \(x_{j}^{(k)}\) in the gradient direction of \(\Psi\) with a non-negative step size \(s_{j}^{(k)}\). For the line search step, the search direction is \(\mathbf{d}^{(k)}=\mathbf{x}^{(k+1/2)}-\mathbf{x}^{(k)}\) with \(\alpha^{(k)}>0\) denoting the line search step size. Sine \(\alpha^{(k)}\leq 1\) guarantees \(\mathbf{x}^{(k+1)}\geq 0\), we only search in the fixed range of \(0<\alpha^{(k)}\leq 1\). After including a line search step \(\mathbf{x}^{(k+1)}\) is obtained according to  
\[\mathbf{x}^{(k+1)}=\mathbf{x}^{(k)}+\alpha^{(k)}\mathbf{d}^{(k)} \tag{57}\]  
Due to the fixed search interval, this line search is remarkably simple. One simple and efficient search strategy is provided by the [PERSON]'s rule (e.g., [43]). [PERSON] line search is a finite terminating algorithm. Briefly, it starts with \(\alpha=1\), and for each \(\alpha\) it checks if the following Armijo condition is satisfied:  
\[\
abla_{j}\Psi(\mathbf{x}) \leq 0\text{ if }x_{j}=0 \tag{50}\]0  
where \(0<\xi<1\) is a fixed parameter such as \(\xi=10^{-2}\). If Equation (58) is true then stop; otherwise, reset \(\alpha=\rho\alpha\) (such as \(\rho=0.6\)) and reevaluate the Armijo condition (58). Note that the repeated evaluations of \(\Psi(\mathbf{x}^{(k)}+\alpha\mathbf{d}^{(k)})\) can be made with \(A\mathbf{d}^{(k)}\) being computed only once. Therefore, the line search step does not add extra major computations to the MI algorithm. Convergence properties of the MI algorithm are given in [26,41].