Mathematical Optimization: Theory and Algorithms

数学优化：理论与算法

• 批准号: RGPIN-2020-04324
• 负责人: Tuncel, Levent
• 金额: $ 3.5万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749582
• 关键词: Mathematical; Optimization; Theory; Algorithms

My research program aims to find tractable mathematical models for problems treated within computer science, and then focuses on the design, mathematical analysis and implementation of efficient and robust algorithms (solution methods) for such problems. These problems arise in many application areas such as information technology (including quantum information and computing), manufacturing, transportation, planning, economics, finance, as well as service sectors. The research program focuses on modelling these problems and their mathematical generalizations as accurately as possible (and reasonable) by mathematical optimization problems. These mathematical optimization problems will typically lie in a special subclass (i.e., with additional special structures) of: (a) 0,1 mixed integer programming, or (b) semidefinite optimization problems where we seek low-rank solutions, or (c) semidefinite optimization problems where there are discrete variables, or (d) semidefinite optimization problems where we seek highest rank solutions,or (e) optimization problems defined by (possibly nonconvex) polynomial equations and inequalities. Since convex optimization problems form a very wide class of tractable mathematical optimization problems (under reasonable assumptions, such problems, when well-posed, can be solved to arbitrary accuracy in polynomial-time), the next step is the construction of a tractable convex approximation to the original, hard mathematical optimization problem. From a theoretical viewpoint, this approach provides a framework to design primal-dual algorithms. This framework then leads to, together with approximately optimal solutions, certificates of optimality. For hard problems, we can only hope for certificates of approximate optimality, hence for those, we focus on efficient approximation algorithms. This research program will advance the design, study and implementation of composite first--order and higher--order algorithms which focus on the big-data regime and adapt to the given data instance. These algorithms will combine the desired features of first--order algorithms: 1. low memory requirements, 2. low complexity per iteration, 3. distributability, 4. parallelizability; with those of second--order and higher--order algorithms: 5. much faster global convergence, 6. much, much faster local convergence, 7. high accuracy solutions, 8. robustness. Whenever feasible, the source codes of the resulting implementations as well as the data used for computational test and benchmarking will be made available on the web.

我的研究计划旨在为计算机科学中处理的问题找到易于处理的数学模型，然后专注于设计，数学分析和实现高效和鲁棒的算法（解决方法）。这些问题出现在许多应用领域，如信息技术（包括量子信息和计算），制造业，运输，规划，经济，金融以及服务部门。该研究计划的重点是通过数学优化问题尽可能准确（和合理）地对这些问题及其数学概括进行建模。这些数学优化问题通常将位于特殊子类（即，具有附加的特殊结构）的：（a）0，1混合整数规划，或（B）寻找低秩解的半定优化问题，或（c）存在离散变量的半定优化问题，或（d）寻找最高秩解的半定优化问题，或（e）由（可能非凸的）多项式方程和不等式定义的优化问题。由于凸优化问题形成了一类非常广泛的易处理的数学优化问题（在合理的假设下，当适定性时，这些问题可以在多项式时间内求解到任意精度），下一步是构造一个易处理的凸逼近原始的困难数学优化问题。从理论的角度来看，这种方法提供了一个框架来设计原始对偶算法。这个框架，然后导致，连同近似最优的解决方案，证书的最优性。对于困难的问题，我们只能希望得到近似最优性的证明，因此对于这些问题，我们专注于有效的近似算法。本研究计划将推进面向大数据体系、适应给定数据实例的复合一阶和高阶算法的设计、研究和实现。这些算法将联合收割机的一阶算法所需的功能：1。低内存需求，2.每次迭代的低复杂度，3.可分配性，4.并行性;与二阶和高阶算法的并行性：5.全球收敛速度更快，6.更快的局部收敛，7。高精度解决方案，8。鲁棒性只要可行，所产生的实现的源代码以及用于计算测试和基准测试的数据将在网上提供。