2期

最新文章

• Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix AI翻译
  作者：Bader, Jorg; Hildebrand, Robert; Weismantel, Robert; Zenklusen, Rico
  作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; International Business Machines (IBM); IBM USA
  摘要：We study the reformulation of integer linear programs by means of a mixed integer linear program with fewer integer variables. Such reformulations can be solved efficiently with mixed integer linear programming techniques. We exhibit examples that demonstrate how integer programs can be reformulated using far fewer integer variables. To this end, we introduce a generalization of total unimodularity called the affine TU-dimension of a matrix and study related theory and algorithms for determini...
• SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices AI翻译
  作者：Jiang, Rujun; Li, Duan; Wu, Baiyi
  作者单位：Chinese University of Hong Kong; Guangdong University of Foreign Studies
  摘要：We investigate in this paper the generalized trust region subproblem (GTRS) of minimizing a general quadratic objective function subject to a general quadratic inequality constraint. By applying a simultaneous block diagonalization approach, we obtain a congruent canonical form for the symmetric matrices in both the objective and constraint functions. By exploiting the block separability of the canonical form, we show that all GTRSs with an optimal value bounded from below are second order con...
• Deriving convex hulls through lifting and projection AI翻译
  作者：Nguyen, Trang T.; Richard, Jean-Philippe P.; Tawarmalani, Mohit
  作者单位：State University System of Florida; University of Florida; Purdue University System; Purdue University
  摘要：We consider convex hull descriptions for certain sets described by inequality constraints over a hypercube and propose a lifting-and-projection technique to construct them. The general procedure obtains the convex hulls as an intersection of semi-infinite families of linear inequalities, each derived using lifting techniques that are interpreted using convexification tools. We demonstrate that differentiability and concavity of certain perturbation functions help reduce the number of inequalit...
• Stochastic optimization using a trust-region method and random models AI翻译
  作者：Chen, R.; Menickelly, M.; Scheinberg, K.
  作者单位：Bosch; Lehigh University
  摘要：In this paper, we propose and analyze a trust-region model-based algorithm for solving unconstrained stochastic optimization problems. Our framework utilizes random models of an objective function f(x), obtained from stochastic observations of the function or its gradient. Our method also utilizes estimates of function values to gauge progress that is being made. The convergence analysis relies on requirements that these models and these estimates are sufficiently accurate with high enough, bu...
• On decomposability of Multilinear sets AI翻译
  作者：Del Pia, Alberto; Khajavirad, Aida
  作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Carnegie Mellon University
  摘要：We consider the Multilinear set defined as the set of binary points (x, y) satisfying a collection of multilinear equations of the form , , where denotes a family of subsets of of cardinality at least two. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the Multilinear set is possible when is decomposable into simpler Multilinea...
• Global convergence rate analysis of unconstrained optimization methods based on probabilistic models AI翻译
  作者：Cartis, C.; Scheinberg, K.
  作者单位：University of Oxford; Lehigh University
  摘要：We present global convergence rates for a line-search method which is based on random first-order models and directions whose quality is ensured only with certain probability. We show that in terms of the order of the accuracy, the evaluation complexity of such a method is the same as its counterparts that use deterministic accurate models; the use of probabilistic models only increases the complexity by a constant, which depends on the probability of the models being good. We particularize an...
• New computational guarantees for solving convex optimization problems with first order methods, via a function growth condition measure AI翻译
  作者：Freund, Robert M.; Lu, Haihao
  作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
  摘要：Motivated by recent work of Renegar (A framework for applying subgradient methods to conic optimization problems, 2015) we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods. Our problem of interest is the general convex optimization problem , where we presume knowledge of a strict lower bound . [Indeed, is naturally known when optimizing many loss functions in statistics and machine learning (least-squar...
• Critical solutions of nonlinear equations: local attraction for Newton-type methods AI翻译
  作者：Izmailov, A. F.; Kurennoy, A. S.; Solodov, M. V.
  作者单位：Lomonosov Moscow State University; Peoples Friendship University of Russia; Derzhavin Tambov State University
  摘要：We show that if the equation mapping is 2-regular at a solution in some nonzero direction in the null space of its Jacobian (in which case this solution is critical; in particular, the local Lipschitzian error bound does not hold), then this direction defines a star-like domain with nonempty interior from which the iterates generated by a certain class of Newton-type methods necessarily converge to the solution in question. This is despite the solution being degenerate, and possibly non-isolat...
• Chain-constrained spanning trees AI翻译
  作者：Olver, Neil; Zenklusen, Rico
  作者单位：Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI); Swiss Federal Institutes of Technology Domain; ETH Zurich
  摘要：We consider the problem of finding a spanning tree satisfying a family of additional constraints. Several settings have been considered previously, the most famous being the problem of finding a spanning tree with degree constraints. Since the problem is hard, the goal is typically to find a spanning tree that violates the constraints as little as possible. Iterative rounding has become the tool of choice for constrained spanning tree problems. However, iterative rounding approaches are very h...
• Bilevel programming for generating discrete representations in multiobjective optimization AI翻译
  作者：Kirlik, Gokhan; Sayin, Serpil
  作者单位：Koc University
  摘要：The solution to a multiobjective optimization problem consists of the nondominated set that portrays all relevant trade-off information. The ultimate goal is to identify a Decision Maker's most preferred solution without generating the entire set of nondominated solutions. We propose a bilevel programming formulation that can be used to this end. The bilevel program is capable of delivering an efficient solution that maps into a given set, provided that one exits. If the Decision Maker's prefe...