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

University Of Houston, Houston TX

Investigators

Abstract

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.