An improved linearization strategy for zero-one quadratic programming problems

We present a new linearized model for the zero-one quadratic programming problem, whose size is linear in terms of the number of variables in the original nonlinear problem. Our derivation yields three alternative reformulations, each varying in model size and tightness. We show that our models are at least as tight as the one recently proposed in [7], and examine the theoretical relationship of our models to a standard linearization of the zero-one quadratic programming problem. Finally, we demonstrate the efficacy of solving each of these models on a set of randomly generated test instances.     

Partial Lagrangian relaxation for general quadratic programming

We give a complete characterization of constant quadratic functions over an affine variety. This result is used to convexify the objective function of a general quadratic programming problem (Pb) which contains linear equality constraints. Thanks to this convexification, we show that one can express as a semidefinite program the dual of the partial Lagrangian relaxation of (Pb) where the linear constraints are not relaxed. We apply these results by comparing two semidefinite relaxations made from two sets of null quadratic functions over an affine variety.      

一类特殊二维0-1规划的广义指派模型求解

二维0-1整数规划模型应用广泛,对广义指派问题的研究,解决了一些二维0-1整数规划问题.但有些实际问题具有特殊上限约束,目前还没有对应的方法.针对该实际情形,本文建立了相应的数学模型,利用对指派模型的推广,求得问题最优解,从理论上解决了这一类特殊约束二维0-1整数规划的最优解求取问题.并通过算例说明了方法的使用.     

Sufficient Conditions for Global Optimality of Bivalent Nonconvex Quadratic Programs with Inequality Constraints

We present sufficient conditions for the global optimality of bivalent nonconvex quadratic programs involving quadratic inequality constraints as well as equality constraints. By employing the Lagrangian function, we extend the global subdifferential approach, developed recently in Jeyakumar et al. (J. Glob. Optim., 2007, to appear; Math. Program. Ser. A, 2007, to appear) for studying bivalent quadratic programs without quadratic constraints, and derive global optimality conditions. The authors are grateful to the referees for constructive comments and suggestions which have contributed to the final preparation of the paper. Z.Y. Wu’s current address: School of Information Technology and Mathematical Sciences, University of Ballarat, Ballarat, Victoria, Australia. The work of this author was completed while at the Department of Applied Mathematics, University of New South Wales, Sydney, Australia.     

Quadratic distances for capacity and bi-capacity approximation and identification

The application of multi-attribute utility theory based on the Choquet integral requires the prior identification of a capacity if the utility scale is unipolar, or of a bi-capacity if the utility scale is bipolar. In order to implement a minimum distance principle for capacity or bi-capacity approximation or identification, quadratic distances between capacities and bi-capacities are studied. The proposed approach, consisting in solving a strictly convex quadratic program, has been implemented within the GNU R kappalab package for capacity and nonadditive integral manipulation. Its application is illustrated on two examples.      

Generalization of Ulam stability problem for Euler-Lagrange quadratic mappings

In 1968 S.M. Ulam proposed the problem: “When is it true that by changing a little the hypotheses of a theorem one can still assert that the thesis of the theorem remains true or approximately true?” In 1978 P.M. Gruber proposed the Ulam type problem: “Suppose a mathematical object satisfies a certain property approximately. Is it then possible to approximate this object by objects, satisfying the property exactly?” In this paper we solve the generalized Ulam stability problem for non-linear Euler-Lagrange quadratic mappings satisfying approximately a mean equation and an Euler-Lagrange type functional equations in quasi-Banach spaces and p-Banach spaces.     

Monotonic solutions of a quadratic integral equation of fractional order

In the paper we indicate an error made in the proof of the main result of the paper [M.A. Darwish, On quadratic integral equation of fractional orders, J. Math. Anal. Appl. 311 (2005) 112-119]. Moreover, we provide correct proof of a slightly modified version of the mentioned result. The main tool used in our proof is the technique associated with the Hausdorff measure of noncompactness.     

广义线性系统基于PI观测器鲁棒极点配置分离原理

对广义线性系统提出了基于全维比例-积分观测器的控制系统设计的鲁棒极点配置分离原理.基于矩阵灵敏度理论证明了如下事实：与状态反馈系统相同的闭环系统极点具有和状态反馈系统极点相同的极点灵敏度,与观测器系统相同的闭环系统.极点具有和观测器系统极点相同的极点灵敏度.于是基于全维PI观测器的状态反馈控制器的具有最小灵敏度的鲁棒极点配置可以通过求解两个分开的鲁棒状态反馈极点配置问题实现.     

分派问题一种标号算法

文章采用一定技巧,把求最短路的Ｄｉｊｋｓｔｒａ算法用于求解分派问题,得到一种标号算法,计算复杂性仅为Ｏ（ｎ２）,比以往的算法减少了一个数量阶Ｏ（ｎ）。     

Nonlinear programming via an exact penalty function: Global analysis

In this paper we motivate and describe an algorithm to solve the nonlinear programming problem. The method is based on an exact penalty function and possesses both global and superlinear convergence properties. We establish the global qualities here (the superlinear nature is proven in [7]). The numerical implementation techniques are briefly discussed and preliminary numerical results are given.This work is supported in part by NSERC Grant No. A8639 and the U.S. Dept. of Energy.