23 citations · 82 across the 21 of their papers we have counts for
18 papers · 1 filter
Strict complementarity in semidefinite programming, singularity degree, and the (dis)connection of forward and backward errors
Gábor Pataki
Strict complementarity of a primal-dual pair of optimal solutions is fundamental in the numerical analysis of semidefinite programs (SDPs). Strict complementarity drives the conver…
A combinatorial approach to Ramana's exact dual for semidefinite programming
Gabor Pataki
Thirty years ago, in a seminal paper Ramana derived an exact dual for Semidefinite Programming (SDP). Ramana's dual has the following remarkable features: i) it is an explicit, pol…
A Simplified Treatment of Ramana's Exact Dual for Semidefinite Programming
Bruno F. Lourenço, Gábor Pataki
In semidefinite programming the dual may fail to attain its optimal value and there could be a duality gap, i.e., the primal and dual optimal values may differ. In a striking paper…
An echelon form of weakly infeasible semidefinite programs and bad projections of the psd cone
Gábor Pataki, Aleksandr Touzov
A weakly infeasible semidefinite program (SDP) has no feasible solution, but it has approximate solutions whose constraint violation is arbitrarily small. These SDPs are ill-posed…
How do exponential size solutions arise in semidefinite programming?
Gábor Pataki, Aleksandr Touzov
A striking pathology of semidefinite programs (SDPs) is illustrated by a classical example of Khachiyan: feasible solutions in SDPs may need exponential space even to write down. S…
On Positive Duality Gaps in Semidefinite Programming
Gabor Pataki
We present a novel analysis of semidefinite programs (SDPs) with positive duality gaps, i.e. different optimal values in the primal and dual problems. These SDPs are extremely path…
Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
Yuzixuan, Zhu, Gabor Pataki +1
We introduce Sieve-SDP, a simple facial reduction algorithm to preprocess semidefinite programs (SDPs). Sieve-SDP inspects the constraints of the problem to detect lack of strict f…
Characterizing bad semidefinite programs: normal forms and short proofs
Gabor Pataki
Semidefinite programs (SDPs) -- some of the most useful and versatile optimization problems of the last few decades -- are often pathological: the optimal values of the primal and…
A simple preprocessing algorithm for semidefinite programming
Preston Faulk, Gabor Pataki, Quoc Tran-Dinh
We propose a very simple preprocessing algorithm for semidefinite programming. Our algorithm inspects the constraints of the problem, deletes redundant rows and columns in the cons…
Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming
Minghui Liu, Gabor Pataki
In conic linear programming -- in contrast to linear programming -- the Lagrange dual is not an exact dual: it may not attain its optimal value, or there may be a positive duality…
Exact duality in semidefinite programming based on elementary reformulations
Minghui Liu, Gabor Pataki
In semidefinite programming (SDP), unlike in linear programming, Farkas' lemma may fail to prove infeasibility. Here we obtain an exact, short certificate of infeasibility in SDP b…
Coordinate shadows of semi-definite and Euclidean distance matrices
D. Drusvyatskiy, G. Pataki, H. Wolkowicz
We consider the projected semi-definite and Euclidean distance cones onto a subset of the matrix entries. These two sets are precisely the input data defining feasible semi-definit…
Strong duality in conic linear programming: facial reduction and extended duals
Gabor Pataki
The facial reduction algorithm of Borwein and Wolkowicz and the extended dual of Ramana provide a strong dual for the conic linear program in…
On the connection of facially exposed and nice cones
Gabor Pataki
A closed convex cone K is called nice, if the set K^* + F^\perp is closed for all F faces of K, where K^* is the dual cone of K, and F^\perp is the orthogonal complement of the lin…
Bad semidefinite programs: they all look the same
Gabor Pataki
Conic linear programs, among them semidefinite programs, often behave pathologically: the optimal values of the primal and dual programs may differ, and may not be attained. We pre…
Basis Reduction, and the Complexity of Branch-and-Bound
Gabor Pataki, Mustafa Tural
The classical branch-and-bound algorithm for the integer feasibility problem has exponential worst case complexity. We prove that it is surprisingly efficient on reformulated probl…
Parallel Approximation and Integer Programming Reformulation
Gabor Pataki, Mustafa Tural
We show that in a knapsack feasibility problem an integral vector , which is short, and near parallel to the constraint vector gives a branching direction with small integer wid…
Column basis reduction, and decomposable knapsack problems
Bala Krishnamoorthy, Gabor Pataki
We propose a very simple preconditioning method for integer programming feasibility problems: replacing the problem b' <= Ax <= b, x \in Z^n with b' <= AUy <= b, y \in Z^n, where U…