Inverse problems, Robust Optimization and Mathematical Programs with Equilibrium Constraints: Algorithms and Applications

反问题、鲁棒优化和具有平衡约束的数学程序：算法和应用

• 批准号: 0606712
• 负责人: Donald Goldfarb
• 金额: $ 48.58万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-09-01 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0606712&HistoricalAwards=false
• 关键词: Inverse; problems; Robust; Optimization; Mathematical

This project involves the study and development of optimization methods for modeling and solving inverse problems, robust optimization problems, and mathematical programs with equilibrium constraints (MPECs). The goal of inverse problems is to determine the most likely causes for an observed or desired effect. Such problems arise in a number of important military, imaging, signal processing, biomedical, remote-sensing, and geological applications. Inverse problems are ill-posed in the sense that a small error in measurement can lead to large errors in the estimated quantities. The regularization techniques used to obtain stable solutions to inverse problems give rise to general nonlinear programming problems. In special cases, such as imaging and signal processing, the inverse problem can be reformulated as a tractable convex programming problem. In most cases, e.g. shape optimization, however, a non-convex optimization problem needs to be solved. Robust optimization is an approach for modeling and managing uncertainty in an optimization context. Here, rather than solving a parameter identification problem, one is concerned with constrained optimization problems in which the parameters are data and, due to measurement or estimation errors, are only known to lie within bounded uncertainty sets. In ambiguous chance-constrained (robust) optimization it is assumed the parameters are random variables with an uncertain distribution that is only known to lie within an uncertainty set of probability measures. Fortunately, for certain classes of uncertainty sets, robust optimization problems give rise to tractable convex programming problems as long as the non-robust versions of the problems are themselves convex. These problems arise in areas as diverse as engineering design, portfolio selection, and the design of service networks. MPECs have their roots in game theory and bi-level optimization. They are optimization problems in which some of the constraints are parametric variational inequalities or complementarity systems that arise from the optimality conditions for a lower-level optimization problem. MPECs are a good model for a number of important economic problems, where the equilibrium constraints arise from competitive forces, and optimal engineering design problems. Consequently, developing scalable solution algorithms for MPECs is of considerable practical importance. In general, solving problems from any of these three classes is quite difficult and requires significant computational resources. At first glance, these three modeling paradigms appear quite distinct. Consequently, there has been very little interaction between the algorithmic developments that have occurred in these three areas. While all of the paradigms have a unique structure and a special set of issues, they have much in common. Besides their formal analytical similarity, depending on the context all three paradigms are often used to model the same application. A goal of this project is to leverage the common features of these paradigms to develop new and more efficient solution methods. A second goal is to provide interdisciplinary training in inverse problems, robust optimization, and MPECs through the development of new doctoral courses and involvement of students in theoretical research and software development.

该项目涉及建模和求解逆问题，鲁棒优化问题和平衡约束数学程序（MPEC）的优化方法的研究和开发。 逆问题的目标是确定观察到的或期望的效果的最可能的原因。 这样的问题出现在许多重要的军事，成像，信号处理，生物医学，遥感和地质应用。 反问题是不适定的，因为测量中的小误差会导致估计量的大误差。 正则化技术用于获得稳定的解决方案，反问题产生一般的非线性规划问题。 在特殊情况下，如成像和信号处理，反问题可以重新表述为一个易于处理的凸规划问题。 然而，在大多数情况下，例如形状优化，需要解决非凸优化问题。 鲁棒优化是一种在优化环境中建模和管理不确定性的方法。 这里，而不是解决一个参数识别问题，一个是关注约束优化问题，其中的参数是数据，由于测量或估计误差，只知道位于有界不确定性集。 在模糊机会约束（鲁棒）优化中，假设参数是具有不确定分布的随机变量，该不确定分布仅已知位于概率测度的不确定性集合内。 幸运的是，对于某些类别的不确定性集，鲁棒优化问题会产生易处理的凸规划问题，只要问题的非鲁棒版本本身是凸的。 这些问题出现在工程设计、投资组合选择和服务网络设计等不同领域。 MPEC的根源在于博弈论和双层优化。它们是优化问题，其中一些约束是参数变分不等式或互补系统，这些约束是由低级优化问题的最优性条件产生的。 MPEC是一个很好的模型，许多重要的经济问题，其中的均衡约束来自竞争力，以及最优工程设计问题。 因此，开发可扩展的解决方案算法的MPEC是相当重要的实际意义。 一般来说，解决这三类中的任何一类问题都非常困难，并且需要大量的计算资源。 乍一看，这三种建模范式似乎非常不同。 因此，这三个领域的算法发展之间几乎没有相互作用。 虽然所有的范式都有一个独特的结构和一套特殊的问题，但它们有很多共同之处。 除了它们在形式分析上的相似性之外，根据上下文，这三种范式通常用于对同一个应用程序建模。 这个项目的目标是利用这些范例的共同特征来开发新的更有效的解决方法。 第二个目标是通过开发新的博士课程和学生参与理论研究和软件开发，提供反问题，鲁棒优化和MPEC的跨学科培训。