CAREER: Semidefinite Methods for Robust and Discrete Optimization and Their Applications

这个项目的目标是开发和实施新的和有效的优化方法，用于稳健和离散的优化问题。我们感兴趣的应用领域是金融工程和网络设计。稳健优化框架是对工程中不可避免的建模不确定性的一种尝试。优化问题特别容易受到建模错误的影响，因为在试图利用约束的过程中，最优解通常会放大几倍的错误。在鲁棒框架中，扰动被建模为未知的但有界的，并且假设这些扰动的最坏情况下的行为，优化问题被求解。对建模和估计误差的稳健性对于金融优化问题来说是一个至关重要的问题，因为错误下注会带来严重的后果！然而，令人惊讶的是，稳健优化在金融工程中还没有得到广泛的探索。本文提出的研究为金融问题建立了稳健的动力学模型，并发展了基于半定规划的方法来解决这些问题。这些模型系统地考虑了参数的不确定性，并随着时间的推移获得更多的信息，稳健地更新了误差界。此外，该项目将半定松弛方法扩展到金融环境中自然出现的概率稳健优化问题。该建议的另一个研究重点是为图论问题(如旅行推销员问题和网络设计)建立半定模型。这些模型使用线性矩阵不等式(LM)来表示几何约束，例如图的连通性、指定数目的边/顶点不相交路径等。由这些线性矩阵不等式模型产生的优化问题通常是混合整数半定程序，即其中一些决策变量被约束为整数的半定程序。目前，混合半定规划都是通过放宽完整性约束来近似求解的。然而，随着计算能力的增加和求解半定规划的内点方法变得更加有效，PI期望有一种系统的方法来加强松弛--就像混合整数规划的线性规划松弛的情况一样。作为这一方向的第一步，PI建议为混合半定规划开发几种割道策略。虽然PI感兴趣的问题属于不同的应用领域，但它们是联系在一起的，因为线性矩阵不等式和半定规划提供了必要的工具来有效地建模和求解它们。这项建议的教育部分包括开发一系列关于优化工程应用的研究生课程。这些课程将通过为学生提供坚实的优化理论和实践基础，填补该系课程的一个重要空白。万维网将在这些课程中广泛使用。所有的教学材料都可以在网上找到。PI将为课程中使用的所有示例开发基于Java的小程序，这将允许学生实时实验这些示例。此外，网络上的优化资源将被整合到课程中。这对于通过视频网络学习课程的工科学生来说尤其有用。为了让本科生接触到研究，PI计划组织一个跨学科的优化及其应用研究项目。为方便业界推广，私隐专员公署计划把拟议研究的结果编成软件，并发表有关新技术应用的说明性文章。国际和平研究所预计，用户友好的软件的提供将促进更多的应用程序，并鼓励工业合作。

The objective of this project is to develop and implement new andefficient optimization methods for robust and discrete optimizationproblems. The applications of interest to us are in the fields offinancial engineering and network design. The robust optimizationframework is an attempt to correct for the modeling uncertaintiesthat are inevitable in engineering. Optimization problems areespecially susceptible to modeling errors since, in trying to exploitthe constraints, the optimal solutions typically amplify the errorsseveral fold. In the robust framework, the perturbations are modeledas unknown, but bounded, and optimization problems are solvedassuming worst case behavior of these perturbations. Robustness tomodeling and estimation errors is an issue of critical importance forfinancial optimization problems because of the serious consequencesof making wrong bets! Surprisingly, however, robust optimization hasnot been widely explored in financial engineering. The researchproposed here formulates robust dynamical models for financialproblems and develops semidefinite rogramming based methods forsolving them. These models systematically account for parameteruncertainty and robustly update error-bounds as more informationbecomes available over time. In addition, the project extends thesemidefinite relaxation methodology to probabilistically robustoptimization problems that naturally emerge in the financial context.The other research focus of this proposal is on developingsemidefinite models for graph theoretic problems such as thetraveling salesman problem and network design. These models employlinear matrix inequalities (LM ) to represent geometricconstraints, such as graph connectivity, specified number ofedge/vertex disjoint paths, etc. The optimization problems resultingfrom these LM models are, typically, mixed integer semidefiniteprograms, i.e. semidefinite programs where some of the decisionvariables are constrained to be integers. Currently, mixedsemidefinite programs are appproximately solved by relaxing theintegrality constraints. However, as computational ower increases andthe interior point methods for solving semidefinite programs becomemore efficient, the PI expects that there would be a push fordeveloping systematic methods of tightening the relaxations - as inthe case of linear programming relaxations of mixed integer programs.As a first step in this direction, the PI proposes to develop severalcutting lane strategies for mixed semidefinite programs. Although theproblems of interest to the PI belong to disparate application areas,they are linked in that linear matrix inequalities and semidefiniteprogramming provide the necessary tools to efficiently model andsolve them. The education component of this proposal includesdeveloping a sequence of graduate courses on engineering applicationsof optimization. These courses would fill an important gap in thecurriculum of the Deppartment by providing students with a firmtheoretical and practical grounding in optimization. The World WideWeb will be extensively used in these courses. All the teachingmaterial will be available on the web. The PI will develop Java-basedapplets for all the examples used in the courses which would allowstudents to experiment with these examples in real time. Also, theoptimization resources on the web will be integrated into thecurriculum. This should be particularly useful to students fromindustry who would take the courses over the Video Network. To exposeundergraduate students to research, the PI plans to organize aninterdisciplinary research program in optimization and itsapplications. To facilitate industry outreach, the PI plans toimplement the results of the proposed research into a softwarepackage and publish expository articles on the applications of thenew techniques. The PI expects that the availability of a userfriendly software will spur further applications and encourageindustrial collaboration.