An improved lower bound and approximation algorithm for binary constrained quadratic programming problem

This paper presents an improved lower bound and an approximation algorithm based on spectral decomposition for the binary constrained quadratic programming problem. To decompose spectrally the quadratic matrix in the objective function, we construct a low rank problem that provides a lower bound. Then an approximation algorithm for the binary quadratic programming problem together with a worst case performance analysis for the algorithm is provided.     

Reducing the number of variables in integer quadratic programming problem

In this paper, a new variable reduction technique is presented for general integer quadratic programming problem (GP), under which some variables of (GP) can be fixed at zero without sacrificing optimality. A sufficient condition and a necessary condition for the identification of dominated terms are provided. By comparing the given data of the problem and the upper bound of the variables, if they meet certain conditions, some variables can be fixed at zero. We report a computational study to demonstrate the efficacy of the proposed technique in solving general integer quadratic programming problems. Furthermore, we discuss separable integer quadratic programming problems in a simpler and clearer form.     

A mathematical programming approach to sample coefficient of variation with interval-valued observations

The coefficient of variation is a useful statistical measure, which has long been widely used in many areas. In real-world applications, there are situations where the observations are inexact and imprecise in nature and they have to be estimated. This paper investigates the sample coefficient of variation (CV) with uncertain observations, which are represented by interval values. Since the observations are interval-valued, the derived CV should be interval-valued as well. A pair of mathematical programs is formulated to calculate the lower bound and upper bound of the CV. Originally, the pair of mathematical programs is nonlinear fractional programming problems, which do not guarantee to have global optimum solutions. By model reduction and variable substitutions, the mathematical programs are transformed into a pair of quadratic programs. Solving the pair of quadratic programs produces the global optimum solutions and constructs the interval of the CV. The given example shows that the proposed model is indeed able to help the manufacturer select the most suitable manufacturing process with interval-valued observations.     

Lower Bound Improvement and Forcing Rule for Quadratic Binary Programming

In this paper several equivalent formulations for the quadratic binary programming problem are presented. Based on these formulations we describe four different kinds of strategies for estimating lower bounds of the objective function, which can be integrated into a branch and bound algorithm for solving the quadratic binary programming problem. We also give a theoretical explanation for forcing rules used to branch the variables efficiently, and explore several properties related to obtained subproblems. From the viewpoint of the number of subproblems solved, new strategies for estimating lower bounds are better than those used before. A variant of a depth-first branch and bound algorithm is described and its numerical performance is presented.     

The exact extreme response and the confidence extreme response analysis of structures subjected to uncertain-but-bounded excitations

In this study, the methods for computing the exact bounds and the confidence bounds of the dynamic response of structures subjected to uncertain-but-bounded excitations are discussed. Here the Euclidean norm of the nodal displacement is considered as the measurement of the structural response. The problem of calculating the exact lower bound, the confidence (outer) approximation and the inner approximation of the exact upper bound, and the exact upper bound of the dynamic response are modeled as three convex QB (quadratic programming with box constraints) problems and a problem of quadratic programming with bivalent constraints at each time point, respectively. Accordingly, the DCA (difference of convex functions algorithm) and the vertex method are adopted to solve the above convex QB problems and the quadratic programming problem with bivalent constraints, respectively. Based on the inner approximation and the outer approximation of the exact upper bound, the error between the confidence upper bound and the exact upper bound of dynamic response could be yielded. Specially, we also investigate how to obtain the confidence bound of the dynamic response of structures subjected to harmonic excitations with uncertain-but-bounded excitation frequencies. Four examples are given to show the efficiency and accuracy of the proposed method.     

A Global Optimization Method,QBB, for Twice-Differentiable Nonconvex Optimization Problem

