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

Positive semidefinite penalty method for quadratically constrained quadratic programming

IMA JOURNAL OF NUMERICAL ANALYSIS 2021年第4期41卷 2488-2515页

作者： Gu, Ran Du, Qiang Yuan, Ya-xiang Columbia Univ Dept Appl Phys & Appl Math Fu Fdn Sch Engn & Appl Sci New York NY 10027 USA Columbia Univ Data Sci Inst New York NY 10027 USA Chinese Acad Sci Acad Math & Syst Sci Inst Computat Math & Sci Engn Comp State Key Lab Sci & Engn Comp Beijing 100190 Peoples R China

quadratically constrained quadratic programming (QCQP) appears widely in engineering applications such as wireless communications and networking and multiuser detection with examples like the MAXCUT problem and boolean optimization. A general QCQP problem is NP-hard. We propose a penalty formulation for the QCQP problem based on semidefinite relaxation. Under suitable assumptions we show that the optimal solutions of the penalty problem are the same as those of the original QCQP problem if the penalty parameter is sufficiently large. Then, to solve the penalty problem, we present a proximal point algorithm and an update rule for the penalty parameter. Numerically, we test our algorithm on two well-studied QCQP problems. The results show that our proposed algorithm is very effective in finding high-quality solutions.

关键词： quadratically constrained quadratic programming semidefinite programming semidefinite relaxation penalty function

来源：评论

学校读者我要写书评

暂无评论

Design perfect reconstruction cosine-modulated filter banks via quadratically constrained quadratic programming and least squares optimization

引用

SIGNAL PROCESSING 2017年 141卷 199-203页

作者： Liu, Hongying Yi, Caixia Yang, Zhiming Beihang Univ Sch Math & Syst Sci Beijing 100191 Peoples R China

In this paper, the design of perfect reconstruction (PR) cosine-modulated filter banks (CMFBs) is implemented via quadratically constrained quadratic programming (QCQP) and least squares (LS) optimization. To this end, a PR CMFB design problem is formulated as a nonconvex QCQP after re-arranging the coefficients of the prototype filter. Then a deep insight is offered into the algebraic relationship between the PR conditions and near-perfect reconstruction (NPR) ones for CMFB designs. Here we theoretically show that the NPR conditions are just the summations of the PR conditions. Firmly in the light of this relationship, a two-stage method is proposed for PR CMFB design. We firstly solve an NPR CMFB problem to obtain its optimal solution as a reference point, then model the PR CMFB design problem as a series of small-sized LS problems near the reference point. And we solve the LS problems in parallel with cheap iteration. Our analysis and numerical results show that the proposed method bears superior performance on effectiveness and efficiency, especially in the case of designing PR CMFBs with large number of channels. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Perfect reconstruction Near-perfect reconstruction Cosine-modulated filter bank quadratically constrained quadratic programming Least squares

来源：评论

学校读者我要写书评

暂无评论

Global Optimization of a Class of Nonconvex quadratically constrained quadratic programming Problems

引用

Acta Mathematica Sinica,English Series 2011年第9期27卷 1803-1812页

作者： Yong XIA LMIB of the Ministry of Education School of Mathematics and Systems Science Beihang University Beijing 100191 P. R. China

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.

关键词： Nonconvex programming quadratically constrained quadratic programming quadratic assignment problem polynomial solvability strong duality

来源：评论

学校读者我要写书评

暂无评论

The exact solution of multiparametric quadratically constrained quadratic programming problems

引用

JOURNAL OF GLOBAL OPTIMIZATION 2021年第1期79卷 59-85页

作者： Pappas, Iosif Diangelakis, Nikolaos A. Pistikopoulos, Efstratios N. Texas A&M Univ Artie McFerrin Dept Chem Engn College Stn TX 77845 USA Texas A&M Univ Texas A&M Energy Inst College Stn TX 77845 USA

