Research and selected publications

My research is in convex programming, especially in semidefinite programming, and conic linear programming. A few years back I also did research in integer programming. I also have several papers on applications of optimization.

My main research area, which is closest to my heart, is on Semidefinite Programs (SDPs), some of the most exciting, and useful class of optimization problems of the last few decades.

The goal is to produce easy-to-verify, combinatorial certificates for SDPs: for example, to verify

• infeasibility,
• weak infeasibility: when an SDP is infeasible, but within zero distance to the set of feasible instances. Weak infeasibility does not happen in linear programming and it leads to very challenging SDPs.
• Pathological behavior of semidefinite systems: why essentially all “bad” SDPs in the literature look strikingly similar.
• Positive duality gaps — again a fascinating behavior that leads to very difficult SDPs and cannot happen in linear programming.
• Exponential size solutions — these are impossible to even write down in a reasonable amount of space.

Interestingly, we can use mostly elementary row operations (coming from Gaussian elimination) to bring SDPs (more generally, conic linear systems) into a form, so the infeasibility, weak infeasibility, etc. become easy to see.

The structural insights that we obtain can be used to preprocess SDPs and to create difficult SDP instance libraries.

• How do exponential size solutions arise in semidefinite programming?   G. Pataki, A. Touzov
  To appear, SIAM Journal on Optimization     A talk   
  Poster talk at the MIP 2021 conference, May 24, 2021   2nd prize to Alex Touzov
• A simplified treatment of Ramana’s exact dual for semidefinite programming   B. Lourenco, G. Pataki,
  Optimization Letters (2022): 1-25.
• An echelon form of weakly infeasible semidefinite programs and bad projections of the psd cone   G. Pataki, A. Touzov
  Foundations of Computational Mathematics, 2022, 1–38.   A talk  
• On positive duality gaps in semidefinite programming   G. Pataki
  Submitted   A talk
• Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs Y. Zhu, G. Pataki, Q. Tran-Dinh
  Mathematical Programming Computation (2019) DOI   A talk
  Poster talk at the 2018 Princeton Optimization Day, sept 2018.   First prize to Yuzixuan Zhu in the Algorithms category.
• Characterizing bad semidefinite programs: normal forms and short proofs   G. Pataki
  SIAM Review (2019)   DOI   A talk
• Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming , M. Liu, G. Pataki,
  Mathematical Programming, Ser. A (2018) 167:435–480   DOI   A talk
• Bad semidefinite programs: they all look the same   G. Pataki
  SIAM Journal on Optimization, 2017, 27(3), 146–172, 2017     DOI     A talk
• Exact duality in semidefinite programming based on elementary reformulations , M. Liu, G. Pataki,
  SIAM Journal on Optimization, 25(3), 1441–1454, 2015   DOI   A talk

An older paper, which deals with a closely related, classical problem is

• On the Closedness of the Linear Image of a Closed Convex Cone , G. Pataki
  Mathematics of Operations Research. 32(2), 395-412, 2007   DOI   A talk

The geometry of SDPs and more generally of conic LPs (extreme points, degeneracy, etc.)

• The Geometry of Semidefinite Programming   G. Pataki,
  In the The Handbook of Semidefinite Programming, Kluwer, 2000   A talk
• On the Rank of Extreme Matrices in Semidefinite Programs and the
  Multiplicity of Optimal Eigenvalues, G. Pataki
  Mathematics of Operations Research, 23 (2), 339-358, 1998    DOI

Reformulating integer programs using basis reduction

These papers show how to reformulate integer programming problems (IPs) by nearly orthogonalizing the columns. The reformulation makes many hard IPs easier, and more surprisingly, it makes most integer programs solvable by just one branch-and-bound node.

• Basis Reduction, and the Complexity of Branch-and-Bound, G. Pataki, M. Tural, E. B. Wong  
  2010 ACM-SIAM Symposium on Discrete Algorithms (SODA 10)     DOI   A talk
• Column Basis Reduction and Decomposable Knapsack Problems, B. Krishnamoorthy and G. Pataki,
  Discrete Optimization, 6(3), August 2009, 242-270    DOI   A talk

Solving a hard, previously unsolved integer program

• Solving the seymour problem, M. C. Ferris, G. Pataki and S. Schmieta
  Optima, 66:1-7, 2001.   A talk