Closing Duality Gaps of SDPs through Perturbation

\(\) Let \(({\bf P},{\bf D})\) be a primal-dual pair of SDPs with a nonzero finite duality gap. Under such circumstances, \({\bf P}\) and \({\bf D}\) are weakly feasible and if we perturb the problem data to recover strong feasibility, the (common) optimal value function \(v\) as a function of the perturbation is not well-defined at … Read more

A generalized block-iterative projection method for the common fixed point problem induced by cutters

The block-iterative projections (BIP) method of Aharoni and Censor [Block-iterative projection methods for parallel computation of solutions to convex feasibility problems, Linear Algebra and its Applications 120, (1989), 165-175] is an iterative process for finding asymptotically a point in the nonempty intersection of a family of closed convex subsets. It employs orthogonal projections onto the … Read more

A Limiting Analysis on Regularization of Singular SDP and its Implication to Infeasible Interior-point Algorithms

We consider primal-dual pairs of semidefinite programs and assume that they are ill-posed, i.e., both primal and dual are either weakly feasible or weakly infeasible. Under such circumstances, strong duality may break down and the primal and dual might have a nonzero duality gap. Nevertheless, there are arbitrary small perturbations to the problem data which … Read more

Borwein–Preiss Vector Variational Principle

This article extends to the vector setting the results of our previous work Kruger et al. (2015) which refined and slightly strengthened the metric space version of the Borwein–Preiss variational principle due to Li and Shi, J. Math. Anal. Appl. 246(1), 308–319 (2000). We introduce and characterize two seemingly new natural concepts of epsilon-minimality, one … Read more

Borwein-Preiss Variational Principle Revisited

In this article, we refine and slightly strengthen the metric space version of the Borwein–Preiss variational principle due to Li, Shi, J. Math. Anal. Appl. 246, 308–319 (2000), clarify the assumptions and conclusions of their Theorem 1 as well as Theorem 2.5.2 in Borwein, Zhu, Techniques of Variational Analysis, Springer (2005) and streamline the proofs. … Read more

The Linear Complementarity Problem, Lemke Algorithm, Perturbation, and the Complexity Class PPAD

We present a single sufficient condition for the processability of the Lemke algorithm for semimonotone Linear Complementarity problems (LCP) which unifies several sufficient conditions for a number of well known subclasses of semimonotone LCPs. In particular, we study the close relationship of these problems to the complexity class PPAD. Next, we show that these classes … Read more