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

NEW RESULTS ON NARROWING THE DUALITY GAP OF THE EXTENDED CELIS-DENNIS-TAPIA PROBLEM

SIAM JOURNAL ON OPTIMIZATION 2017年第2期27卷 890-909页

作者： Yuan, Jianhua Wang, Meiling Ai, Wenbao Shuai, Tianping Beijing Univ Posts & Telecommun Sch Sci Beijing 100876 Peoples R China

In this paper, we consider the extended Celis-Dennis-Tapia (CDT) problem that has a positive duality gap. It is presented in theory that this positive duality gap can be narrowed by adding an appropriate second-order-cone (SOC) constraint, which may lead to dividing the problem into two separate subproblems. More concretely, for any extended CDT problem with a positive duality gap, we prove that one SOC constraint is valid to narrow the positive duality gap if and only if the corresponding hyperplane intersects the "open optimal line segment." Especially when the second constraint function consists of the product of two linear functions, we prove that the positive duality gap can be eliminated thoroughly by solving two subproblems with SOC constraints. For any classical CDT problem with a positive duality gap, a new model with two SOC constraints is proposed, and a sufficient condition is presented under which this positive duality gap can be eliminated thoroughly. In particular, based on the sufficient condition, it is proved that the positive duality gaps of any two-dimensional classical CDT problem and a class of three-dimensional classical CDT problems can be eliminated thoroughly. Numerical results of some gap-existing examples coming from other papers show that their positive duality gaps are indeed eliminated by our SOC reformulation technique.

关键词： quadratically constrained quadratic programming CDT problem second-order cone global solutions SDP relaxation

来源：评论

学校读者我要写书评

暂无评论

AN ITERATIVE RANK PENALTY METHOD FOR NONCONVEX quadratically constrained quadratic PROGRAMS

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 2019年第6期57卷 3749-3766页

作者： Sun, Chuangchuang Dai, Ran Ohio State Univ Dept Mech & Aerosp Engn Columbus OH 43210 USA

This paper examines the nonconvex quadratically constrained quadratic programming (QCQP) problems using an iterative method. A QCQP problem can be handled as a linear matrix programming problem with a rank-one constraint on the to-be-determined matrix. One of the existing approaches for solving nonconvex QCQPs relaxes the rank one constraint on the unknown matrix into a semidefinite constraint to obtain the bound on the optimal value without finding the exact solution. By reconsidering the rank one matrix, the iterative rank penalty (IRP) method is proposed to gradually approach the rank one constraint. Each iteration of IRP is formulated as a convex problem with semidefinite constraints. Furthermore, an augmented Lagrangian method, called an extended Uzawa algorithm, is developed to solve the sequential problem at each iteration of IRP for improved scalability and computational efficiency. Simulation examples are presented using the proposed method, and comparative results obtained from the other methods are provided and discussed.

关键词： quadratically constrained quadratic programming semidefinite programming nonconvex optimization augmented Lagrangian method linear convergence

来源：评论

学校读者我要写书评

暂无评论

Response Vector constrained Robust LCMV Beamforming Based on Semidefinite programming

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2015年第21期63卷 5720-5732页

作者： Xu, Jingwei Liao, Guisheng Zhu, Shengqi Huang, Lei Xidian Univ Natl Lab Radar Signal Proc Xian 710071 Shaanxi Peoples R China Shenzhen Univ Coll Informat Engn Shenzhen 518060 Guangdong Peoples R China

Although linearly constrained minimum variance (LCMV) beamforming is robust against imprecise target information, it usually leads to relatively high sidelobe and distorted mainlobe which would induce a high false alarm probability. To circumvent this problem, this work devises a novel robust LCMV beamforming approach by utilizing response vector optimization. It intends to find the optimal response vector in lieu of the all-one response vector in traditional LCMV beamformer. The proposed robust beamformer is first formulated as a nonconvex quadratically constrained quadratic programming problem, and then transformed into a semidefinite programming problem which can be efficiently and exactly solved. The proposed beamformer not only improves the performance in terms of signal-to-interference-plus-noise ratio substantially, but also possesses low sidelobe and well-maintained mainlobe. Moreover, since the response vector is quite small in size, the complexity of calculating the optimal response vector is negligible. Additionally, the proposed beamformer is also extended to two-dimensional space-time adaptive processing. Simulation results are presented to demonstrate the superiority of the proposed approach.

关键词： Robust adaptive beamforming linearly constrained minimum variance beamformer response vector optimization quadratically constrained quadratic programming semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Path following in the exact penalty method of convex programming

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2015年第3期61卷 609-634页

作者： Zhou, Hua Lange, Kenneth N Carolina State Univ Dept Stat Raleigh NC 27695 USA Univ Calif Los Angeles Dept Biomath Los Angeles CA 90095 USA Univ Calif Los Angeles Dept Human Genet Los Angeles CA 90095 USA Univ Calif Los Angeles Dept Stat Los Angeles CA 90095 USA

