1-2期

最新文章

• Regularization methods for optimization problems with probabilistic constraints AI翻译
  作者：Dentcheva, Darinka; Martinez, Gabriela
  作者单位：Stevens Institute of Technology
  摘要：We analyze nonlinear stochastic optimization problems with probabilistic constraints on nonlinear inequalities with random right hand sides. We develop two numerical methods with regularization for their numerical solution. The methods are based on first order optimality conditions and successive inner approximations of the feasible set by progressive generation of p-efficient points. The algorithms yield an optimal solution for problems involving alpha-concave probability distributions. For a...
• A robust optimization approach to experimental design for model discrimination of dynamical systems AI翻译
  作者：Skanda, Dominik; Lebiedz, Dirk
  作者单位：University of Freiburg; Ulm University
  摘要：A high-ranking goal of interdisciplinary modeling approaches in science and engineering are quantitative prediction of system dynamics and model based optimization. Quantitative modeling has to be closely related to experimental investigations if the model is supposed to be used for mechanistic analysis and model predictions. Typically, before an appropriate model of an experimental system is found different hypothetical models might be reasonable and consistent with previous knowledge and ava...
• An exact algorithm for graph partitioning AI翻译
  作者：Hager, William W.; Phan, Dzung T.; Zhang, Hongchao
  作者单位：State University System of Florida; University of Florida; International Business Machines (IBM); IBM USA; Louisiana State University System; Louisiana State University
  摘要：An exact algorithm is presented for solving edge weighted graph partitioning problems. The algorithm is based on a branch and bound method applied to a continuous quadratic programming formulation of the problem. Lower bounds are obtained by decomposing the objective function into convex and concave parts and replacing the concave part by an affine underestimate. It is shown that the best affine underestimate can be expressed in terms of the center and the radius of the smallest sphere contain...
• A very simple SQCQP method for a class of smooth convex constrained minimization problems with nice convergence results AI翻译
  作者：Auslender, Alfred
  作者单位：Centre National de la Recherche Scientifique (CNRS); Ecole Centrale de Lyon; Institut National des Sciences Appliquees de Lyon - INSA Lyon; Universite Claude Bernard Lyon 1; Universite Jean Monnet; Institut Polytechnique de Paris; Ecole Polytechnique
  摘要：We introduce a new and very simple algorithm for a class of smooth convex constrained minimization problems which is an iterative scheme related to sequential quadratically constrained quadratic programming methods, called sequential simple quadratic method (SSQM). The computational simplicity of SSQM, which uses first-order information, makes it suitable for large scale problems. Theoretical results under standard assumptions are given proving that the whole sequence built by the algorithm co...
• On generalizations of network design problems with degree bounds AI翻译
  作者：Bansal, Nikhil; Khandekar, Rohit; Koenemann, Jochen; Nagarajan, Viswanath; Peis, Britta
  作者单位：Eindhoven University of Technology; International Business Machines (IBM); IBM USA; University of Waterloo; Technical University of Berlin
  摘要：Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope of the iterative relaxation method in two directions: (1) by handling more complex degree constraints in the minimum spanning tree problem (namely laminar crossing spanning tree), and (2) by incorporating 'degree bounds' in other combinatorial optimization problems such as matroid intersection and lattice polyhedra....
• A simple LP relaxation for the asymmetric traveling salesman problem AI翻译
  作者：Thanh Nguyen
  作者单位：Northwestern University
  摘要：It is a long-standing open question in combinatorial optimization whether the integrality gap of the subtour linear program relaxation (subtour LP) for the asymmetric traveling salesman problem (ATSP) is a constant. The study on the structure of this linear program is important and extensive. In this paper, we give a new and simpler LP relaxation for the ATSP. Our linear program consists of a single type of constraints that combine both the subtour elimination and the degree constraints in the...
• Strong lift-and-project cutting planes for the stable set problem AI翻译
  作者：Giandomenico, Monia; Rossi, Fabrizio; Smriglio, Stefano
  作者单位：University of L'Aquila
  摘要：A great deal of research has been focusing, since the early seventies, on finding strong relaxations for the stable set problem. Polyhedral combinatorics techniques have been at first developed to strengthen the natural linear formulation. Afterward, strong semidefinite programming relaxations have been deeply investigated. Nevertheless, the resulting integer programming (IP) algorithms cannot be regarded as being quite successful in practice, as most of the relaxations give rise to one out of...
• Enclosing ellipsoids and elliptic cylinders of semialgebraic sets and their application to error bounds in polynomial optimization AI翻译
  作者：Kojima, Masakazu; Yamashita, Makoto
  作者单位：Institute of Science Tokyo; Tokyo Institute of Technology
  摘要：This paper is concerned with a class of ellipsoidal sets (ellipsoids and elliptic cylinders) in which are determined by a freely chosen m x m positive semidefinite matrix. All ellipsoidal sets in this class are similar to each other through a parallel transformation and a scaling around their centers by a constant factor. Based on the basic idea of lifting, we first present a conceptual min-max problem to determine an ellipsoidal set with the smallest size in this class which encloses a given ...
• The tracial moment problem and trace-optimization of polynomials AI翻译
  作者：Burgdorf, Sabine; Cafuta, Kristijan; Klep, Igor; Povh, Janez
  作者单位：University of Neuchatel; University of Ljubljana; University of Maribor; University of Ljubljana
  摘要：The main topic addressed in this paper is trace-optimization of polynomials in noncommuting (nc) variables: given an nc polynomial f, what is the smallest trace can attain for a tuple of matrices ? A relaxation using semidefinite programming (SDP) based on sums of hermitian squares and commutators is proposed. While this relaxation is not always exact, it gives effectively computable bounds on the optima. To test for exactness, the solution of the dual SDP is investigated. If it satisfies a ce...
• Simple bounds for recovering low-complexity models AI翻译
  作者：Candes, Emmanuel; Recht, Benjamin
  作者单位：Stanford University; Stanford University; University of Wisconsin System; University of Wisconsin Madison
  摘要：This note presents a unified analysis of the recovery of simple objects from random linear measurements. When the linear functionals are Gaussian, we show that an s-sparse vector in can be efficiently recovered from 2s log n measurements with high probability and a rank r, n x n matrix can be efficiently recovered from r(6n - 5r) measurements with high probability. For sparse vectors, this is within an additive factor of the best known nonasymptotic bounds. For low-rank matrices, this matches ...