研究業績リスト
ジャーナル論文 - 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
ジャーナル論文 - rm_published_papers: Scientific Journal
公開済 01/12/2023
IEICE Transactions on Information and Systems, E106.D, 12, 2078 - 2084
ジャーナル論文 - 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.
ジャーナル論文 - rm_published_papers: Scientific Journal
Solving SDP completely with an inerior point oracle
公開済 2021
Optimization Methods and Software, 36, 2-3, 425 - 471
We suppose the existence of an oracle which solves any semidefinite programming (SDP) problem satisfying strong feasibility (i.e. Slater's condition) simultaneously at its primal and dual sides. We note that such an oracle might not be able to directly solve general SDPs even after certain regularization schemes are applied. In this work we fill this gap and show how to use such an oracle to ‘completely solve’ an arbitrary SDP. Completely solving entails, for example, distinguishing between weak/strong feasibility/infeasibility and detecting when the optimal value is attained or not. We will employ several tools, including a variant of facial reduction where all auxiliary problems are ensured to satisfy strong feasibility at all sides. Our main technical innovation, however, is an analysis of double facial reduction, which is the process of applying facial reduction twice: first to the original problem and then once more to the dual of the regularized problem obtained during the first run. Although our discussion is focused on semidefinite programming, the majority of the results are proved for general convex cones.
ジャーナル論文 - rm_published_papers: Scientific Journal
公開済 2020
IEEE Transactions on Vehicular Technology, 69, 12, 16168 - 16172
ジャーナル論文 - rm_published_papers: Scientific Journal
Approach to Problem of Minimizing Network Power Consumption Based on Robust Optimization
公開済 01/2019
International Journal of Communication Systems, online available
ジャーナル論文 - rm_published_papers: International Conference Proceedings
公開済 05/2018
IEEE Communications Quality and Reliability Workshop
ジャーナル論文 - rm_published_papers: Scientific Journal
Network congestion minimization models based on robust optimization
公開済 01/03/2018
IEICE Transactions on Communications, E101B, 3, 772 - 784
ジャーナル論文 - rm_published_papers: Scientific Journal
Facial reduction and partial polyhedrality
公開済 2018
SIAM Journal on Optimization, 28, 3, 2304 - 2326
ジャーナル論文 - rm_published_papers: International Conference Proceedings
公開済 2018
SAE Technical Papers, 2018-, 0399, 1 - 5