We consider trust-region methods for solving optimization problems where the objective is the sum of a smooth, nonconvex function and a nonsmooth, convex regularizer. We extend the global convergence theory of such methods to include worst-case complexity bounds in the case of unbounded model Hessian growth, and introduce a new, simple nonsmooth trust-region subproblem solver … Read more
This paper deals with the Constrained Riemannian Optimization (CRO) problem, which involves minimizing a function subject to equality and inequality constraints on Riemannian manifolds. The study aims to advance optimization theory in the Riemannian setting by presenting and analyzing a penalty-type method for solving CRO problems. The proposed approach is based on techniques that involve … Read more
This paper presents a novel restarted version of Nesterov’s accelerated gradient method and establishes its optimal iteration-complexity for solving convex smooth composite optimization problems. The proposed restart accelerated gradient method is shown to be a specific instance of the accelerated inexact proximal point framework introduced in “An accelerated hybrid proximal extragradient method for convex optimization … Read more
We consider the problem of computing the optimal solution and objective of a linear program under linearly changing linear constraints. The problem studied is given by $\min c^t x \text{ s.t } Ax + \lambda Dx \leq b$ where $\lambda$ belongs to a set of predefined values $\Lambda$. Based on the information given by a … Read more
ArticleDownload View PDF
Building on the blueprint from Goemans and Williamson (1995) for the Max-Cut problem, we construct a polynomial-time approximation algorithm for orthogonally constrained quadratic optimization problems. First, we derive a semidefinite relaxation and propose a randomized rounding algorithm to generate feasible solutions from the relaxation. Second, we derive constant-factor approximation guarantees for our algorithm. When optimizing … Read more
We introduce two-stage stochastic min-max and min-min integer programs with bi-parameterized recourse (BTSPs), where the first-stage decisions affect both the objective function and the feasible region of the second-stage problem. To solve these programs efficiently, we introduce Lagrangian-integrated \(L\)-shaped (\(L^2\)) methods, which guarantee exact solutions when the first-stage decisions are pure binary. For mixed-binary first-stage … Read more
The restarted primal-dual hybrid gradient method (rPDHG) is a first-order method recently known for its computational effectiveness in solving linear programming (LP) problems. Despite its impressive practical performance, the theoretical iteration bounds for rPDHG can be exponentially poor. To investigate this gap from a probabilistic perspective, we show that rPDHG achieves polynomial-time complexity in a … Read more
We study proximity (resp. integrality gap), that is, the distance (resp. difference) between the optimal solutions (resp. optimal values) of convex integer programs (IP) and the optimal solutions (resp. optimal values) of their continuous relaxations. We show that these values can be upper bounded in terms of the recession cone of the feasible region of … Read more
Single-source capacitated facility location problems are well studied in the operations research literature, yet classic problems often lack practicability by disregarding the customers’ perspective: An authority that assigns customers to open facilities deprives customers from choosing facilities according to their individual preferences. In reality, this can render solutions infeasible, as customers may deviate to their … Read more