半正定値計画法を使った大域的最適化問題に対する新解法の研究

半定规划全局优化问题新求解方法研究

基本信息

  • 批准号:
    11750055
  • 负责人:
  • 金额:
    $ 1.6万
  • 依托单位:
  • 依托单位国家:
    日本
  • 项目类别:
    Grant-in-Aid for Encouragement of Young Scientists (A)
  • 财政年份:
    1999
  • 资助国家:
    日本
  • 起止时间:
    1999 至 2000
  • 项目状态:
    已结题

项目摘要

本研究は,大規模な非凸2次計画問題に対する大域的最適化アルゴリズムの構築を目標とした.この際,半正定値計画問題を解くことで,最適解の近似が行えるという性質を用いた.また,本研究では,半正定値計画問題に,ある種の不等式(切除平面)群を追加し最適化を行うこと,すなわち切除平面法を応用することで,より計算効率の高いアルゴリズムの構築を目指した.そのために,半正定値計画問題を緩和問題として使い,線型制約上で非凸2次関数を最小化するアルゴリズムを,計算機上に実装した.計算効率の向上に寄与する度合いの大きな不等式の生成,選択,追加等に関する戦略の検討を数値実験を通じて行った.その結果,低ランク(ランク2あるいはランク3)不等式(切除平面)を提案した.問題の目的関数が粗な行列の場合や,非常に凸性や凹性の強い場合では,ランク1の不等式を使うだけで,十分によい解を短時間に生成できることが確認できた.たま,一方で,行列が密で,正の固有値数と負の固有値数がほぼ同数といった問題に対しては,ランク1の不等式だけでは不十分であり,一般的な低ランク不等式を追加することで,解が改善されることを確認した.また,粗な問題に対しても,ここで提案した低ランク不等式使った場合の方が,より少ない本数の不等式で制度のよい解を算出できることを示した.さらに,その現実問題への応用性を確かめるために,ディスタンスジオメトリー問題と呼ばれる,空間に点を配置する問題へ,本手法の適用を行った.この問題は,適当な変形を施せば,凹2次計画問題へと定式化が可能であり,その近似的な最適解を半正定値計画問題を解くことで得ることが可能である.数値的な実験の結果,従来の近似手法と比べ,はるかに精度の良い解を算出できることが確認された.
The purpose of this study is to construct a large domain optimization system for large scale nonconvex quadratic programming problems. In this case, the semi-definite program problem is solved, and the approximation of the optimal solution is used. In this paper, we study the problem of semi-positive definite planning, the inequality of species (cutting plane), the optimization of the group, the cutting plane method, the construction of the high calculation rate. The problem of semi-definite planning is solved by minimizing the non-convex second-order relations on linear constraints. The calculation of the rate of upward transmission and the degree of convergence of large inequalities in the generation, selection, addition, etc. As a result, the inequality (cutting plane) is proposed. The objective of the problem is to determine whether the problem is very convex or concave, and whether the problem is very convex or concave. For example, if the number of positive eigenvalues is equal to the number of negative eigenvalues, the inequality of 1 is equal to the number of negative eigenvalues, and the inequality of 1 is equal to the number of negative eigenvalues, the inequality of 1 is equal to the number of negative eigenvalues. The solution of the inequality of this number is calculated. For example, if you want to use this method, you can use it. The optimal solution of the problem is a semi-definite plan problem. The result of numerical value calculation, approximation method and comparison, accuracy calculation and confirmation.

项目成果

期刊论文数量(6)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Yajima Y.Konno H: "An Algorithm for a Concave Cost Network Flow problem"JJIAM. 16. 243-256 (1999)
Yajima Y.Konno H:“凹成本网络流问题的算法”JJIAM。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
矢島安敏: "非凸2次計画問題と組合せ最適化"オペレーションズ・リサーチ. 445. 237-246 (1999)
Yasutoshi Yajima:“非凸二次规划问题和组合优化”运筹学 445. 237-246 (1999)。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
Yajima.Y: "Obtaining an Approximate Solutions for Quadratic Maximazation Problem"Approximation and Complexity in Numerical Optimization. 561-577 (2000)
Yajima.Y:“获得二次最大化问题的近似解”数值优化中的近似和复杂性。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
Yajima.Y: "Positive Semidefinte Relaxation for Distance Geamatry Problems"Advances in Corvee Analysical Global Optimization. 29-90 (2000)
Yajima.Y:“距离几何问题的正半定松弛”在 Corvee 分析全局优化方面取得了进展。
  • 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 }}

矢島 安敏其他文献

グラフラプラシアンを用いたCDの特徴抽出とその利用
图拉普拉斯CD特征提取及其应用

矢島 安敏的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('矢島 安敏', 18)}}的其他基金

グラフ構造を用いた大規模な分類手法の構築とその実システムへの応用
利用图结构构建大规模分类方法及其在实际系统中的应用
  • 批准号:
    19510141
  • 财政年份:
    2007
  • 资助金额:
    $ 1.6万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
組合せ構造を持った非凸型関数最適化問題とその社会システムへの応用
组合结构非凸函数优化问题及其在社会系统中的应用
  • 批准号:
    06780363
  • 财政年份:
    1994
  • 资助金额:
    $ 1.6万
  • 项目类别:
    Grant-in-Aid for Encouragement of Young Scientists (A)
非凸型最適化問題に対する解法の研究と開発
非凸优化问题求解方法的研究与发展
  • 批准号:
    03730013
  • 财政年份:
    1991
  • 资助金额:
    $ 1.6万
  • 项目类别:
    Grant-in-Aid for Encouragement of Young Scientists (A)
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了