研究業績リスト
ジャーナル論文 - rm_published_papers: Scientific Journal
Closing duality gaps of SDPs completely through perturbation when singularity degree is one
公開済 02/09/2024
Optimization Methods and Software, 39, 5, 1040 - 1067
その他
Tackling Mixed Integer Semidefinite Programming Problems
作成日時 01/04/2024–31/03/2027
Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3600000, indirect: 1080000)
ジャーナル論文 - rm_published_papers: Scientific Journal
公開済 01/12/2023
IEICE Transactions on Information and Systems, E106.D, 12, 2078 - 2084
会議発表プレゼンテーション
公開済 07/03/2023
日本OR学会2023年度春季研究発表会
会議発表プレゼンテーション
A Variant of Knapsack Problem Efficient for Benders Decomposition
公開済 12/2022
13th International Congress on Advanced Applied Informatics Winter
ジャーナル論文 - rm_published_papers: Scientific Journal
公開済 11/2022
Mathematical Programming, 200, 1, 531 - 568
Abstract
We consider primal-dual pairs of semidefinite programs and assume that they are singular, i.e., both primal and dual are either weakly feasible or weakly infeasible. Under such circumstances, strong duality may break down and the primal and dual might have a nonzero duality gap. Nevertheless, there are arbitrary small perturbations to the problem data which would make them strongly feasible thus zeroing the duality gap. In this paper, we conduct an asymptotic analysis of the optimal value as the perturbation for regularization is driven to zero. Specifically, we fix two positive definite matrices, $$I_p$$ and $$I_d$$, say, (typically the identity matrices), and regularize the primal and dual problems by shifting their associated affine space by $$\eta I_p$$ and $$\varepsilon I_d$$, respectively, to recover interior feasibility of both problems, where $$\varepsilon $$ and $$\eta $$ are positive numbers. Then we analyze the behavior of the optimal value of the regularized problem when the perturbation is reduced to zero keeping the ratio between $$\eta $$ and $$\varepsilon $$ constant. A key feature of our analysis is that no further assumptions such as compactness or constraint qualifications are ever made. It will be shown that the optimal value of the perturbed problem converges to a value between the primal and dual optimal values of the original problems. Furthermore, the limiting optimal value changes “monotonically” from the primal optimal value to the dual optimal value as a function of $$\theta $$, if we parametrize $$(\varepsilon , \eta )$$ as $$(\varepsilon , \eta )=t(\cos \theta , \sin \theta )$$ and let $$t\rightarrow 0$$. Finally, the analysis leads us to the relatively surprising consequence that some representative infeasible interior-point algorithms for SDP generate sequences converging to a number between the primal and dual optimal values, even in the presence of a nonzero duality gap. Though this result is more of theoretical interest at this point, it might be of some value in the development of infeasible interior-point algorithms that can handle singular problems.
その他
無限次元統計モデルに基づくベイズ予測理論の構築とデータ解析手法の開発
作成日時 01/04/2022–31/03/2027
Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業, Category: 基盤研究(A), Fund Type: -, Overall Grant Amount: - (direct: 32200000, indirect: 9660000)
会議発表プレゼンテーション
公開済 18/03/2022
日本OR学会2022年度春季研究発表会
会議発表プレゼンテーション
公開済 17/03/2022
日本OR学会2022年春季研究発表会
会議発表プレゼンテーション
公開済 17/03/2022
日本OR学会 2022年春季研究発表会