A global optimization method, QBB, for twice-differentiable NLPs (Non-Linear Programming) is developed to operate within a branch-and-bound framework and require the construction of a relaxed convex problem on the basis of the quadratic lower bounding functions for the generic nonconvex structures. Within an exhaustive simplicial division of the constrained region, the rigorous quadratic underestimation function is constructed for the generic nonconvex function structure by virtue of the maximal eigenvalue analysis of the interval Hessian matrix. Each valid lower bound of the NLP problem with the division progress is computed by the convex programming of the relaxed optimization problem obtained by preserving the convex or linear terms, replacing the concave term with linear convex envelope, underestimating the special terms and the generic terms by using their customized tight convex lower bounding functions or the valid quadratic lower bounding functions, respectively. The standard convergence properties of the QBB algorithm for nonconvex global optimization problems are guaranteed. The preliminary computation studies are presented in order to evaluate the algorithmic efficiency of the proposed QBB approach.     

An improved enumerative algorithm for solving quadratic zero-one programming

An improved algorithm is proposed for the minimization of a quadratic function in zero-one variables under quadratic constraints which is based on the idea of additive penalties proposed by P. Hansen. At first, the quadratic function in which all the coefficients except the constant term are nonnegative is obtained by the introduction of the negative variables, and the constant term is a tighter bound of the function. Starting from the tighter bound, some properties are obtained and some efficient tests are established. To obtain a much tighter bound, a simple heuristic method is suggested instead of solving a linear programming problem. Furthermore, the flexibility dealing with some tests is discussed and it is also helpful to the algorithm.     

Lower bounds based on linear programming for the quadratic assignment problem

In this paper we prove that the Classical Gilmore-Lawler lower bound for the quadratic assignment problem is equivalent to a solution of a certain linear programming problem. By adding additional constraints to this linear programming problem we derive a lower bound which is at least as good as the Gilmore-Lawler lower bound.Some of this research was done while the author was on sabbatical leave at the Department of Management, The Hong Kong University of Science and Technology, Kowloon, Hong Kong.     

Global optimality conditions and optimization methods for quadratic integer programming problems

In this paper, we first establish some sufficient and some necessary global optimality conditions for quadratic integer programming problems. Then we present a new local optimization method for quadratic integer programming problems according to its necessary global optimality conditions. A new global optimization method is proposed by combining its sufficient global optimality conditions, local optimization method and an auxiliary function. The numerical examples are also presented to show that the proposed optimization methods for quadratic integer programming problems are very efficient and stable.     

Parallel distributed block coordinate descent methods based on pairwise comparison oracle

The aim of this paper is to find the global solutions of uncertain optimization problems having a quadratic objective function and quadratic inequality constraints. The bounded epistemic uncertainties in the constraint coefficients are represented using either universal or existential quantified parameters and interval parameter domains. This approach allows to model non-controlled uncertainties by using universally quantified parameters and controlled uncertainties by using existentially quantified ones. While existentially quantified parameters could be equivalently considered as additional variables, keeping them as parameters allows maintaining the quadratic problem structure, which is essential for the proposed algorithm. The branch and bound algorithm presented in the paper handles both universally and existentially quantified parameters in a homogeneous way, without branching on their domains, and uses some dedicated numerical constraint programming techniques for finding a robust, global solution. Several examples clarify the theoretical parts and the tests demonstrate the usefulness of the proposed method.     

边界约束非凸二次规划问题的分枝定界方法

本文是研究带有边界约束非凸二次规划问题,我们把球约束二次规划问题和线性约束凸二次规划问题作为子问题,分明引用了它们的一个求整体最优解的有效算法,我们提出几种定界的紧、松驰策略,给出了求解原问题整体最优解的分枝定界算法,并证明了该算法的收敛性,不同的定界组合就可以产生不同的分枝定界算法,最后我们简单讨论了一般有界凸域上非凸二次规划问题求整体最优解的分枝与定界思想。     

带非凸二次约束的二次比式和问题的全局优化算法(英文)

