Journal: SIAM Journal on Optimization

Abbreviation

SIAM J. Optim.

Publisher

SIAM

Journal Volumes

ISSN

1052-6234
1095-7189

Description

Filters

Reset filters

Search Results

Publications 1 - 10 of 20
  • Approximation of Corner Polyhedra with Families of Intersection Cuts
    Item type: Journal Article
    Averkov, Gennadiy; Basu, Amitabh; Paat, Joseph (2018)
    SIAM Journal on Optimization
  • Randomized Solutions to Convex Programs with Multiple Chance Constraints
    Item type: Journal Article
    Schildbach, Georg; Fagiano, Lorenzo; Morari, Manfred (2013)
    SIAM Journal on Optimization
  • Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximation
    Item type: Journal Article
    Cayci, Semih; He, Niao; Srikant, R. (2024)
    SIAM Journal on Optimization
    Natural policy gradient (NPG) methods, equipped with function approximation and entropy regularization, achieve impressive empirical success in reinforcement learning problems with large state-action spaces. However, their convergence properties and the impact of entropy regularization remain elusive in the function approximation regime. In this paper, we establish finite-time convergence analyses of entropy-regularized NPG with linear function approximation under softmax parameterization. In particular, we prove that entropy-regularized NPG with averaging satisfies the persistence of excitation condition, and achieves a fast convergence rate of Õ(1/T) up to a function approximation error in regularized Markov decision processes. This convergence result does not require any a priori assumptions on the policies. Furthermore, under mild regularity conditions on the concentrability coefficient and basis vectors, we prove that entropy-regularized NPG exhibits linear convergence up to the compatible function approximation error. Finally, we provide sample complexity results for sample-based NPG with entropy regularization.
  • On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
    Item type: Journal Article
    Ling, Shuyang; Xu, Ruitu; Bandeira, Afonso S. (2019)
    SIAM Journal on Optimization
  • A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation
    Item type: Journal Article
    Basu, Amitabh; Hildebrand, Robert; Köppe, Matthias; et al. (2013)
    SIAM Journal on Optimization
  • Quantum Bilinear Optimization
    Item type: Journal Article
    Berta, Mario; Fawzi, Omar; Scholz, Volkher B. (2016)
    SIAM Journal on Optimization
  • Computational Complexity of Sum-of-Squares Bounds for Copositive Programs
    Item type: Journal Article
    Palomba, Marilena; Slot, Lucas; Vargas, Luis Felipe; et al. (2025)
    SIAM Journal on Optimization
    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.
  • New Bounds for the Integer Carathéodory Rank
    Item type: Journal Article
    Aliev, Iskander; Henk, Martin; Hogan, Mark; et al. (2024)
    SIAM Journal on Optimization
    Abstract. Given a rational pointed \(n\)-dimensional cone \(C\), we study the integer Carathéodory rank \(\operatorname{CR}(C)\) and its asymptotic form \(\operatorname{CR^a}(C)\), where we consider “most” integer vectors in the cone. The main result significantly improves the previously known upper bound for \(\operatorname{CR^a}(C)\). We also study bounds on \(\operatorname{CR}(C)\) in terms of \(\Delta\), the maximal absolute \(n\times n\) minor of the matrix given in an integral polyhedral representation of \(C\). If \(\Delta \in \{1,2\}\), we show that \(\operatorname{CR}(C)=n\), and prove upper bounds for simplicial cones, improving the best known upper bound on \(\operatorname{CR}(C)\) for \(\Delta \leq n\).
  • Numerical Algebraic Geometry for Optimal Control Applications
    Item type: Journal Article
    Rostalski, Philipp; Fotiou, Ioannis A.; Bates, Daniel J.; et al. (2011)
    SIAM Journal on Optimization
  • Minimizing a Low-Dimensional Convex Function Over a High-Dimensional Cube
    Item type: Journal Article
    Hunkenschröder, Christoph; Pokutta, Sebastian; Weismantel, Robert (2023)
    SIAM Journal on Optimization
    For a matrix W \in Zmx n, m \leq n, and a convex function g : Rm \rightarrowR, we are interested in minimizing f(x) = g(Wx) over the set {0, 1\} n. We will study separable convex functions and sharp convex functions g. Moreover, the matrix W is unknown to us. Only the number of rows m \leq n and II W II,, are revealed. The composite function f (x) is presented by a zeroth and first order oracle only. Our main result is a proximity theorem that ensures that an integral minimum and a continuous minimum for separable convex and sharp convex functions are always ``close"" by. This will be a key ingredient in developing an algorithm for detecting an integer minimum that achieves a running time of roughly (mII W II,,)O(m3) \cdot poly(n). In the special case when (i) W is given explicitly and (ii) g is separable convex one can also adapt an algorithm of Hochbaum and Shanthikumar [J. ACM, 37 (1990), pp. 843--862]. The running time of this adapted algorithm matches the running time of our general algorithm.
Publications 1 - 10 of 20