-
作者：Arutyunov, A. V.; Avakov, E. R.; Izmailov, A. F.
作者单位：Lomonosov Moscow State University; Peoples Friendship University of Russia; Russian Academy of Sciences
摘要：We derive first- and second-order necessary optimality conditions for set-constrained optimization problems under the constraint qualification-type conditions significantly weaker than Robinson's constraint qualification. Our development relies on the so-called 2-regularity concept, and unifies and extends the previous studies based on this concept. Specifically, in our setting constraints are given by an inclusion, with an arbitrary closed convex set on the right-hand side. Thus, for the seco...
-
作者：Rodriguez-Mancilla, Jose R.; Ziemba, William T.
作者单位：Bank of Mexico; University of British Columbia; University of Zurich; Massachusetts Institute of Technology (MIT); University of Oxford
摘要：This paper explores the structure of optimal investment strategies using stochastic programming and duality theory in investment portfolios containing options for a hedge fund manager who attempts to beat a benchmark. Explicit optimal conditions for option investments are obtained for several models.
-
作者：Balas, Egon; Saxena, Anureet
作者单位：Carnegie Mellon University
摘要：The polyhedron defined by all the split cuts obtainable directly (i.e. without iterated cut generation) from the LP-relaxation P of a mixed integer program (MIP) is termed the (elementary, or rank 1) split closure of P. This paper deals with the problem of optimizing over the elementary split closure. This is accomplished by repeatedly solving the following separation problem: given a fractional point, say x, find a rank-1 split cut violated by x or show that none exists. Following Caprara and...
-
作者：Lasserre, Jean B.
作者单位：Centre National de la Recherche Scientifique (CNRS)
摘要：We consider the generalized problem of moments (GPM) from a computational point of view and provide a hierarchy of semidefinite programming relaxations whose sequence of optimal values converges to the optimal value of the GPM. We then investigate in detail various examples of applications in optimization, probability, financial economics and optimal control, which all can be viewed as particular instances of the GPM.
-
作者：Cornuejols, Gerard
作者单位：Carnegie Mellon University; Aix-Marseille Universite
摘要：This tutorial presents a theory of valid inequalities for mixed integer linear sets. It introduces the necessary tools from polyhedral theory and gives a geometric understanding of several classical families of valid inequalities such as lift-and-project cuts, Gomory mixed integer cuts, mixed integer rounding cuts, split cuts and intersection cuts, and it reveals the relationships between these families. The tutorial also discusses computational aspects of generating the cuts and their strength.
-
作者：Gaur, Daya Ram; Krishnamurti, Ramesh; Kohli, Rajeev
作者单位：Columbia University; Simon Fraser University; University of Lethbridge
摘要：We consider a capacitated max k-cut problem in which a set of vertices is partitioned into k subsets. Each edge has a non-negative weight, and each subset has a possibly different capacity that imposes an upper bound on its size. The objective is to find a partition that maximizes the sum of edge weights across all pairs of vertices that lie in different subsets. We describe a local-search algorithm that obtains a solution with value no smaller than 1 - 1/k of the optimal solution value. This ...
-
作者：Chua, Chek Beng
作者单位：Nanyang Technological University
摘要：The purpose of this paper is two-fold. Firstly, we show that every Cholesky-based weighted central path for semidefinite programming is analytic under strict complementarity. This result is applied to homogeneous cone programming to show that the central paths defined by the known class of optimal self-concordant barriers are analytic in the presence of strictly complementary solutions. Secondly, we consider a sequence of primal-dual solutions that lies within a prescribed neighborhood of the ...
-
作者：Avis, David; Imai, Hiroshi; Ito, Tsuyoshi
作者单位：University of Tokyo; McGill University; Japan Science & Technology Agency (JST)
摘要：The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper we introduce a lift...
-
作者：Baldacci, Roberto; Christofides, Nicos; Mingozzi, Aristide
作者单位：University of Bologna; Imperial College London; University of Bologna
摘要：This paper presents a new exact algorithm for the Capacitated Vehicle Routing Problem (CVRP) based on the set partitioning formulation with additional cuts that correspond to capacity and clique inequalities. The exact algorithm uses a bounding procedure that finds a near optimal dual solution of the LP-relaxation of the resulting mathematical formulation by combining three dual ascent heuristics. The first dual heuristic is based on the q-route relaxation of the set partitioning formulation o...
-
作者：Jeyakumar, V.; Lee, G. M.
作者单位：University of New South Wales Sydney; Pukyong National University
摘要：We establish necessary and sufficient conditions for a stable Farkas' lemma. We then derive necessary and sufficient conditions for a stable duality of a cone-convex optimization problem, where strong duality holds for each linear perturbation of a given convex objective function. As an application, we obtain stable duality results for convex semi-definite programs and convex second-order cone programs.