In this paper, we present a strategy for the exact solution of multiparametric quadratically constrained quadratic programs (mpQCQPs). Specifically, we focus on multiparametric optimization problems with a convex quadratic objective function, quadratic inequality and linear equality constraints, described by constant matrices. The proposed approach is founded on the expansion of the Basic Sensitivity Theorem to a second-order Taylor approximation, which enables the derivation of the exact parametric solution of mpQCQPs. We utilize an active set strategy to implicitly explore the parameter space, based on which (i) the complete map of parametric solutions for convex mpQCQPs is constructed, and (ii) the determination of the optimal parametric solution for every feasible parameter realization reduces to a nonlinear function evaluation. Based on the presented results, we utilize the second-order approximation to the Basic Sensitivity Theorem to expand to the case of nonconvex quadratic constraints, by employing the Fritz John necessary conditions. Example problems are provided to illustrate the algorithmic steps of the proposed approach.

关键词： quadratically constrained quadratic programming Global optimization Multiparametric programming Flexibility analysis

来源：评论

学校读者我要写书评

暂无评论

A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming

引用

JOURNAL OF GLOBAL OPTIMIZATION 2019年第2期73卷 371-388页

作者： Lu, Cheng Deng, Zhibin Zhou, Jing Guo, Xiaoling North China Elect Power Univ Sch Econ & Management Beijing 102206 Peoples R China Univ Chinese Acad Sci Chinese Acad Sci Sch Econ & Management Key Lab Big Data Min & Knowledge Management Beijing 100190 Peoples R China Zhejiang Univ Technol Dept Appl Math Coll Sci Hangzhou 310023 Zhejiang Peoples R China China Univ Min & Technol Dept Math Beijing 100083 Peoples R China

In this paper, we design an eigenvalue decomposition based branch-and-bound algorithm for finding global solutions of quadratically constrained quadratic programming (QCQP) problems. The hardness of nonconvex QCQP problems roots in the nonconvex components of quadratic terms, which are represented by the negative eigenvalues and the corresponding eigenvectors in the eigenvalue decomposition. For certain types of QCQP problems, only very few eigenvectors, defined as sensitive-eigenvectors, determine the relaxation gaps. We propose a semidefinite relaxation based branch-and-bound algorithm to solve QCQP. The proposed algorithm, which branches on the directions of the sensitive-eigenvectors, is very efficient for solving certain types of QCQP problems.

关键词： quadratically constrained quadratic programming Semidefinite relaxation Branch-and-bound algorithm Global optimization

来源：评论

学校读者我要写书评

暂无评论

On convex relaxations for quadratically constrained quadratic programming

引用

MATHEMATICAL programming 2012年第2期136卷 233-251页

作者： Anstreicher, Kurt M. Univ Iowa Dept Management Sci Iowa City IA 52242 USA

We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let denote the feasible region for the linear constraints. We first show that replacing the quadratic objective and constraint functions with their convex lower envelopes on is dominated by an alternative methodology based on convexifying the range of the quadratic form for . We next show that the use of "BB" underestimators as computable estimates of convex lower envelopes is dominated by a relaxation of the convex hull of the quadratic form that imposes semidefiniteness and linear constraints on diagonal terms. Finally, we show that the use of a large class of D.C. ("difference of convex") underestimators is dominated by a relaxation that combines semidefiniteness with RLT constraints.

关键词： quadratically constrained quadratic programming Convex envelope Semidefinite programming Reformulation-linearization technique

来源：评论

学校读者我要写书评

暂无评论

SIMULTANEOUS DIAGONALIZATION OF MATRICES AND ITS APPLICATIONS IN quadratically constrained quadratic programming

引用

SIAM JOURNAL ON OPTIMIZATION 2016年第3期26卷 1649-1668页

作者： Jiang, Rujun Li, Duan Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China

