For the nonconvex quadratic programming problem, a new linear programming relaxation bound-and-reduce algorithm is proposed and its convergence is proved. In this algorithm, a new hyper-rectangle partition technique a...
详细信息
For the nonconvex quadratic programming problem, a new linear programming relaxation bound-and-reduce algorithm is proposed and its convergence is proved. In this algorithm, a new hyper-rectangle partition technique and a new linear programming relaxation tactics are used. At the same time, the hyper-rectangular reduction method is used to raise its convergent speed. The numerical results demonstrate the effectiveness and feasibility of the proposed algorithm. (C) 2014 Published by Elsevier Inc.
Cutting planes from the Boolean Quadric Polytope can be used to reduce the optimality gap of the NP-hard nonconvexquadratic program with box constraints (BoxQP). It is known that all cuts of the Chvatal-Gomory closur...
详细信息
Cutting planes from the Boolean Quadric Polytope can be used to reduce the optimality gap of the NP-hard nonconvexquadratic program with box constraints (BoxQP). It is known that all cuts of the Chvatal-Gomory closure of the Boolean Quadric Polytope are A-odd cycle inequalities. We obtain a compact extended relaxation of all A-odd cycle inequalities, which allows to optimize over the Chvatal-Gomory closure without repeated calls to separation algorithms and has less inequalities than the formulation provided by Boros et al. (SIAM J Discrete Math 5(2):163-177, 1992) for sparse matrices. In a computational study, we confirm the strength of this relaxation and show that we can provide very strong bounds for the BoxQP, even with a plain linear program. The resulting bounds are significantly stronger than these from Bonami et al. (Math Program Comput 10(3):333-382, 2018), which arise from separating A-odd cycle inequalities heuristically.
In this paper, a conic reformulation and approximation is proposed for solving a nonconvex quadratic programming problem subject to several convex quadratic constraints. The original problem is transformed into a line...
详细信息
In this paper, a conic reformulation and approximation is proposed for solving a nonconvex quadratic programming problem subject to several convex quadratic constraints. The original problem is transformed into a linear conic programming problem, which can be approximated by a sequence of linear conic programming problems over the dual cone of the cone of nonnegative quadratic functions. Since the dual cone of the cone of nonnegative quadratic functions has a linear matrix inequality representation, each linear conic programming problem in the sequence can be solved efficiently using the semidefinite programming techniques. In order to speed up the convergence of the approximation sequence and relieve the computational effort in solving the linear conic programming problems, an adaptive scheme is adopted in the proposed algorithm. We prove that the lower bounds generated by the linear conic programming problems converge to the optimal value of the original problem. Several numerical examples are used to illustrate how the algorithm works and the computational results demonstrate the efficiency of the proposed algorithm.
Jigsaw puzzles consist of reconstructing a picture that has been divided into many interlocking pieces. This paper describes an automatic global method for solving the square-piece jigsaw puzzle problem in which neith...
详细信息
Jigsaw puzzles consist of reconstructing a picture that has been divided into many interlocking pieces. This paper describes an automatic global method for solving the square-piece jigsaw puzzle problem in which neither the orientations nor the locations of the jigsaw pieces are known. This hard combinatorial sorting task is formulated as a nonconvex quadratic programming problem that is solved via the projected power method. Specifically, this work aims to specify the locations and orientations of puzzle pieces by maximizing a constrained quadratic function that resolves an optimized permutation matrix composed of the noisy pairwise affinities between jigsaw pieces. The experimental results obtained in the MIT, McGill and Pomeranz datasets indicate that our method outperforms state-of-the-art techniques.
The paper presents a new rectangle branch-and-reduce approach for solving nonconvex quadratic programming problems, in which a new lower approximate linear functions of the quadratic function over an n-rectangle is gi...
详细信息
The paper presents a new rectangle branch-and-reduce approach for solving nonconvex quadratic programming problems, in which a new lower approximate linear functions of the quadratic function over an n-rectangle is given to determine a lower bound of the global optimal value of the original problem over each rectangle, and a simple two-partition technique on rectangle is used, as well as the tactics on reducing and deleting subrectangles is used to accelerate the convergence of the proposed algorithm. The proposed algorithm is proved to be convergent and shown to be effective with numerical results. (c) 2004 Elsevier Inc. All rights reserved.
In this work, we propose a new approach called "Successive Linear programming Algorithm (SLPA)" for finding an approximate global minimizer of general nonconvexquadratic programs. This algorithm can be init...
详细信息
In this work, we propose a new approach called "Successive Linear programming Algorithm (SLPA)" for finding an approximate global minimizer of general nonconvexquadratic programs. This algorithm can be initialized by any extreme point of the convex polyhedron of the feasible domain. Furthermore, we generalize the simplex algorithm for finding a local minimizer of concave quadratic programs written in standard form. We prove a new necessary and sufficient condition for local optimality, then we describe the Revised Primal Simplex Algorithm (RPSA). Finally, we propose a hybrid local-global algorithm called "SLPLEX", which combines RPSA with SLPA for solving general concave quadratic programs. In order to compare the proposed algorithms to the branch-and-bound algorithm of CPLEX12.8 and the branch-and-cut algorithm of Quadproga, we develop an implementation with MATLAB and we present numerical experiments on 139 nonconvexquadratic test problems.
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 quest...
详细信息
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.
In this article, we present a parametric linear relaxation algorithm for globally solving the nonconvex quadratic programming (NQP). In this algorithm, a new parametric linearized technique is proposed for generating ...
详细信息
In this article, we present a parametric linear relaxation algorithm for globally solving the nonconvex quadratic programming (NQP). In this algorithm, a new parametric linearized technique is proposed for generating parametric linear relaxation programming (PLRP) of the NQP, which can be used to determine the lower bound of global minimum value of the NQP. To improve the convergent speed of the proposed algorithm, a pruning operation is employed to compress the investigated region. By subdividing subsequently the initial domain and solving subsequently a series of parametric linear relaxation programming problems over the subdivided domain, the proposed algorithm is convergent to the global minimum of the NQP. Finally, an engineering problem for the design of heat exchanger network and some test examples are used to verify the effectiveness of the proposed algorithm. (C) 2014 Elsevier Inc. All rights reserved.
In this paper a barrier function method is proposed for approximating a solution of the nonconvex quadratic programming problem with box constraints. The method attempts to produce a solution of good quality by follow...
详细信息
In this paper a barrier function method is proposed for approximating a solution of the nonconvex quadratic programming problem with box constraints. The method attempts to produce a solution of good quality by following a path as the barrier parameter decreases from a sufficiently large positive number. For a given value of the barrier parameter, the method searches for a minimum point of the barrier function in a descent direction, which has a desired property that the box constraints are always satisfied automatically if the step length is a number between zero and one. When all the diagonal entries of the objective function are negative, the method converges to at least a local minimum point of the problem if it yields a local minimum point of the barrier function for a sequence of decreasing values of the barrier parameter with zero limit. Numerical results show that the method always generates a global or near global minimum point as the barrier parameter decreases at a sufficiently slow pace.
In this paper, we provide a new regularization technique based on DC programming and DC Algorithms to handle indefinite Hessians in a primal-dual interior point context for nonconvex quadratic programming problems. Th...
详细信息
In this paper, we provide a new regularization technique based on DC programming and DC Algorithms to handle indefinite Hessians in a primal-dual interior point context for nonconvex quadratic programming problems. The new regularization leads automatically to a strongly factorizable quasidefinite matrix in the Newton system. Numerical results show the robustness and the efficiency of our approach compared with LOQO. Moreover, in our computational testing, our method always provided globally optimal solutions to those nonconvexquadratic programs that arise from reformulations of linear complementarity problems.
暂无评论