Design, analysis and implementation of algorithms utilizing convex optimization

利用凸优化的算法的设计、分析和实现

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

My research program aims to design, analyze and implement efficient and robust algorithms (solution methods) for problems arising in many application areas such as planning, manufacturing, transportation, finance, as well as service sectors, and information technology (including quantum information and computing). The approach will model these problems and their mathematical generalizations as accurately and reasonably as possible 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) optimization problems defined by (possibly nonconvex) polynomial 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 good solutions, certificates of optimality. For hard problems, we can only hope for certificates of approximate optimality, hence approximation algorithms.***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.***On the theoretical side of the research program lies the subjects of:***(i) lift-and-project methods,***(ii) tractable lifted semidefinite representation and relaxations,***(iii) interior-point algorithms for semidefinite optimization, hyperbolic cone programming and beyond,***(iv) designing convex relaxations and representations based on hyperbolic cone programming.**

我的研究计划旨在设计，分析和实施有效和强大的算法（解决方案方法），以解决规划，制造，交通，金融以及服务部门和信息技术（包括量子信息和计算）等许多应用领域中出现的问题。该方法将尽可能准确、合理地用数学优化问题对这些问题及其数学概括进行建模。这些数学优化问题通常将位于特殊子类（即，* （a）0，1混合整数规划，或 *（B）寻求低秩解的半定优化问题，或 *（c）存在离散变量的半定优化问题，或 *（d）由（可能非凸）多项式不等式定义的优化问题。由于凸优化问题形成了一类非常广泛的易处理的数学优化问题（在合理的假设下，当适定性时，这些问题可以在多项式时间内求解到任意精度），下一步是构造一个易处理的凸逼近原始的困难数学优化问题。从理论的角度来看，这种方法提供了一个框架来设计原始对偶算法。这个框架，然后导致，连同良好的解决方案，证书的最优性。对于困难的问题，我们只能希望近似最优性的证明，因此近似算法。只要可行，最终实现的源代码以及用于计算测试和基准测试的数据将在网上提供。在研究计划的理论方面，主题是：*（i）提升和投影方法，*（ii）易处理的提升半定表示和松弛，*（iii）半定优化，双曲锥规划和超越的边界点算法，*（iv）基于双曲锥规划设计凸松弛和表示。