WEKO3
アイテム
{"_buckets": {"deposit": "39099a0e-d202-429b-ae50-53cc2d0ed433"}, "_deposit": {"created_by": 13, "id": "10334", "owners": [13], "pid": {"revision_id": 0, "type": "depid", "value": "10334"}, "status": "published"}, "_oai": {"id": "oai:uec.repo.nii.ac.jp:00010334", "sets": ["6"]}, "author_link": ["27434", "27435", "27436", "27437"], "item_10001_biblio_info_7": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2022-11-07", "bibliographicIssueDateType": "Issued"}, "bibliographic_titles": [{}, {"bibliographic_title": "Mathematical Programming", "bibliographic_titleLang": "en"}]}]}, "item_10001_description_5": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "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 ηI_p and εI_d, respectively, to recover interior feasibility of both problems, where ε and η 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 η and ε 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 θ, if we parametrize (ε,η) as (ε,η)=t(cosθ,sinθ) and let t→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.", "subitem_description_type": "Abstract"}]}, "item_10001_publisher_8": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "Springer"}]}, "item_10001_relation_14": {"attribute_name": "DOI", "attribute_value_mlt": [{"subitem_relation_type": "isIdenticalTo", "subitem_relation_type_id": {"subitem_relation_type_id_text": "10.1007/s10107-022-01891-8", "subitem_relation_type_select": "DOI"}}]}, "item_10001_relation_17": {"attribute_name": "関連サイト", "attribute_value_mlt": [{"subitem_relation_type_id": {"subitem_relation_type_id_text": "https://doi.org/10.1007/s10107-022-01891-8", "subitem_relation_type_select": "DOI"}}]}, "item_10001_rights_15": {"attribute_name": "権利", "attribute_value_mlt": [{"subitem_rights": "© The Author(s) 2022. The version of record of this article, first published in Mathematical Programming, is available online at Publisher’s website: http://dx.doi.org/10.1007/s10107-022-01891-8"}]}, "item_10001_source_id_9": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "00255610", "subitem_source_identifier_type": "ISSN"}]}, "item_10001_version_type_20": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_version_resource": "http://purl.org/coar/version/c_970fb48d4fbd8a85", "subitem_version_type": "VoR"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Tsuchiya, Takashi", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "27434", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Lourenço, Bruno F.", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "27435", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Muramatsu, Masakazu", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "27436", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Okuno, Takayuki", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "27437", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2023-03-16"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "s10107-022-01891-8.pdf", "filesize": [{"value": "532.5 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensefree": "CC BY 4.0", "licensetype": "license_free", "mimetype": "application/pdf", "size": 532500.0, "url": {"label": "s10107-022-01891-8.pdf", "url": "https://uec.repo.nii.ac.jp/record/10334/files/s10107-022-01891-8.pdf"}, "version_id": "9d6da188-2afb-4c98-9488-fe3778de1995"}]}, "item_keyword": {"attribute_name": "キーワード", "attribute_value_mlt": [{"subitem_subject": "Semidefinite programs", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Singular problems", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Nonzero duality gaps", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Perturbation", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Regularization", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Infeasible interior-point algorithms", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "journal article", "resourceuri": "http://purl.org/coar/resource_type/c_6501"}]}, "item_title": "A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms", "subitem_title_language": "en"}]}, "item_type_id": "10001", "owner": "13", "path": ["6"], "permalink_uri": "https://uec.repo.nii.ac.jp/records/10334", "pubdate": {"attribute_name": "公開日", "attribute_value": "2023-03-16"}, "publish_date": "2023-03-16", "publish_status": "0", "recid": "10334", "relation": {}, "relation_version_is_last": true, "title": ["A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms"], "weko_shared_id": -1}
A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms
https://uec.repo.nii.ac.jp/records/10334
https://uec.repo.nii.ac.jp/records/103346e13e7e8-1f1a-4279-8650-a4f1d0b92954
名前 / ファイル | ライセンス | アクション |
---|---|---|
s10107-022-01891-8.pdf (532.5 kB)
|
CC BY 4.0
|
Item type | 学術雑誌論文 / Journal Article(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2023-03-16 | |||||
タイトル | ||||||
言語 | en | |||||
タイトル | A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms | |||||
言語 | ||||||
言語 | eng | |||||
キーワード | ||||||
言語 | en | |||||
主題 | Semidefinite programs | |||||
キーワード | ||||||
言語 | en | |||||
主題 | Singular problems | |||||
キーワード | ||||||
言語 | en | |||||
主題 | Nonzero duality gaps | |||||
キーワード | ||||||
言語 | en | |||||
主題 | Perturbation | |||||
キーワード | ||||||
言語 | en | |||||
主題 | Regularization | |||||
キーワード | ||||||
言語 | en | |||||
主題 | Infeasible interior-point algorithms | |||||
資源タイプ | ||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
資源タイプ | journal article | |||||
著者 |
Tsuchiya, Takashi
× Tsuchiya, Takashi× Lourenço, Bruno F.× Muramatsu, Masakazu× Okuno, Takayuki |
|||||
抄録 | ||||||
内容記述タイプ | 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 ηI_p and εI_d, respectively, to recover interior feasibility of both problems, where ε and η 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 η and ε 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 θ, if we parametrize (ε,η) as (ε,η)=t(cosθ,sinθ) and let t→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. | |||||
書誌情報 |
en : Mathematical Programming 発行日 2022-11-07 |
|||||
出版者 | ||||||
出版者 | Springer | |||||
ISSN | ||||||
収録物識別子タイプ | ISSN | |||||
収録物識別子 | 00255610 | |||||
DOI | ||||||
関連タイプ | isIdenticalTo | |||||
識別子タイプ | DOI | |||||
関連識別子 | 10.1007/s10107-022-01891-8 | |||||
権利 | ||||||
権利情報 | © The Author(s) 2022. The version of record of this article, first published in Mathematical Programming, is available online at Publisher’s website: http://dx.doi.org/10.1007/s10107-022-01891-8 | |||||
関連サイト | ||||||
識別子タイプ | DOI | |||||
関連識別子 | https://doi.org/10.1007/s10107-022-01891-8 | |||||
著者版フラグ | ||||||
出版タイプ | VoR | |||||
出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 |