Research and selected publications
My research is in convex programming, especially in semidefinite programming, conic linear programming, integer programming, and applications of optimization. Below I list some research projects and papers that are close to my heart.
My main research area in the last few years has been on Semidefinite Programs (SDPs), some of the most exciting, and useful class of optimization problems of the last few decades.
I mainly looked at pathological SDPs. Precisely, in the duality theory of SDPs strange pathologies occur: the optimal values of primal and dual SDPs may differ and may not be attained.
Preprocessing semidefinite programs (SDPs)
A simple algorithm can remove many redundancies in SDPs, reduce their size, and often get rid of the pathological behavior, or detect infeasibility.
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs Y. Zhu, G. Pataki, Q. Tran-Dinh
Understanding the pathological behavior of semidefinite programs (SDPs) and more generally, of conic linear programs (LPs).
In these few papers I give combinatorial characterizations of the pathological behaviors.I also show how to use elementary row operations (coming from Gaussian elimination) to bring semidefinite systems (or more generally, conic linear systems) into a form, so the pathological behavior becomes easy to see.
- Bad semidefinite programs with short proofs, and the closedness of the linear image of the semidefinite cone G. Pataki
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,
To appear, Mathematical Programming, series A 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)