A class of problems for which cyclic relaxation converges linearly

    loading  Checking for direct PDF access through Ovid


The method of cyclic relaxation for the minimization of a function depending on several variables cyclically updates the value of each of the variables to its optimum subject to the condition that the remaining variables are fixed.We present a simple and transparent proof for the fact that cyclic relaxation converges linearly to an optimum solution when applied to the minimization of functions of the formfor ai, j, bi, ci ∈ ℝ≥0 with max{min{b1, b2,…, bn}, min{c1,c2,…, cn}}>0 over the n-dimensional interval [l1,u1]×[l2,u2]×…×[ln, un] with 0<li<ui for 1≤in. Our result generalizes several convergence results that have been observed for algorithms applied to gate- and wire-sizing problems that arise in chip design.

    loading  Loading Related Articles