Search

線形半無限計画問題(LSIP)とは, 有限次元の変数をもつ線形関数を, 無限個の線形不等式で表される制約領域上で最小化する問題であり, フィルタ設計や汚染費用問題など多くの応用が知られている. LSIPに対する解法アルゴリズムとして切除平面法が知られているが, この手法では毎回の反復で生成される部分問題を厳密に解くことが前提となっている. そこで, 本稿ではこの部分問題を非厳密に解くことによって切除平面法を高速化するアプローチを提案し, アルゴリズムの収束解析を行う. 数値実験ではテスト問題に対して提案した高速化アプローチを適用し, 特に高次元の問題に対して, 提案アプローチの方が既存の切除平面法よりも高速に解が得られることを確認する.

It is known that the complementarity problems and the variational inequality problems are reformulated equivalently as a vector equation by using the natural residual or Fischer-Burmeister function. In this short paper, we first study the global convergence of a sequential injective algorithm for weakly univalent vector equation. Then, we apply the convergence analysis to the regularized smoothing Newton algorithm for mixed nonlinear second-order cone complementarity problems. We prove the global convergence property under the (Cartesian) P_{0} assumption, which is strictly weaker than the original monotonicity assumption.