Integer programming, duality and superadditive functions

Given $A \in Z^{m\times n}$, $b \in Z^m, c \in R^n$, we consider the integer program $P_d: \max \{c’x\vert Ax=b;x\in Z^n_+\}$ which has a well-known abstract dual optimization problem stated in terms of superadditive functions. Using a linear program $Q$ equivalent to $P_d$ that we have introduced recently, we show that its dual $Q^*$ can … Read more

On the globally convexized filled function method for box constrained continuous global optimization

In this paper we show that the unconstrained continuous global minimization problem can not be solved by any algorithm. So without loss of generality we consider the box constrained continuous global minimization problem. We present a new globally convexized filled function method for the problem. The definition of globally convexized filled function is adapted from … Read more

Hyperbolic Programs, and Their Derivative Relaxations

We study the algebraic and facial structures of hyperbolic programs, and examine natural relaxations of hyperbolic programs, the relaxations themselves being hyperbolic programs. Citation TR 1406, School of Operations Research, Cornell University, Ithaca, NY 14853, U.S., 3/04 Article Download View Hyperbolic Programs, and Their Derivative Relaxations

A new notion of weighted centers for semidefinite programming

The notion of weighted centers is essential in V-space interior-point algorithms for linear programming. Although there were some successes in generalizing this notion to semidefinite programming via weighted center equations, we still do not have a generalization that preserves two important properties — 1) each choice of weights uniquely determines a pair of primal-dual weighted … Read more

Valid inequalities based on the interpolation procedure

We study the interpolation procedure of Gomory and Johnson (1972), which generates cutting planes for general integer programs from facets of master cyclic group polyhedra. This idea has recently been re-considered by Evans (2002) and Gomory, Johnson and Evans (2003). We compare inequalities generated by this procedure with mixed-integer rounding (MIR) based inequalities discussed in … Read more

Semidefinite Approximations for Global Unconstrained Polynomial Optimization

We consider here the problem of minimizing a polynomial function on $\oR^n$. The problem is known to be hard even for degree $4$. Therefore approximation algorithms are of interest. Lasserre \cite{lasserre:2001} and Parrilo \cite{Pa02a} have proposed approximating the minimum of the original problem using a hierarchy of lower bounds obtained via semidefinite programming relaxations. We … Read more

Graph Coloring in the Estimation of Sparse Derivative Matrices: Instances and Applications

We describe a graph coloring problem associated with the determination of mathematical derivatives. The coloring instances are obtained as intersection graphs of row partitioned sparse derivative matrices. The size of the graph is dependent on the partition and can be varied between the number of columns and the number of nonzero entries. If solved exactly … Read more

Preprocessing sparse semidefinite programs via matrix completion

Considering that preprocessing is an important phase in linear programming, it should be systematically more incorporated in semidefinite programming solvers. The conversion method proposed by the authors (SIAM Journal on Optimization, vol.~11, pp.~647–674, 2000, and Mathematical Programming, Series B, vol.~95, pp.~303–327, 2003) is a preprocessing of sparse semidefinite programs based on matrix completion. This article … Read more

A moment approach to analyze zeros of triangular polynomial sets

Let $I=(g_1,…, g_n)$ be a zero-dimensional ideal of $ \R[x_1,…,x_n]$ such that its associated set $G$ of polynomial equations $g_i(x)=0$ for all $i=1,…,n$, is in triangular form. By introducing multivariate Newton sums we provide a numerical characterization of polynomials in the radical ideal of $I$. We also provide a necessary and sufficient (numerical) condition for … Read more