Houska Boris, Chachuat Benoît
1School of Information Science and Technology, ShanghaiTech University, 319 Yueyang Road, Shanghai, 200031 China.
2Department of Chemical Engineering, Centre for Process Systems Engineering, Imperial College London, South Kensington Campus, London, SW7 2AZ UK.
Math Program. 2019;173(1):221-249. doi: 10.1007/s10107-017-1215-7. Epub 2017 Dec 16.
We propose a complete-search algorithm for solving a class of non-convex, possibly infinite-dimensional, optimization problems to global optimality. We assume that the optimization variables are in a bounded subset of a Hilbert space, and we determine worst-case run-time bounds for the algorithm under certain regularity conditions of the cost functional and the constraint set. Because these run-time bounds are independent of the number of optimization variables and, in particular, are valid for optimization problems with infinitely many optimization variables, we prove that the algorithm converges to an -suboptimal global solution within finite run-time for any given termination tolerance . Finally, we illustrate these results for a problem of calculus of variations.
我们提出一种完全搜索算法，用于将一类非凸的、可能是无限维的优化问题求解到全局最优。我们假设优化变量位于希尔伯特空间的一个有界子集中，并在成本泛函和约束集的某些正则性条件下确定该算法的最坏情况运行时间界限。由于这些运行时间界限与优化变量的数量无关，特别是对于具有无限多个优化变量的优化问题也有效，我们证明了对于任何给定的终止容差 ，该算法在有限运行时间内收敛到一个 -次优全局解。最后，我们通过一个变分法问题来说明这些结果。