An equivalence between attainability of simultaneous diagonalization (SD) and hidden convexity in quadratically constrained quadratic programming (QCQP) stimulates us to investigate necessary and sufficient SD conditions, which is one of the open problems posted by Hiriart-Urruty [SIAM Rev., 49 (2007), pp. 255-273] nine years ago. In this paper we give a necessary and sufficient SD condition for any two real symmetric matrices and offer a necessary and sufficient SD condition for any finite collection of real symmetric matrices under the existence assumption of a semidefinite matrix pencil. Moreover, we apply our SD conditions to QCQP, especially with one or two quadratic constraints, to verify the exactness of its second-order cone programming relaxation and to facilitate the solution process of QCQP.

关键词： simultaneous diagonalization congruence quadratically constrained quadratic programming second-order cone programming relaxation

来源：评论

学校读者我要写书评

暂无评论

On solving quadratically constrained quadratic programming problem with one non-convex constraint

引用

OPSEARCH 2018年第2期55卷 320-336页

作者： Keyanpour, Mohammad Osmanpour, Naser Univ Guilan Fac Math Sci Rasht Iran

In this paper we consider a quadratically constrained quadratic programming problem with convex objective function and many constraints in which only one of them is non-convex. This problem is transformed to a parametric quadratic programming problem without any non-convex constraint and then by solving the parametric problem via an iterative scheme and updating the parameter in each iteration, the solution of the problem is achieved. The convergence of the proposed method is investigated. Numerical examples are given to show the applicability of the new method.

关键词： Adaptive ellipsoid based method quadratically constrained quadratic programming Non-convex constraint Semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Learning the Kernel Matrix in Discriminant Analysis via quadratically constrained quadratic programming

Learning the Kernel Matrix in Discriminant Analysis via Quad...

引用

13th International Conference on Knowledge Discovery and Data Mining

作者： Ye, Jieping Ji, Shuiwang Chen, Jianhui Arizona State Univ Tempe AZ 85287 USA

ISBN: (纸本)9781595936097

In this paper, we consider the automated learning of the kernel matrix over a convex combination of pre-specified kernel matrices in Regularized Kernel Discriminant Analysis (RKDA), which performs linear discriminant analysis in the feature space via the kernel trick. Previous studies have shown that this kernel learning problem can be formulated as a semidefinite program (SDP), which is however computationally expensive, even with the recent advances in interior point methods. Based on the equivalence relationship between RKDA and least square problems in the binary-class case, we propose a quadratically constrained quadratic programming (QCQP) formulation for the kernel learning problem, which can be solved more efficiently than SDP. While most existing work on kernel learning deal with binary-class problems only, we show that our QCQP formulation can be extended naturally to the multi-class case. Experimental results on both binary-class and multi-class benchmark data sets show the efficacy of the proposed QCQP formulations.

关键词： quadratically constrained quadratic programming kernel learning model selection kernel discriminant analysis convex optimization

来源：评论

学校读者我要写书评

暂无评论

A sequential quadratically constrained quadratic programming method for differentiable convex minimization

引用

SIAM JOURNAL ON OPTIMIZATION 2003年第4期13卷 1098-1119页

作者： Fukushima, M Luo, ZQ Tseng, P Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan McMaster Univ Dept Elect & Comp Engn Hamilton ON L8S 4L7 Canada Univ Washington Dept Math Seattle WA 98195 USA

This paper presents a sequential quadratically constrained quadratic programming (SQCQP) method for solving smooth convex programs. The SQCQP method solves at each iteration a subproblem that involves convex quadratic inequality constraints as well as a convex quadratic objective function. Such a quadratically constrained quadratic programming problem can be formulated as a second-order cone program, which can be solved efficiently by using interior point methods. We consider the following three fundamental issues on the SQCQP method: the feasibility of subproblems, the global convergence, and the quadratic rate of convergence. In particular, we show that the Maratos effect is avoided without any modification to the search direction, even though we use an ordinary l(1) exact penalty function as the line search merit function.

关键词： convex programming quadratically constrained quadratic programming Maratos effect quadratic convergence global convergence

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：