A class of problems for which cyclic relaxation converges linearly |
| |
| Authors: | Dieter Rautenbach Christian Szegedy |
| |
| Institution: | (1) Institut für Mathematik, TU Ilmenau, Postfach 100565, 98684 Ilmenau, Germany;(2) Cadence Berkeley Labs, 1995 University Ave, Berkeley, CA 94704, USA |
| |
| Abstract: | 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 form
for a
i,j
,b
i
,c
i
∈ℝ≥0 with max {min {b
1,b
2,…,b
n
},min {c
1,c
2,…,c
n
}}>0 over the n-dimensional interval l
1,u
1]×l
2,u
2]×⋅⋅⋅×l
n
,u
n
] with 0<l
i
<u
i
for 1≤i≤n. Our result generalizes several convergence results that have been observed for algorithms applied to gate- and wire-sizing
problems that arise in chip design. |
| |
| Keywords: | Cyclic relaxation Coordinate relaxation Method of alternating variables Linear convergence |
| 本文献已被 SpringerLink 等数据库收录！ |
|
