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

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

• 批准号: 1402052
• 负责人: Jong-Shi Pang
• 金额: $ 15万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-08-16 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1402052&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）的二进制限制（BC），数学程序类别（BC）进行深入研究。 这种程序与二进制变量形成了一类广泛的约束优化问题，其中某些约束是通过互补性的分离条件来描述的。 后者的特征来自许多应用问题，在这些问题中，离散变量用于模拟二进制决策，互补性约束是某些较低级别的最优性或均衡条件的结果。基于线性互补性约束（LPCC）的全球线性程序的最新进展，及其扩展到凸二次目标函数（QPCC）的问题，仅具有连续变量，此调查最初将开发出有效的解决方案方法，以解决binary-consented LPCCS和QPCCS的全球解决方案方法。 提出的方法将具有互补性约束的更广泛的二进制二元约束数学计划扩展为研究的第二阶段。经济体系涉及层次决策具有逻辑限制。为了有效地处理所考虑的问题的离散和连续特征，需要集​​成各种优化领域的计算进步。这种优化子域的整合和理解这种新的优化问题的内在特性的预期理论进步构成了拟议项目的智力核心。