A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations

Existing global optimization techniques for nonconvex quadratic programming (QP) branch by recursively partitioning the convex feasible set and thus generate an infinite number of branch-and-bound nodes. An open question of theoretical interest is how to develop a finite branch-and-bound algorithm for nonconvex QP. One idea, which guarantees a finite number of branching decisions, is to enforce the first-order Karush-Kuhn-Tucker (KKT) conditions through branching. In addition, such an approach naturally yields linear programming (LP) relaxations at each node. However, the LP relaxations are unbounded, a fact that precludes their use. In this paper, we propose and study semidefinite programming relaxations, which are bounded and hence suitable for use with finite KKT-branching. Computational results demonstrate the practical effectiveness of the method, with a particular highlight being that only a small number of nodes are required. This author was supported in part by NSF Grants CCR-0203426 and CCF-0545514.     

FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension

We show the existence of a fully polynomial-time approximation scheme (FPTAS) for the problem of maximizing a non-negative polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed. Moreover, using a weaker notion of approximation, we show the existence of a fully polynomial-time approximation scheme for the problem of maximizing or minimizing an arbitrary polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed. A conference version of this article, containing a part of the results presented here, appeared in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006, pp. 743–748. The first author gratefully acknowledges support from NSF grant DMS-0608785, a 2003 UC-Davis Chancellor’s fellow award, the Alexander von Humboldt foundation, and IMO Magdeburg. The remaining authors were supported by the European TMR network ADONET 504438.     

基于进化人工神经网络的组合系统滤波技术

在组合系统运用Kalman滤波器技术时,准确的系统模型和可靠的观测数据是保证其性能的重要因素,否则将大大降低Kalman滤波器的估计精度,甚至导致滤波器发散.为解决上述Kalman应用中的实际问题,提出了一种新颖的基于进化人工神经网络技术的自适应Kalman滤波器.仿真试验表明该算法可以在系统模型不准确时、甚至外部观测数据短暂中断时,仍能保证Kalman滤波器的性能.     

Comparison of a special-purpose algorithm with general-purpose algorithms for solving geometric programming problems

We study the performance of four general-purpose nonlinear programming algorithms and one special-purpose geometric programming algorithm when used to solve geometric programming problems. Experiments are reported which show that the special-purpose algorithm GGP often finds approximate solutions more quickly than the general-purpose algorithm GRG2, but is usually not significantly more efficient than GRG2 when greater accuracy is required. However, for some of the most difficult test problems attempted, GGP was dramatically superior to all of the other algorithms. The other algorithms are usually not as efficient as GGP or GRG2. The ellipsoid algorithm is most robust.This work was supported in part by the National Science Foundation, Grant No. MCS-81-02141.     

Quadratic assignment problems

This paper surveys quadratic assignment problems (QAP). At first several applications of this problem class are described and mathematical formulations of QAPs are given. Then some exact solution methods and good heuristics are outlined. Their computational behaviour is illustrated by numerical results. Further recent results on the asymptotic probabilistic behaviour of QAPs are outlined.     

An approach for solving a fuzzy multiobjective programming problem

In this paper we present a new approach, based on the Nearest Interval Approximation Operator, for dealing with a multiobjective programming problem with fuzzy-valued objective functions.     

A computational analysis of multidimensional piecewise-linear models with applications to oil production optimization

Production optimization of gas-lifted oil wells under facility, routing and pressure constraints is a challenging problem, which has attracted the interest of operations engineers aiming to drive economic gains and scientists for its inherent complexity. The hardness of this problem rests on the non-linear characteristics of the multidimensional well-production and pressure-drop functions, as well as the discrete routing decisions. To this end, this work develops several formulations in Mixed-Integer Linear Programming (MILP) using multidimensional piecewise-linear models to approximate the non-linear functions with domains spliced in hypercubes and simplexes. Computational and simulation analyses were performed considering a synthetic but realistic oil field modeled with a multiphase-flow simulator. The purpose of the analyses was to assess the relative performance of the MILP formulations and their impact on the simulated oil production.     

The contribution of K.-H. Elster to generalized conjugation theory and nonconvex duality

This article surveys the main contributions of K.-H. Elster to the theory of generalized conjugate functions and its applications to duality in nonconvex optimization.     

Global convergence of slanting filter methods for nonlinear programming

In this paper, we present a general algorithm for nonlinear programming which uses a slanting filter criterion for accepting the new iterates. Independently of how these iterates are computed, we prove that all accumulation points of the sequence generated by the algorithm are feasible. Computing the new iterates by the inexact restoration method, we prove stationarity of all accumulation points of the sequence.