检索结果-内蒙古大学图书馆

A new bound-and-reduce approach of nonconvex quadratic programming problems

APPLIED MATHEMATICS AND COMPUTATION 2015年 250卷 298-308页

作者： Gao, Yuelin Wei, Fei Natl Univ Nationalities Inst Informat & Syst Sci Beijing Peoples R China Xidian Univ Sch Comp Sci & Technol Xian 710071 Peoples R China

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.

关键词： nonconvex quadratic programming Global optimization Branch-and-bound Relaxation technique Hyper-rectangle reducing

来源：评论

学校读者我要写书评

暂无评论

Tight compact extended relaxations for nonconvex quadratic programming problems with box constraints

引用

JOURNAL OF GLOBAL OPTIMIZATION 2022年第3期84卷 591-606页

作者： de Vries, Sven Perscheid, Bernd Trier Univ FB Math 4 Operat Res D-54286 Trier Germany

Cutting planes from the Boolean Quadric Polytope can be used to reduce the optimality gap of the NP-hard nonconvex quadratic 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.

关键词： nonconvex quadratic programming Linear relaxation Chvatal-Gomory closure Extended formulation

来源：评论

学校读者我要写书评

暂无评论

Conic approximation to nonconvex quadratic programming with convex quadratic constraints

引用

JOURNAL OF GLOBAL OPTIMIZATION 2015年第3期61卷 459-478页

作者： Deng, Zhibin Fang, Shu-Cherng Jin, Qingwei Lu, Cheng Univ Chinese Acad Sci Sch Management Beijing Peoples R China N Carolina State Univ Dept Ind & Syst Engn Raleigh NC 27695 USA Zhejiang Univ Dept Management Sci & Engn Hangzhou 310003 Zhejiang Peoples R China Tsinghua Univ Dept Elect Engn Beijing 100084 Peoples R China

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.

关键词： nonconvex quadratic programming Adaptive scheme Cone of nonnegative quadratic functions

来源：评论

学校读者我要写书评

暂无评论

Solving Jigsaw Puzzles via nonconvex quadratic programming With the Projected Power Method

引用

IEEE TRANSACTIONS ON MULTIMEDIA 2021年 23卷 2310-2320页

作者： Yan, Fang Zheng, Yuanjie Cong, Jinyu Liu, Liu Tao, Dacheng Hou, Sujuan Shandong Normal Univ Sch Informat Sci & Engn Jinan 250014 Peoples R China Univ Shandong Key Lab Intelligent Comp & Informat Secur Jinan 250014 Peoples R China Shandong Prov Key Lab Novel Distributed Comp Soft Jinan 250014 Peoples R China Shandong Normal Univ Inst Biomed Sci Jinan 250014 Peoples R China Univ Sydney URTECH Sydney Artificial Intelligence Ctr Fac Engn Darlington NSW 2008 Australia Univ Sydney Sch Comp Sci Fac Engn Darlington NSW 2008 Australia

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.

关键词： quadratic programming Image reconstruction Noise measurement Shape Image edge detection Computational modeling Square-piece jigsaw unknown orientation nonconvex quadratic programming multiple images

来源：评论

学校读者我要写书评

暂无评论

A new rectangle branch-and-reduce approach for solving nonconvex quadratic programming problems

引用

APPLIED MATHEMATICS AND COMPUTATION 2005年第2期168卷 1409-1418页

作者： Gao, YL Xue, HG Shen, PP NW Secondly Natl Coll Dept Informat & Computat Sci Yin Chuan 750021 Peoples R China Ningxia Univ Sch Math & Comp Sci Yin Chuan 750021 Peoples R China Xian Sci & Technol Univ Dept Math Xian 710048 Peoples R China Henan Normal Univ Sch Math & Informat Sci Xinxiang 453007 Henan Peoples R China

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.

关键词： nonconvex quadratic programming global optimization branch-and-bound method rectangle reducing tactics

来源：评论

学校读者我要写书评

暂无评论

New LP-based local and global algorithms for continuous and mixed-integer nonconvex quadratic programming

引用

JOURNAL OF GLOBAL OPTIMIZATION 2022年第4期82卷 659-689页

作者： Bentobache, Mohand Telli, Mohamed Mokhtari, Abdelkader Univ Laghouat Lab Pure & Appl Math Laghouat Algeria

In this work, we propose a new approach called "Successive Linear programming Algorithm (SLPA)" for finding an approximate global minimizer of general nonconvex quadratic 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 nonconvex quadratic test problems.

关键词： nonconvex quadratic programming Concave quadratic programming Successive linear programming Simplex algorithm Extreme point Local minimizer Global minimizer Approximate global minimizer Numerical experiments

来源：评论

学校读者我要写书评

暂无评论

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

引用

MATHEMATICAL programming 2008年第2期113卷 259-282页

作者： Burer, Samuel Vandenbussche, Dieter Univ Iowa Dept Management Sci Iowa City IA 52242 USA Axioma Inc Marietta GA 30068 USA

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.

关键词： nonconcave quadratic maximization nonconvex quadratic programming branch-and-bound lift-and-project relaxations semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

A parametric linear relaxation algorithm for globally solving nonconvex quadratic programming

引用

APPLIED MATHEMATICS AND COMPUTATION 2015年 250卷 973-985页

作者： Jiao, Hongwei Liu, Sanyang Lu, Nan Xidian Univ Sch Math & Stat Xian 710071 Peoples R China

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.

关键词： nonconvex quadratic programming Global optimization Parametric linearized technique Pruning operation

来源：评论

学校读者我要写书评

暂无评论

A barrier function method for the nonconvex quadratic programming problem with box constraints

引用

JOURNAL OF GLOBAL OPTIMIZATION 2000年第2期18卷 165-188页

作者： Dang, CY Xu, L City Univ Hong Kong Dept Mfg Engn & Engn Management Kowloon Hong Kong Peoples R China Chinese Univ Hong Kong Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China

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.

关键词： nonconvex quadratic programming box constraints global optimization barrier function descent direction iterative method

来源：评论

学校读者我要写书评

暂无评论

Combining DCA (DC Algorithms) and interior point techniques for large-scale nonconvex quadratic programming

引用

OPTIMIZATION METHODS & SOFTWARE 2008年第4期23卷 609-629页

作者： Dinh, T. Pham Le Thi, H. A. Akoa, F. Natl Inst Appl Sci Lab Modelling Optimizat & Operat Res Rouen France Univ Paul Verlaine MIM UFR Lab Theoret & Appl Comp Sci Metz France

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 nonconvex quadratic programs that arise from reformulations of linear complementarity problems.

关键词： nonconvex quadratic programming DC programming DCA ( DCAlgorithms) interior point DC regularization quasidefinite matrix merit function exact penalty

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：