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.