-
作者：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.
-
作者：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 ...
-
作者：Lam, Fumei; Newman, Alantha
作者单位：Massachusetts Institute of Technology (MIT); Max Planck Society
摘要：In the traveling salesman path problem, we are given a set of cities, traveling costs between city pairs and fixed source and destination cities. The objective is to find a minimum cost path from the source to destination visiting all cities exactly once. In this paper, we study polyhedral and combinatorial properties of a variant we call the traveling salesman walk problem, in which the objective is to find a minimum cost walk from the source to destination visiting all cities at least once. ...
-
作者：Ben-Tal, Aharon; Nemirovski, Arkadi
作者单位：University System of Georgia; Georgia Institute of Technology; Technion Israel Institute of Technology
摘要：Robust Optimization is a rapidly developing methodology for handling optimization problems affected by non-stochastic uncertain-but- bounded data perturbations. In this paper, we overview several selected topics in this popular area, specifically, (1) recent extensions of the basic concept of robust counterpart of an optimization problem with uncertain data, (2) tractability of robust counterparts, (3) links between RO and traditional chance constrained settings of problems with stochastic dat...
-
作者：Monteiro, Renato D. C.; Tsuchiya, Takashi
作者单位：University System of Georgia; Georgia Institute of Technology; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan
摘要：The main goals of this paper are to: i) relate two iteration-complexity bounds derived for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) algorithm for linear programming (LP), and; ii) study the geometrical structure of the LP central path. The first iteration-complexity bound for the MTY P-C algorithm considered in this paper is expressed in terms of the integral of a certain curvature function over the traversed portion of the central path. The second iteration-complexity bound, derived r...
-
作者：Zhao, M.; de Farias, I. R., Jr.
作者单位：State University of New York (SUNY) System; University at Buffalo, SUNY; State University of New York (SUNY) System; SUNY Optometry; SUNY Maritime College; SUNY Community College
摘要：We study the set = {(x, y) is an element of R+ x Z(n) : x + B(j)y(j) >= b(j), j=1,..., n}, where B-j, b(j) is an element of R+ -{0}, j = 1,..., n, and B-1 vertical bar...vertical bar B-n. The set S generalizes the mixed-integer rounding (MIR) set of Nemhauser and Wolsey and the mixing-MIR set of Gunluk and Pochet. In addition, it arises as a substructure in general mixed-integer programming (MIP), such as in lot-sizing. Despite its importance, a number of basic questions about S remain unanswe...
-
作者：Bomze, Immanuel M.; Locatelli, Marco; Tardella, Fabio
作者单位：Sapienza University Rome; University of Vienna; University of Turin
摘要：A standard quadratic optimization problem (StQP) consists in minimizing a quadratic form over a simplex. Among the problems which can be transformed into a StQP are the general quadratic problem over a polytope, and the maximum clique problem in a graph. In this paper we present several new polynomial-time bounds for StQP ranging from very simple and cheap ones to more complex and tight constructions. The main tools employed in the conception and analysis of most bounds are Semidefinite Progra...
