• 文献检索
  • 文档翻译
  • 深度研究
  • 学术资讯
  • Suppr Zotero 插件Zotero 插件
  • 邀请有礼
  • 套餐&价格
  • 历史记录
应用&插件
Suppr Zotero 插件Zotero 插件浏览器插件Mac 客户端Windows 客户端微信小程序
定价
高级版会员购买积分包购买API积分包
服务
文献检索文档翻译深度研究API 文档MCP 服务
关于我们
关于 Suppr公司介绍联系我们用户协议隐私条款
关注我们

Suppr 超能文献

核心技术专利：CN118964589B侵权必究
粤ICP备2023148730 号-1Suppr @ 2026

文献检索

告别复杂PubMed语法，用中文像聊天一样搜索，搜遍4000万医学文献。AI智能推荐，让科研检索更轻松。

立即免费搜索

文件翻译

保留排版，准确专业，支持PDF/Word/PPT等文件格式，支持 12+语言互译。

免费翻译文档

深度研究

AI帮你快速写综述，25分钟生成高质量综述，智能提取关键信息，辅助科研写作。

立即免费体验

关于两个信赖域子问题的全局优化求解器的计算研究。

A computational study of global optimization solvers on two trust region subproblems.

作者信息

Montanher Tiago, Neumaier Arnold, Domes Ferenc

机构信息

Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria.

出版信息

J Glob Optim. 2018;71(4):915-934. doi: 10.1007/s10898-018-0649-7. Epub 2018 Apr 12.

DOI:10.1007/s10898-018-0649-7
PMID:30956397
原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC6417392/
Abstract

One of the relevant research topics to which Chris Floudas contributed was quadratically constrained quadratic programming (QCQP). This paper considers one of the simplest hard cases of QCQP, the two trust region subproblem (TTRS). In this case, one needs to minimize a quadratic function constrained by the intersection of two ellipsoids. The Lagrangian dual of the TTRS is a semidefinite program (SDP) and this result has been extensively used to solve the problem efficiently. We focus on numerical aspects of branch-and-bound solvers with three goals in mind. We provide (i) a detailed analysis of the ability of state-of-the-art solvers to complete the global search for a solution, (ii) a quantitative approach for measuring the cluster effect on each solver and (iii) a comparison between the branch-and-bound and the SDP approaches. We perform the numerical experiments on a set of 212 challenging problems provided by Kurt Anstreicher. Our findings indicate that SDP relaxations and branch-and-bound have orthogonal difficulties, thus pointing to a possible benefit of a combined method. The following solvers were selected for the experiments: , , , and .

摘要

克里斯·弗洛达斯所涉及的相关研究主题之一是二次约束二次规划（QCQP）。本文探讨了QCQP中最简单的难题之一，即双信赖域子问题（TTRS）。在这种情况下，需要在两个椭球相交所构成的约束条件下，使一个二次函数最小化。TTRS的拉格朗日对偶是一个半定规划（SDP），这一结果已被广泛用于高效地解决该问题。我们着眼于三个目标，关注分支定界求解器的数值方面。我们提供：（i）对当前最先进的求解器完成全局解搜索能力的详细分析；（ii）一种用于衡量每个求解器聚类效应的定量方法；（iii）分支定界法和SDP方法之间的比较。我们针对库尔特·安斯特赖歇尔提供的一组212个具有挑战性的问题进行了数值实验。我们的研究结果表明，SDP松弛法和分支定界法存在相互正交的困难，因此这表明了一种组合方法可能具有的优势。以下求解器被选用于实验： ， ， ， 以及 。

