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

SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices

MATHEMATICAL programming 2018年第2期169卷 531-563页

作者： Jiang, Rujun Li, Duan Wu, Baiyi Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China Guangdong Univ Foreign Studies Sch Finance Guangzhou Guangdong Peoples R China

We investigate in this paper the generalized trust region subproblem (GTRS) of minimizing a general quadratic objective function subject to a general quadratic inequality constraint. By applying a simultaneous block diagonalization approach, we obtain a congruent canonical form for the symmetric matrices in both the objective and constraint functions. By exploiting the block separability of the canonical form, we show that all GTRSs with an optimal value bounded from below are second order cone programming (SOCP) representable. Our result generalizes the recent work of Ben-Tal and den Hertog (Math. Program. 143(1-2):1-29, 2014), which establishes the SOCP representability of the GTRS under the assumption of the simultaneous diagonalizability of the two matrices in the objective and constraint functions. We then derive a closed-form solution for the GTRS when the two matrices are not simultaneously diagonalizable. We further extend our method to two variants of the GTRS in which the inequality constraint is replaced by either an equality constraint or an interval constraint.

关键词： Trust region subproblem Canonical form quadratically constrained quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Constructing Multiple Kernel Learning Framework for Blast Furnace Automation

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2012年第4期9卷 763-777页

作者： Jian, Ling Gao, Chuanhou Xia, Zhonghang China Univ Petr Coll Sci Qingdao 266555 Peoples R China Dalian Univ Technol Sch Math Sci Dalian 116024 Peoples R China Zhejiang Univ Dept Math Hangzhou 310027 Zhejiang Peoples R China Western Kentucky Univ Dept Comp Sci Bowling Green KY 42101 USA

This paper constructs the framework of the reproducing kernel Hilbert space for multiple kernel learning, which provides clear insights into the reason that multiple kernel support vector machines (SVM) outperform single kernel SVM. These results can serve as a fundamental guide to account for the superiority of multiple kernel to single kernel learning. Subsequently, the constructed multiple kernel learning algorithms are applied to model a nonlinear blast furnace system only based on its input-output signals. The experimental results not only confirm the superiority of multiple kernel learning algorithms, but also indicate that multiple kernel SVM is a kind of highly competitive data-driven modeling method for the blast furnace system and can provide reliable indication for blast furnace operators to take control actions. Note to Practitioners-This paper is motivated by the problem of predicting the silicon content in blast furnace hot metal, which is an open problem for realizing blast furnace automation. Here, based on the single kernel and multiple kernel SVM, we pay special attention to the silicon trend prediction since it can provide more direct guideline for taking control action in the blast furnace operation. Theoretically, we have given the detailed reasons that multiple kernel SVM is superior to single kernel SVM, which can improve the transparency of multiple kernel learning algorithm. The experimental results, not only confirm the superiority of multiple kernel learning algorithms, but also indicate that multiple kernel SVM is a kind of highly competitive data-driven modeling method for the blast furnace system and can provide reliable indication for blast furnace operators to take control actions.

关键词： Data-driven multiple kernel support vector machines (SVM) nonlinear blast furnace system quadratically constrained quadratic programming reproducing kernel Hilbert space

来源：评论

学校读者我要写书评

暂无评论

NONCONVEX PHASE SYNCHRONIZATION

引用

SIAM JOURNAL ON OPTIMIZATION 2016年第4期26卷 2355-2377页

作者： Boumal, Nicolas Princeton Univ Dept Math Princeton NJ 08544 USA

We estimate n phases (angles) from noisy pairwise relative phase measurements. The task is modeled as a nonconvex least-squares optimization problem. It was recently shown that this problem can be solved in polynomial time via convex relaxation, under some conditions on the noise. In this paper, under similar but more restrictive conditions, we show that a modified version of the power method converges to the global optimum. This is simpler and (empirically) faster than convex approaches. Empirically, they both succeed in the same regime. Further analysis shows that, in the same noise regime as previously studied, second-order necessary optimality conditions for this quadratically constrained quadratic program are also sufficient, despite nonconvexity.

关键词： angular synchronization nonconvex optimization generalized power method projected power method sufficient optimality conditions quadratically constrained quadratic programming optimization on manifolds

来源：评论

学校读者我要写书评

暂无评论

Multi-class discriminant kernel learning via convex programming

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2008年第4期9卷 719-758页

作者： Ye, Jieping Ji, Shuiwang Chen, Jianhui Arizona State Univ Dept Comp Sci & Engn Ctr Evolutionary Funct Genom Biodesign Inst Tempe AZ 85287 USA

