Message-Passing Algorithms: A New Approach to Large Scale Optimization

这项研究的目的是开发和分析的消息传递算法，解决大规模的优化问题。 将进行涉及资源分配和计算机网络监测应用程序的案例研究，以验证这些想法。 算法将被设计为解决凸和非凸优化问题，并以集中或异步分布式格式执行。 所有的变化都将在案例研究中考虑，这将解决需要这些功能的问题公式。如果成功，这项研究将导致有用的分析和计算方法，补充目前从更传统的优化领域，如线性，凸和整数规划的工具集。 在资源分配的上下文中，消息传递算法将提供解决非凸优化的异步分布式算法。 例如，这可以用于设计新的协议，以管理具有非弹性流量的通信网络中的传输速率。 在计算机网络监视的上下文中，消息传递算法支持有效的机制，通过该机制，可以使用可管理数量的硬件计数器来有效地估计流。 这对于计费、确保满足提供商之间的服务级别协议以及安全性都是必要的。它也适用于交通工程和容量规划。

The objective of this proposed research is for the development and analysis of message-passing algorithms that address large-scale optimization problems. Case studies involving applications in resource allocation and computer network monitoring will be conducted to validate ideas. Algorithms will be designed to address both convex and nonconvex optimization problems and to be executed in either centralized or asynchronous distributed formats. All variations will be considered in the case studies, which will address problem formulations that call for these features.If successful, this research will lead to useful analytical and computational methods that complement the set of tools currently available from more traditional areas of optimization such as linear, convex, and integer programming. In the context of resource allocation, message-passing algorithms will provide asynchronous distributed algorithms that address nonconvex optimization. This can be used, for example, to design new protocols that govern transmission rates in communication networks with inelastic traffic. In the context of computer network monitoring, message-passing algorithms support efficient mechanisms through which flows can be efficiently estimated using a manageable number of hardware counters. This is necessary for billing, ensuring that service level agreements between providers are met, and for security. It is also useful in for traffic engineering and capacity planning.