{"id":16540,"date":"2023-01-04T09:12:17","date_gmt":"2023-01-04T01:12:17","guid":{"rendered":"https:\/\/iora.nus.edu.sg\/?post_type=paper-p&#038;p=16540"},"modified":"2023-01-04T09:43:14","modified_gmt":"2023-01-04T01:43:14","slug":"an-inexact-projected-gradient-method-with-rounding-and-lifting-by-nonlinear-programming-for-solving-rank-one-semidefinite-relaxation-of-polynomial-optimization","status":"publish","type":"paper-p","link":"https:\/\/iora.nus.edu.sg\/paper-p\/an-inexact-projected-gradient-method-with-rounding-and-lifting-by-nonlinear-programming-for-solving-rank-one-semidefinite-relaxation-of-polynomial-optimization\/","title":{"rendered":"An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization"},"content":{"rendered":"<p>We consider solving high-order and tight semidefinite programming (SDP) relaxations of nonconvex polynomial optimization problems (POPs) that often admit degenerate rank-one optimal solutions. Instead of solving the SDP alone, we propose a new algorithmic framework that blends local search using the nonconvex POP into global descent using the convex SDP. In particular, we first design a globally convergent inexact projected gradient method (iPGM) for solving the SDP that serves as the backbone of our framework. We then accelerate iPGM by taking long, but safeguarded, rank-one steps generated by fast nonlinear programming algorithms. We prove that the new framework is still globally convergent for solving the SDP. To solve the iPGM subproblem of projecting a given point onto the feasible set of the SDP, we design a two-phase algorithm with phase one using a symmetric Gauss\u2013Seidel based accelerated proximal gradient method (sGS-APG) to generate a good initial point, and phase two using a modified limited-memory BFGS (L-BFGS) method to obtain an accurate solution. We analyze the convergence for both phases and establish a novel global convergence result for the modified L-BFGS that does not require the objective function to be twice continuously differentiable. We conduct numerical experiments for solving second-order SDP relaxations arising from a diverse set of POPs. Our framework demonstrates state-of-the-art efficiency, scalability, and robustness in solving degenerate SDPs to high accuracy, even in the presence of millions of equality constraints.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We consider solving high-order and tight semidefinite programming (SDP) relaxations of nonconvex polynomial optimization problems (POPs) that often admit degenerate rank-one optimal solutions. Instead of solving the SDP alone, we [&hellip;]<\/p>\n","protected":false},"featured_media":16541,"template":"","meta":{"_acf_changed":false,"_price":"","_stock":"","_tribe_ticket_header":"","_tribe_default_ticket_provider":"","_tribe_ticket_capacity":"0","_ticket_start_date":"","_ticket_end_date":"","_tribe_ticket_show_description":"","_tribe_ticket_show_not_going":false,"_tribe_ticket_use_global_stock":"","_tribe_ticket_global_stock_level":"","_global_stock_mode":"","_global_stock_cap":"","_tribe_rsvp_for_event":"","_tribe_ticket_going_count":"","_tribe_ticket_not_going_count":"","_tribe_tickets_list":"[]","_tribe_ticket_has_attendee_info_fields":false},"tags":[],"publication":[78,77,50],"keyword":[],"class_list":["post-16540","paper-p","type-paper-p","status-publish","has-post-thumbnail","hentry","publication-moe-t3","publication-papers","publication-publications-by-iora"],"acf":[],"_links":{"self":[{"href":"https:\/\/iora.nus.edu.sg\/wp-json\/wp\/v2\/paper-p\/16540","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/iora.nus.edu.sg\/wp-json\/wp\/v2\/paper-p"}],"about":[{"href":"https:\/\/iora.nus.edu.sg\/wp-json\/wp\/v2\/types\/paper-p"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/iora.nus.edu.sg\/wp-json\/wp\/v2\/media\/16541"}],"wp:attachment":[{"href":"https:\/\/iora.nus.edu.sg\/wp-json\/wp\/v2\/media?parent=16540"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/iora.nus.edu.sg\/wp-json\/wp\/v2\/tags?post=16540"},{"taxonomy":"publication","embeddable":true,"href":"https:\/\/iora.nus.edu.sg\/wp-json\/wp\/v2\/publication?post=16540"},{"taxonomy":"keyword","embeddable":true,"href":"https:\/\/iora.nus.edu.sg\/wp-json\/wp\/v2\/keyword?post=16540"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}