Regularized kernel discriminant analysis (RKDA) performs linear discriminant analysis in the feature space via the kernel trick. Its performance depends on the selection of kernels. In this paper, we consider the problem of multiple kernel learning (MKL) for RKDA, in which the optimal kernel matrix is obtained as a linear combination of pre-specified kernel matrices. We show that the kernel learning problem in RKDA can be formulated as convex programs. First, we show that this problem can be formulated as a semidefinite program (SDP). Based on the equivalence relationship between RKDA and least square problems in the binary-class case, we propose a convex quadratically constrained quadratic programming (QCQP) formulation for kernel learning in RKDA. A semi-infinite linear programming (SILP) formulation is derived to further improve the efficiency. We extend these formulations to the multi-class case based on a key result established in this paper. That is, the multi-class RKDA kernel learning problem can be decomposed into a set of binary-class kernel learning problems which are constrained to share a common kernel. Based on this decomposition property, SDP formulations are proposed for the multi-class case. Furthermore, it leads naturally to QCQP and SILP formulations. As the performance of RKDA depends on the regularization parameter, we show that this parameter can also be optimized in a joint framework with the kernel. Extensive experiments have been conducted and analyzed, and connections to other algorithms are discussed.

关键词： model selection kernel discriminant analysis semidefinite programming quadratically constrained quadratic programming semi-infinite linear programming

来源：评论

学校读者我要写书评

暂无评论

A working set SQCQP algorithm with simple nonmonotone penalty parameters

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2011年第6期236卷 1382-1398页

作者： Tang, Chun-Ming Jian, Jin-Bao Li, Guo-Yin Guangxi Univ Coll Math & Informat Sci Nanning 530004 Peoples R China Univ New S Wales Dept Appl Math Sydney NSW 2052 Australia

In this paper, we present a new sequential quadratically constrained quadratic programming (SQCQP) algorithm, in which a simple updating strategy of the penalty parameter is adopted. This strategy generates nonmonotone penalty parameters at early iterations and only uses the multiplier corresponding to the bound constraint of the quadratically constrained quadratic programming (QCQP) subproblem instead of the multipliers of the quadratic constraints, which will bring some numerical advantages. Furthermore, by using the working set technique, we remove the constraints of the QCQP subproblem that are locally irrelevant, and thus the computational cost could be reduced. Without assuming the convexity of the objective function or the constraints, the algorithm is proved to be globally, superlinearly and quadratically convergent. Preliminary numerical results show that the proposed algorithm is very promising when compared with the tested SQP algorithms. (C) 2011 Elsevier B.V. All rights reserved.

关键词： SQCQP quadratically constrained quadratic programming Working set Nonmonotone penalty parameters Superlinear convergence

来源：评论

学校读者我要写书评

暂无评论

Maximizing the sum of a generalized Rayleigh quotient and another Rayleigh quotient on the unit sphere via semidefinite programming

引用

JOURNAL OF GLOBAL OPTIMIZATION 2016年第2期64卷 399-416页

作者： Van-Bong Nguyen Sheu, Ruey-Lin Xia, Yong Natl Cheng Kung Univ Dept Math Tainan 701 Taiwan Beihang Univ Sch Math & Syst Sci State Key Lab Software Dev Environm LMIB Minist Educ Beijing 100191 Peoples R China

The problem is a type of "sum-of-ratios" fractional programming and is known to be NP-hard. Due to many local maxima, finding the global maximizer is in general difficult. The best attempt so far is a critical point approach based on a necessary optimality condition. The problem therefore has not been completely solved. Our novel idea is to replace the generalized Rayleigh quotient by a parameter and generate a family of quadratic subproblems subject to two quadratic constraints. Each , if the problem dimension , can be solved in polynomial time by incorporating a version of S-lemma;a tight SDP relaxation;and a matrix rank-one decomposition procedure. Then, the difficulty of the problem is largely reduced to become a one-dimensional maximization problem over an interval of parameters . We propose a two-stage scheme incorporating the quadratic fit line search algorithm to find numerically. Computational experiments show that our method solves the problem correctly and efficiently.

关键词： Fractional programming (Generalized) Rayleigh quotient quadratically constrained quadratic programming S-Lemma Semidefinite programming quadratic fit line search

来源：评论

学校读者我要写书评

暂无评论

PROJECTIVELY AND WEAKLY SIMULTANEOUSLY DIAGONALIZABLE MATRICES AND THEIR APPLICATIONS\ast

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2024年第1期45卷 167-202页

作者： Ding, Wentao Li, Jianze Zhang, Shuzhong Chinese Univ Hong Kong Shenzhen Res Inst Big Data Sch Data Sci Shenzhen Guangdong Peoples R China Chinese Univ Hong Kong Shenzhen Res Inst Big Data Shenzhen Guangdong Peoples R China Univ Minnesota Dept Ind & Syst Engn Minneapolis MN 55455 USA

