A method of truncated codifferential with application to some problems of cluster analysis (Q1598886): Difference between revisions

This paper proposes a descent method based the truncated codifferential. A function \(f: X \to \mathbb{R}\) is called codifferentiable at a point \(x\) if there exists compact convex sets \(\underline{d}f(x) \subseteq \mathbb{R}^{n+1}\) and \(\overline{d} f(x) \subseteq \mathbb{R}^{n+1}\) such that \[ f(x + \Delta) = f(x) + \max_{[a,v] \in \underline{d}f(x)} [a + (v, \Delta )] + \min_{[b, w ] \in \overline{d}f(x)} [b + (w, \Delta )] + o(x, \Delta) , \] where \(\frac{o(x, \Delta)}{\| \Delta \| } \to 0\) as \(\Delta \to 0\). Without loss of generality it is assumed \(\max_{[a,v] \in \underline{d}f(x)} a =0\) and \( \min_{[b, w ] \in \overline{d}f(x)} b=0\). A necessary optimality condition is formulated in terms of the coderivative and \(x\) is called an \textit{inf-stationary} point of \(f\) if \[ 0 \in [\overline{w} + \underline{d}f(x)] \quad \forall \overline{w} = [0, w] \in \overline{d}f(x). \] The class of functions considered are those of the form \[ f(x) = f_{1} (x) + f_{2} (x) = \max_{i \in I} \varphi_{i} (x) + \min_{j \in J} \psi_{j} (x), \] where \(I\), \(J\) are finite index sets and \(\varphi_{i}(i \in I)\) and \(\psi_{j} ( j \in J)\) are continuously differentiable. The \((\varepsilon, \mu)\)- truncated codifferential mappings \(D_{x} f (y) = [\underline{d}_{x} f(y), \overline{d}_{x}f(y)]\) for this class of mappings is given by: \[ \begin{aligned} \underline{d}_{x} f(y) &:= \text{co} \{[a_{i} , v_{i} ] \mid a_{i} = \varphi_{i} (y) - f_{1} (y), \;v_{i} = \varphi_{i}^{\prime} (y), \;i \in R_{\varepsilon} (x) \} \\ \overline{d}_{x} f(y) &:= \text{co} \{[b_{i} , w_{i} ] \mid b_{j} = \psi_{i} (y) - f_{2} (y),\;w_{i} = \psi_{j}^{\prime} (y), \;j \in Q_{\mu} (x) \} \end{aligned} \] where \(R_{\varepsilon} (x) := \{ i \in I \mid \exists y \in S_{\delta} (x): \varphi_{i} (y) \geq f_{1} (y) - \varepsilon \}\) and \(Q_{\mu} (x) := \{j \in J \mid \exists y \in S_{\delta} (x) : \psi_{j} (y) \leq f_{2} (y) + \mu \}\) (\(S_{\delta} (x)\) the \(\delta\) ball around \(x\)). It is shown that \(D_{x} f\) is only Hausdorff continuous in a neighbourhood of \(x\) and so methods for continuous coderivatives do not apply. Convergence to an inf-stationary point of a descent method based on the truncated codifferential is proved. Numerical experiments are reported that use four test functions of varying size as well as an application of the algorithm to the clustering problem for the Wisconsin Diagnostic Breast Cancer database. Best results were obtained using the \(1\)-norm in the objective function. No claim is made that a global minimum is computed but it is noted that the algorithm does jump over some local minima.