Proximal operator of quotient functions with application to a feasibility problem in query optimization

摘要

In this paper we determine the proximity functions of the sum and the maximum of componentwise (reciprocal) quotients of positive vectors. For the sum of quotients, denoted by Q1, the proximity function is just a componentwise shrinkage function which we call q-shrinkage. This is similar to the proximity function of the ℓ1-norm which is given by componentwise soft shrinkage. For the maximum of quotients Q∞, the proximal function can be computed by first order primal–dual methods involving epigraphical projections.The proximity functions of Qν, ν=1,∞ are applied to solve convex problems of the form argminxQν(Axb) subject to x≥0, 1⊤x≤1. Such problems are of interest in selectivity estimation for cost-based query optimizers in database management systems.