The Primal-Dual Corrector (PDC) algorithm that we propose computes on each iteration a corrector direction in addition to the direction of the standard primal-dual path-following interior point method (Kojima et al., 1989) for Linear Programming (LP), in an attempt to improve performance. The new iterate is chosen by moving along the sum of these directions, … Read more
The simplex method is frequently the most efficient method of solving linear programming (LP) problems. This paper reviews previous attempts to parallelise the simplex method in relation to efficient serial simplex techniques and the nature of practical LP problems. For the major challenge of solving general large sparse LP problems, there has been no parallelisation … Read more
We present a review of several professional software products that serve to analyze and solve nonlinear (global and local) optimization problems across a variety of hardware and software environments. The product versions discussed have been implemented for compiler platforms, spreadsheets, algebraic (optimization) modeling languages, and for integrated scientific-technical computing systems. The discussion highlights some of … Read more
Techniques that identify the active constraints at a solution of a nonlinear programming problem from a point near the solution can be a useful adjunct to nonlinear programming algorithms. They have the potential to improve the local convergence behavior of these algorithms, and in the best case can reduce an inequality constrained problem to an … 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
We consider the problem of computing the minimum value $p_{\min}$ taken by a polynomial $p(x)$ of degree $d$ over the standard simplex $\Delta$. This is an NP-hard problem already for degree $d=2$. For any integer $k\ge 1$, by minimizing $p(x)$ over the set of rational points in $\Delta$ with denominator $k$, one obtains a hierarchy … Read more
When dealing with extremely hard global optimization problems, i.e. problems with a large number of variables and a huge number of local optima, heuristic procedures are the only possible choice. In this situation, lacking any possibility of guaranteeing global optimality for most problem instances, it is quite difficult to establish rules for discriminating among different … Read more
We give a hierarchy of semidefinite upper bounds for the maximum size $A(n,d)$ of a binary code of word length $n$ and minimum distance at least $d$. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in $n$; this is based on a result of … Read more