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.

这个合作研究项目的目标是进行深入研究的类二进制约束（BC），数学规划与互补约束（MPCC）。 此类程序形成了一类广泛的具有二元变量的约束优化问题，其中一些约束由互补的析取条件描述。 后者的功能产生于一些应用问题，其中离散变量被用来模拟二元决策和互补约束的结果，一些较低层次的最优性或平衡条件。基于线性互补约束（LPCC）及其扩展到凸二次目标函数（QPCC）问题的全局解的最新进展，本研究将首先开发二进制约束LPCC和QPCC全局解的有效求解方法。 扩展所提出的方法，以更广泛的一类二进制约束凸数学规划与互补约束将是第二阶段的调查。如果成功的话，这项研究的结果将导致更好地理解这样的问题，如最佳工厂在竞争市场中的位置，离散选择投资组合选择的风险，分类在医疗决策，以及信号和图像处理中的压缩传感，以及涉及具有逻辑约束的分层决策的复杂工程和经济系统中的许多相关应用。为了有效地处理所考虑问题的离散和连续特征，需要整合来自不同优化领域的计算进步。这些优化子域的整合以及在理解这类新优化问题的内在属性方面预期的理论进展构成了拟议项目的知识核心。