# 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 main 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 leads to very challenging SDPs, and it does not happen in linear programming.
- 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.

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.

- On positive duality gaps in semidefinite programming G. Pataki

*Submitted* - Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs Y. Zhu, G. Pataki, Q. Tran-Dinh

*Submitted*

A simple algorithm can remove many redundancies in SDPs, reduce their size, and often get rid of the pathological behavior. It can often detect infeasibility. - Bad semidefinite programs with short proofs, and the closedness of the linear image of the semidefinite cone G. Pataki

*to appear, SIAM Review*

A talk in 2017

**Remark: a much simplified treatment of the SDP results of the “Bad SDP” paper; that paper, however, addresses general conic linear programs** - 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, Aug 2016 - Bad semidefinite programs: they all look the same G. Pataki

*SIAM Journal on Optimization, 2017, 27(3), 146–172, 2017***DOI**

A talk in 2014 - Exact duality in semidefinite programming based on elementary reformulations , M. Liu, G. Pataki,

*SIAM Journal on Optimization, 25(3), 1441–1454, 2015***DOI**

Talk at Tamas Terlaky’s birthday conference June 2015

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**

Talk at Dalhousie University, January 2005

** 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*

Talk at Cornell University, 1998 - 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**

Talk at the Combinatorial Optimization workshop in Aussois, 2011- Column Basis Reduction and Decomposable Knapsack Problems, B. Krishnamoorthy and G. Pataki,

*Discrete Optimization, 6(3), August 2009, 242-270***DOI**

A talk, January 2005

** Solving a hard, previously unsolved integer program **

- Solving the seymour problem, M. C. Ferris, G. Pataki and S. Schmieta

*Optima, 66:1-7, 2001.*

Talk at ISMP 2000 (given by Stefan Schmieta)