Branch and cut based on the volume algorithm: Steiner trees in graphs and max-cut

We present a Branch-and-Cut algorithm where the Volume Algorithm is applied to the linear programming relaxations arising at each node of the search tree. This means we use fast approximate solutions to these linear programs instead of exact but slower solutions given by the traditionally used dual simplex method. Our claim is that such a … Read more

[PENNON – A Generalized Augmented Lagrangian Methodfor Semidefinite Programming

This article describes a generalization of the PBM method by Ben-Tal and Zibulevsky to convex semidefinite programming problems. The algorithm used is a generalized version of the Augmented Lagrangian method. We present details of this algorithm as implemented in a new code PENNON. The code can also solve second-order conic programming (SOCP) problems, as well … Read more

Block-iterative algorithms with diagonally scaled oblique projections for the linear feasibility problem

We formulate a block-iterative algorithmic scheme for the solution of systems of linear inequalities and/or equations and analyze its convergence. This study provides as special cases proofs of convergence of (i) the recently proposed Component Averaging (CAV) method of Censor, Gordon and Gordon ({\it Parallel Computing}, 27:777–808, 2001), (ii) the recently proposed Block-Iterative CAV (BICAV) … Read more

An Analysis of the EM Algorithm andEntropy-Like Proximal Point Methods

The EM algorithm is a popular method for maximum likelihood estimation from incomplete data. This method may be viewed as a proximal point method for maximizing the log-likelhood function using an integral form of the Kullback-Leibler distance function. Motivated by this interpretation, we consider a proximal point method using an integral form of entropy-like distance … Read more

A new class of proximal algorithms for the nonlinear complementarity problem

In this paper, we consider a variable proximal regularization method for solving the nonlinear complementarity problem for P0 functions. Citation Applied Optimization Series, 96, Optimization and Control With Applications, L. Qi, K. Teo and X. Yang (Eds.), pp 549-561, Springer, 2005.

A sequential convexification method (SCM) for continuous global optimization

A new method for continuous global minimization problems, acronymed SCM, is introduced. This method gives a simple transformation to convert the original objective function to an auxiliary function with gradually fewer local minimizers. All Local minimizers except a prefixed one of the auxiliary function is in the region where the function value of the original … Read more

A Dynamic Large-Update Primal-Dual Interior-Point Method for Linear Optimization

Primal-dual interior-point methods (IPMs) have shown their power in solving large classes of optimization problems. However, at present there is still a gap between the practical behavior of these algorithms and their theoretical worst-case complexity results, with respect to the strategies of updating the duality gap parameter in the algorithm. The so-called small-update IPMs enjoy … Read more

Semidefinite programming vs LP relaxations for polynomial programming

We consider the global minimization of a multivariate polynomial on a semi-algebraic set \Omega defined with polynomial inequalities. We then compare two hierarchies of relaxations, namely, LP-relaxations based on products of the original constraints, in the spirit of the RLT procedure of Sherali and Adams and recent SDP (semi definite programming) relaxations introduced by the … Read more

A Laplace transform algorithm for the volume of a convex polytope

We provide two algorithms for computing the volume of the convex polytope $\Omega:=\{x\in \R^n_+ \,|\,Ax\leq b\}$, for $A\in\R^{m\times n}, b\in\R^n$. The computational complexity of both algorithms is essentially described by $n^m$, which makes them especially attractive for large $n$ and relatively small $m$, when the other methods with $O(m^n)$ complexity fail. The methodology which differs … Read more