3 présentations

• 
  14h45 - 15h07

  Interior point algorithms for nonsymmetric conic optimization and dual membership certificates

  • Anita Varga, prés., North Carolina State University
  • Dávid Papp, North Carolina State University

  In this talk, we present path-following interior point algorithms for nonsymmetric conic optimization. We discuss different initialization techniques and update strategies.
  Our main application area is finding dual membership certificates for convex cones. For a given vector in the primal cone, we aim to identify a vector in the dual cone that certifies its membership. We define different types of dual certificates and demonstrate how the proposed interior point methods can be applied to determine the certificates efficiently.
  We also share numerical results to illustrate the practical performance of our algorithms.

• 
  15h07 - 15h29

  Algebraic programming

  • Muhammad Maaz, prés., University of Toronto
  • Adam Strzebonski, Wolfram Research

  We consider a generalization of polynomial programs: algebraic programs, which are optimization or feasibility problems with algebraic objectives or constraints. Algebraic functions, which are zeros of multivariate polynomials, are a rich class of functions encompassing polynomials, ratios, radicals, and their finite compositions. While algebraic programs with radical expressions can be reformulated as polynomial programs by introducing variables for each radical, we propose a more efficient approach that often requires fewer variables. Our method first determines a defining polynomial for an algebraic function expressed as a radical. Since polynomials may define multiple algebraic functions, we develop a technique to isolate the desired function through additional polynomial constraints. This allows reformulation using only one new variable per algebraic function. When tested on modified classic optimization benchmarks with algebraic terms, our approach demonstrates significant efficiency gains, achieving up to 40x speedup compared to conventional reformulation methods.

• 
  15h29 - 15h51

  Tightening Quadratic Convex Relaxations for the AC Optimal Transmission Switching Problem

  • Cheng Guo, prés., Clemson University
  • Harsha Nagarajan, Los Alamos National Laboratory
  • Merve Bodur, University of Edinburgh

  The Alternating Current Optimal Transmission Switching (ACOTS) problem incorporates line switching decisions into the AC Optimal Power Flow framework, offering benefits in reducing costs and enhancing reliability. ACOTS optimization models contain discrete variables and nonlinear, non-convex constraints, which make it difficult to solve. We develop strengthened quadratic convex (QC) relaxations for ACOTS, where we tighten the relaxation with several new valid inequalities, including a novel kind of on/off cycle-based polynomial constraints by taking advantage of the network structure. We demonstrate theoretical tightness, and efficiently incorporate on/off cycle-based polynomial constraints through disjunctive programming-based cutting planes. Our method results in the tightest QC-based ACOTS relaxation to date. We additionally propose a novel maximum spanning tree-based heuristic to improve the computational performance by fixing certain lines to be switched on. Tests on large-scale instances with up to 2,312 buses demonstrate substantial performance gains.