题  目：New Global Algorithms for Quadratic Programming with A Few Negative Eigenvalues

主讲人：罗和治 浙江工业大学教授

时  间：2018年5月29日 10:30-11:30

地  点：同济大厦A楼305教室

报告内容摘要

We consider a quadratic program with a few negative eigenvalues (denoted by QP-r-NE) subject to linear and convex quadratic constraints that covers a broad range of applications and is known to be NP-hard even with one negative eigenvalue (r=1, denoted by QP1NE). In this paper, we first introduce a new global algorithm (called ADMBB), which integrates several simple effective optimization techniques such as alternative direction method (ADM), convex relaxation, initialization and branch-and-bound, to  find a globally optimal solution to the underlying QP within a pre-specified $\epsilon$-tolerance. We establish the global convergence of the algorithm and estimate its complexity. Second, we combine ADM, convex relaxation and line search technique to develop a global search  algorithm (GSA) for QP1NE that can locate an optimal solution  to QP1NE within $\epsilon$-tolerance. We establish a worst-case complexity of  the GSA. Preliminary numerical results demonstrate that the ADMBB algorithm can effectively find a global optimal solution to large-scale QP-r-NE instances when r<=10, and the GSA outperforms the ADMBB for most of the tested QP1NE instances.

Keywords: quadratic programming, alternative direction method, convex relaxation, branch-and-bound, line search, computational complexity.

报告人简介

罗和治，浙江工业大学经贸管理学院教授，现为中国运筹学会数学规划分会理事。2007年获上海大学运筹学博士学位，2008-2010年为复旦大学管理科学与工程博士后研究人员。主要研究方向为全局最优化理论与算法及其在金融工程中的应用。已在国际运筹与优化期刊SIAM J. Optim.、Comput. Optim. Appl.、J. Global Optim.、J. Optim. Theory Appl.等上发表SCI 论文20 余篇。主持了国家自然科学基金面上项目2 项，中国博士后科学基金重点项目1 项，浙江省自然科学基金面上项目3项。入选浙江省“新世纪151人才工程”第二层次培养人员（2012）。曾获中国运筹学会青年科技奖提名奖（2010）、复旦大学优秀博士后（2011）、浙江省自然科学学术奖三等奖（2012）。曾多次学术访问美国伊利诺伊大学香槟分校、美国休斯顿大学和香港中文大学。