Presented By: U-M Industrial & Operations Engineering
Departmental Seminar (899): Santanu Dey, Georgia Tech — Convexification of substructures in quadratically constrained quadratic program
Convexification of substructures in quadratically constrained quadratic program
The Departmental Seminar Series is open to all. U-M Industrial and Operations Engineering graduate students and faculty are especially encouraged to attend.
The seminar will be followed by a reception in the IOE Commons (Room 1709) from 4 p.m. to 5 p.m.
Title:
Convexification of substructures in quadratically constrained quadratic program
Abstract:
An important approach to solving non-convex quadratically constrained quadratic program (QCQP) to global optimality is to use convex relaxations and branch-and-bound algorithms. In our first result, we show that the exact convex hull of the solutions of a general quadratic equation intersected with any polytope is second-order cone representable. The proof is constructive and relies on the discovery of an interesting property of quadratic functions, which may be of independent interest: A set defined by a single quadratic equation is either (1) the boundary of a convex set, or (2) the boundary of union of two convex sets or (3) it has the property that through every point on the surface, there exists a straight line that is entirely contained in the surface. We next study sets defined for matrix variables that satisfy rank-1 constraint together with different choices of linear side constraints. We identify different conditions on the linear side constraints, under which the convex hull of the rank-1 set is polyhedral or second-order cone representable. Finally, we present results from comprehensive set of computational experiments and show that our convexification results together with discretization significantly help in improving dual bounds for the generalized pooling problem. (This is joint work with Asteroide Santana and Burak Kocuk.)
Bio:
Santanu S. Dey is A. Russell Chandler III Professor in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Institute of Technology. Dr. Dey's research interests are in the area of non convex optimization, and in particular mixed integer linear and nonlinear programming. His research is partly motivated by applications of non convex optimization arising in areas such as electrical power engineering, process engineering, civil engineering, logistics, and statistics. Dr. Dey has served as the vice chair for Integer Programming for INFORMS Optimization Society (2011-2013) and has served on the program committees of Mixed Integer Programming Workshop 2013 and Integer Programming and Combinatorial Optimization 2017. He currently serves on the editorial board of Computational Optimization and Applications, MOS-SIAM book series on Optimization, is an area editor for Mathematical Programming C and is an associate editor for Mathematical Programming A, Mathematics of Operations Research and SIAM Journal on Optimization.
The seminar will be followed by a reception in the IOE Commons (Room 1709) from 4 p.m. to 5 p.m.
Title:
Convexification of substructures in quadratically constrained quadratic program
Abstract:
An important approach to solving non-convex quadratically constrained quadratic program (QCQP) to global optimality is to use convex relaxations and branch-and-bound algorithms. In our first result, we show that the exact convex hull of the solutions of a general quadratic equation intersected with any polytope is second-order cone representable. The proof is constructive and relies on the discovery of an interesting property of quadratic functions, which may be of independent interest: A set defined by a single quadratic equation is either (1) the boundary of a convex set, or (2) the boundary of union of two convex sets or (3) it has the property that through every point on the surface, there exists a straight line that is entirely contained in the surface. We next study sets defined for matrix variables that satisfy rank-1 constraint together with different choices of linear side constraints. We identify different conditions on the linear side constraints, under which the convex hull of the rank-1 set is polyhedral or second-order cone representable. Finally, we present results from comprehensive set of computational experiments and show that our convexification results together with discretization significantly help in improving dual bounds for the generalized pooling problem. (This is joint work with Asteroide Santana and Burak Kocuk.)
Bio:
Santanu S. Dey is A. Russell Chandler III Professor in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Institute of Technology. Dr. Dey's research interests are in the area of non convex optimization, and in particular mixed integer linear and nonlinear programming. His research is partly motivated by applications of non convex optimization arising in areas such as electrical power engineering, process engineering, civil engineering, logistics, and statistics. Dr. Dey has served as the vice chair for Integer Programming for INFORMS Optimization Society (2011-2013) and has served on the program committees of Mixed Integer Programming Workshop 2013 and Integer Programming and Combinatorial Optimization 2017. He currently serves on the editorial board of Computational Optimization and Applications, MOS-SIAM book series on Optimization, is an area editor for Mathematical Programming C and is an associate editor for Mathematical Programming A, Mathematics of Operations Research and SIAM Journal on Optimization.
Explore Similar Events
-
Loading Similar Events...