Using Nemirovski's Mirror-Prox method as basic procedure in Chubanov's method for solving homogeneous feasibility problems

We introduce a new variant of Chubanov's method for solving linear homogeneous systems with positive variables. In the Basic Procedure we use a recently introduced cut in combination with Nemirovski's Mirror-Prox method. We show that the cut requires at most time, just as Chubanov's c...

Full description

Saved in:
Bibliographic Details
Published in:Optimization methods & software 2022-07, Vol.37 (4), p.1447-1470
Main Authors: Wei, Zhang, Roos, Kees
Format: Article
Language:English
Subjects:
Algorithms
Chubanov's method
homogeneous
Linear optimization
Mirror-Prox method
Optimization
Rescaling
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c333t-776a3b0e51c3697d8770dbddb9cd3b164fcade95c9f14bb9975b880a58267c6e3
container_end_page 1470
container_issue 4
container_start_page 1447
container_title Optimization methods & software
container_volume 37
creator Wei, Zhang
Roos, Kees
description We introduce a new variant of Chubanov's method for solving linear homogeneous systems with positive variables. In the Basic Procedure we use a recently introduced cut in combination with Nemirovski's Mirror-Prox method. We show that the cut requires at most time, just as Chubanov's cut. In an earlier paper it was shown that the new cuts are at least as sharp as those of Chubanov. Our Modified Main Algorithm is in essence the same as Chubanov's Main Algorithm, except that it uses the new Basic Procedure as a subroutine. The new method has time complexity, where is a suitably defined condition number. As we show, a simplified version of the new Basic Procedure competes well with the Smooth Perceptron Scheme of Peña and Soheili and, when combined with Rescaling, also with two commercial codes for linear optimization.
doi_str_mv 10.1080/10556788.2021.2023523
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2754996534</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2754996534</sourcerecordid><originalsourceid>FETCH-LOGICAL-c333t-776a3b0e51c3697d8770dbddb9cd3b164fcade95c9f14bb9975b880a58267c6e3</originalsourceid><addsrcrecordid>eNp9kEtPwzAQhC0EElD4CUiWOHBKsePYjm-gipdUHgd6tvxKa0hisJNC-fUkarly2d3DNzPaAeAMoylGJbrEiFLGy3KaoxyPg9Cc7IEjjHKRFYLw_fGmNBuhQ3Cc0htCqMAFOwI_i-TbJXxyjY9hnd79RYKPPsYQs5cYvmHjulWwUCWoVfIGfsRgnO2jg76Fs1WvVRvWg2bHVSHCFOr16LkKTVi61oU-wcoNau1r321GC127Jp2Ag0rVyZ3u9gQsbm9eZ_fZ_PnuYXY9zwwhpMs4Z4po5Cg2hAluS86R1dZqYSzRmBWVUdYJakSFC62F4FSXJVK0zBk3zJEJON_6DsGfvUudfAt9bIdImXNaCMEoKQaKbikTQ0rRVfIj-kbFjcRIjjXLv5rlWLPc1TzorrY63w7PN-orxNrKTm3qEKuoWuOTJP9b_AJzu4Z4</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2754996534</pqid></control><display><type>article</type><title>Using Nemirovski's Mirror-Prox method as basic procedure in Chubanov's method for solving homogeneous feasibility problems</title><source>Taylor and Francis Science and Technology Collection</source><creator>Wei, Zhang ; Roos, Kees</creator><creatorcontrib>Wei, Zhang ; Roos, Kees</creatorcontrib><description>We introduce a new variant of Chubanov's method for solving linear homogeneous systems with positive variables. In the Basic Procedure we use a recently introduced cut in combination with Nemirovski's Mirror-Prox method. We show that the cut requires at most time, just as Chubanov's cut. In an earlier paper it was shown that the new cuts are at least as sharp as those of Chubanov. Our Modified Main Algorithm is in essence the same as Chubanov's Main Algorithm, except that it uses the new Basic Procedure as a subroutine. The new method has time complexity, where is a suitably defined condition number. As we show, a simplified version of the new Basic Procedure competes well with the Smooth Perceptron Scheme of Peña and Soheili and, when combined with Rescaling, also with two commercial codes for linear optimization.</description><identifier>ISSN: 1055-6788</identifier><identifier>EISSN: 1029-4937</identifier><identifier>DOI: 10.1080/10556788.2021.2023523</identifier><language>eng</language><publisher>Abingdon: Taylor &amp; Francis</publisher><subject>Algorithms ; Chubanov's method ; homogeneous ; Linear optimization ; Mirror-Prox method ; Optimization ; Rescaling</subject><ispartof>Optimization methods &amp; software, 2022-07, Vol.37 (4), p.1447-1470</ispartof><rights>2022 The Author(s). Published by Informa UK Limited, trading as Taylor &amp; Francis Group. 2022</rights><rights>2022 The Author(s). Published by Informa UK Limited, trading as Taylor &amp; Francis Group. This work is licensed under the Creative Commons Attribution License http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c333t-776a3b0e51c3697d8770dbddb9cd3b164fcade95c9f14bb9975b880a58267c6e3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Wei, Zhang</creatorcontrib><creatorcontrib>Roos, Kees</creatorcontrib><title>Using Nemirovski's Mirror-Prox method as basic procedure in Chubanov's method for solving homogeneous feasibility problems</title><title>Optimization methods &amp; software</title><description>We introduce a new variant of Chubanov's method for solving linear homogeneous systems with positive variables. In the Basic Procedure we use a recently introduced cut in combination with Nemirovski's Mirror-Prox method. We show that the cut requires at most time, just as Chubanov's cut. In an earlier paper it was shown that the new cuts are at least as sharp as those of Chubanov. Our Modified Main Algorithm is in essence the same as Chubanov's Main Algorithm, except that it uses the new Basic Procedure as a subroutine. The new method has time complexity, where is a suitably defined condition number. As we show, a simplified version of the new Basic Procedure competes well with the Smooth Perceptron Scheme of Peña and Soheili and, when combined with Rescaling, also with two commercial codes for linear optimization.</description><subject>Algorithms</subject><subject>Chubanov's method</subject><subject>homogeneous</subject><subject>Linear optimization</subject><subject>Mirror-Prox method</subject><subject>Optimization</subject><subject>Rescaling</subject><issn>1055-6788</issn><issn>1029-4937</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2022</creationdate><recordtype>article</recordtype><sourceid>0YH</sourceid><recordid>eNp9kEtPwzAQhC0EElD4CUiWOHBKsePYjm-gipdUHgd6tvxKa0hisJNC-fUkarly2d3DNzPaAeAMoylGJbrEiFLGy3KaoxyPg9Cc7IEjjHKRFYLw_fGmNBuhQ3Cc0htCqMAFOwI_i-TbJXxyjY9hnd79RYKPPsYQs5cYvmHjulWwUCWoVfIGfsRgnO2jg76Fs1WvVRvWg2bHVSHCFOr16LkKTVi61oU-wcoNau1r321GC127Jp2Ag0rVyZ3u9gQsbm9eZ_fZ_PnuYXY9zwwhpMs4Z4po5Cg2hAluS86R1dZqYSzRmBWVUdYJakSFC62F4FSXJVK0zBk3zJEJON_6DsGfvUudfAt9bIdImXNaCMEoKQaKbikTQ0rRVfIj-kbFjcRIjjXLv5rlWLPc1TzorrY63w7PN-orxNrKTm3qEKuoWuOTJP9b_AJzu4Z4</recordid><startdate>20220704</startdate><enddate>20220704</enddate><creator>Wei, Zhang</creator><creator>Roos, Kees</creator><general>Taylor &amp; Francis</general><general>Taylor &amp; Francis Ltd</general><scope>0YH</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20220704</creationdate><title>Using Nemirovski's Mirror-Prox method as basic procedure in Chubanov's method for solving homogeneous feasibility problems</title><author>Wei, Zhang ; Roos, Kees</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c333t-776a3b0e51c3697d8770dbddb9cd3b164fcade95c9f14bb9975b880a58267c6e3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2022</creationdate><topic>Algorithms</topic><topic>Chubanov's method</topic><topic>homogeneous</topic><topic>Linear optimization</topic><topic>Mirror-Prox method</topic><topic>Optimization</topic><topic>Rescaling</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Wei, Zhang</creatorcontrib><creatorcontrib>Roos, Kees</creatorcontrib><collection>Taylor &amp; Francis Open Access(OpenAccess)</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Optimization methods &amp; software</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Wei, Zhang</au><au>Roos, Kees</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Using Nemirovski's Mirror-Prox method as basic procedure in Chubanov's method for solving homogeneous feasibility problems</atitle><jtitle>Optimization methods &amp; software</jtitle><date>2022-07-04</date><risdate>2022</risdate><volume>37</volume><issue>4</issue><spage>1447</spage><epage>1470</epage><pages>1447-1470</pages><issn>1055-6788</issn><eissn>1029-4937</eissn><abstract>We introduce a new variant of Chubanov's method for solving linear homogeneous systems with positive variables. In the Basic Procedure we use a recently introduced cut in combination with Nemirovski's Mirror-Prox method. We show that the cut requires at most time, just as Chubanov's cut. In an earlier paper it was shown that the new cuts are at least as sharp as those of Chubanov. Our Modified Main Algorithm is in essence the same as Chubanov's Main Algorithm, except that it uses the new Basic Procedure as a subroutine. The new method has time complexity, where is a suitably defined condition number. As we show, a simplified version of the new Basic Procedure competes well with the Smooth Perceptron Scheme of Peña and Soheili and, when combined with Rescaling, also with two commercial codes for linear optimization.</abstract><cop>Abingdon</cop><pub>Taylor &amp; Francis</pub><doi>10.1080/10556788.2021.2023523</doi><tpages>24</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1055-6788
ispartof Optimization methods & software, 2022-07, Vol.37 (4), p.1447-1470
issn 1055-6788
1029-4937
language eng
recordid cdi_proquest_journals_2754996534
source Taylor and Francis Science and Technology Collection
subjects Algorithms
Chubanov's method
homogeneous
Linear optimization
Mirror-Prox method
Optimization
Rescaling
title Using Nemirovski's Mirror-Prox method as basic procedure in Chubanov's method for solving homogeneous feasibility problems
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-27T07%3A09%3A01IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Using%20Nemirovski's%20Mirror-Prox%20method%20as%20basic%20procedure%20in%20Chubanov's%20method%20for%20solving%20homogeneous%20feasibility%20problems&rft.jtitle=Optimization%20methods%20&%20software&rft.au=Wei,%20Zhang&rft.date=2022-07-04&rft.volume=37&rft.issue=4&rft.spage=1447&rft.epage=1470&rft.pages=1447-1470&rft.issn=1055-6788&rft.eissn=1029-4937&rft_id=info:doi/10.1080/10556788.2021.2023523&rft_dat=%3Cproquest_cross%3E2754996534%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c333t-776a3b0e51c3697d8770dbddb9cd3b164fcade95c9f14bb9975b880a58267c6e3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2754996534&rft_id=info:pmid/&rfr_iscdi=true