A nonsmooth optimization problem in envelope constrained filtering (Q1206221)

The authors develop an efficient method for solving a class of nonsmooth optimization problems which covers the envelope-constrained filtering problem as a special case. The basic problem considered in this note is the following: Problem 1. \(\min\| u\|^ 2\) subject to \(Au+B| u|\leq e\), \(Du=d\), \(B\geq 0\), where \(u\in R^ n\), \(e\in R^ l\), \(d\in R^ k\) are given vectors, \(A,B\in R^{l\times n}\), \(D\in R^{k\times n}\) are given matrices and \(| u|\) denotes the vector \(u\) with \(u_ i\) replaced by \(| u_ i|\). The authors prove that the above Problem 1 is equivalent to the following: Problem 2. \(\min\| z\|^ 2\) subject to \(Hz\leq e\), \(Gz=d\), \(z\geq 0\), where \(z\in R^{2n}\), \(H=[A+B,-A+B]\in R^{l\times 2n}\) and \(G=[D,-D]\in R^{k\times 2n}\). Problem 2 is a standard quadratic programming problem and can be solved by the well-known techniques.