-
作者：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...
-
作者：Conforti, Michele; Wolsey, Laurence A.
作者单位：Universite Catholique Louvain; University of Padua
摘要：We explore one method for finding the convex hull of certain mixed integer sets. The approach is to break up the original set into a small number of subsets, find a compact polyhedral description of the convex hull of each subset, and then take the convex hull of the union of these polyhedra. The resulting extended formulation is then compact, its projection is the convex hull of the original set, and optimization over the mixed integer set is reduced to solving a linear program over the exten...
-
作者：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...
-
作者：Sun, Defeng; Sun, Jie; Zhang, Liwei
作者单位：National University of Singapore; National University of Singapore; Dalian University of Technology
摘要：We analyze the rate of local convergence of the augmented Lagrangian method in nonlinear semidefinite optimization. The presence of the positive semidefinite cone constraint requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and variational analysis on the projection operator in the symmetric matrix space. Without requiring strict complementarity, we prove that, under the constraint nondegeneracy condition and t...
-
作者：Pang, Jong-Shi; Stewart, David E.
作者单位：Rensselaer Polytechnic Institute; Rensselaer Polytechnic Institute; University of Iowa
摘要：This paper introduces and studies the class of differential variational inequalities (DVIs) in a finite-dimensional Euclidean space. The DVI provides a powerful modeling paradigm for many applied problems in which dynamics, inequalities, and discontinuities are present; examples of such problems include constrained time-dependent physical systems with unilateral constraints, differential Nash games, and hybrid engineering systems with variable structures. The DVI unifies several mathematical p...
-
作者：Kalantari, B.; Lari, I.; Ricca, F.; Simeone, B.
作者单位：Sapienza University Rome; Rutgers University System; Rutgers University New Brunswick
摘要：Given an n x m nonnegative matrix A = (a(ij)) and positive integral vectors r is an element of R-n and c is an element of R-m having a common one-norm h, the (r,c)-scaling problem is to obtain positive diagonal matrices X and Y, if they exist, such that XAY has row and column sums equal to r and c, respectively. The entropy minimization problem corresponding to A is to find an n x m matrix z = (z(ij)) having the same zero pattern as A, the sum of whose entries is a given number h, its row and ...
-
作者：Drummond, L. M. Grana; Maculan, N.; Svaiter, B. F.
作者单位：Universidade Federal do Rio de Janeiro; Universidade Federal do Rio de Janeiro