Classical penalty methods solve a sequence of unconstrained problems that put greater and greater stress on meeting the constraints. In the limit as the penalty constant tends to , one recovers the constrained solution. In the exact penalty method, squared penalties are replaced by absolute value penalties, and the solution is recovered for a finite value of the penalty constant. In practice, the kinks in the penalty and the unknown magnitude of the penalty constant prevent wide application of the exact penalty method in nonlinear programming. In this article, we examine a strategy of path following consistent with the exact penalty method. Instead of performing optimization at a single penalty constant, we trace the solution as a continuous function of the penalty constant. Thus, path following starts at the unconstrained solution and follows the solution path as the penalty constant increases. In the process, the solution path hits, slides along, and exits from the various constraints. For quadratic programming, the solution path is piecewise linear and takes large jumps from constraint to constraint. For a general convex program, the solution path is piecewise smooth, and path following operates by numerically solving an ordinary differential equation segment by segment. Our diverse applications to (a) projection onto a convex set, (b) nonnegative least squares, (c) quadratically constrained quadratic programming, (d) geometric programming, and (e) semidefinite programming illustrate the mechanics and potential of path following. The final detour to image denoising demonstrates the relevance of path following to regularized estimation in inverse problems. In regularized estimation, one follows the solution path as the penalty constant decreases from a large value.

关键词： constrained convex optimization Exact penalty Geometric programming Ordinary differential equation quadratically constrained quadratic programming Regularization Semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

A New Global Optimization Scheme for quadratic Programs with Low-Rank Nonconvexity

引用

INFORMS JOURNAL ON COMPUTING 2021年第4期33卷 1368-1383页

作者： Cen, Xiaoli Xia, Yong Beihang Univ Sch Math Sci Minist Educ Informat Math & Behav Key Lab Beijing 100191 Peoples R China

We consider the classical convex constrained nonconvex quadratic programming problem where the Hessian matrix of the objective to be minimized has r negative eigenvalues, denoted by (QP(r)). Based on a biconvex programming reformulation in a slightly higher dimension, we propose a novel branch-and-bound algorithm to solve (QP(1)) and show that it returns an epsilon-approximate solution of (QP(1)) in at most O(1/root epsilon) iterations. We further extend the new algorithm to solve the general (QP(r)) with r > 1. Computational comparison shows the efficiency of our proposed global optimization method for small r. Finally, we extend the explicit relaxation approach for (QP(1)) to (QP(r)) with r > 1.

关键词： quadratic programming quadratically constrained quadratic programming branch and bound

来源：评论

学校读者我要写书评

暂无评论

A Unified Formulation and Nonconvex Optimization Method for Mixed-Type Decision-Making of Robotic Systems

引用

IEEE TRANSACTIONS ON ROBOTICS 2021年第3期37卷 831-846页

作者： Sun, Chuangchuang Kingry, Nathaniel Dai, Ran MIT Dept Aeronaut & Astronaut Cambridge MA 02139 USA Rockwell Collins Cedar Rapids IA 52498 USA Purdue Univ Sch Aeronaut & Astronaut W Lafayette IN 47907 USA

Mixed-type decision-making is ubiquitously required in robotic systems and has attracted significant research interests. Examples include, but not limited to, the integrated task and motion planning and optimal control of hybrid systems involving both continuous and discrete dynamic behaviors. For decision-making of robotic systems to improve operational efficiency, safety, and/or mission success rate, they involve both discrete variables representing task allocation or transitions between discrete modes and continuous variables representing trajectories of the planned motion or states governed by differential equations. This paper formulates a class of mixed-type decision-making problems with polynomial objective and constraints as quadratically constrained quadratic programming (QCQP) problems and a nonconvex optimization method based on alternating direction method of multipliers is proposed to solve the QCQP. The proposed optimization method consists of three sequential subproblems, all of which admit closed-form solutions. Moreover, convergence proof of the optimization algorithm is provided. Two representative problems, traveling salesman with obstacle avoidance and rendezvous and docking of a charging station with distinct phase constraints, are described and solved via the proposed method. Numerical simulations as well as experimental verification of both problems are presented and compared with a state-of-art method to validate the effectiveness, efficacy and robustness of the nonconvex optimization method.

关键词： Robots Decision making Convergence Planning Task analysis Charging stations Sparse matrices Alternating direction method of multipliers (ADMMs) hybrid control integrated task and motion planning (ITMP) mixed-type decision-making quadratically constrained quadratic programming robot rendezvous and docking

来源：评论

学校读者我要写书评

暂无评论

Update Summarization via Graph-Based Sentence Ranking

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2013年第5期25卷 1162-1174页

作者： Li, Xuan Du, Liang Shen, Yi-Dong Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing 100190 Peoples R China

