対称錐上の線形計画問題と大域的最適化
对称锥上的线性规划问题和全局优化
基本信息
- 批准号:15740054
- 负责人:
- 金额:$ 1.98万
- 依托单位:
- 依托单位国家:日本
- 项目类别:Grant-in-Aid for Young Scientists (B)
- 财政年份:2003
- 资助国家:日本
- 起止时间:2003 至 2005
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
今年度も多項式計画(大域的最適化)に関する研究と,2次錐計画に対するピボットアルゴリズムという2本をテーマに研究を行なった。両方とも対称錐上の線形計画問題に密接に関係するテーマである。前年より続く東工大の小島教授,韓国Ewha Women's UniversityのKim教授,それに大学院生の脇氏らと共同研究をさらにすすめた。SDP緩和問題を作る際に,その疎性を利用して解くべき最適化問題のサイズを小さくするアイデアを論文にしたものはSIAM Journal on Optimizationに受理された。これにより,変数の数が多い大域的最適化問題(多項式計画問題)を解けるようになった。また,そのアイデアに基づくソフトウエアSparsePOPをMATLABで実装し,公開している。従来の多項式計画のソフトウェアが15変数程度の問題までしか解けないのに比べ、SparsePOPは条件によっては1000変数の問題まで解くことができるようになった。一方,対称錐計画問題の一種である2次錐計画に対しても,ピボットを用いたアルゴリズムの研究は続けている。理論的には,複数の2次錐を持つ場合の解析を行ない,ピボットアルゴリズムをすっきり記述できるようにした。この結果は現在投稿中である。また1つの錐の場合の実装を大学院生の栗田氏と共同で行ない、アルゴリズムの挙動を観察した。その結果,実装に関する様々な問題点が浮かび上がった。この結果は日本語の論文としてまとめ,統計数理に受理・掲載された。
This year's polynomial project (optimization of large domains) is related to the study of the second order cone project. The relationship between the linear design problem and the cone The year before last, Professor Kojima of East China University of Technology and Professor Kim of Ewha Women's University in South Korea jointly conducted research on university students. SDP Mitigation Problem is a problem that can be solved by using the properties of the problem. The optimization problem (polynomial project problem) of multi-medium large domain is solved by the number of variables. In addition, the software for SparsePOP is implemented in MATLAB and is open to the public. The solution to the problem of the polynomial program is 15 degrees. The solution to the problem of the SparsePOP condition is 1000 degrees. One of the problems of cone planning is that the second order cone planning problem is a problem of cone planning. For the sake of theory, the analysis of multiple quadratic cones can be carried out in various situations, and the descriptions can be written on the computer. The result is now posted in. 1. To observe the behavior of university students in the event of a serious injury As a result, the problem points are floating and rising. The results of this paper are Japanese, statistical and mathematical.
项目成果
期刊论文数量(8)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
2次錐計画のサブクラスに対する単体法的アルゴリズムにおけるピボット選択規則について
关于二次锥设计子类单纯形算法中的主元选择规则
- DOI:
- 发表时间:2005
- 期刊:
- 影响因子:0
- 作者:Masakazu Muramatsu;Rameswar Debnath;栗田圭介
- 通讯作者:栗田圭介
A Unified Class of Directly Solvable Semidefinite Programming Problms
一类统一的可直接求解的半定规划问题
- DOI:
- 发表时间:2005
- 期刊:
- 影响因子:0
- 作者:Masakazu Muramatsu;Rameswar Debnath;栗田圭介;Masakazu Muramatsu
- 通讯作者:Masakazu Muramatsu
Masakazu Muramatsu: "A Unified Class of Directly Solvable SDP"Annals of Operations Research. (to appear).
Masakazu Muramatsu:“可直接解决的 SDP 的统一类”运筹学年鉴。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity
- DOI:
- 发表时间:2004
- 期刊:
- 影响因子:0
- 作者:Hayato Waki;Sunyoung Kim;M. Kojima;M. Muramatsu
- 通讯作者:Hayato Waki;Sunyoung Kim;M. Kojima;M. Muramatsu
Masakazu Muramatsu, Tsunehiro Suzuki: "A New Second-Order Cone Relaxation for MAX-CUT Problems"Journal of Operations Research Society of Japan. 46. 164-177 (2003)
Masakazu Muramatsu、Tsunehiro Suzuki:“针对 MAX-CUT 问题的新二阶锥松弛”日本运筹学会杂志。
- 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 }}
村松 正和其他文献
Chubanov による同次線形計画問題の内点許容解を求めるアルゴリズムとその拡張に関する最近の展開
用于寻找齐次线性规划问题及其扩展的内点可接受解的丘巴诺夫算法的最新进展。
- DOI:
- 发表时间:
2017 - 期刊:
- 影响因子:0
- 作者:
松本 翔太;村松 正和;村松正和 - 通讯作者:
村松正和
村松 正和的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('村松 正和', 18)}}的其他基金
整数制約つき半正定値計画問題への挑戦
整数约束半定规划问题的挑战
- 批准号:
24K14838 - 财政年份:2024
- 资助金额:
$ 1.98万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Theory and algorithms for ill-conditioned conic linear programming
病态二次曲线线性规划的理论与算法
- 批准号:
20H04145 - 财政年份:2020
- 资助金额:
$ 1.98万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
対称錐線形計画に対する内点法に関する研究
对称圆锥线性规划内点法研究
- 批准号:
12740073 - 财政年份:2000
- 资助金额:
$ 1.98万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
対称行列空間における線形最適化問題に対する効率的な解法アルゴリズムに関する研究
对称矩阵空间线性优化问题高效求解算法研究
- 批准号:
08750486 - 财政年份:1996
- 资助金额:
$ 1.98万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
相似海外基金
線形計画法と深層学習による人工衛星データの復元と解析
使用线性规划和深度学习恢复和分析卫星数据
- 批准号:
20K21792 - 财政年份:2020
- 资助金额:
$ 1.98万 - 项目类别:
Grant-in-Aid for Challenging Research (Exploratory)
線形計画問題に対する離散・連続融合アルゴリズムの開発
线性规划问题的离散/连续融合算法的开发
- 批准号:
19K11830 - 财政年份:2019
- 资助金额:
$ 1.98万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
非線形計画問題の大域的最適解を求める研究
非线性规划问题全局最优解的研究
- 批准号:
14780193 - 财政年份:2002
- 资助金额:
$ 1.98万 - 项目类别:
Grant-in-Aid for Young Scientists (B)
組合せ凸関数理論の構築と組合せ最適化問題に対する非線形計画アプローチの研究
组合凸函数理论的构建及组合优化问题的非线性规划方法研究
- 批准号:
13740079 - 财政年份:2001
- 资助金额:
$ 1.98万 - 项目类别:
Grant-in-Aid for Young Scientists (B)
対称錐線形計画に対する内点法に関する研究
对称圆锥线性规划内点法研究
- 批准号:
12740073 - 财政年份:2000
- 资助金额:
$ 1.98万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
組合せ最適化問題に対する半正定値計画緩和と線形計画緩和
组合优化问题的半定规划松弛和线性规划松弛
- 批准号:
12780337 - 财政年份:2000
- 资助金额:
$ 1.98万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
線形計画問題に対する新しい非内点法型逐次反復解法の開発
线性规划问题新的非内点迭代求解方法的发展
- 批准号:
10780272 - 财政年份:1998
- 资助金额:
$ 1.98万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
線形計画法を用いた非線形システムの全解探索アルゴリズム開発とLSI設計への応用
使用线性规划开发非线性系统完整解搜索算法及其在 LSI 设计中的应用
- 批准号:
09750447 - 财政年份:1997
- 资助金额:
$ 1.98万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
線形計画法を援用した新しい区間演算方式に関する研究
一种新的线性规划区间计算方法研究
- 批准号:
09750458 - 财政年份:1997
- 资助金额:
$ 1.98万 - 项目类别:
Grant-in-Aid for Encouragement of Young Scientists (A)
ミニマックス計画法と非線形計画問題の感度分析の研究
非线性规划问题的极小极大规划与敏感性分析研究
- 批准号:
08680456 - 财政年份:1996
- 资助金额:
$ 1.98万 - 项目类别:
Grant-in-Aid for Scientific Research (C)