Multi-Precision Optimization and Methods with Inaccurate Functions and Derivatives

优化是指在所有满足期望属性的候选者中寻找问题的最佳解决方案。大量的优化问题在计算机上例行解决，如规划航线、预报天气、设计空气动力学结构、提供用户建议、管理水库、发电厂以及加拿大人每天依赖的许多其他任务。解决这些问题需要消耗大量的能源。本提案的主题是设计更好的方法，利用问题结构和现代计算机体系结构。其主要目标是减少在解决此类问题时所消耗的计算工作量和能量。现代计算机，包括笔记本电脑、电子手表、智能手机和超级计算机，都以混合处理单元为特色，每个处理单元都被设计用于执行特定类型的计算，达到特定的精度。随着单位精度能力的提高，执行类似计算所消耗的能量增加了大约四倍。通常，用中等精度解决问题，称为双精度。某些类型的问题，例如推荐系统，只需要较低的精度，例如半精度。在系统生物学中，其他一些问题则需要高精度的解决方案，称为四倍精度，因此需要专门的硬件或软件。在本提案中，我们描述了在低精度和高精度单元之间动态交替的解决方法的设计，目的是在廉价，节能的低精度中执行尽可能多的工作。这样做，我们仍然达到用户或应用程序所要求的精度水平。我们将根据流体动力学等应用中使用的方法所启发的原理，设计出多精度优化策略。我们的方法自动发现并利用问题结构和计算机上可用的计算单元来运行它们。典型的双精度方法只能依赖这么多的问题信息，而我们的方法则受益于额外的低精度信息，这些信息比高精度信息的获取成本更低，并允许它们在解决方案的道路上做出更明智的决策。我们的方法的优点是：1)更快的解决方案，因为在低精度下发生更多的计算；2)更少的数据在慢速和快速内存之间移动；3)更环保的计算，因为在解决过程中节省了能源消耗。我们最近的研究表明，简单的策略可以节省2到5倍的能源。本文提出的一些方法的初步实验表明，在解决问题时节省高达95%的成本，而最终解决方案的质量没有明显差异。这项研究将产生适用于大型应用程序的高效开放软件和更快的计算方法。对加拿大的直接好处是决策过程更高效、更环保。

Optimization is concerned with the search for a best solution to a problem among all candidates satisfying desirable properties. Large numbers of optimization problems are solved routinely on computers to plan air routes, forecast weather, design aerodynamic structures, provide user recommendations, manage water reservoirs, power plants, and many more tasks that Canadians rely on daily. Solving those problems consumes large amounts of energy. The theme of this proposal is the design of better methods that take advantage of problem structure and modern computer architectures. The main objective is to decrease the computational effort and energy expended in solving such problems. Modern computers, including laptops, e-watches and smart phones and supercomputers, feature a mixture of processing units, each designed to perform certain types of computations to a specified accuracy. As the accuracy capacity of a unit increases, the energy expended to perform a similar calculation increases approximately fourfold. Commonly, problems are solved with intermediate accuracy, known as double precision. Certain types of problems, such as recommendation systems, only require low accuracy, e.g., half precision. Others, in systems biology, require solutions to such high accuracy, called quadruple precision, that specialized hardware or software is required. In this proposal, we describe the design of solution methods that alternate between low and high-accuracy units dynamically with the objective of performing as much work as possible in cheap, energy-efficient low accuracy. In doing so, we still attain the accuracy level requested by the user or demanded by the application. We will devise multi-precision optimization strategies based on principles inspired from methods used in applications such as fluid dynamics. Our methods automatically discover and capitalize on the problem structure and on the computational units available on the computer on which they run. Whereas typical double-precision methods can only afford to rely on so much problem information, our methods benefit from additional low-accuracy information, which is cheaper to obtain than high accuracy information, and allows them to make better-informed decisions on the way to a solution. The advantages of our approach are: 1) Faster solves due to more computation occurring in low precision 2) Less data movement between slow and fast memory 3) Greener computation due to savings in energy expended during the solves. Simple strategies in our recent research showed energy savings of a factor from 2 to 5. Preliminary experiments with some of the methods proposed here suggest savings up to 95% to solve problems without noticeable difference in the quality of the final solution. This research will result in efficient open software and faster computational methods that apply to large classes of applications. The immediate benefits to Canada are more efficient and greener decision processes.