The Complexity Analysis of the Inverse Center Location Problem

Given a feasible solution, the inverse optimization problem is to modify some parameters of the original problem as little as possible, and sometimes also with bound restrictions on these adjustments, to make the feasible solution become an optimal solution under the new parameter values. So far it is unknown that for a problem which is solvable in polynomial time, whether its inverse problem is also solvable in polynomial time. In this note we answer this question by considering the inverse center location problem and show that even though the original problem is polynomially solvable, its inverse problem is NP–hard.     

Easy capacitated facility location problems,with connections to lot-sizing

In this note, we consider the capacitated facility location problem when the transportation costs of the instance satisfy the Monge property. We show that a straightforward dynamic program finds the optimal solution when the demands are polynomially bounded. When demands are not polynomially bounded, we give a fully polynomial-time approximation scheme by adapting an algorithm and analysis of Van Hoesel and Wagelmans (2001).     

Radially symmetric solutions of the p-Laplacian in perforated-like domain with nonlocal boundary condition

In this paper, we study the stability of solutions to a von Kármán system for Kirchhoff plate equations with a memory condition working at the boundary. We show that such dissipation is strong enough to produce exponential decay of the solution provided the relaxation functions also decay exponentially. When the relaxation functions decay polynomially, we show that the solution decays polynomially.     

Conjugacy growth in polycyclic groups

In this paper, we consider the conjugacy growth function of a group, which counts the number of conjugacy classes which intersect a ball of radius n centered at the identity. We prove that in the case of virtually polycyclic groups, this function is either exponential or polynomially bounded, and is polynomially bounded exactly when the group is virtually nilpotent. The proof is fairly short, and makes use of the fact that any polycyclic group has a subgroup of finite index which can be embedded as a lattice in a Lie group, as well as exponential radical of Lie groups and Dirichlet’s approximation theorem.     

Dirichlet regularity in arbitrary o‐minimal structures on the field ℝ up to dimension 4

In this article we show that the set of Dirichlet regular boundary points of a bounded domain of dimension up to 4, definable in an arbitrary o‐minimal structure on the field ?, is definable in the same structure. Moreover we give estimates for the dimension of the set of non‐regular boundary points, depending on whether the structure is polynomially bounded or not. This paper extends the results from the author's Ph.D. thesis [6, 7] where the problem was solved for polynomially bounded o‐minimal structures expanding the real field. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints

In this paper, we propose a branch-and-bound algorithm for finding a global optimal solution for a nonconvex quadratic program with convex quadratic constraints (NQPCQC). We first reformulate NQPCQC by adding some nonconvex quadratic constraints induced by eigenvectors of negative eigenvalues associated with the nonconvex quadratic objective function to Shor’s semidefinite relaxation. Under the assumption of having a bounded feasible domain, these nonconvex quadratic constraints can be further relaxed into linear ones to form a special semidefinite programming relaxation. Then an efficient branch-and-bound algorithm branching along the eigendirections of negative eigenvalues is designed. The theoretic convergence property and the worst-case complexity of the proposed algorithm are proved. Numerical experiments are conducted on several types of quadratic programs to show the efficiency of the proposed method.     

A Marchenko equation for complex interactions with a regular analytic continuation

Using Marchenko's own method, it is shown that three elements are required for the existence of a Marchenko fundamental equation. These are a convergent sum over the discrete spectrum, a bounded translation operator, and sometimes when there are “spectral singularities,” a domain in the complex plane of the momentum k where the representation of the regular solution as a linear combination of the two Jost solutions is meaningful. Meanwhile, we prove that for a class of complex potentials that will be called regular, a variant of Marchenko's equation exists. Clarification of the relationship between the completeness of the two sets of solutions for the unperturbed and the perturbed equation on one hand and the existence of a fundamental equation on the other hand is also achieved.     

On the Kirchhoff plates equations with thermal effects and memory boundary conditions

In this paper we study the existence of weak and strong global solutions and uniform decay of the energy to the Kirchhoff plates equations with thermal effect and memory conditions working at the boundary. We show that the dissipation produced by the memory effect not depend on the present values of temperature gradient. That is, we show that the dissipation produced by memory effect is strong enough to produce exponential decay of the solution provided the relaxation functions also decays exponentially. When the relaxation functions decays polynomially, we show that the solution decays polynomially with the same rate.     

The contraction number of a multigrid method with mesh ratio 2 for solving Poisson's equation

The convergence rate of a multigrid method for the solution of Poisson's equation on a uniform grid is estimated. In contrast to recent results of Braess, no intermediate grids are used. Refined estimates of Gauss-Seidel relaxation by weak norms, a strengthened Cauchy inequality, and a duality argument are central. We obtain 0.273 as an upper bound for the contraction number of the two-level procedure. The results hold for arbitrary convex polygonal regions and are independent of the smoothness of the solution.     

An efficient computational method for a stochastic dynamic lot-sizing problem under service-level constraints

We provide an efficient computational approach to solve the mixed integer programming (MIP) model developed by Tarim and Kingsman [8] for solving a stochastic lot-sizing problem with service level constraints under the static-dynamic uncertainty strategy. The effectiveness of the proposed method hinges on three novelties: (i) the proposed relaxation is computationally efficient and provides an optimal solution most of the time, (ii) if the relaxation produces an infeasible solution, then this solution yields a tight lower bound for the optimal cost, and (iii) it can be modified easily to obtain a feasible solution, which yields an upper bound. In case of infeasibility, the relaxation approach is implemented at each node of the search tree in a branch-and-bound procedure to efficiently search for an optimal solution. Extensive numerical tests show that our method dominates the MIP solution approach and can handle real-life size problems in trivial time.     

