Support set invariancy sensitivity analysis deals with finding the range of the parameter variation where there are optimal solutions with the same positive variables for all parameter values throughout this range. This approach to sensitivity analysis has been studied for Linear Optimization (LO) and Convex Quadratic Optimization (CQO) problems, when they are in standard form. … Read more
In this paper, we are concerned with nonlinear minimization problems with second order cone constraints. A primal-dual interior point method is proposed for solving the problems. We also propose a new primal-dual merit function by combining the barrier penalty function and the potential function within the framework of the line search strategy, and show the … Read more
The purpose of this paper is two-fold. Firstly, we show that every Cholesky-based weighted central path for semidefinite programming is analytic under strict complementarity. This result is applied to homogeneous cone programming to show that the central paths defined by the known class of optimal self-concordant barriers are analytic in the presence of strictly complementary … Read more
In this paper we present a long-step infeasible primal-dual path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of a preconditioned iterative linear solver. In contrast to the authors’ previous paper \cite{ONE04}, we propose a new linear system, which we refer to as the \emph{hybrid augmented normal equation} (HANE), to … Read more
It is well known that a wide-neighborhood interior-point algorithm for linear programming performs much better in implementation than those small-neighborhood counterparts. In this paper, we provide a unified way to enlarge the neighborhoods of predictor-corrector interior-point algorithms for linear programming. We prove that our methods not only enlarge the neighborhoods but also retain the so-far … Read more
Lov\’ asz and Schrijver [1991] have constructed semidefinite relaxations for the stable set polytope of a graph $G=(V,E)$ by a sequence of lift-and-project operations; their procedure finds the stable set polytope in at most $\alpha(G)$ steps, where $\alpha(G)$ is the stability number of $G$. Two other hierarchies of semidefinite bounds for the stability number have … Read more
This paper presents a branch-and-bound algorithm for nonconvex quadratic programming, which is based on solving semidefinite relaxations at each node of the enumeration tree. The method is motivated by a recent branch-and-cut approach for the box-constrained case that employs linear relaxations of the first-order KKT conditions. We discuss certain limitations of linear relaxations when handling … Read more
We describe a Jordan-algebraic version of results related to convexity of images of quadratic mappings as well as related results on exactness of symmetric relaxations of certain classes of nonconvex optimization problems. The exactness of relaxations is proved based on rank estimates. Our approach provides a unifying viewpoint on a large number of classical results … Read more
Suppose x and s lie in the interiors of a cone K and its dual K^* respectively. We seek dual ellipsoidal norms such that the product of the radii of the largest inscribed balls centered at x and s and incribed in K and K^* respectively is maximized. Here the balls are defined using the … Read more
We present a full-Newton step infeasible interior-point algorithm. It is shown that at most $O(n)$ (inner) iterations suffice to reduce the duality gap and the residuals by the factor $\frac1{e}$. The bound coincides with the best known bound for infeasible interior-point algorithms. It is conjectured that further investigation will improve the above bound to $O(\sqrt{n})$. … Read more