Characterizing simultaneously diagonalizable (SD) matrices has been receiving considerable attention in recent decades due to its wide applications and its role in matrix analysis. However, the notion of SD matrices is arguably still restrictive for wider applications. In this paper, we consider two error measures related to the simultaneous diagonalization of matrices and propose several new variants of SD thereof;in particular, TWSD, TWSD-B, Tm,n-SD (SDO), DWSD, and Dm,n-SD (SDO). Those are all weaker forms of SD. We derive various sufficient and/or necessary conditions of them under different assumptions and show the relationships between these new notions. Finally, we discuss the applications of these new notions in, e.g., quadratically constrained quadratic programming and independent component analysis.

关键词： simultaneous diagonalization weak simultaneous diagonalization projective simul- taneous diagonalization canonical form quadratically constrained quadratic programming indepen- dent component analysis

来源：评论

学校读者我要写书评

暂无评论

Generating cutting planes for the semidefinite relaxation of quadratic programs

引用

COMPUTERS & OPERATIONS RESEARCH 2015年第Mar.期55卷 65-75页

作者： Gorge, Agnes Lisser, Abdel Zorgati, Riadh Univ Paris 11 LRI F-91405 Orsay France EDF R&D OSIRIS F-92141 Clamart France

Semidefinite programming is well-known for providing relaxations of quadratic programs. In practice, only few real-world applications of this approach have been reported. This can be explained by the fact that the standard semidefinite relaxation must generally be tightened with cuts, which increases the substantial computational cost of the semidefinite program. Then, the challenge is to come up with the most effective cuts. In this paper, we present a systematic approach based on a polynomial separation problem to compute such cuts. Then, we apply this technique to a well-known problem of energy management, i.e., the scheduling of the nuclear outages which is a combinatorial problem with quadratic objective and non-convex quadratic constraints. This leads to the identification of some relevant cutting planes for this problem, allowing an average enhancement of 25% of the semidefinite relaxation compared to the linear relaxation. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： quadratically constrained quadratic programming Semidefinite relaxation Cutting planes

来源：评论

学校读者我要写书评

暂无评论

Robust adaptive beamforming based on a new steering vector estimation algorithm

引用

SIGNAL PROCESSING 2013年第9期93卷 2539-2542页

作者： Jia, Weimin Jin, Wei Zhou, Shuhua Yao, Minli Xian Res Inst High Technol Dept Elect & Informat Engn Xian 710025 Shaanxi Peoples R China Xian Res Inst High Technol Wire Commun Tech Off Qing Zhou 262500 Shandong Peoples R China

A new approach to the design of robust adaptive beamforming is introduced. In the proposed approach, the mismatch vector of the desired steering vector is estimated by solving a quadratically constrained quadratic programming problem using an interference-plus-noise subspace projection matrix. The presumed look direction of desired signal is the only prior information of the proposed approach, and the parameters of uncertainty set or the angular sectors of the desired signal are not needed. In the presence of large DOA mismatch, the proposed beamformer performs well. Moreover, the proposed approach can deal with arbitrary steering vector mismatch in theory while many existing advanced robust beamformers cannot. Hence, it is very suitable for many practical applications. Crown Copyright (c) 2013 Published by Elsevier B.V. All rights reserved.

关键词： Adaptive beamforming Steering vector estimation quadratically constrained quadratic programming Robustness

来源：评论

学校读者我要写书评

暂无评论

New notions of simultaneous diagonalizability of quadratic forms with applications to QCQPs

引用

MATHEMATICAL programming 2024年 1-48页

作者： Wang, Alex L. Jiang, Rujun Carnegie Mellon Univ Pittsburgh PA USA Purdue Univ Daniels Sch Business W Lafayette IN USA Fudan Univ Sch Data Sci Shanghai Peoples R China Shanghai Key Lab Contemporary Appl Math Shanghai Peoples R China

A set of quadratic forms is simultaneously diagonalizable via congruence (SDC) if there exists a basis under which each of the quadratic forms is diagonal. This property appears naturally when analyzing quadratically constrained quadratic programs (QCQPs) and has important implications in globally solving such problems using branch-and-bound methods. This paper extends the reach of the SDC property by studying two new weaker notions of simultaneous diagonalizability. Specifically, we say that a set of quadratic forms is almost SDC (ASDC) if it is the limit of SDC sets and d-restricted SDC (d-RSDC) if it is the restriction of an SDC set in up to d-many additional dimensions. In the context of QCQPs, these properties correspond to problems that may be diagonalized after arbitrarily small perturbations or after the introduction of d additional variables. Our main contributions are complete characterizations of the ASDC pairs and nonsingular triples of symmetric matrices, as well as a sufficient condition for the 1-RSDC property for pairs of symmetric matrices. Surprisingly, we show that every singular symmetric pair is ASDC and that almost every symmetric pair is 1-RSDC. We accompany our theoretical results with preliminary numerical experiments applying these constructions to solve QCQPs within branch-and-bound schemes.

关键词： Almost simultaneously diagonalizable Restricted simultaneously diagonalizable Simultaneous congruence quadratic forms quadratically constrained quadratic programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：