-
作者：Jiang, Bo; Dai, Yu-Hong
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：This paper considers optimization problems on the Stiefel manifold (XX)-X-T = I-p, where X is an element of R-nxp is the variable and I-p is the p-by-p identity matrix. A framework of constraint preserving update schemes is proposed by decomposing each feasible point into the range space of X and the null space of X-T. While this general framework can unify many existing schemes, a new update scheme with low complexity cost is also discovered. Then we study a feasible Barzilai-Borwein-like met...
-
作者：Nie, Jiawang
作者单位：University of California System; University of California San Diego
摘要：This paper studies the hierarchy of local minimums of a polynomial in the vector space . For this purpose, we first compute -minimums, for which the first and second order necessary optimality conditions are satisfied. To compute each -minimum, we construct a sequence of semidefinite relaxations, based on optimality conditions. We prove that each constructed sequence has finite convergence, under some generic conditions. A procedure for computing all local minimums is given. When there are equ...
-
作者：Pena, Javier; Vera, Juan C.; Zuluaga, Luis F.
作者单位：Carnegie Mellon University; Tilburg University; Lehigh University
摘要：Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well established body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of completely positive matrices, or its conic dual, the cone of copositive matrices. As a result of this reformulation approach, novel solution scheme...
-
作者：Chatzipanagiotis, Nikolaos; Dentcheva, Darinka; Zavlanos, Michael M.
作者单位：Duke University; Stevens Institute of Technology
摘要：We propose a novel distributed method for convex optimization problems with a certain separability structure. The method is based on the augmented Lagrangian framework. We analyze its convergence and provide an application to two network models, as well as to a two-stage stochastic optimization problem. The proposed method compares favorably to two augmented Lagrangian decomposition methods known in the literature, as well as to decomposition methods based on the ordinary Lagrangian function.
-
作者：King, Douglas M.; Jacobson, Sheldon H.; Sewell, Edward C.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; Southern Illinois University System; Southern Illinois University Edwardsville
摘要：Graph partitioning is an intractable problem that arises in many practical applications. Heuristics such as local search generate good (though suboptimal) solutions in limited time. Such heuristics must be able to explore the solution space quickly and, when the solution space is constrained, differentiate feasible solutions from infeasible ones. Geographic zoning problems allocate some resource (e.g., political representation, school enrollment, police patrols) to contiguous zones modeled by ...
-
作者：Letchford, Adam N.; Lasserre, Jean B.; Parrilo, Pablo A.; Steurer, David
作者单位：Lancaster University; Centre National de la Recherche Scientifique (CNRS); Massachusetts Institute of Technology (MIT); Cornell University
-
作者：Caprara, Alberto; Dell'Amico, Mauro; Diaz-Diaz, Jose Carlos; Iori, Manuel; Rizzi, Romeo
作者单位：Universita di Modena e Reggio Emilia; University of Verona
摘要：It is well known that the gap between the optimal values of bin packing and fractional bin packing, if the latter is rounded up to the closest integer, is almost always null. Known counterexamples to this for integer input values involve fairly large numbers. Specifically, the first one was derived in 1986 and involved a bin capacity of the order of a billion. Later in 1998 a counterexample with a bin capacity of the order of a million was found. In this paper we show a large number of counter...
-
作者：Gouveia, Luis; Leitner, Markus; Ljubic, Ivana
作者单位：Universidade de Lisboa; University of Vienna; Technische Universitat Wien
摘要：In this article, we introduce the two-level diameter constrained spanning tree problem (2-DMSTP), which generalizes the classical DMSTP by considering two sets of nodes with different latency requirements. We first observe that any feasible solution to the 2-DMSTP can be viewed as a DMST that contains a diameter constrained Steiner tree. This observation allows us to prove graph theoretical properties related to the centers of each tree which are then exploited to develop mixed integer program...
-
作者：Dey, Santanu S.; Molinaro, Marco; Wang, Qianyi
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：In this paper, we study how well one can approximate arbitrary polytopes using sparse inequalities. Our motivation comes from the use of sparse cutting-planes in mixed-integer programing (MIP) solvers, since they help in solving the linear programs encountered during branch-&-bound more efficiently. However, how well can we approximate the integer hull by just using sparse cutting-planes? In order to understand this question better, given a polyope (e.g. the integer hull of a MIP), let be its ...
-
作者：Drusvyatskiy, D.; Ioffe, A. D.
作者单位：University of Washington; University of Washington Seattle; Technion Israel Institute of Technology
摘要：We show that quadratic growth of a semi-algebraic function is equivalent to strong metric subregularity of the subdifferential-a kind of stability of generalized critical points. In contrast, this equivalence can easily fail outside of the semi-algebraic setting. As a consequence, we derive necessary conditions and sufficient conditions for optimality in subdifferential terms.
