PURDUE UNIVERSITY
Grant: $204,171 - National Science Foundation - Jun. 15, 2009
No votes have been cast for this award yet
Join the conversation: Post a comment about this award
Award Description: The expressive power of nonlinear programs allows the formulation of a remarkable number of application problems from business, science, engineering, and economics. In the presence of nonconvexity, global optimization of such programs poses unmistakable challenges. The objective of this project is to explore how lifting and orthogonal disjunctions can generate computationally tractable cutting planes and convex relaxations for nonlinear programs. The proposed research departs from existing techniques in two crucial dimensions. First, instead of relaxing the left-hand-side and right-hand-side of an inequality independently of each other, tighter relaxations are derived by considering them simultaneously. Second, the techniques do not add new variables, a feature with obvious computational advantages over existing approaches. The objective is to (i) derive, preferably in closed-form, new strong cuts or relaxations for commonly occurring nonlinear structures in areas such as process design and bi-clustering, (ii) characterize structures of nonconvex inequalities where the proposed techniques yield provably tight relaxations, and (iii) design computational procedures that automatically generate strong cuts and evaluate the impact of integrating them in a branch-and-bound algorithm. If successful, this project will provide an impetus to theoretical, algorithmic, and computational advances in deterministic global optimization through research on convexification procedures. A significant expected outcome of this research project is the improvement of the branch-and-bound algorithm for nonconvex programs through the derivation of new and stronger convex relaxations. This project will invigorate the research at the interface of integer programming and global optimization and benefit both communities. The proposed relaxation schemes will be implemented in software enabling the solution of larger nonconvex problems, which, in turn, will impact many application contexts in science, engineering, business, and economics. Work on solving specially-structured problems will bring operational efficiencies in those contexts.
Project Description: The researcher is considering the problem of convexification of nonlinear functions over the 0-1 hypercube. This problem is equivalent to finding a simplicial decomposition of the hypercube where the linear estimator for each simplex underestimates the function over the complete hypercube. He has found some interesting decompositions for the hypercube and is investigating classes of functions that can be convexified using these approaches. In another part, he is working on lifting for disjunctive sets. This has allowed him to interpret perspective cuts from a lifting standpoint. In a third part, he is working on using lifting to obtain inequalities for a bilinear covering set and has been able to identify some classes of facet-defining inequalities for this problem. A student has been employed in this activity starting Fall 2009.
Infrastructure Description: n/a
Jobs Summary: This grant allowed for the creation/retention of the following position: Graduate Research Assistant (130 Hours). (Total jobs reported: 0)
Project Status: Less Than 50% Completed
This award's data was last updated on Jun. 15, 2009. Help expand these official descriptions using the wiki below.
No comments have been added for this project.