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

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

• 批准号: 1334639
• 负责人: Andreas Waechter
• 金额: $ 15万
• 依托单位: Northwestern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-08-15 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1334639&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.

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