A Cholesky dual method for proximal piecewise linear programming (Q1338808)

Let us consider the problem of the form: find an \(n\)-vector \(x\) to minimize \[ f(x):= ux^ T x/2+ \sum_{i= 1}^ m c_ i f_ i(x) \] over all \(x\in X\), where \(u\) is a positive scalar, \(c_ i\) are positive components of an \(m\)-vector \(c\), superscript \(T\) denotes transposition, \(f_ i(X)= \max\{P_ j^ T x- a_ j: j\in J_ i\}\), \(i= 1,\dots, m\), \(X=\{x: P_ j^ T x\leq a_ j\) \(\forall j\in J_ 0\}\neq\emptyset\), \(P_ j\) denotes the \(j\)th column of an \(n\times m_ J\) matrix \(P\), \(m_ J\) being the cardinality of the finite set \(J= \{1,2,\dots, m_ J\}\) partitioned into \(m+ 1\) disjoint subsets \(J_ i\) for \(i= 1,\dots, m\), \(a_ j\) are components of an \(m_ J\)-vector \(a\). One may rewrite this problem into an equivalent quadratic programming problem: minimize \(ux^ T x/2+ c^ T v\) over all \((x, v)\in \mathbb{R}^ n\times \mathbb{R}^ m\) satisfying \(P^ T x- H^ T v\leq a\) or its dual problem: minimize \((P\lambda)^ T (P\lambda)/ 2u+ a^ T\lambda\) over all \(\lambda\in \mathbb{R}^{m_ J}\) satisfying \(H\lambda= c\), \(\lambda\geq 0\), where the \(m\times m_ J\) matrix \(H\) has elements \(H_{ij}= 1\) if \(j\in J_ i\) and \(i\geq 1\), otherwise 0. The author concentrates on the case when \(X\) is defined by the simple bounds \(x^{\text{low}}\leq x\leq x^{\text{up}}\) with given \(n\)- vectors \(x^{\text{low}}\leq x^{\text{up}}\); the remaining \(m_ L= m_ J- 2n\) constraints will be called general constraints. He modifies his own recent algorithm [SIAM J. Sci. Stat. Comput. 10, No. 1, 175-186 (1989; Zbl 0663.65063)] solving the above dual problem with a classical active-set strategy, by replacing the QR-factorization by Cholesky factorization of the active general constraints. The obtained implementation reduces the space needs from about \(3n^ 2/2\) to \(m_ L^ 2\); moreover, some special techniques reduce the work per iteration. The author proposes a unified way of finding generalized Newton directions in various cases, including hot starts and iterative refinement; this makes possible the updating of a Cholesky factorization of a certain matrix after row or column additions and deletions. The numerical experiments, done in sixteen-digit precision, suggest that the method is very suitable (robust and accurate enough) for nondifferentiable optimization problems; the author supposes that it is the only one suitable for large scale problems of this type.