对带非凸二次约束的二次比式和问题(P)给出分枝定界算法,首先将问题(P)转化为其等价问题(Q),然后利用线性化技术,建立了(Q)松弛线性规划问题(RLP),通过对(RLP)可行域的细分及求解一系列线性规划问题,不断更新(Q)的上下界,从理论上证明了算法的收敛性,数值实验表明了算法的可行性和有效性.     

二次比式和问题的加速分枝定界算法

本文给出非凸二次约束上二次比式和问题(P)的一个新的加速分枝定界算法.该算法利用线性化技术建立了问题(P)的松弛线性规划问题(RLP),通过对其可行域的细分和求解一系列线性规划问题,不断更新(P)的全局最优值的上下界.为了提高收敛速度,从最优性和可行性两方面,提出了新的删除技术,理论上证明该算法是收敛的,数值试验表明了算法的有效性和可行性.     

Learning rates for multi-kernel linear programming classifiers

In this paper, we consider the learning rates of multi-kernel linear programming classifiers. Our analysis shows that the convergence behavior of multi-kernel linear programming classifiers is almost the same as that of multi-kernel quadratic programming. This is implemented by setting a stepping stone between the linear programming and the quadratic programming. An upper bound is presented for general probability distributions and distribution satisfying some Tsybakov noise condition.     

An exact solution method for unconstrained quadratic 0–1 programming: a geometric approach

We explore in this paper certain rich geometric properties hidden behind quadratic 0–1 programming. Especially, we derive new lower bounding methods and variable fixation techniques for quadratic 0–1 optimization problems by investigating geometric features of the ellipse contour of a (perturbed) convex quadratic function. These findings further lead to some new optimality conditions for quadratic 0–1 programming. Integrating these novel solution schemes into a proposed solution algorithm of a branch-and-bound type, we obtain promising preliminary computational results.     

Global optimization of a class of nonconvex quadratically constrained quadratic programming problems

In this paper we study a class of nonconvex quadratically constrained quadratic programming problems generalized from relaxations of quadratic assignment problems. We show that each problem is polynomially solved. Strong duality holds if a redundant constraint is introduced. As an application, a new lower bound is proposed for the quadratic assignment problem.     

求不定二次规划全局解的一个新算法

本文提出了一个求不定二次规划问题全局最优解的新算法.首先,给出了三种计算下界的方法:线性逼近法、凸松弛法和拉格朗日松弛法;并且证明了拉格朗日对偶界与通过凸松弛得到的下界是相等的;然后建立了基于拉格朗日对偶界和矩形两分法的分枝定界算法,并给出了初步的数值试验结果.     

A scalable FETI-DP algorithm with non-penetration mortar conditions on contact interface

By combining FETI algorithms of dual-primal type with recent results for bound constrained quadratic programming problems, we develop an optimal algorithm for the numerical solution of coercive variational inequalities. The model problem is discretized using non-penetration conditions of mortar type across the potential contact interface, and a FETI-DP algorithm is formulated. The resulting quadratic programming problem with bound constraints is solved by a scalable algorithm with a known rate of convergence given in terms of the spectral condition number of the quadratic problem. Numerical experiments for non-matching meshes across the contact interface confirm the theoretical scalability of the algorithm.     

Solving quadratic convex bilevel programming problems using a smoothing method

In this paper, we present a smoothing sequential quadratic programming to compute a solution of a quadratic convex bilevel programming problem. We use the Karush-Kuhn-Tucker optimality conditions of the lower level problem to obtain a nonsmooth optimization problem known to be a mathematical program with equilibrium constraints; the complementary conditions of the lower level problem are then appended to the upper level objective function with a classical penalty. These complementarity conditions are not relaxed from the constraints and they are reformulated as a system of smooth equations by mean of semismooth equations using Fisher-Burmeister functional. Then, using a quadratic sequential programming method, we solve a series of smooth, regular problems that progressively approximate the nonsmooth problem. Some preliminary computational results are reported, showing that our approach is efficient.