-
作者：Kuhn, Daniel
作者单位：University of St Gallen
摘要：Multistage stochastic programs have applications in many areas and support policy makers in finding rational decisions that hedge against unforeseen negative events. In order to ensure computational tractability, continuous-state stochastic programs are usually discretized; and frequently, the curse of dimensionality dictates that decision stages must be aggregated. In this article we construct two discrete, stage-aggregated stochastic programs which provide upper and lower bounds on the optim...
-
作者：Shapiro, Alexander
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：In this paper we discuss computational complexity and risk averse approaches to two and multistage stochastic programming problems. We argue that two stage (say linear) stochastic programming problems can be solved with a reasonable accuracy by Monte Carlo sampling techniques while there are indications that complexity of multistage programs grows fast with increase of the number of stages. We discuss an extension of coherent risk measures to a multistage setting and, in particular, dynamic pr...
-
作者：Toh, Kim-Chuan
作者单位：National University of Singapore; Massachusetts Institute of Technology (MIT); Nanyang Technological University; Singapore-MIT Alliance for Research & Technology Centre (SMART)
摘要：We propose primal - dual path- following Mehrotra- type predictor corrector methods for solving convex quadratic semidefinite programming (QSDP) problems of the form: min(X){1/2X center dot Q(X) + C center dot X : A( X) = b, X >= 0}, where Q is a self- adjoint positive semidefinite linear operator on S (n), b is an element of R-m, and A is a linear map from S n to Rm. At each interior- point iteration, the search direction is computed from a dense symmetric indefinite linear system ( called th...
-
作者：Kaibel, Volker; Pfetsch, Marc
作者单位：Zuse Institute Berlin
摘要：We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal subject to a group acting on the columns. Special cases are packing and partitioning orbitopes, which arise from restrictions to matrices with at most or exactly one 1-entry in each row, respectively. The goal of investigating these polytopes is to gain insight into ways of breaking certain symmetries in integer programs by adding constraints, e.g., for a well-known formulation of the graph coloring p...
-
作者：Drummond, L. M. Grana; Maculan, N.; Svaiter, B. F.
作者单位：Universidade Federal do Rio de Janeiro; Universidade Federal do Rio de Janeiro
-
作者：Andreani, Roberto; Martinez, Jose Mario; Martinez, Leandro; Yano, Flavio
作者单位：Universidade Estadual de Campinas; Universidade Estadual de Campinas
摘要：Structural Alignment is an important tool for fold identification of proteins, structural screening on ligand databases, pharmacophore identification and other applications. In the general case, the optimization problem of superimposing two structures is nonsmooth and nonconvex, so that most popular methods are heuristic and do not employ derivative information. Usually, these methods do not admit convergence theories of practical significance. In this work it is shown that the optimization of...
-
作者：Louveaux, Quentin; Weismantel, Robert
作者单位：Otto von Guericke University
摘要：We address the question to what extent polyhedral knowledge about individual knapsack constraints suffices or lacks to describe the convex hull of the binary solutions to their intersection. It turns out that the sign patterns of the weight vectors are responsible for the types of combinatorial valid inequalities appearing in the description of the convex hull of the intersection. In particular, we introduce the notion of an incomplete set inequality which is based on a combinatorial principle...
-
作者：Dunagan, John; Vempala, Santosh
作者单位：Massachusetts Institute of Technology (MIT); Microsoft
摘要：The perceptron algorithm, developed mainly in the machine learning literature, is a simple greedy method for finding a feasible solution to a linear program (alternatively, for learning a threshold function). In spite of its exponential worst-case complexity, it is often quite useful, in part due to its noise-tolerance and also its overall simplicity. In this paper, we show that a randomized version of the perceptron algorithm along with periodic rescaling runs in polynomial-time. The resultin...
-
作者：Goulart, Paul J.; Kerrigan, Eric C.; Ralph, Daniel
作者单位：University of Cambridge; Imperial College London; Imperial College London; University of Cambridge
摘要：This paper proposes an efficient computational technique for the optimal control of linear discrete-time systems subject to bounded disturbances with mixed linear constraints on the states and inputs. The problem of computing an optimal state feedback control policy, given the current state, is non-convex. A recent breakthrough has been the application of robust optimization techniques to reparameterize this problem as a convex program. While the reparameterized problem is theoretically tracta...
-
作者：Deza, Antoine; Nematollahi, Eissa; Terlaky, Tamas
作者单位：McMaster University
摘要：By refining a variant of the Klee-Minty example that forces the central path to visit all the vertices of the Klee-Minty n-cube, we exhibit a nearly worst-case example for path-following interior point methods. Namely, while the theoretical iteration-complexity upper bound is O(2(n) n(5/2)), we prove that solving this n-dimensional linear optimization problem requires at least 2(n)-1 iterations.