Improving Hit-and-Run for global optimization

Improving Hit-and-Run is a random search algorithm for global optimization that at each iteration generates a candidate point for improvement that is uniformly distributed along a randomly chosen direction within the feasible region. The candidate point is accepted as the next iterate if it offers an improvement over the current iterate. We show that for positive definite quadratic programs, the expected number of function evaluations needed to arbitrarily well approximate the optimal solution is at most O(n^5/2) wheren is the dimension of the problem. Improving Hit-and-Run when applied to global optimization problems can therefore be expected to converge polynomially fast as it approaches the global optimum.Paper presented at the II. IIASA-Workshop on Global Optimization, December 9–14, 1990, Sopron (Hungary).     

Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems

Branch and cut methods for integer programming problems solve a sequence of linear programming problems. Traditionally, these linear programming relaxations have been solved using the simplex method. The reduced costs available at the optimal solution to a relaxation may make it possible to fix variables at zero or one. If the solution to a relaxation is fractional, additional constraints can be generated which cut off the solution to the relaxation, but donot cut off any feasible integer points. Gomory cutting planes and other classes of cutting planes are generated from the final tableau. In this paper, we consider using an interior point method to solve the linear programming relaxations. We show that it is still possible to generate Gomory cuts and other cuts without having to recreate a tableau, and we also show how variables can be fixed without using the optimal reduced costs. The procedures we develop do not require that the current relaxation be solved to optimality; this is useful for an interior point method because early termination of the current relaxation results in an improved starting point for the next relaxation.     

Stability of travelling wave solutions to a semilinear hyperbolic system with relaxation

We study a semilinear hyperbolic system with relaxation and investigate the asymptotic stability of travelling wave solutions with shock profile. It is shown that the travelling wave solution is asymptotically stable, provided the initial disturbance is suitably small. Moreover, we show that the time convergence rate is polynomially (resp. exponentially) fast as t→∞ if the initial disturbance decays polynomially (resp. exponentially) for x→∞. Our proofs are based on the space–time weighted energy method. Copyright © 2008 John Wiley & Sons, Ltd.     

Enhanced intersection cutting-plane approach for linear complementarity problems

In this paper, we develop an enhanced intersection cutting-plane algorithm for solving a mixed integer 0–1 bilinear programming formulation of the linear complementarity problem (LCP). The matrixM associated with the LCP is not assumed to possess any special structure, except that the corresponding feasible region is assumed to be bounded. A procedure is described to generate cuts that are deeper versions of the Tuy intersection cuts, based on a relaxation of the usual polar set. The proposed algorithm then attempts to find an LCP solution in the process of generating either a single or a pair of such strengthened intersection cuts. The process of generating these cuts involves a vertexranking scheme that either finds an LCP solution, or else these cuts eliminate the entire feasible region leading to the conclusion that no LCP solution exists. Computational experience on various test problems is provided.This material is based upon work supported by the National Science Foundation under Grant No. DMII-9121419 to the first author and Grant No. DMII-9114489 to the third author. The authors gratefully acknowledge the constructive suggestions of a referee that helped focus the approach and its presentation.     

An o-minimal structure without mild parameterization

We prove, by explicit construction, that not all sets definable in polynomially bounded o-minimal structures have mild parameterization. Our methods do not depend on the bounds particular to the definition of mildness and therefore our construction is also valid for a generalized form of parameterization, which we call G-mild. Moreover, we present a cell decomposition result for certain o-minimal structures which may be of independent interest. This allows us to show how our construction can produce polynomially bounded, model complete expansions of the real ordered field which, in addition to lacking G-mild parameterization, nonetheless still have analytic cell decomposition.     

A joint similarity problem on vector-valued Bergman spaces

We investigate pairs of commuting Foias-Williams/Peller type operators acting on vector-valued weighted Bergman spaces. We prove that a commuting pair of such operators is jointly polynomially bounded if and only if it is similar to a pair of contractions, if and only if both operators are polynomially bounded.     

Mean Ergodicity and Mean Stability of Regularized Solution Families

We prove general theorems on mean ergodicity and mean stability of regularized solution families with respect to fairly general summability methods. They can be applied to integrated solution families, integrated semigroups and cosine functions. In particular, through applications with modified Cesàro, Abel, Gauss, and Gamma like summability methods we deduce particular results on mean ergodicity and mean stability of polynomially bounded C₀-semigroups and cosine operator functions.     

Clark's theorem for semi-infinite convex programs

In 1961, Clark proved that if either the feasible region of a linear program or its dual is nonempty and bounded, then the other is unbounded. Recently, Duffin has extended this result to a convex program and its Lagrangian dual. Moreover, Duffin showed that under this boundedness assumption there is no duality gap. The purpose of this paper is to extend Duffin's results to semi-infinite programs.     

A joint similarity problem for n-tuples of operators on vector-valued Bergman spaces

We investigate n-tuples of commuting Foias-Williams/Peller type operators acting on vector-valued weighted Bergman spaces. We prove that a commuting n-tuple of such operators is jointly (completely) polynomially bounded if and only if it is similar to an n-tuple of contractions, if and only if each of the n operators is polynomially bounded.