Skip to main content
To KTH's start page To KTH's start page

Title: Inner approximations in mixed-integer nonlinear optimization

Akshay Gupte

We present two streams of work for generating good feasible solutions to mixed integer nonlinear programs. In the first part of the talk, we consider nonlinear integer programs and provide an approximation method that uses monomial orders on the integer lattice with different permutations of the variable order. An approximation factor is obtained, and it depends in some sense on the sparsity of the objective function. We also show that our method is exact (i.e., obtains the optimal solution) for binary problems. Although the method is not polynomial-time in general, we give some tractable approximations and implementable algorithms that are competitive in providing good solutions on benchmark test instances for linear and quadratic integer problems. This is joint work with my PhD student Yiran Zhu.

A second idea is to do variable discretizations and reformulate the resulting problem into a mixed-integer linear program. I will talk about the many ways of doing this on mixed-integer quadratically constrained programs and how the discretizations can be adaptively refined in an iterative algorithm to improve the quality of solutions. Numerical tests on a wide range of test instances gives very good performance in comparison to global solvers. This is joint work with Arie Koster and Sascha Kuhnke at RWTH Aachen.

Time: Wed 2023-12-06 11.00 - 12.00

Location: Seminar room 3418

Video link: Zoom room nr 63658381373

Language: English

Participating: Akshay Gupte

Export to calendar

Bio: Akshay Gupte

My primary research interests are in theory, algorithms, and applications of nonconvex optimization. On the theoretical side, I work mainly on convexification techniques for mixed-integer and nonlinear (polynomial optimization) problems. I also have secondary research interests in computational discrete mathematics, particularly the structural study of convex polytopes and structural graph theory, and the use of tools from computational algebraic geometry in polynomial optimization. The theoretical results of my research have direct impact on accelerating convergence of global optimization algorithms for nonconvex problems. The motivating applications for my research come from various disciplines, such as chemical engineering, resilient network design, quantitative finance, game theory.

My research has been funded by multiple grants from US federal agencies:

  • National Science Foundation -- Computational Maths 2019-21 (sole PI) and NRT 2016-21 (co-Inv.),
  • Office of Naval Research Mathematical Optimization 2016-20 (co-PI), Dept. Education GAANN 2015-18 (co-PI).