Extended Mathematical Programs: Hierarchical Models and Solution

传统的优化方法在解决许多应用领域的实际、大规模、复杂问题时已不再有效。典型的应用程序需要许多优化和互补建模方法与特定领域知识的复杂耦合，并需要专家以及时和健壮的方式生成解决方案。这个项目将开发工具和算法，通过制定和探索扩展数学程序(EMP)的概念来帮助解决这种性质的协调问题。这提供了使用嵌入式模型的概念对代理之间的竞争进行建模的能力，这是其他优化方法所缺少的功能。具体的例子包括动态博弈，用于分析多个领域中代理人之间的互动，包括产业组织、劳工和金融谈判和合同、政府财政和货币政策设计、拍卖设计、政治决策和国际冲突解决。主要的好处有三：EMP将使建模者的任务变得更容易，因为可以更自然地、在更高的概念水平上描述模型；可以可靠而高效地生成要求解的实际模型；算法可以以有效的计算方式利用额外的结构。在早期工作的基础上，该项目将开发基于理论的、高效、快速、可靠、用户友好的数值方法来解决扩展的数学规划。如果成功，该项目将开发一个通用的建模框架，适用于广泛的实际问题，并将产生一套连贯和全面的建模和计算工具，可应用于许多应用领域的系统。预计运筹学应用中的进一步重大进展可以通过识别给定模型中的特定问题结构来实现，这一概念构成了电磁脉冲的核心。与多重均衡和潜在问题的大维度相关的困难将通过将结构传达给求解者并开发新的算法来解决，这些算法明确地利用该结构来获得更健壮的解决方案。该项目旨在证明，这种结构的可用性促进了现有求解器的新功能的产生，并推动了新类算法的开发。将在这里实施的算法和方法将通过与GAMS、AMPL和MATLAB的建模系统连接，以及通过使用NEOS服务器和Coin-OR项目等资源通过互联网广泛传播，向整个用户社区提供。

Traditional optimization approaches are no longer effective in solvingpractical, large scale, complex problems from many application domains. Typical applications require a sophisticated coupling of a number of optimization and complementarity modeling approaches with specific domain knowledge and expertize to generate solutions in a timely and robust manner. This project will develop tools and algorithms that help in solving coordinated problems of this nature by formulating and exploring the notion of an extended mathematical program (EMP). This provides the ability to model competition between agents using the notion of an embedded model, a feature that is missing from other optimization approaches. Specific instances include dynamic games that are used to analyze interactions between agents in multiple fields, including industrial organization, labor and financial bargaining and contracts, government design of fiscal and monetary policies, auction design, political decision-making and international conflict resolution. The major benefits are threefold: EMP will make the modelers task easier, in that the model can be described more naturally and at a higher conceptual level; the actual model to be solved can be reliably and efficiently generated; an algorithm can exploit additional structure in an effective computational manner. Building on earlier work, this project will develop theory-based, efficient, fast, reliable, user-friendly numerical methods to solve extended mathematical programs. If successful, this project will develop a general modeling framework, applicable to a wide range of real problems and will produce a coherent and comprehensive suite of tools for modeling and computation that can be applied to systems in many application areas. It is anticipated that further significant advancements in operations research applications can be achieved via identification of specific problem structures within a given model, a notion that forms the core of an EMP. Difficulties associated with multiplicity of equilibria and the large dimension of the underlying problems will be addressed by communicating structure to solvers and developing new algorithms that explicitly utilize that structure for more robust solution. The project aims to demonstrate that the availability of such structure fosters the generation of new features to existing solvers and drives the development of new classes of algorithms. The algorithms and methods that will be implemented here will be made available to the whole user community via modeling system hookups to GAMS, AMPL and MATLAB, and via broad dissemination via the internet using resources such as the NEOS server and the COIN-OR project.