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

nonconvex quadratically constrained quadratic programming: best D.C. decompositions and their SDP representations

JOURNAL OF GLOBAL OPTIMIZATION 2011年第4期50卷 695-712页

作者： Zheng, X. J. Sun, X. L. Li, D. Fudan Univ Sch Management Dept Management Sci Shanghai 200433 Peoples R China Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China

We propose in this paper a general D.C. decomposition scheme for constructing SDP relaxation formulations for a class of nonconvex quadratic programs with a nonconvex quadratic objective function and convex quadratic constraints. More specifically, we use rank-one matrices and constraint matrices to decompose the indefinite quadratic objective into a D.C. form and underestimate the concave terms in the D.C. decomposition formulation in order to get a convex relaxation of the original problem. We show that the best D.C. decomposition can be identified by solving an SDP problem. By suitably choosing the rank-one matrices and the linear underestimation, we are able to construct convex relaxations that dominate Shor's SDP relaxation and the strengthened SDP relaxation. We then propose an extension of the D.C. decomposition to generate an SDP bound that is tighter than the SDP+RLT bound when additional box constraints are present. We demonstrate via computational results that the optimal D.C. decomposition schemes can generate both tight SDP bounds and feasible solutions with good approximation ratio for nonconvex quadratically constrained quadratic problems.

关键词： nonconvex quadratically constrained quadratic programming Optimal DC decomposition Semidefinite program Piecewise linear approximation Feasible solution

来源：评论

学校读者我要写书评

暂无评论

Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming

引用

JOURNAL OF GLOBAL OPTIMIZATION 2019年第2期75卷 461-494页

作者： Jiang, Rujun Li, Duan Fudan Univ Sch Data Sci Shanghai Peoples R China City Univ Hong Kong Sch Data Sci Hong Kong Peoples R China

In this paper, we present new convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP) problems. While recent research has focused on strengthening convex relaxations of QCQP using the reformulation-linearization technique (RLT), the state-of-the-art methods lose their effectiveness when dealing with (multiple) nonconvex quadratic constraints in QCQP, except for direct lifting and linearization. In this research, we decompose and relax each nonconvex constraint to two second order cone (SOC) constraints and then linearize the products of the SOC constraints and linear constraints to construct some new effective valid constraints. Moreover, we extend the reach of the RLT-like techniques for almost all different types of constraint-pairs (including valid inequalities by linearizing the product of a pair of SOC constraints, and the Hadamard product or the Kronecker product of two respective valid linear matrix inequalities), examine dominance relationships among different valid inequalities, and explore almost all possibilities of gaining benefits from generating valid constraints. We also successfully demonstrate that applying RLT-like techniques to additional redundant linear constraints could reduce the relaxation gap significantly. We demonstrate the efficiency of our results with numerical experiments.

关键词： nonconvex quadratically constrained quadratic programming Convex relaxations Reformulation-linearization technique SOC-RLT

来源：评论

学校读者我要写书评

暂无评论

Imputing radiobiological parameters of the linear-quadratic dose-response model from a radiotherapy fractionation plan

引用

PHYSICS IN MEDICINE AND BIOLOGY 2020年第22期65卷 225009页

作者： Ghate, Archis Univ Washington Ind & Syst Engn Seattle WA 98195 USA

The objective in cancer radiotherapy is to maximize tumor-kill while limiting toxic effects of radiation dose on nearby organs-at-risk (OAR). Given a fixed number of treatment sessions, planners thus face the problem of finding a dosing sequence that achieves this goal. This is called the fractionation problem, and has received steady attention over a long history in the clinical literature. Mathematical formulations of the resulting optimization problem utilize the linear-quadratic (LQ) framework to characterize radiation dose-response of tumors and OAR. This yields a nonconvex quadratically constrained quadratic program. The optimal dosing plan in this forward problem crucially depends on the parameters of the LQ model. Unfortunately, these parameters are difficult to estimate via in vitro or in vivo studies, and as such, their values are unknown to treatment planners. The clinical literature is thus replete with debates about what parameter values will make specific dosing plans effective. This paper formulates this as an inverse optimization problem. The LQ dose-response parameters appear in the objective function, the left hand side, and the right hand side of the forward problem, and none of the existing generic methods can provide an exact solution of the inverse problem. This paper exploits the structure of the problem and identifies all possible parameter values that render the given dosing plan optimal, in closed-form. This closed-form formula is applied to dosing-plans from three clinical studies published within the last two years.

