Computational results obtained when solving a subset of NETLIB problems by using a dense projected gradient implementation of the non-simplex active-set sagitta method presented in [12] are summarized. Two different addition rules for its initial phase are considered and, for each problem solved, two corresponding graphs are reported to illustrate the variations of the objective … Read more
Semidefinite optimization, commonly referred to as semidefinite programming, has been a remarkably active area of research in optimization during the last decade. For combinatorial problems in particular, semidefinite programming has had a truly significant impact. This paper surveys some of the results obtained in the application of semidefinite programming to satisfiability and maximum-satisfiability problems. The … Read more
We define a variant of Anstreicher and Terlaky’s (1994) monotonic build-up (MBU) simplex algorithm for linear feasibility problems. Under a nondegeneracy assumption weaker than the normal one, the complexity of the algorithm can be given by $m\Delta$, where $\Delta$ is a constant determined by the input data of the problem and $m$ is the number … Read more
We study the problem of maximizing the second smallest eigenvalue of the Laplace matrix of a graph over all nonnegative edge weightings with bounded total weight. The optimal value is the \emph{absolute algebraic connectivity} introduced by Fiedler, who proved tight connections of this value to the connectivity of the graph. Using semidefinite programming techniques and … Read more
One perceived deficiency of interior-point methods in comparison to active set methods is their inability to efficiently re-optimize by solving closely related problems after a warmstart. In this paper, we investigate the use of a primal-dual penalty approach to overcome this problem. We prove exactness and convergence and show encouraging numerical results on a set … Read more
In \cite{SPT} the authors considered a variant of Mehrotra’s predictor-corrector algorithm that has been widely used in several IPMs based optimization packages. By an example they showed that this variant might make very small steps in order to keep the iterate in a certain neighborhood of the central path, that itself implies the inefficiency of … Read more
We consider 3-partitioning the vertices of a graph into sets $S_1, S_2$ and $S_3$ of specified cardinalities, such that the total weight of all edges joining $S_1$ and $S_2$ is minimized. This problem is closely related to several NP-hard problems like determining the bandwidth or finding a vertex separator in a graph. We show that … Read more
We present a simple, scaleable, distributed simplex implementation for large linear programs. It is designed for coarse grained computation, particularly, readily available networks of workstations. Scalability is achieved by using the standard form of the simplex rather than the revised method. Virtually all serious implementations are based on the revised method because it is much … Read more
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