https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/5ad2e444bf3e/10898_2018_649_Fig16_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/6e3f2a6267e1/10898_2018_649_Fig1_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/a1401c857d09/10898_2018_649_Fig2_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/f63d5e59082f/10898_2018_649_Fig3_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/922658f57575/10898_2018_649_Fig4_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/bcfed59b54f8/10898_2018_649_Fig5_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/61d71fb2d725/10898_2018_649_Fig6_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/1bf2dbb8728c/10898_2018_649_Fig7_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/b6d03cf7d592/10898_2018_649_Fig8_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/d2172147d98a/10898_2018_649_Fig9_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/340250059fde/10898_2018_649_Fig10_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/8b71fef3d0a1/10898_2018_649_Fig11_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/c50a2c840b5f/10898_2018_649_Fig12_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/6516e4d46c8e/10898_2018_649_Fig13_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/266f5bb7309d/10898_2018_649_Fig14_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/d3556b134b4e/10898_2018_649_Fig15_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/5ad2e444bf3e/10898_2018_649_Fig16_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/6e3f2a6267e1/10898_2018_649_Fig1_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/a1401c857d09/10898_2018_649_Fig2_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/f63d5e59082f/10898_2018_649_Fig3_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/922658f57575/10898_2018_649_Fig4_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/bcfed59b54f8/10898_2018_649_Fig5_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/61d71fb2d725/10898_2018_649_Fig6_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/1bf2dbb8728c/10898_2018_649_Fig7_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/b6d03cf7d592/10898_2018_649_Fig8_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/d2172147d98a/10898_2018_649_Fig9_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/340250059fde/10898_2018_649_Fig10_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/8b71fef3d0a1/10898_2018_649_Fig11_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/c50a2c840b5f/10898_2018_649_Fig12_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/6516e4d46c8e/10898_2018_649_Fig13_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/266f5bb7309d/10898_2018_649_Fig14_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/d3556b134b4e/10898_2018_649_Fig15_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/3aef/6417392/5ad2e444bf3e/10898_2018_649_Fig16_HTML.jpg

相似文献

1
A computational study of global optimization solvers on two trust region subproblems.关于两个信赖域子问题的全局优化求解器的计算研究。
J Glob Optim. 2018;71(4):915-934. doi: 10.1007/s10898-018-0649-7. Epub 2018 Apr 12.
2
A computational study of exact subgraph based SDP bounds for Max-Cut, stable set and coloring.基于精确子图的最大割、稳定集和着色问题的半定规划界的计算研究。
Math Program. 2020;183(1):283-308. doi: 10.1007/s10107-020-01512-2. Epub 2020 May 25.
3
Large-Scale Binary Quadratic Optimization Using Semidefinite Relaxation and Applications.基于半定松弛的大规模二进制二次优化及其应用。
IEEE Trans Pattern Anal Mach Intell. 2017 Mar;39(3):470-485. doi: 10.1109/TPAMI.2016.2541146. Epub 2016 Mar 11.
4
Worst case linear discriminant analysis as scalable semidefinite feasibility problems.最坏情况线性判别分析作为可扩展的半定可行性问题。
IEEE Trans Image Process. 2015 Aug;24(8):2382-92. doi: 10.1109/TIP.2015.2401511. Epub 2015 Feb 6.
5
Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization.可验证的最优离群值鲁棒几何感知：半定松弛与可扩展全局优化
IEEE Trans Pattern Anal Mach Intell. 2023 Mar;45(3):2816-2834. doi: 10.1109/TPAMI.2022.3179463. Epub 2023 Feb 3.
6
An SDP-based approach for computing the stability number of a graph.一种基于半定规划（SDP）的计算图的稳定数的方法。
Math Methods Oper Res (Heidelb). 2022;95(1):141-161. doi: 10.1007/s00186-022-00773-1. Epub 2022 Mar 12.
7
Efficient semidefinite spectral clustering via lagrange duality.通过拉格朗日对偶实现高效半定谱聚类。
IEEE Trans Image Process. 2014 Aug;23(8):3522-34. doi: 10.1109/TIP.2014.2329453. Epub 2014 Jun 6.
8
Determining protein structures from NOESY distance constraints by semidefinite programming.通过半定规划从NOESY距离约束确定蛋白质结构。
J Comput Biol. 2013 Apr;20(4):296-310. doi: 10.1089/cmb.2012.0089. Epub 2012 Oct 31.
9
Ground truth clustering is not the optimum clustering.真实聚类并非最优聚类。
Sci Rep. 2025 Mar 17;15(1):9223. doi: 10.1038/s41598-025-90865-9.
10
Phase transitions in semidefinite relaxations.半定松弛中的相变。
Proc Natl Acad Sci U S A. 2016 Apr 19;113(16):E2218-23. doi: 10.1073/pnas.1523097113. Epub 2016 Mar 21.

引用本文的文献

1
Assessment of trends and emission sources of heavy metals from the soil sediments near the Bohai Bay.渤海湾近岸土壤沉积物重金属的趋势评估及排放源分析。
Environ Sci Pollut Res Int. 2019 Oct;26(28):29095-29109. doi: 10.1007/s11356-019-06130-w. Epub 2019 Aug 7.