-
作者：Lee, Jisun; Gomez, Andres; Atamturk, Alper
作者单位：University System of Georgia; Georgia Institute of Technology; University of Southern California; University of California System; University of California Berkeley
摘要：We study a multi-period mixed-integer convex quadratic optimization problem, where the state evolves dynamically as an affine function of the state and action (control) variables in each period. We begin by projecting out the state variables using linear dynamics, resulting in a mixed-integer quadratic optimization problem with a positive-definite (block-)factorizable cost matrix. Employing this expression, we construct a closed convex hull representation of the epigraph of the quadratic cost ...
-
作者：O'Leary-Roseberry, Thomas; Bollapragada, Raghu
作者单位：University System of Ohio; Ohio State University; University of Texas System; University of Texas Austin; University of Texas System; University of Texas Austin
摘要：We consider minimizing finite-sum objective functions via Hessian-averaging based subsampled Newton methods. These methods allow for gradient inexactness and have fixed per-iteration Hessian approximation costs. The recent work (Na et al. 2023) demonstrated that Hessian averaging can be utilized to achieve fast Ologkk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \...
-
作者：Tawarmalani, Mohit
作者单位：Purdue University System; Purdue University
摘要：This paper introduces novel relaxation hierarchies for concavo-convex programs (CXP), a class of problems that includes disjoint bilinear programming (DBP) and concave minimization (CM) as special cases. At the core of these hierarchies is an algorithm based on double-description (DD) that computes the barycentric coordinates of a polyhedral cone as rational, non-negative functions representing multipliers associated with the cone's rays. These hierarchies combine geometric structure derived f...
-
作者：Lu, Zhaosong; Wang, Xiangyuan
作者单位：University of Minnesota System; University of Minnesota Twin Cities
摘要：We study a class of constrained nonconvex-nonconcave minimax optimization problems in which the inner maximization involves potentially complex constraints. Under the assumption that the inner problem of a novel lifted minimax reformulation satisfies a local Kurdyka-& Lstrok;ojasiewicz (KL) condition, we show that the maximal function of the original problem enjoys a local generalized H & ouml;lder smoothness property. We also propose a sequential convex programming (SCP) method for solving co...
-
作者：Hou, Di; Tang, Tianyun; Toh, Kim-Chuan
作者单位：National University of Singapore; University of Chicago; National University of Singapore
摘要：Polynomial optimization problems (POPs) can be reformulated as geometric convex conic programs, as shown by Kim, Kojima, and Toh (SIOPT 30:1251-1273, 2020), though such formulations remain NP-hard. In this work, we prove that several well-known relaxations can be unified under a common polyhedral-SDP framework, which arises by approximating the intractable cone by tractable intersections of polyhedral cones with the positive semidefinite matrix cone. Although effective in providing tight lower...
-
作者：Tran, Hoang Anh; Toh, Kim-Chuan
作者单位：National University of Singapore; National University of Singapore
摘要：The moment-SOS hierarchy, which is based on Putinar-type (quadratic module) and Schm & uuml;dgen-type (preordering) sum-of-squares positivity certificates, is a widely applicable framework to address polynomial optimization problems over basic semi-algebraic sets. Recent works show that the convergence rate of this hierarchy over certain simple sets, namely, the unit ball, hypercube, and standard simplex, is of the order O(1/r2) , where r denotes the level of the moment-SOS hierarchy. This pap...
-
作者：Monteiro, Renato D. C.; Sujanani, Arnesh; Cifuentes, Diego
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：This paper introduces HALLaR, a new first-order method for solving large-scale semidefinite programs (SDPs) with bounded domain. HALLaR is an inexact augmented Lagrangian (AL) method where the AL subproblems are solved by a hybrid low-rank (HLR) method. The recipe behind HLR is based on two key ingredients: 1) an adaptive inexact proximal point method with inner acceleration; 2) Frank-Wolfe steps to escape from spurious local stationary points. In contrast to the low-rank method of Burer and M...
-
作者：Borst, Sander; Kashaev, Danish; Koh, Zhuan Khye
作者单位：Max Planck Society; Boston University
摘要：The online matching problem was introduced by Karp, Vazirani and Vazirani (STOC 1990) on bipartite graphs with vertex arrivals. It is well-known that the optimal competitive ratio is 1-1/e\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1-1/e$$\end{document} for both integral and fractional versions of the problem. ...
-
作者：Liu, Hongcheng; Tong, Jindong
作者单位：State University System of Florida; University of Florida
摘要：This paper studies sample average approximation (SAA) in solving convex or strongly convex stochastic programming (SP) problems. In estimating SAA's sample efficiency, the state-of-the-art sample complexity bounds entail metric entropy terms (such as the logarithm of the feasible region's covering number), which often grow polynomially with problem dimensionality. While it has been shown that metric entropy-free complexity rates are attainable under a uniform Lipschitz condition, such an assum...
-
作者：Warme, David M.
摘要：We study the notion of strength of inequalities used in integer and mixed-integer programming, and the branch-and-cut algorithms used to solve such problems. Strength is an ethereal property lacking any good formal definition, but crucially affects speed of computations. We review several quantitative indicators proposed in the literature that we claim provide a measure of the relative strength of inequalities with respect to a given polyhedron. We evaluate two of these indicators (extreme poi...
