-
作者：Pennanen, Teemu; Perkkioe, Ari-Pekka
作者单位：University of London; King's College London; University of Munich
摘要：This paper studies duality and optimality conditions in general convex stochastic optimization problems introduced by Rockafellar and Wets in (Math Programm Stud 6:170-187, 1976). We derive an explicit dual problem in terms of two dual variables, one of which is the shadow price of information while the other one gives the marginal cost of a perturbation much like in classical Lagrangian duality. Existence of primal solutions and the absence of duality gap are obtained without compactness or b...
-
作者：Ponte, Gabriel; Fampa, Marcia; Lee, Jon
作者单位：Universidade Federal Rural do Rio de Janeiro (UFRRJ); Universidade Federal do Rio de Janeiro; University of Michigan System; University of Michigan
摘要：We develop a branch-and-bound algorithm for the integer D-optimality problem, a central problem in statistical design theory, based on two convex relaxations, employing variable-bound tightening and fast local-search procedures, testing our ideas on various test problems.
-
作者：Li, Yongchun; Xie, Weijun
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective function subject to multiple two-sided linear inequalities intersected with a low-rank and spectral constrained domain. Although solving LSOP is generally NP-hard, its partial convexification (i.e., replacing the domain with its convex hull), termed LSOP-R, is often tractable and yields a high-quality solution. This motivates us to study the strength of LSOP-R. Specifically, we derive rank bounds for any extreme point...
-
作者：Li, Tianjiao; Lan, Guanghui
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Line search (or backtracking) procedures have been widely employed into first-order methods for solving convex optimization problems, especially those with unknown problem parameters (e.g., Lipschitz constant). In this paper, we show that line search is superfluous in attaining the optimal rate of convergence for solving a convex optimization problem whose parameters are not given a priori. In particular, we present a novel accelerated gradient descent type algorithm called auto-conditioned fa...
-
作者：Schade, Jamico; Sinha, Makrand; Weltge, Stefan
作者单位：Technical University of Munich; University of Illinois System; University of Illinois Urbana-Champaign
摘要：Standard mixed-integer programming formulations for the stable set problem on n-node graphs require n integer variables. We prove that this is almost optimal: We give a family of n-node graphs for which every polynomial-size MIP formulation requires Omega(n/log(2) n) integer variables. By a polyhedral reduction we obtain an analogous result for n-item knapsack problems. In both cases, this improves the previously known bounds of Omega(root n/log n) by Cevallos et al. (in Proceedings of the twe...
-
作者：Balas, Egon; Kazachkov, Aleksandr M.
作者单位：Carnegie Mellon University; State University System of Florida; University of Florida
摘要：We introduce V-polyhedral disjunctive cuts (VPCs) to generate valid inequalities from general disjunctions for a mixed-integer linear program. While optimization solvers critically rely on cuts, they only deploy limited families derivable from weak disjunctions, as the typical cut-generating linear program needs a costly higher-dimensional representation. The VPC framework mitigates this through a polar perspective to more efficiently use deeper, multiterm disjunctions, which partition the fea...
-
作者：Zhu, Landi; Gurbuzbalaban, Mert; Ruszczynski, Andrzej
作者单位：Rutgers University System; Rutgers University New Brunswick
摘要：We consider a distributionally robust stochastic optimization problem where the ambiguity sets are implicitly defined by the dual representation of the mean-semideviation risk measure. Utilizing the specific form of this risk measure, we reformulate the problem as a stochastic two-level composition optimization problem. In this setting, we consider a single time-scale algorithm, involving two versions of the inner function value tracking: linearized tracking of a continuously differentiable lo...
-
作者：Liberti, Leo; Sager, Sebastian; Wiegele, Angelika
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; Otto von Guericke University; University of Klagenfurt
-
作者：Jang, Uijeong; Gupta, Shuvomoy Das; Ryu, Ernest K.
作者单位：University of California System; University of California Los Angeles; Rice University
摘要：The accelerated composite optimization method FISTA (Beck, Teboulle 2009) is suboptimal by a constant factor, and we present a new method OptISTA that improves FISTA by a constant factor of 2. The performance estimation problem (PEP) has recently been introduced as a new computer-assisted paradigm for designing optimal first-order methods. In this work, we present a double-function stepsize-optimization PEP methodology that poses the optimization over fixed-step first-order methods for composi...
-
作者：Buchheim, Christoph; Merkert, Maximilian
作者单位：Dortmund University of Technology; Braunschweig University of Technology
摘要：Many discrete optimal control problems feature combinatorial constraints on the possible switching patterns, a common example being minimum dwell-time constraints. After discretizing to a finite time grid, it is sometimes possible to give a description of the convex hull of feasible (finite-dimensional) binary controls via flow-based extended formulations. For example, this is the case if the feasible set can be characterized via finite-state automata. In this work, we aim to transfer such des...
