Source author record

Gabor Pataki

Gabor Pataki appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.OC Applications

Catalog footprint

What is connected

7works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2021arXiv

Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs

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 feasibility, deletes redundant rows and columns, and reduces the size of the variable matrix. It often detects infeasibility. It does not rely on any optimization solver: the only subroutine it needs is Cholesky factorization, hence it can be implemented in a few lines of code in machine precision. We present extensive computational results on several problem collections from the literature, with many SDPs coming from polynomial optimization.

preprint2020arXiv

On Positive Duality Gaps in Semidefinite Programming

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 pathological, often unsolvable, and also serve as models of more general pathological convex programs. However, despite their allure, they are not well understood even when they have just two variables. We first completely characterize two variable SDPs with positive gaps; in particular, we transform them into a standard form that makes the positive gap trivial to recognize. The transformation is very simple, as it mostly uses elementary row operations coming from Gaussian elimination. We next show that the two variable case sheds light on larger SDPs with positive gaps: we present SDPs in any dimension in which the positive gap is caused by the same structure as in the two variable case. We analyze a fundamental parameter, the {\em singularity degree} of the duals of our SDPs, and show that it is the largest that can result in a positive gap. We finally generate a library of difficult SDPs with positive gaps (some of these SDPs have only two variables) and present a computational study.

preprint2016arXiv

A simple preprocessing algorithm for semidefinite programming

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 constraints, and reduces the size of the variable matrix. It often detects infeasibility. Our algorithm does not rely on any optimization solver: the only subroutine it needs is Cholesky factorization, hence it can be implemented with a few lines of code in machine precision. We present computational results on a set of problems arising mostly from polynomial optimization.

preprint2015arXiv

Exact duality in semidefinite programming based on elementary reformulations

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 by an elementary approach: we reformulate any semidefinite system of the form Ai*X = bi (i=1,...,m) (P) X >= 0 using only elementary row operations, and rotations. When (P) is infeasible, the reformulated system is trivially infeasible. When (P) is feasible, the reformulated system has strong duality with its Lagrange dual for all objective functions. As a corollary, we obtain algorithms to generate the constraints of {\em all} infeasible SDPs and the constraints of {\em all} feasible SDPs with a fixed rank maximal solution.

preprint2013arXiv

Strong duality in conic linear programming: facial reduction and extended duals

The facial reduction algorithm of Borwein and Wolkowicz and the extended dual of Ramana provide a strong dual for the conic linear program $$ (P) \sup {<c, x> | Ax \leq_K b} $$ in the absence of any constraint qualification. The facial reduction algorithm solves a sequence of auxiliary optimization problems to obtain such a dual. Ramana's dual is applicable when (P) is a semidefinite program (SDP) and is an explicit SDP itself. Ramana, Tuncel, and Wolkowicz showed that these approaches are closely related; in particular, they proved the correctness of Ramana's dual using certificates from a facial reduction algorithm. Here we give a clear and self-contained exposition of facial reduction, of extended duals, and generalize Ramana's dual: -- we state a simple facial reduction algorithm and prove its correctness; and -- building on this algorithm we construct a family of extended duals when $K$ is a {\em nice} cone. This class of cones includes the semidefinite cone and other important cones.

preprint2012arXiv

On the connection of facially exposed and nice cones

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 linear span of F. The niceness property is important for two reasons: it plays a role in the facial reduction algorithm of Borwein and Wolkowicz, and the question whether the linear image of a nice cone is closed also has a simple answer. We prove several characterizations of nice cones and show a strong connection with facial exposedness. We prove that a nice cone must be facially exposed; in reverse, facial exposedness with an added condition implies niceness. We conjecture that nice, and facially exposed cones are actually the same, and give supporting evidence.

preprint2010arXiv

Visualizing the Structure of Large Trees

This study introduces a new method of visualizing complex tree structured objects. The usefulness of this method is illustrated in the context of detecting unexpected features in a data set of very large trees. The major contribution is a novel two-dimensional graphical representation of each tree, with a covariate coded by color. The motivating data set contains three dimensional representations of brain artery systems of 105 subjects. Due to inaccuracies inherent in the medical imaging techniques, issues with the reconstruction algo- rithms and inconsistencies introduced by manual adjustment, various discrepancies are present in the data. The proposed representation enables quick visual detection of the most common discrepancies. For our driving example, this tool led to the modification of 10% of the artery trees and deletion of 6.7%. The benefits of our cleaning method are demonstrated through a statistical hypothesis test on the effects of aging on vessel structure. The data cleaning resulted in improved significance levels.