-
作者：Chen, Xiaojun; Wets, Roger
-
作者：Bandeira, Afonso S.; Boumal, Nicolas; Singer, Amit
作者单位：New York University; Princeton University
摘要：Maximum likelihood estimation problems are, in general, intractable optimization problems. As a result, it is common to approximate the maximum likelihood estimator (MLE) using convex relaxations. In some cases, the relaxation is tight: it recovers the true MLE. Most tightness proofs only apply to situations where the MLE exactly recovers a planted solution (known to the analyst). It is then sufficient to establish that the optimality conditions hold at the planted signal. In this paper, we st...
-
作者：Drusvyatskiy, Dmitriy; Li, Guoyin; Wolkowicz, Henry
作者单位：University of Washington; University of Washington Seattle; University of New South Wales Sydney; University of Waterloo
摘要：We observe that Sturm's error bounds readily imply that for semidefinite feasibility problems, the method of alternating projections converges at a rate of , where d is the singularity degree of the problem-the minimal number of facial reduction iterations needed to induce Slater's condition. Consequently, for almost all such problems (in the sense of Lebesgue measure), alternating projections converge at a worst-case rate of O(1/root k).
-
作者：Kolliopoulos, Stavros G.; Moysoglou, Yannis
作者单位：National & Kapodistrian University of Athens
摘要：Metric uncapacitated facility location is a well-studied problem for which linear programming methods have been used with great success in deriving approximation algorithms. Capacitated facility location (Cfl) is a generalization for which there are local-search-based constant-factor approximations, while there is no known compact relaxation with constant integrality gap. This paper produces, through a host of impossibility results, the first comprehensive investigation of the effectiveness of...
-
作者：Gade, Dinakar; Hackebeil, Gabriel; Ryan, Sarah M.; Watson, Jean-Paul; Wets, Roger J. -B.; Woodruff, David L.
作者单位：United States Department of Energy (DOE); Sandia National Laboratories; Texas A&M University System; Texas A&M University College Station; Iowa State University; University of California System; University of California Davis
摘要：We present a method for computing lower bounds in the progressive hedging algorithm (PHA) for two-stage and multi-stage stochastic mixed-integer programs. Computing lower bounds in the PHA allows one to assess the quality of the solutions generated by the algorithm contemporaneously. The lower bounds can be computed in any iteration of the algorithm by using dual prices that are calculated during execution of the standard PHA. We report computational results on stochastic unit commitment and s...
-
作者：Rebennack, Steffen
作者单位：Colorado School of Mines
摘要：Nested Benders decomposition is a widely used and accepted solution methodology for multi-stage stochastic linear programming problems. Motivated by large-scale applications in the context of hydro-thermal scheduling, in 1991, Pereira and Pinto introduced a sampling-based variant of the Benders decomposition method, known as stochastic dual dynamic programming (SDDP). In this paper, we embed the SDDP algorithm into the scenario tree framework, essentially combining the nested Benders decomposi...
-
作者：Ghadimi, Saeed; Lan, Guanghui; Zhang, Hongchao
作者单位：State University System of Florida; University of Florida; Louisiana State University System; Louisiana State University
摘要：This paper considers a class of constrained stochastic composite optimization problems whose objective function is given by the summation of a differentiable (possibly nonconvex) component, together with a certain non-differentiable (but convex) component. In order to solve these problems, we propose a randomized stochastic projected gradient (RSPG) algorithm, in which proper mini-batch of samples are taken at each iteration depending on the total budget of stochastic samples allowed. The RSPG...
-
作者：Leston-Rey, Mario; Lee, Orlando
作者单位：Universidade Estadual de Campinas
摘要：In this paper, we consider integral (and fractional) packing problems in generalized kernel systems with a mixed family (gksmf). This framework generalizes combinatorial packing problems of several structures as, for instance, st-flows, arborescences, kernel systems, branchings, convex branchings, and covers in bi-set systems. We provide an algorithm, which improves by a factor of 2 on the upperbound for the size of a packing in a gksmf, provided by Leston-Rey and Wakabayashi. This in turn imp...
-
作者：Dash, Sanjeeb; Guenluek, Oktay; Wolsey, Laurence A.
作者单位：International Business Machines (IBM); IBM USA; Universite Catholique Louvain
摘要：We study the convex hull of the continuous knapsack set which consists of a single inequality constraint with non-negative integer and non-negative bounded continuous variables. When , this set is a generalization of the single arc flow set studied by Magnanti et al. (Math Program 60:233-250, 1993). We first show that in any facet-defining inequality, the number of distinct non-zero coefficients of the continuous variables is bounded by . Our next result is to show that when , this upper bound...
-
作者：Lewis, A. S.; Wright, S. J.
作者单位：Cornell University; University of Wisconsin System; University of Wisconsin Madison
摘要：We consider minimization of functions that are compositions of convex or prox-regular functions (possibly extended-valued) with smooth vector functions. A wide variety of important optimization problems fall into this framework. We describe an algorithmic framework based on a subproblem constructed from a linearized approximation to the objective and a regularization term. Properties of local solutions of this subproblem underlie both a global convergence result and an identification property ...
