{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:43:49Z","timestamp":1787341429589,"version":"build-2736575974"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["(B)24310112"],"award-info":[{"award-number":["(B)24310112"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["(C)26330025"],"award-info":[{"award-number":["(C)26330025"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["(B)26280005"],"award-info":[{"award-number":["(B)26280005"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["(B)15H02968"],"award-info":[{"award-number":["(B)15H02968"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We present FRA-Poly, a facial reduction algorithm (FRA) for conic linear programs that is sensitive to the presence of polyhedral faces in the cone. The main goals of FRA and FRA-Poly are the same, i.e., finding the minimal face containing the feasible region and detecting infeasibility, but FRA-Poly treats polyhedral constraints separately. This reduces the number of iterations drastically when there are many linear inequality constraints. The worst-case number of iterations for FRA-Poly is written in terms of a \u201cdistance to polyhedrality\u201d quantity and provides better bounds than FRA under mild conditions. In particular, in the case of the doubly nonnegative cone, FRA-Poly gives a worst-case bound of $n$ whereas the classical FRA bound is $\\mathcal{O}(n^2)$. Of possible independent interest, we prove a variant of the Gordan--Stiemke theorem and a proper separation theorem which takes into account partial polyhedrality. We provide a discussion on the optimal facial reduction strategy and an instance that forces FRAs to perform many steps. We also present a few applications. In particular, we will use FRA-Poly to improve the bounds recently obtained by Liu and Pataki on the dimension of certain affine subspaces which appear in weakly infeasible problems.<\/jats:p>","DOI":"10.1137\/15m1051634","type":"journal-article","created":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T12:24:10Z","timestamp":1534854250000},"page":"2304-2326","source":"Crossref","is-referenced-by-count":14,"title":["Facial Reduction and Partial Polyhedrality"],"prefix":"10.1137","volume":"28","author":[{"given":"Bruno F.","family":"Louren\u00e7o","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Masakazu","family":"Muramatsu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Takashi","family":"Tsuchiya","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,21]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591803"},{"key":"atypb2","unstructured":"N. Arima, S. Kim, M. Kojima, and K.C. Toh,\n                      Lagrangian-Conic Relaxations, Part I: A Unified Framework and Its Applications to Quadratic Optimization Problems\n                      , Technical report B-475, Tokyo Institute of Technology, Tokyo, 2014."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700017250"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(81)90138-4"},{"key":"atypb5","first-page":"251","author":"Cheung Y.-L.","year":"2013","journal-title":"New York"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(97)00011-4"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/140968318"},{"key":"atypb8","unstructured":"R. M. Freund, R. Roundy, and M. Todd,\n                      Identifying the Set of Always-Active Constraints in a System of Linear Inequalities by a Single Linear Program\n                      , Working paper 1674-85, Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA, 1985; available athttps:\/\/EconPapers.repec.org\/RePEc:mit:sloanp:2111."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2016.08.004"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2017.06.043"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0874-5"},{"key":"atypb12","first-page":"10","volume":"167","author":"Liu M.","year":"2017","journal-title":"Math. Program."},{"key":"atypb13","unstructured":"B. F. Lourenc\u0327o, M. Muramatsu, and T. Tsuchiya,\n                      Solving SDP Completely with an Interior Point Oracle\n                      , preprint,https:\/\/arxiv.org\/abs\/1507.08065, 2015."},{"key":"atypb14","first-page":"241","volume":"59","author":"Lourenc\u0327o B. F.","year":"2016","journal-title":"J. Oper. Res. Soc. Japan"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-015-0982-4"},{"key":"atypb16","unstructured":"Z. Luo and J. F. Sturm,\n                      Error analysis\n                      , in Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds., Kluwer Academic Publishers, Norwell, MA, 2000."},{"key":"atypb17","unstructured":"Z. Luo, J. F. Sturm, and S. Zhang,\n                      Duality Results for Conic Convex Programming\n                      , Technical report, Econometric Institute, Erasmus University, Rotterdam, 1997."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585102"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585180"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s10107980009a"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"G. Pataki,\n                      The geometry of semidefinite programming\n                      , in Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds., Kluwer Academic Publishers, Norwell, MA, 2000; also available online fromhttps:\/\/www.unc.edu\/~pataki\/papers\/chapter.pdf.","DOI":"10.1007\/978-1-4615-4381-7_3"},{"key":"atypb22","first-page":"613","author":"Pataki G.","year":"2013","journal-title":"New York"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/15M1049415"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"F. Permenter and P. Parrilo,\n                      Partial facial reduction: Simplified, equivalent SDPs via approximations of the PSD cone\n                      , Math. Program. (2017),https:\/\/doi.org\/10.1007\/s10107-017-1169-9.","DOI":"10.1007\/s10107-017-1169-9"},{"key":"atypb25","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton University Press, Princeton, NJ, 1997."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623498338606"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"L. Tunc\u0327el,\n                      Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization\n                      , Fields Institute Monogr. 27, American Mathematical Society, Providence, RI, 2010.","DOI":"10.1090\/fim\/027"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-012-9480-0"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-012-0219-y"},{"key":"atypb30","first-page":"13","author":"Yoshise A.","year":"2010","journal-title":"NJ"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1051634","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:19:11Z","timestamp":1787339951000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1051634"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/15M1051634"],"URL":"https:\/\/doi.org\/10.1137\/15m1051634","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}