-
作者：Liu, Peijing; Fattahi, Salar; Gomez, Andres; Kucukyavuz, Simge
作者单位：University of Southern California; University of Michigan System; University of Michigan; Northwestern University
摘要：In this paper, we consider convex quadratic optimization problems with indicator variables when the matrix Q defining the quadratic term in the objective is sparse. We use a graphical representation of the support of Q, and show that if this graph is a path, then we can solve the associated problem in polynomial time. This enables us to construct a compact extended formulation for the closure of the convex hull of the epigraph of the mixed-integer convex problem. Furthermore, motivated by infe...
-
作者：Verschae, Jose; Villagra, Matias; von Niederhausern, Leonard
作者单位：Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile; Columbia University; Universidad de O'Higgins; Universidad de Chile; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
摘要：Breaking symmetries is a popular way of speeding up the branch-and-bound method for symmetric integer programs. We study fundamental domains, which are minimal and closed symmetry breaking polyhedra. Our long-term goal is to understand the relationship between the complexity of such polyhedra and their symmetry breaking capability. Borrowing ideas from geometric group theory, we provide structural properties that relate the action of the group with the geometry of the facets of fundamental dom...
-
作者：De Marchi, Alberto; Jia, Xiaoxi; Kanzow, Christian; Mehlitz, Patrick
作者单位：Bundeswehr University Munich; University of Wurzburg; Brandenburg University of Technology Cottbus
摘要：We investigate finite-dimensional constrained structured optimization problems, featuring composite objective functions and set-membership constraints. Offering an expressive yet simple language, this problem class provides a modeling framework for a variety of applications. We study stationarity and regularity concepts, and propose a flexible augmented Lagrangian scheme. We provide a theoretical characterization of the algorithm and its asymptotic properties, deriving convergence results for ...
-
作者：Davarnia, Danial; Rajabalizadeh, Atefeh; Hooker, John
作者单位：Iowa State University; Carnegie Mellon University
摘要：The primary role of cutting planes is to separate fractional solutions of the linear programming relaxation, which results in tighter bounds for pruning the search tree and reducing its size. Bounding, however, has an indirect impact on the size of the search tree. Cutting planes can also reduce backtracking by excluding inconsistent partial assignments that occur in the course of branching, which directly reduces the tree size. A partial assignment is inconsistent with a constraint set when i...
-
作者：Eifler, Leon; Gleixner, Ambros
作者单位：Zuse Institute Berlin
摘要：The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce in...
-
作者：Hahn, Mirko; Leyffer, Sven; Sager, Sebastian
作者单位：Otto von Guericke University; United States Department of Energy (DOE); Argonne National Laboratory
摘要：We present a trust-region steepest descent method for dynamic optimal control problems with binary-valued integrable control functions. Our method interprets the control function as an indicator function of a measurable set and makes set-valued adjustments derived from the sublevel sets of a topological gradient function. By combining this type of update with a trust-region framework, we are able to show by theoretical argument that our method achieves asymptotic stationarity despite possible ...
-
作者：Nie, Jiawang; Tang, Xindong
作者单位：University of California System; University of California San Diego; Hong Kong Polytechnic University
摘要：This paper studies convex generalized Nash equilibrium problems that are given by polynomials. We use rational and parametric expressions for Lagrange multipliers to formulate efficient polynomial optimization for computing generalized Nash equilibria (GNEs). The Moment-SOS hierarchy of semidefinite relaxations are used to solve the polynomial optimization. Under some general assumptions, we prove the method can find a GNE if there exists one, or detect nonexistence of GNEs. Numerical experime...
-
作者：Burtscheidt, Johanna; Claus, Matthias; Conti, Sergio; Rumpf, Martin; Sassen, Josua; Schultz, Rudiger
作者单位：University of Duisburg Essen; University of Bonn; University of Bonn
摘要：We consider pessimistic bilevel stochastic programs in which the follower maximizes over a fixed compact convex set a strictly convex quadratic function, whose Hessian depends on the leader's decision. This results in a random upper level outcome which is evaluated by a convex risk measure. Under assumptions including real analyticity of the lower-level goal function, we prove the existence of optimal solutions. We discuss an alternate model, where the leader hedges against optimal lower-level...
-
作者：Demange, Gabrielle
作者单位：Paris School of Economics
摘要：In a variety of systems, in particular in a financial system, entities hold liabilities on each other. The reimbursement abilities are intertwined, thereby potentially generating coordination failures and cascades of defaults calling for orderly resolution. With a single indebted firm, a bankruptcy law organizes such an orderly resolution. With cross-liabilities, a resolution rule should be defined at the system level to account for all those affected, directly or indirectly. This paper invest...
-
作者：Lee, Ching-pei
作者单位：Academia Sinica - Taiwan
摘要：For regularized optimization that minimizes the sum of a smooth term and a regularizer that promotes structured solutions, inexact proximal-Newton-type methods, or successive quadratic approximation (SQA) methods, are widely used for their superlinear convergence in terms of iterations. However, unlike the counter parts in smooth optimization, they suffer from lengthy running time in solving regularized subproblems because even approximate solutions cannot be computed easily, so their empirica...