关键词： inverse optimization linear programming nonconvex quadratically constrained quadratic programming non-linear programming

来源：评论

学校读者我要写书评

暂无评论

An Optimal Full-Duplex AF Relay for Joint Analog and Digital Domain Self-Interference Cancellation

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2014年第8期62卷 2758-2772页

作者： Kang, Young Yun Kwak, Byung-Jae Cho, Joon Ho Pohang Univ Sci & Technol POSTECH Dept Elect Engn Pohang 790784 South Korea ETRI Taejon 305700 South Korea

In this paper, a full-duplex (FD) amplify-and-forward (AF) relay is designed to compensate for the duplexing loss of the half-duplex (HD) AF relay. In particular, when there is no direct link between a source and a destination, joint analog domain self-interference suppression and digital domain residual self-interference cancellation is considered with an FD-AF relay having single receive antenna but multiple transmit antennas. Unlike previous approaches, a nonconvex quadratically constrained quadratic programming problem is formulated to find the optimal solution. The end-to-end spectral efficiency or, equivalently, the end-to-end signal-to-interference-plus-noise ratio from the source to the destination is chosen as the objective function to be maximized subject to the average transmit power constraint at the relay. In addition, an average power constraint is imposed on the output of the relay's receive antenna to avoid the nonlinear distortion in the low noise amplifier and the excessive quantization noise in the analog-to-digital converter. Through the systematic reduction and the partitioning of the constraint set, the optimal solution is derived in a closed algorithmic expression and shows how it allocates the transmission power not only in the direction of maximal performance improvement but also in the orthogonal direction in order to balance the system performance and the amount of self interference. It is shown that the optimal FD-AF relay significantly outperforms the optimal HD-AF relay even with the hardware limitations in the RF chain of the relay's receiver being well taken into account.

关键词： Full-duplex relay amplify-and-forward relay self-interference cancellation nonconvex quadratically constrained quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Is a Finite Intersection of Balls Covered by a Finite Union of Balls in Euclidean Spaces?

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2020年第2期187卷 431-447页

作者： Runge, Vincent Univ Evry Univ Paris Saclay CNRS Lab Math & Modelisat Evry F-91037 Evry France

Considering a finite intersection of balls and a finite union of other balls in an Euclidean space, we propose an exact method to test whether the intersection is covered by the union. We reformulate this problem into quadratic programming problems. For each problem, we study the intersection between a sphere and a Voronoi-like polyhedron. That way, we get information about a possible overlap between the frontier of the union and the intersection of balls. If the polyhedra are non-degenerate, the initial nonconvex geometric problem, which is NP-hard in general, is tractable in polynomial time by convex optimization tools and vertex enumeration. Under some mild conditions, the vertex enumeration can be skipped. Simulations highlight the accuracy and efficiency of our approach compared with competing algorithms in Python for nonconvex quadratically constrained quadratic programming. This work is motivated by an application in statistics to the problem of multidimensional changepoint detection using pruned dynamic programming algorithms.

关键词： Ball covering problem nonconvex quadratically constrained quadratic programming Computational geometry Voronoi-like polyhedron Vertex enumeration Polynomial time complexity

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm using polar cuts for solving nonconvex quadratic programming problems

引用

OPTIMIZATION 2018年第2期67卷 359-375页

作者： Deng, Zhibin Fang, Shu-Cherng Lu, Cheng Guo, Xiaoling Univ Chinese Acad Sci Sch Econ & Management Beijing Peoples R China Chinese Acad Sci Key Lab Big Data Min & Knowledge Management Beijing Peoples R China North Carolina State Univ Dept Ind & Syst Engn Raleigh NC USA North China Elect Power Univ Sch Econ & Management Beijing Peoples R China China Univ Min & Technol Dept Math Beijing Peoples R China

