-
作者：Yuan, Ya-xiang
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：Trust region methods are a class of numerical methods for optimization. Unlike line search type methods where a line search is carried out in each iteration, trust region methods compute a trial step by solving a trust region subproblem where a model function is minimized within a trust region. Due to the trust region constraint, nonconvex models can be used in trust region subproblems, and trust region algorithms can be applied to nonconvex and ill-conditioned problems. Normally it is easier ...
-
作者：Fujishige, Satoru; Massberg, Jens
作者单位：Kyoto University; Ulm University
摘要：We introduce a concept of dual consistency of systems of linear inequalities with full generality. We show that a cardinality constrained polytope is represented by a certain system of linear inequalities if and only if the systems of linear inequalities associated with the cardinalities are dual consistent. Typical dual consistent systems of inequalities are those which describe polymatroids, generalized polymatroids, and dual greedy polyhedra with certain choice functions. We show that the s...
-
作者：Kolda, Tamara G.
作者单位：United States Department of Energy (DOE); Sandia National Laboratories
摘要：We consider the problem of decomposing a real-valued symmetric tensor as the sum of outer products of real-valued vectors. Algebraic methods exist for computing complex-valued decompositions of symmetric tensors, but here we focus on real-valued decompositions, both unconstrained and nonnegative, for problems with low-rank structure. We discuss when solutions exist and how to formulate the mathematical program. Numerical results show the properties of the proposed formulations (including one t...
-
作者：Guerbuzbalaban, M.; Ozdaglar, A.; Parrilo, P.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：Motivated by machine learning problems over large data sets and distributed optimization over networks, we develop and analyze a new method called incremental Newton method for minimizing the sum of a large number of strongly convex functions. We show that our method is globally convergent for a variable stepsize rule. We further show that under a gradient growth condition, convergence rate is linear for both variable and constant stepsize rules. By means of an example, we show that without th...
-
作者：Cominetti, Roberto
作者单位：Universidad de Chile
摘要：We provide a brief introduction to the basic models used to describe traffic on congested networks, both in urban transport and telecommunications. We discuss traffic equilibrium models, covering atomic and non-atomic routing games, with emphasis on situations where the travel times are subject to random fluctuations. We use convex optimization to present the models in a unified framework that stresses the common underlying structures. As a prototypical example of traffic equilibrium with elas...
-
作者：Fawzi, Hamza; Gouveia, Joao; Parrilo, Pablo A.; Robinson, Richard Z.; Thomas, Rekha R.
作者单位：Massachusetts Institute of Technology (MIT); Universidade de Coimbra; University of Washington; University of Washington Seattle
摘要：Let M is an element of R-pxq be a nonnegative matrix. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices of size such that . The psd rank has many appealing geometric interpretations, including semidefinite representations of polyhedra and information-theoretic applications. In this paper we develop and survey the main mathematical properties of psd rank, including its geometry, relationships with other rank notions, an...
-
作者：Goemans, Michel X.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：In this note, we consider the permutahedron, the convex hull of all permutations of . We show how to obtain an extended formulation for this polytope from any sorting network. By using the optimal Ajtai-Komls-Szemer,di sorting network, this extended formulation has variables and inequalities. Furthermore, from basic polyhedral arguments, we show that this is best possible (up to a multiplicative constant) since any extended formulation has at least inequalities. The results easily extend to th...
-
作者：Leovey, H.; Roemisch, W.
作者单位：Humboldt University of Berlin
摘要：Quasi-Monte Carlo (QMC) algorithms are studied for generating scenarios to solve two-stage linear stochastic programming problems. Their integrands are piecewise linear-quadratic, but do not belong to the function spaces considered for QMC error analysis. We show that under some weak geometric condition on the two-stage model all terms of their ANOVA decomposition, except the one of highest order, are continuously differentiable and second order mixed derivatives exist almost everywhere and be...
-
作者：Conforti, Michele; Gerards, Bert; Pashkovich, Kanstantsin
作者单位：University of Padua; University of Waterloo
摘要：We develop decomposition/composition tools for efficiently solving maximum weight stable sets problems as well as for describing them as polynomially sized linear programs (using compact systems). Some of these are well-known but need some extra work to yield polynomial decomposition schemes. We apply the tools to graphs with no even hole and no cap. A hole is a chordless cycle of length greater than three and a cap is a hole together with an additional node that is adjacent to two adjacent no...
-
作者：Fiorini, Samuel; Pashkovich, Kanstantsin
作者单位：Universite Libre de Bruxelles; University of Padua
摘要：An extended formulation of a polytope is a linear description of this polytope using extra variables besides the variables in which the polytope is defined. The interest of extended formulations is due to the fact that many interesting polytopes have extended formulations with a lot fewer inequalities than any linear description in the original space. This motivates the development of methods for, on the one hand, constructing extended formulations and, on the other hand, proving lower bounds ...
