Numerical Methods for Large Scale Semidefinite Programming
大规模半定规划的数值方法
基本信息
- 批准号:09680418
- 负责人:
- 金额:$ 2.05万
- 依托单位:
- 依托单位国家:日本
- 项目类别:Grant-in-Aid for Scientific Research (C)
- 财政年份:1997
- 资助国家:日本
- 起止时间:1997 至 1998
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
In this research project, we developed the SDPA (SemiDefinite Programming Algorithm) for solving large scale semidefinite programs. The main features of the SDPA are :(a) The SDPA is written in C++.(b) The SDPA incorporates the Mebrotra-type predictor-corrector step, which contributes to saving the number of iterations and to increasing the numerical stability.(c) Besides the HRVW/KSH/M search direction the AHO search direction and the NT search direction are available at the user's option.(d) The SDPA utilizes the Meschach to increase the numerical stability.(e) The SDPA provides some information on infeasibility of a semidefinite program to be solved.(f) The SDPA handles not only block diagonal matrices but also sparse matrix data structure. When an SDP to be solved is large scale and sparse, this sparse matrix data structure is effectively utilized in increasing the computational efficiency and saving the memory.We applied the SDPA to various problems such as the semidefinite programming relaxation of nonconvex quadratic programming problems and bilinear matrix inequalities, and confirmed its computational efficiency through numerious computational experiments.
在本研究计画中,我们发展了一个求解大型半定规划的半定规划演算法。SDPA的主要特点是:(a)SDPA是用C++编写的。(b)SDPA采用了Mebrotra型预估-校正步,节省了迭代次数,提高了数值稳定性。(c)除了HRVW/KSH/M搜索方向外,用户还可以选择AHO搜索方向和NT搜索方向。(d)SDPA利用Meschach来增加数值稳定性。(e)SDPA提供了一些关于半定规划不可行性的信息。(f)SDPA不仅处理块对角矩阵,而且处理稀疏矩阵数据结构。当待解的SDP规模较大且稀疏时,这种稀疏矩阵数据结构可以有效地提高计算效率和节省内存,我们将SDPA应用于非凸二次规划问题的半定规划松弛和双线性矩阵不等式等问题,并通过大量的计算实验验证了其计算效率。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
小島政和: "A Conjugate Direction Method for Approximating the Analytic Center of a Polytope" Journal of Inequalities and Applications. Vol.2. 181-194 (1998)
Masakazu Kojima:“近似多面体分析中心的共轭方向方法”《不等式与应用杂志》第 2 卷(1998 年)。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
M.Kojima, M.Shida and S.Shindoh: ""Search Directions in the SDP and the Monotone SDLCP : Generalization and Inexact Computation"" (to appear). Mathematical Programming.
M.Kojima、M.Shida 和 S.Shindoh:“SDP 和单调 SDLCP 中的搜索方向:泛化和不精确计算”(即将出现)。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
小島 政和: "Search Directions in the SDP and the Monotone SDLCP : Generalization and Inexact Computation" Mathematical Programming. 掲載予定.
Masakazu Kojima:“SDP 和单调 SDLCP 中的搜索方向:泛化和不精确计算”数学编程。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
K.Nakata, K.Fujisawa and M.Kojima: ""Using the Conjugate Gradient Method in Interior-Point Methods for Semidefinite Programs"(in Japanese)" Proceedings of the Institute of Statistical Mathematics. Vol.46, No.2. 297-316 (1998)
K.Nakata、K.Fujisawa 和 M.Kojima:“在半定规划的内点方法中使用共轭梯度法”(日文)”统计数学研究所论文集。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
小島政和: "Interior-Point Methods for the Monotone Linear Complementarity Problem in Symmetric Matrices" SIAM J. Optimization. 7. 86‐125 (1997)
Masakazu Kojima:“对称矩阵中单调线性互补问题的内点方法”SIAM J. Optimization。7. 86-125 (1997)
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
KOJIMA Masakazu其他文献
KOJIMA Masakazu的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('KOJIMA Masakazu', 18)}}的其他基金
Numerical methods for large sensor network localization problems
大型传感器网络定位问题的数值方法
- 批准号:
22310089 - 财政年份:2010
- 资助金额:
$ 2.05万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
A challenge to huge scale semidefinite programs-exploiting sparsity, parallel computation and polynomial optimization problems
对大规模半定规划的挑战——利用稀疏性、并行计算和多项式优化问题
- 批准号:
19310096 - 财政年份:2007
- 资助金额:
$ 2.05万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
Polyhedral Homotopy Continuation Methods for Computing All Real and Complex Solutions of Systems of Polynomial Equations
计算多项式方程组全实数和复数解的多面体同伦延拓方法
- 批准号:
13650444 - 财政年份:2001
- 资助金额:
$ 2.05万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Successive Convex Relaxation Methods for Nonconvex Optimization Problems
非凸优化问题的连续凸松弛方法
- 批准号:
11680441 - 财政年份:1999
- 资助金额:
$ 2.05万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Interior Point Methods for Linear Programs and Their Applications
线性规划的内点法及其应用
- 批准号:
03832017 - 财政年份:1991
- 资助金额:
$ 2.05万 - 项目类别:
Grant-in-Aid for General Scientific Research (C)
相似海外基金
Study on Renewable Energy Integration with Mathematical Programming Model considering Electricity and Non-Electricity Sectors
考虑电力与非电力部门的可再生能源并网数学规划模型研究
- 批准号:
20H02679 - 财政年份:2020
- 资助金额:
$ 2.05万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
Study on combination of mathematical programming and evolutionary multi-point methods
数学规划与进化多点方法结合的研究
- 批准号:
20K11970 - 财政年份:2020
- 资助金额:
$ 2.05万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Improved Mathematical Programming Techniques for Approximation Algorithms
改进近似算法的数学编程技术
- 批准号:
RGPIN-2015-06496 - 财政年份:2019
- 资助金额:
$ 2.05万 - 项目类别:
Discovery Grants Program - Individual
Research on resource allocation method for service chaining based on approach of applied mathematical programming
基于应用数学规划方法的服务链资源分配方法研究
- 批准号:
19K14980 - 财政年份:2019
- 资助金额:
$ 2.05万 - 项目类别:
Grant-in-Aid for Early-Career Scientists
AI Planning and Mathematical Programming
人工智能规划与数学规划
- 批准号:
RGPIN-2015-05072 - 财政年份:2019
- 资助金额:
$ 2.05万 - 项目类别:
Discovery Grants Program - Individual
AF: Small: Faster and Better Algorithms for, and via, Mathematical Programming Relaxations
AF:小:更快更好的算法,并通过数学编程松弛
- 批准号:
1910149 - 财政年份:2019
- 资助金额:
$ 2.05万 - 项目类别:
Standard Grant
Behavioural-based mathematical programming: algorithmics and applications
基于行为的数学规划:算法和应用
- 批准号:
RGPIN-2017-05073 - 财政年份:2019
- 资助金额:
$ 2.05万 - 项目类别:
Discovery Grants Program - Individual
Behavioural-based mathematical programming: algorithmics and applications
基于行为的数学规划:算法和应用
- 批准号:
RGPIN-2017-05073 - 财政年份:2018
- 资助金额:
$ 2.05万 - 项目类别:
Discovery Grants Program - Individual
Mathematical programming techniques for the solution of hard combinatorial optimization problems arising in transportation
用于解决运输中出现的硬组合优化问题的数学编程技术
- 批准号:
435824-2013 - 财政年份:2018
- 资助金额:
$ 2.05万 - 项目类别:
Discovery Grants Program - Individual
AI Planning and Mathematical Programming
人工智能规划与数学规划
- 批准号:
RGPIN-2015-05072 - 财政年份:2018
- 资助金额:
$ 2.05万 - 项目类别:
Discovery Grants Program - Individual