Design, analysis and implementation of algorithms utilizing convex optimization

点击翻译按钮获取中文摘要

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.**