The purpose of this paper is to derive computational checks for the simplex method of Linear Programming which can be applied at any iteration. The paper begins with a quick review of the simplex algorithm. It then goes through a theoretical development of the simplex method and its dual all the time focusing on the … Read more
In this paper we consider the following two types of complex quadratic maximization problems: (i) maximize $z^{\HH} Q z$, subject to $z_k^m=1$, $k=1,…,n$, where $Q$ is a Hermitian matrix with $\tr Q=0$ and $z\in \C^n$ is the decision vector; (ii) maximize $\re y^{\HH}Az$, subject to $y_k^m=1$, $k=1,…,p$, and $z_l^m=1$, $l=1,…,q$, where $A\in \C^{p\times q}$ and … Read more
This paper studies the possibilities of the Linear Matrix Inequality (LMI) characterization of the matrix cones formed by nonnegative complex Hermitian quadratic functions over specific domains in the complex space. In its real case analog, such studies were conducted in Sturm and Zhang in 2003. In this paper it is shown that stronger results can … Read more
We address a problem of covariance selection, where we seek a trade-off between a high likelihood against the number of non-zero elements in the inverse covariance matrix. We solve a maximum likelihood problem with a penalty term given by the sum of absolute values of the elements of the inverse covariance matrix, and allow for … Read more
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