Collaborative Research: Binary Constrained Convex Quadratic Programs with Complementarity Constraints and Extensions

协作研究：具有互补约束和扩展的二元约束凸二次规划

• 批准号: 1334327
• 负责人: John Mitchell
• 金额: $ 15万
• 依托单位: Rensselaer Polytechnic Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-08-15 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1334327&HistoricalAwards=false
• 关键词: Collaborative; Research; Binary; Constrained; Convex

The objective of this collaborative research project is to undertake an in-depth study of the class of binary-constrained (BC), mathematical programs with complementarity constraints (MPCCs). Such programs form a broad class of constrained optimization problems with binary variables where some of the constraints are described by the disjunctive condition of complementarity. The latter features arise from a number of applied problems where the discrete variables are used to model binary decisions and the complementarity constraints are the result of some lower-level optimality or equilibrium conditions. Building on recent advances in the global resolution of linear programs with linear complementarity constraints (LPCCs) and their extensions to problems with convex quadratic objective functions (QPCCs), both with continuous variables only, this investigation will initially develop efficient solution methods for the global resolution of binary-constrained LPCCs and QPCCs. Extensions of the proposed methodology to the broader class of binary-constrained convex mathematical programs with complementarity constraints will be the second phase of the investigation.If successful, the results of this research will lead to improved understanding of such problems as optimal plant location in competitive markets, discrete-choice portfolio selection under risk, classification in medical decision making, and compressed sensing in signal and image processing, as well as many related applications in complex engineering and economic systems involving hierarchical decision making with logical constraints. Computational advances from diverse areas of optimization need to be integrated in order to effectively handle the discrete and continuous features of the problems under consideration. The integration of such subdomains of optimization and the expected theoretical advances in understanding the intrinsic properties of this new class of optimization problems form the intellectual core of the proposed project.

这一合作研究项目的目标是深入研究二进制约束(BC)，即具有互补约束的数学规划(MPCCs)。这类程序形成了一大类具有二元变量的约束优化问题，其中一些约束是用互补的析取条件来描述的。后一种特征源于许多应用问题，其中离散变量被用来对二元决策进行建模，而互补约束是一些较低水平的最优性或均衡条件的结果。基于线性互补约束线性规划(LPCCs)全局求解的最新进展及其对具有凸二次目标函数(QPCCs)的问题的推广，这两个问题都只具有连续变量，本研究将初步开发用于二元约束LPCCs和QPCCs全局求解的有效方法。如果研究成功，研究结果将有助于更好地理解竞争市场中的最优工厂选址、风险下的离散投资组合选择、医疗决策中的分类以及信号和图像处理中的压缩感知等问题，以及在复杂工程和经济系统中涉及逻辑约束分层决策的许多相关应用。需要整合来自不同优化领域的计算进展，以便有效地处理所考虑问题的离散和连续特征。这些优化子域的集成以及在理解这类新的优化问题的内在属性方面预期的理论进步构成了拟议项目的智力核心。

项目成果

A penalty method for rank minimization problems in symmetric matrices

• DOI: 10.1007/s10589-018-0010-6
• 发表时间: 2017-01
• 期刊: Computational Optimization and Applications
• 影响因子: 2.2
• 作者: Xin Shen-;J. Mitchell

Solving linear programs with complementarity constraints using branch-and-cut

使用分支剪切法求解具有互补约束的线性规划

• DOI: 10.1007/s12532-018-0149-2
• 发表时间: 2019
• 期刊: Mathematical Programming Computation
• 影响因子: 6.3
• 作者: Yu, Bin;Mitchell, John E.;Pang, Jong-Shi
• 通讯作者: Pang, Jong-Shi