Alternate Direction Method: A New Recipe for Non-Convex Quadratic Programming with Applications

二次规划包括目标函数是二次函数的优化问题。 这样的问题出现在制造系统和服务系统的广泛应用中。虽然存在大量关于二次规划的文献，但大多数现有的优化技术要么不可扩展，要么仅对凸二次规划有效，并且不能为非凸二次规划提供有用的解决方案。该奖项支持基础研究开发一种综合方法，可以有效地解决非凸二次规划问题。新方法可以应用于许多领域，如能源系统和通信的非凸问题。该项目涉及来自代表性不足群体的研究生，并对工程教育产生积极影响。 该研究将主要解决在许多应用中出现的二次约束二次规划优化问题的形式。 除了是非凸的，这些问题是已知的NP-难。 该方法是基于凸规划中的几个简单而有效的优化技术，如线性逼近，交替方向法，多启动技术，线性搜索和凸松弛。然而，需要引入新的概念和程序来建立算法的收敛性并确保所得解的全局最优性。研究团队将探索拉格朗日函数的理论特性，以选择非凸二次规划中理想的拉格朗日乘子，非凸二次规划的新重构模型，以促进新的有效交替方向方法的设计，引入优化的新概念来表征算法生成的序列，以及基于凸松弛和初始化策略的新的线搜索过程，以搜索潜在问题的全局最优解。 研究团队还将进行理论研究，分析新算法的行为，实现新算法，并在合成测试问题和现实应用实例上测试其性能。 所开发的模型和方法将被应用到几个应用程序，如能源系统设计。

Quadratic programming comprises optimization problems where the objective function is a quadratic function. Such problems arise in a broad range of applications from manufacturing systems and service systems. Although there exists a large literature on quadratic programming, most existing optimization techniques are either not scalable or work effectively only for convex quadratic programming and cannot provide useful solutions to non-convex quadratic programming. This award supports fundamental research to develop an integrated approach that can effectively solve classes of non-convex quadratic programming problems. The new approach can be applied to non-convex problems from many domains such as energy systems and communications. The project involves graduate students from underrepresented groups and positively impacts engineering education. The research will primarily address quadratically constrained quadratic programming optimization problems of a form that arises in many applications. Besides being non-convex, these problems are known to be NP-hard. The approach is based on several simple and effective optimization techniques in convex programming such as linear approximation, alternate direction method, multi-starting techniques, linear search and convex relaxation. However, new concepts and procedures need to be introduced to establish the convergence of the algorithm and ensure the global optimality of the obtained solution. The research team will explore the theoretical properties of the Lagrangian function to select the desirable Lagrangian multipliers in nonconvex quadratic programming, new reformulation models for non-convex quadratic programming to facilitate the design of new effective alternate direction method, introduce new concepts in optimization to characterize the generated sequence from the algorithm, and new line search procedures based on convex relaxation and initialization strategies to search for the global optimal solution to the underlying problem. The research team will also conduct theoretical investigations to analyze the behavior of the new algorithm, implement the new algorithm and test its performance on synthetic test problems and instances from real-world applications. The developed models and methodologies will be applied to several applications such as energy system design.