A GENERAL FRAMEWORK FOR CONVEX RELAXATION OF POLYNOMIAL OPTIMIZATION PROBLEMS OVER CONES

スポンサーリンク

概要

• 論文の詳細を見る

• The class of POPs (Polynomial Optimization Problems) over cones covers a wide range of optimization problems such as 0-1 integer linear and quadratic programs, nonconvex quadratic programs and bilinear matrix inequalities. This paper presents a new framework for convex relaxation of POPs over cones in terms of linear optimization problems over cones. It provides a unified treatment of many existing convex relaxation methods based on the lift-and-project linear programming procedure, the reformulation-linearization technique and the semidefinite programming relaxation for a variety of problems. It also extends the theory of convex relaxation methods, and thereby brings flexibility and richness in practical use of the theory.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• 小島 政和

  東京工業大学情報理工学研究科数理・計算科学専攻

• Kojima Masakazu

  Tokyo Institute of Technology

• Kim Sunyoung

  Ewha Women's University

• Waki Hayato

  Tokyo Institute of Technology

• 脇 隼人

  東京工業大学大学院理工学研究科

関連論文

• EQUALITY BASED CONTRACTION OF SEMIDEFINITE PROGRAMMING RELAXATIONS IN POLYNOMIAL OPTIMIZATION
• An algorithm for decomposition of matrix -algebras generated by symmetric matrices (21世紀の数理計画--最適化モデルとアルゴリズム--RIMS研究集会報告集)
• Solving Sparse Semidefinite Programs by Matrix Completion (Part II) (Mathematical Science of Optimization)
• Solving Sparse Semidefinite Programs by Matrix Completion (Part I) (Mathematical Science of Optimization)
• 拡散過程の生存確率に対する半正定値計画を用いた数値計算手法
• ニュートン法および準ニュートン法の区分的連続微分可能な方程式への拡張
• 不動点アルゴリズムの計算効率の改善
• SDPA project and new features of SDPA 7.1.0 (計算科学の基盤技術としての高速アルゴリズムとその周辺--RIMS研究集会)
• 半正定値計画に対する行列補完型主双対内点法の並列化(錘計画問題と相補正問題)
• 半正定値計画問題を解くソフトウェアのPCクラスタ上における並列実装(最適化(2))
• Successive Convex Relaxation Method applied to Nonlinear Programs
• Approximation of global optimal values of nonconvex programs using Successive Convex Relaxation Method (Continuous and Discrete Mathematics for Optimization)
• 線形計画問題に対する双対内点主シンプレックス法
• 最大カット問題に対するSemidefinite Programming緩和(数理計画(2))
• Semidefinite Programming Relaxation for Nonconvex Quadratic Programs(Discrete and Continuous Structures in Optimization)
• 非凸2次計画問題に対するSemidefinite Programming緩和(数理計画(1))
• 広域分散コンピューティング環境における数理計画ソフトウェアSDPA
• 単調な半正定値線形相補性問題に対する内点法における探索方向の存在に関する一考察(数理計画(3))
• 線形計画問題に対する主双対内点法と、その相補性問題へ拡張 : 1992年度Lanchester賞受賞の対象論文を中心として(Lanchester賞)
• 穏やかな非凸計画問題の凹2次不等式条件1本付き凸計画問題への帰着
• SOLVING LARGE SCALE OPTIMIZATION PROBLEMS VIA GRID AND CLUSTER COMPUTING(Network Design, Control and Optimization)
• 多面体ホモトピー法から生じる条件付き線形不等式系の全解列挙法
• ENUMERATION OF ALL SOLUTIONS OF A COMBINATORIAL LINEAR INEQUALITY SYSTEM ARISING FROM THE POLYHEDRAL HOMOTOPY CONTINUATION METHOD
• 半正定値計画問題での大規模線形方程式系に対する前処理付き共役勾配法 (最適化のための連続と離散数理)
• Moderate Nonconvexity = Convexity + Quadratic Concavity (Continuous and Discrete Mathematics for Optimization)
• Polynomial-Time Convergence of Predictor-Corrector Infeasible-Interior-Point Algorithms for Monotone SDLCP : Generalization and Inexact Approach
• Convergence Analysis of Some Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem
• Centers of Generalized Complementarity Problems
• Decomposition in Interior-Point Methods
• Some Applications of the Convex Property of Monotone Complementarity Problems
• 大きなステップ長を許す内点法 : 線形相補性問題の場合(数理計画)
• アフィン・スケーリング法に対するBigM法の適用(数理計画)
• 疎性を持っている多項式最適化問題に対する半正定値計画緩和(最適化数理の手法と実際)
• 平面上の凸包における最小ノルム点問題(計算幾何)
• A Combinatorial Problem Arising from Polyhedral Homotopies for Solving Polynomial Systems (Mathematical Science of Optimization)
• EFFICIENT EVALUATION OF POLYNOMIALS AND THEIR PARTIAL DERIVATIVES IN HOMOTOPY CONTINUATION METHODS
• Computational Aspects of Bilinear Matrix Inequality Problems
• SPARSE SECOND ORDER CONE PROGRAMMING FORMULATIONS FOR CONVEX OPTIMIZATION PROBLEMS
• Solving polynomial least square problems as polynomial semidefinite programs (数値最適化の理論と実際--RIMS研究集会報告集)
• 理論家にとっての数理モデル(モデリング-広い視野を求めて-)
• 疎な多項式計画問題に対する半正定値計画緩和 (決定理論と最適化アルゴリズム)
• 多項式最適化問題に対する半正定値計画緩和
• 多項式計画に対する線形化緩和とLagrange緩和 (数理最適化から見た「凸性の深み,非凸性の魅惑」)
• A GENERAL FRAMEWORK FOR CONVEX RELAXATION OF POLYNOMIAL OPTIMIZATION PROBLEMS OVER CONES
• 錐上の多項式制約を持つ最適化問題に対する緩和手法 (最適化の数理とアルゴリズム)
• 半正定値計画問題に対するソフトウェアSDPAの広域並列計算システム (最適化の数理科学)
• Workshop on Advances in Optimization(Conference Report)
• 1-A-8 一般2次最適化問題と等価なCompletely Positive Programming : O-1混合線形制約2次最適化問題への理論的応用(連続最適化(2))

もっと見る 閉じる

スポンサーリンク