Iterative Optimization of Multidimensional Functions on Turing Machines under Performance Guarantees

Holger Boche, Volker Pohl, H. Vincent Poor · 2025

Read Iterative Optimization of Multidimensional Functions on Turing Machines under Performance Guarantees by Holger Boche, Volker Pohl, H. Vincent Poor (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-13038.txt.

Introduction

Holger Boche and co-authors ask whether iterative solvers can promise a set accuracy in a 2025 paper. Many optimization routines improve step by step toward a minimum. Users want a stop rule that certifies a chosen error bound. The team tested that hope for a classic block wise method.

The answer is generally no, even for friendly curved problems. Some single steps cannot be carried out exactly on a digital machine. Other minima exist but the method can never reach them at all. Plain examples show both failure modes in concrete form.

Catalog record

CREATORHolger Boche, Volker Pohl, H. Vincent Poor
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-13038

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Iterative Optimization of Multidimensional Functions on Turing Machines under Performance Guarantees Thanks: This work was partly supported by the German Federal Ministry of Education and Research (BMBF) within the national initiative on 6G Communication Systems through the research hub 6G-life under Grant 16KISK002, and within the national initiative for Quantum Communication in the BMBF quantum programs QD-CamNetz, Grant 16KISQ077, QuaPhySI, Grant 16KIS1598K, QUIET, Grant 16KISQ093, and QR-X, Grant 16KISQ037K. The work of H. V. Poor was partly supported by the U.S. National Science Foundation under Grand CNS-2128448. Holger Boche, Volker Pohl, H. Vincent Poor Abstract . This paper studies the effective convergence of iterative methods for solving convex minimization problems using block Gauss–Seidel algorithms. It investigates whether it is always possible to algorithmically terminate the iteration in such a way that the outcome of the iterative algorithm satisfies any predefined error bound. It is shown that the answer is generally negative. Specifically, it is shown that even if a computable continuous function which is convex in each variable possesses computable minimizers, a block Gauss–Seidel iterative method might not be able to effectively compute any of these minimizers. This means that it is impossible to algorithmically terminate the iteration such that a given performance guarantee is satisfied. The paper discusses two reasons for this behavior. First, it might happen that certain steps in the Gauss–Seidel iteration cannot be effectively implemented on a digital computer. Second, all computable minimizers of the problem may not be reachable by the Gauss–Seidel method. Simple and concrete examples for both behaviors are provided. 2000 Mathematics Subject Classification Primary 90C25, 90C06; Secondary 68W40, 03D80 1. Introduction Many problems in physics and engineering can be formulated as optimization problems. The most important example may be the second law of thermodynamics which may be restated as the principle of minimum energy. But also problems of finding the optimal allocation of limited resources, signal processing and signal recovery problems [ 22 , 20 ] , solutions for compressed sampling problems [ 11 , 10 , 14 ] , or problems in financial mathematics [ 5 ] and operations research can be formulated as optimization problems. In particular, a large number of problems and challenges in artificial intelligence and data science are formulated as optimization problems [ 19 ] . Modern computer technology makes these theoretical optimization problems extremely powerful engineering tools because fast digital hardware allows one to solve even huge optimization problems in high dimensions very fast based on advanced algorithms developed over the past few decades for the different optimization problems. Nevertheless, the question of whether a particular value ”solves” a certain problem depends on the actual requirements on the ”solution” by the user. Already immediately after the introduction of the mathematical notion of computing , due to Turing [ 27 , 28 ] , it became clear that few physical problems can be solved exactly by digital computations. For most problems, the exact solution can only be approximated (arbitrarily well) by the outcome of computations on a digital computer. For this reason, Turing required that the result of the computing process satisfy a predefined bound on the approximation error. We will discuss this requirement later in more detail, because the underlying question of this paper is whether it is always possible to control this approximation error for solutions obtained by iterative optimization methods. At this point, we only mention that the algorithms from [ 22 , 20 , 11 , 10 , 5 ] as many other algorithms in applications, do not satisfy this condition, i.e. in all these algorithms it is not possible to control the difference between the computed ”solution” and the true value of the problem. The mentioned limitation of digital computation mainly originates from the fact that a digital computer can compute exactly only with rational numbers. Real numbers can generally not be represented exactly on a digital computer, but rather can only be approximated by rational numbers. If a real number can effectively (i.e. by controlling the approximation error) be approximated by rational numbers, it is said to be (Turing-) computable (cf. Section 2 for details). Otherwise it is said to be non-computable . This paper studies some consequences of this limitation of digital computers on the ability to solve optimization problems on digital hardware. We basically consider the following simple optimization problem in the m -dimensional real Euclidean space \mathbb{R}^{m} : (1) \min_{\mathbf{x}\in\mathcal{R}}f(\mathbf{x}) where f:\mathbb{R}^{m}\to\mathbb{R} is a continuous function and \mathcal{R}\subset\mathbb{R}^{m} is a convex and compact subset of \mathbb{R}^{m} . It is well known [ 23 ] that the minimum value \mathrm{Min}_{\mathcal{R}}(f)=\min_{\mathbf{x}\in\mathcal{R}}f(\mathbf{x}) of this optimization problem is always Turing computable. Moreover, if the problem has a unique minimizer, i.e. if the set (2) \mathcal{MIN}_{\mathcal{R}}(f)=\big\{\widehat{\mathbf{x}}\in\mathcal{R}:f(\widehat{\mathbf{x}})=\mathrm{Min}_{\mathcal{R}}(f)\big\} contains exactly one vector, then also this minimizer is Turing computable. If the minimizer is not unique, then some or all of the minimizers might not be Turing computable [ 23 ] which means that these optimizers cannot effectively be computed on any digital computer. Still, as long as the optimization problem contains at least one computable minimizer, this minimizer can, in principle, algorithmically be computed on a digital computer. One only needs to construct a sequence \left\{\mathbf{x}^{(k)}\right\}_{k\in\mathbb{N}} of computable vectors \mathbf{x}^{(k)}\in\mathbb{R}^{m} that effectively converges to the computable minimizer \widehat{\mathbf{x}} . This is always possible, since the minimizer is computable, although finding such a sequence might be a fairly complicated and creative problem. The question is now whether this process, of finding a computable sequence that effectively converges to a computable minimizer, can (efficiently) be automated on a digital computer [ 12 ] . Practical algorithms usually apply a certain (suboptimal) strategy to find such a sequence \big\{\mathbf{x}^{(k)}\big\}_{k\in\mathbb{N}} that converges to a minimizer of the given function. A very popular and successful strategy is to minimize successively only over one (or several) coordinates of \mathbf{x}\in\mathbb{R}^{m} while keeping the other dimensions fixed. This approach appears in the literature in many different variants and under various names such as block Gauss-Seidel methods, block coordinate decent method, or block coordinate update method, to mention only some of many variants of the general idea [ 3 , 30 , 14 , 16 , 25 , 31 ] . Thus, if (3) \mathcal{R}=[a_{1},b_{1}]\times[a_{2},b_{2}]\times\dots\times[a_{m},b_{m}] and if \mathbf{x}^{(0)}=(x^{(0)}_{1},x^{(0)}_{2},\dots,x^{(0)}_{m})\in\mathbb{R}^{m} is an arbitrary initialization vector then one successively solves, for \ell=1,2,\dots,m , the one dimensional optimization problems (4) x_{\ell}^{(k+1)}=\arg\min_{y\in[a_{\ell},b_{\ell}]}f(x_{1}^{(k+1)},\dots,x_{\ell-1}^{(k+1)},y,x_{\ell+1}^{(k)},\dots,x_{m}^{(k)}) and iterates then over k=0,1,2,\dots . This strategy produces a sequence \left\{\mathbf{x}^{(k)}\right\}_{k\in\mathbb{N}} that converges to a global minimizer \widehat{\mathbf{x}} of f under fairly weak (convexity) conditions on f . However, the so determined sequence \left\{\mathbf{x}^{(k)}\right\}_{k\in\mathbb{N}} may not effectively converge to the global minimizer. Instead, it may happen that: • Some of the computational steps of the algorithm are not Turing computable, i.e. they may not be realizable on a digital computer with an effective control of the approximation error. • The sequence \big\{\mathbf{x}^{(k)}\big\}_{k\in\mathbb{N}} may converge to a non-computable minimizer of f . Thus even through there exists a global computable optimizer of f , the automated procedure might not be able to find a corresponding approximation sequence \left\{\mathbf{x}^{(k)}\right\}_{k\in\mathbb{N}} of computable vectors that effectively converges to this minimizer. So the automated procedure, i.e. the algorithm, might not be able to compute a global minimizer of f . In

Read the complete text