Session Detail Information
Add this session to your itinerary

Cluster :  Global Optimization

Session Information  : Monday Jul 13, 14:45 - 16:15

Title:  New Convexification and Branching Techniques for Nonconvex Optimization
Chair: Amir Ali Ahmadi,Princeton University, a_a_a@princeton.edu

Abstract Details

Title: Envelopes of Bilinear Functions over Polytopes with Application to Network Interdiction
 Presenting Author: Daniel Davarnia,University of Florida, 303 Weil Hall, Gainesville FL, United States of America, d.davarnia@gmail.com
 Co-Author: Jean-Philippe P Richard,University of Florida, 303 Weil Hall P.O. Box 116595, Gainesville FL 32611-6595, United States of America, richard@ise.ufl.edu
 Mohit Tawarmalani,Purdue University, 100 S. Grant Street, West Lafayette IN 47907, United States of America, mtawarma@purdue.edu
 
Abstract: We extend the convexification technique of Nguyen et. al. (2013) to obtain, in the space of their defining variables, a linear description of the convex hull of graphs of bilinear functions over the Cartesian product of a general polytope and a simplex. We apply this procedure to study various sets including those arising from unary expansions of integer variables in MIBP. For network interdiction, our procedure yields an improved set of linearization constraints for bilinear objective terms that is cognizant of paths and cycles in the network. This linearization provides a convex hull description of a suitable problem relaxation and can be shown computationally to lead to significant gap reductions over traditional McCormick linearization.
  
Title: Feasibility-oriented Branching Strategies for Global Optimization
 Presenting Author: Damien Gerard,University of Liège, 10 Grande Traverse, Liège 4000, Belgium, damien.gerard@ulg.ac.be
 Co-Author: Matthias Koeppe,Professor, UC Davis, 1 Shields Ave, Davis CA 95616, United States of America, mkoeppe@math.ucdavis.edu
 Quentin Louveaux,Professor, Université de Liège, 10 Grande Traverse, Liège 4000, Belgium, q.louveaux@ulg.ac.be
 
Abstract: Spatial brand-and-bound is an algorithm to solve nonlinear optimization problems to global optimality. Most spatial branch-and-bound-based solvers use a nonglobal solver at a few nodes to try to find better incumbents. We propose new strategies to use these incumbents to improve the branching rules and the node priorities. We show computationally that the new strategies find the first good incumbents and prove the global optimality faster on benchmark instances.
  
Title: DC Decomposition of Nonconvex Polynomials with Algebraic Techniques
 Presenting Author: Georgina Hall,Princeton University, Department of ORFE, Princeton University, Sherrerd Hall, Charlton street, Princeton 08540, United States of America, gh4@princeton.edu
 Co-Author: Amir Ali Ahmadi,Princeton University, Department of ORFE, Princeton University, Sherrerd Hall, Charlton street, Princeton 08540, United States of America, amirali@princeton.edu
 
Abstract: The concave-convex procedure is a majorization-minimization algorithm for difference of convex (DC) optimization, where the constraints and the objective function are given as the difference of two convex functions. Although several important problems (e.g., in machine learning) already appear in DC form, such a decomposition is not always available. We consider this decomposition question for polynomial optimization. We introduce LP, SOCP, and SDP based algorithms for finding optimal DC decompositions by appealing to the algebraic concepts of "DSOS-Convex, SDSOS-Convex, and SOS-Convex" polynomials. We also study structural properties of these polynomials and answer existence questions about polynomial DC decompositions.