In this paper, we propose a branch-and-cut algorithm for solving a nonconvex quadratically constrained quadratic programming (QCQP) problem with a nonempty bounded feasible domain. The problem is first transformed into a linear conic programming problem, and then approximated by semidefinite programming problems over different intervals. In order to improve the lower bounds, polar cuts, generated from corresponding cut-generation problems, are embedded in a branch-and-cut algorithm to yield a globally epsilon(r)-epsilon(z)-optimal solution (with respect to feasibility and optimality, respectively) in a finite number of iterations. To enhance the computational speed, an adaptive branch-and-cut rule is adopted. Numerical experiments indicate that the number of explored nodes required for solving QCQP problems can be significantly reduced by employing the proposed polar cuts.

关键词： Branch-and-cut algorithm nonconvex quadratically constrained quadratic programming polar cut semidefinite relaxation

来源：评论

学校读者我要写书评

暂无评论

Semidefinite Relaxation for Two Mixed Binary quadratically constrained quadratic Programs:Algorithms and Approximation Bounds

引用

Journal of the Operations Research Society of China 2016年第2期4卷 205-221页

作者： Zi Xu Ming-Yi Hong Department of Mathematics College of SciencesShanghai UniversityShanghai 200444China Department of Industrial and Manufacturing Engineering Iowa State UniversityAmesIA 50011USA

This paper develops new semidefinite programming(SDP)relaxation techniques for two classes of mixed binary quadratically constrained quadratic programs and analyzes their approximation *** first class of problems finds two minimum norm vectors in N-dimensional real or complex Euclidean space,such that M out of 2M concave quadratic constraints are *** employing a special randomized rounding procedure,we show that the ratio between the norm of the optimal solution of this model and its SDP relaxation is upper bounded by 54πM2 in the real case and by 24√Mπin the complex *** second class of problems finds a series of minimum norm vectors subject to a set of quadratic constraints and cardinality constraints with both binary and continuous *** show that in this case the approximation ratio is also bounded and independent of problem dimension for both the real and the complex cases.

关键词： nonconvex quadratically constrained quadratic programming Semidefinite program relaxation Approximation bound NP-hard

来源：评论

学校读者我要写书评

暂无评论

Power System State Estimation via Feasible Point Pursuit: Algorithms and Cramer-Rao Bound

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2018年第6期66卷 1649-1658页

作者： Wang, Gang Zamzam, Ahmed S. Giannakis, Georgios B. Sidiropoulos, Nicholas D. Beijing Inst Technol State Key Lab Intelligent Control & Decis Complex Beijing 100081 Peoples R China Univ Minnesota Digital Technol Ctr Minneapolis MN 55455 USA Univ Minnesota Dept Elect & Comp Engn Minneapolis MN 55455 USA Univ Virginia Dept Elect & Comp Engn Charlottesville VA 22904 USA

Accurately monitoring the system's operating point is central to the reliable and economic operation of an autonomous energy grid. Power system state estimation (PSSE) aims to obtain complete voltage magnitude and angle information at each bus given a number of system variables at selected buses and lines. Power flow analysis amounts to solving a set of noise-free power flow equations, and is cast as a special case of PSSE. Physical laws dictate quadratic relationships between available quantities and unknown voltages, rendering general instances of power flow and PSSE nonconvex and NP-hard. Past approaches are largely based on gradient-type iterative procedures or semidefinite relaxation (SDR). Due to nonconvexity, the solution obtained via gradienttype schemes depends on initialization, while SDR methods do not perform as desired in challenging scenarios. This paper puts forth novel feasible point pursuit (FPP)-based solvers for power flow analysis and PSSE, which iteratively seek feasible solutions for a nonconvex quadratically constrained quadratic programming reformulation of the weighted least-squares (WLS). Relative to the prior art, the developed solvers offer superior numerical performance at the cost of higher computational complexity. Furthermore, they converge to a stationary point of the WLS problem. As a baseline for comparing different estimators, the Cramer-Rao lower bound is derived for the fundamental PSSE problem in this paper. Judicious numerical tests on several IEEE benchmark systems showcase markedly improved performance of our FPP-based solvers for both power flow and PSSE tasks over popular WLS-based Gauss-Newton iterations and SDR approaches.

关键词： Power flow analysis state estimation nonconvex quadratically constrained quadratic programming feasible point pursuit autonomous energy grid

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：