Due to the fast evolution of the information on the Internet, update summarization has received much attention in recent years. It is to summarize an evolutionary document collection at current time supposing the users have read some related previous documents. In this paper, we propose a graph-ranking-based method. It performs constrained reinforcements on a sentence graph, which unifies previous and current documents, to determine the salience of the sentences. The constraints ensure that the most salient sentences in current documents are updates to previous documents. Since this method is NP-hard, we then propose its approximate method, which is polynomial time solvable. Experiments on the TAC 2008 and 2009 benchmark data sets show the effectiveness and efficiency of our method.

关键词： Summarization update summarization topic-focused summarization multidocument summarization extraction-based summarization graph-based ranking manifold ranking large-margin constrained ranking novelty quadratically constrained quadratic programming quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Optimal fractionation in radiotherapy with multiple normal tissues

引用

MATHEMATICAL MEDICINE AND BIOLOGY-A JOURNAL OF THE IMA 2016年第2期33卷 211-252页

作者： Saberian, Fatemeh Ghate, Archis Kim, Minsun Univ Washington Ind & Syst Engn Box 352650 Seattle WA 98195 USA Univ Washington Radiat Oncol Seattle WA 98195 USA

The goal in radiotherapy is to maximize the biological effect (BE) of radiation on the tumour while limiting its toxic effects on healthy anatomies. Treatment is administered over several sessions to give the normal tissue time to recover as it has better damage-repair capabilities than tumour cells. This is termed fractionation. A key problem in radiotherapy involves finding an optimal number of treatment sessions (fractions) and the corresponding dosing schedule. A major limitation of existing mathematically rigorous work on this problem is that it includes only a single normal tissue. Since essentially no anatomical region of interest includes only one normal tissue, these models may incorrectly identify the optimal number of fractions and the corresponding dosing schedule. We present a formulation of the optimal fractionation problem that includes multiple normal tissues. Our model can tackle any combination of maximum dose, mean dose and dose-volume type constraints for serial and parallel normal tissues as this is characteristic of most treatment protocols. We also allow for a spatially heterogeneous dose distribution within each normal tissue. Furthermore, we do not a priori assume that the doses are invariant across fractions. Finally, our model uses a spatially optimized treatment plan as input and hence can be seamlessly combined with any treatment planning system. Our formulation is a mixed-integer, non-convex, quadratically constrained quadratic programming problem. In order to simplify this computationally challenging problem without loss of optimality, we establish sufficient conditions under which equal-dosage or single-dosage fractionation is optimal. Based on the prevalent estimates of tumour and normal tissue model parameters, these conditions are expected to hold in many types of commonly studied tumours, such as those similar to head-and-neck and prostate cancers. This motivates a simple reformulation of our problem that leads to a closed-form fo

关键词： intensity modulated radiation therapy quadratically constrained quadratic programming linear-quadratic cell survival model

来源：评论

学校读者我要写书评

暂无评论

A predictive controller with artificial Lyapunov function for linear systems with input/state constraints

引用

AUTOMATICA 1998年第10期34卷 1255-1260页

作者： Bemporad, A ETH Zentrum Automat Control Lab CH-8092 Zurich Switzerland

This paper copes with the problem of satisfying input and/or state hard constraints in set-point tracking problems. Stability is guaranteed by synthesizing a Lyapunov quadratic function for the system, and by imposing that the terminal state lies within a level set of the function. Procedures to maximize the volume of such an ellipsoidal set are provided, and interior-point methods to solve on-line optimization are considered. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： predictive control constraints Lyapunov function set-point control optimization problems interior-point methods quadratically constrained quadratic programming

来源：评论

学校读者我要写书评

暂无评论

An optimal approach for the critical node problem using semidefinite programming

引用

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 2017年 471卷 315-324页

作者： Jiang, Cheng Liu, Zhonghua Wang, Juyun Yu, Hua Guo, Xiaoling Univ Chinese Acad Sci Sch Engn Sci Beijing 100049 Peoples R China Commun Univ China Sch Sci Beijing 100024 Peoples R China China Univ Min & Technol Dept Math Beijing 100083 Peoples R China

Detecting critical nodes in complex networks (CNP) has great theoretical and practical significance in many disciplines. The existing formulations for CNP are mostly, as we know, based on the integer linear programming model. However, we observed that, these formulations only considered the sizes but neglected the cohesiveness properties of the connected components in the induced network. To solve the problem and improve the performance of CNP solutions, we construct a novel nonconvex quadratically constrained quadratic programming (QCQP) model and derive its approximation solutions via semidefinite programming (SDP) technique and heuristic algorithms. Various types of synthesized and real-world networks, in the context of different connectivity patterns, are used to validate and verify the effectiveness of the proposed model and algorithm. Experimental results show that our method improved the state of the art of the CNP. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Critical node problem quadratically constrained quadratic programming Semidefinite programming Network optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：