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

An oracle-based projection and rescaling algorithm for linear semi-infinite feasibility problems and its application to SDP and SOCP

We point out that Chubanov’s oracle-based algorithm for linear programming [5] can be applied almost as it is to linear semi-infinite programming (LSIP). In this note, we describe the details and prove the polynomial complexity of the algorithm based on the real computation model proposed by Blum, Shub and Smale (the BSS model) which is … Read more

An extension of Chubanov’s algorithm to symmetric cones

In this work we present an extension of Chubanov’s algorithm to the case of homogeneous feasibility problems over a symmetric cone K. As in Chubanov’s method for linear feasibility problems, the algorithm consists of a basic procedure and a step where the solutions are confined to the intersection of a half-space and K. Following an … Read more

An Extension of Chubanov’s Polynomial-Time Linear Programming Algorithm to Second-Order Cone Programming

Recently, Chubanov proposed an interesting new polynomial-time algorithm for linear program. In this paper, we extend his algorithm to second-order cone programming. Article Download View An Extension of Chubanov's Polynomial-Time Linear Programming Algorithm to Second-Order Cone Programming

Implementation of Interior-point Methods for LP based on Krylov Subspace Iterative Solvers with Inner-iteration Preconditioning

We apply novel inner-iteration preconditioned Krylov subspace methods to the interior-point algorithm for linear programming (LP). Inner-iteration preconditioners recently proposed by Morikuni and Hayami enable us to overcome the severe ill-conditioning of linear equations solved in the final phase of interior-point iterations. The employed Krylov subspace methods do not suffer from rank-deficiency and therefore no … Read more

Facial Reduction and Partial Polyhedrality

We present FRA-Poly, a facial reduction algorithm (FRA) for conic linear programs that is sensitive to the presence of polyhedral faces in the cone. The main goals of FRA and FRA-Poly are the same, i.e., finding the minimal face containing the feasible region and detecting infeasibility, but FRA-Poly treats polyhedral constraints separately. This idea enables … Read more

Weak Infeasibility in Second Order Cone Programming

The objective of this work is to study weak infeasibility in second order cone programming. For this purpose, we consider a relaxation sequence of feasibility problems that mostly preserve the feasibility status of the original problem. This is used to show that for a given weakly infeasible problem at most m directions are needed to … Read more

Solving SDP Completely with an Interior Point Oracle

We suppose the existence of an oracle which solves any semidefinite programming (SDP) problem satisfying Slater’s condition simultaneously at its primal and dual sides. We note that such an oracle might not be able to directly solve general SDPs even after certain regularization schemes are applied. In this work we fill this gap and show … Read more

Matrix monotonicity and self-concordance:how to handle quantum entropy in optimization problems

Let $g$ be a continuously differentiable function whose derivative is matrix monotone on positive semi-axis. Such a function induces a function $\phi (x)=tr(g(x))$ on the cone of squares of an arbitrary Euclidean Jordan algebra. We show that $\phi (x) -\ln \det(x)$ is a self-concordant function on the interior of the cone. We also show that … Read more

A structural geometrical analysis of weakly infeasible SDPs

In this article, we present a geometric theoretical analysis of semidefinite feasibility problems (SDFPs). We introduce the concept of hyper feasible partitions and sub-hyper feasible directions, and show how they can be used to decompose SDFPs into smaller ones, in a way that preserves most feasibility properties of the original problem. With this technique, we … Read more