Session: Conic and Semidefinite Programming (SDP)
Chair: Takashi Tsuchiya
Cluster: nan
Talk 1: Computational complexity of sum-of-squares bounds for copositive programs
Speaker: Marilena Palomba
Abstract: In recent years, copositive programming has received significant attention for its ability to model hard problems in both discrete and continuous optimization. Several relaxations of copositive programs based on semidefinite programming (SDP) have been proposed in the literature, meant to provide tractable bounds. However, while these SDP-based relaxations are amenable to the ellipsoid algorithm and interior point methods, it is not immediately obvious that they can be solved in polynomial time (even approximately). In this paper, we consider the sum-of-squares (SOS) hierarchies of relaxations for copositive programs introduced by Parrilo (2000), de Klerk & Pasechnik(2002) and Peña, Vera & Zuluaga (2006), which can be formulated as SDPs. We establish sufficient conditions that guarantee the polynomial-time computability (up to fixed precision) of these relaxations. These conditions are satisfied by copositive programs that represent standard quadratic programs and their reciprocals. As an application, we show that the SOS bounds for the (weighted) stability number of a graph can be computed efficiently. Additionally, we provide pathological examples of copositive programs (that do not satisfy the sufficient conditions) whose SOS relaxations admit only feasible solutions of doubly-exponential size. This work was conducted in collaboration with Lucas Slot (ETH Zurich, lucas.slot@inf.ethz.ch), Luis Felipe Vargas (SUPSI, IDSIA, luis.vargas@supsi.ch) and Monaldo Mastrolilli (SUPSI, IDSIA, monaldo.mastrolilli@supsi.ch) Full article available here: https://doi.org/10.48550/arXiv.2501.03698
Talk 2: Towards closing nonzero duality gaps of highly singular SDPs by perturbation
Speaker: Takashi Tsuchiya
Abstract: Let us consider general conic convex programs with finite nonzero duality gaps, where both Primal (P) and Dual (D) are weakly feasible. The optimal values of primal and dual are different, but there are arbitrary small perturbations which can close the duality gap (to zero). Let (eps,eta) be nonnegative, and, Let P(eps,eta) and D(eps,eta) are perturbed primal and dual problems with the conic constraints shifted by eps*e and eta*e' to make the both problems strongly feasible where e and e' are interior-points of the primal and dual cones, respectively. If (eps,eta) is nonnegative and nonzero, then at least one of P(eps,eta) and D(eps,eta) is strongly feasible, ensuring strong duality to hold. Let v(eps,eta) be the common optimal value of P(eps, eta) and D(eps,eta). v is well-defined except for (eps,eta)=(0,0). In the case of SDP, we can show that lim v(t*a,t*b) exists when t>0 goes to zero for any (a,b) nonnegative and nonzero. We denote this limit by lv(a,b). Since lv depends on the ratio between a and b, we define lv'(theta)=lv(cos(theta),sin(theta)), where the domain of lv' is [0,pi/2]. We can show that lv' is monotonically decreasing on [0,pi/2] and further continuous on (0,pi/2), with v(0) and v(pi/2) are primal and dual optimal values, respectively [1]. We can prove continuity at theta=0 and theta=pi/2 when singularity degree of (P) and (D) is one, but this does not holds in general singular SDPs with higher singularity degree [2]. It is an interesting problem if we can recover ``continuity'' by considering lim v(f(t)*a,g(t)*b) instead lim v(t*a,t*b), where f and g are appropriate power functions in t. In this talk, we discuss recent developments in this direction and possible extensions to general conic convex programs. [1] Takashi Tsuchiya, Bruno F. Lourenco, Masakazu Muramatsu and Takayuki Okuno: A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms. Mathematical Programming, Vol.200 (2023), pp.531–568. [2] Takashi Tsuchiya, Bruno F. Lourenco, Masakazu Muramatsu and Takayuki Okuno: Closing duality gaps of SDPs completely through perturbation when singularity degree is one. Optimization Methods and Software, Vol.39 (2024), pp.1040-1067.
Talk 3: Extending the Dahl-Andersen interior-point algorithm to general power cone: practicalities and benchmarks
Speaker: Utkarsh Detha
Abstract: The interior-point algorithm for non-symmetric conic problems as prescribed by Dahl and Andersen [DA] uses primal-dual scalings analogous to Nesterov-Todd's approach for symmetric cones. The practical performance of [DA] method is good, driven in part by the use of a higher-order correction similar to the Mehrotra corrector in LPs. The [DA] algorithm is outlined for a 3-D exponential cone while applicability to the 3-D power cone is mentioned. This method for both cones is implemented in MOSEK, which also handles general (m,n) power cones [Cha09] by splitting them into m-2 cones of three dimensions. A follow-up consideration is extending the method to directly handle general (m, n) power cone. Among other things, this is motivated by an expected reduction in iterations since an LHSCB barrier for the general power cone with barrier parameter m+1 exists, in contrast to a parameter of nearly 3m when the cone is split into m-2 3-D cones. The aim of this talk will be two-fold. Firstly, the extension of the DA algorithm to the (m,n) power cone will be discussed with a focus on implementation details and comparison with the approach of splitting into smaller cones. To understand if the scaling approach used in 3-D case also extends its effectiveness over to larger cones, benchmarks will be considered. Secondly, the talk will provide an alternative approach to obtain the higher-order corrector introduced in [DA]. References: [DA]: Joachim Dahl and Erling D. Andersen. A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimization. 194(1):341–370. [Cha09]: Robert Chares. Cones and interior-point algorithms for structured convex optimization involving powers and exponentials. PhD thesis, Université catholique de Louvain, 2009
