-
作者：Hanasusanto, Grani A.; Kuhn, Daniel; Wallace, Stein W.; Zymler, Steve
作者单位：Imperial College London; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Norwegian School of Economics (NHH)
摘要：We present a risk-averse multi-dimensional newsvendor model for a class of products whose demands are strongly correlated and subject to fashion trends that are not fully understood at the time when orders are placed. The demand distribution is known to be multimodal in the sense that there are spatially separated clusters of probability mass but otherwise lacks a complete description. We assume that the newsvendor hedges against distributional ambiguity by minimizing the worst-case risk of th...
-
作者：Gustavsson, Emil; Patriksson, Michael; Stromberg, Ann-Brith
作者单位：Chalmers University of Technology; University of Gothenburg
摘要：When solving a convex optimization problem through a Lagrangian dual reformulation subgradient optimization methods are favorably utilized, since they often find near-optimal dual solutions quickly. However, an optimal primal solution is generally not obtained directly through such a subgradient approach unless the Lagrangian dual function is differentiable at an optimal solution. We construct a sequence of convex combinations of primal subproblem solutions, a so called ergodic sequence, which...
-
作者：Tapia, Richard
作者单位：Rice University
摘要：In this paper we present several representation theorems and averaging theorems for members of the difference class of secant updates introduced by Brodlie et al. (J Inst Math Appl 11:73-82, 1973). Major contributions are that the integral form of the mean-value theorem leads to a proof that the BFGS update is pointwise the infinite average of all the updates on the one-dimension manifold in the Dennis class that connects the DFP secant update to the Greenstadt update, and that it can be expre...
-
作者：Bertsimas, Dimitris; Goyal, Vineet; Lu, Brian Y.
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Columbia University
摘要：In this paper, we study the performance of static solutions for two-stage adjustable robust linear optimization problems with uncertain constraint and objective coefficients and give a tight characterization of the adaptivity gap. Computing an optimal adjustable robust optimization problem is often intractable since it requires to compute a solution for all possible realizations of uncertain parameters (Feige et al. in Lect Notes Comput Sci 4513:439-453, 2007). On the other hand, a static solu...
-
作者：Locatelli, Marco
作者单位：University of Parma
摘要：The Lovasz and Lovasz-Schrijver bounds are well known upper bounds for the clique number of a graph, based on the solution of semidefinite programming problems. Both bounds can be seen as obtained through a relaxation of a completely positive formulation of the maximum clique problem. In this paper we propose to improve these bounds by adding inequalities based on independent sets, which may be non-valid, in the sense that they may be violated by optimal solutions of the completely positive fo...
-
作者：Correa, Jose; Marchetti-Spaccamela, Alberto; Matuschke, Jannik; Stougie, Leen; Svensson, Ola; Verdugo, Victor; Verschae, Jose
作者单位：Universidad de Chile; Sapienza University Rome; Technical University of Berlin; Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI); Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
摘要：A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by different machines while incurring an arbitrary setup time. In this paper we present increasingly stronger LP-relaxations for this problem and their implications on the approximability of the problem. First we show that the straightforward LP, extending the approach for the original problem, has an integrality gap of 3 and yields an approximation algorithm of the same fa...
-
作者：Marchetti-Spaccamela, Alberto; Rutten, Cyriel; van der Ster, Suzanne; Wiese, Andreas
作者单位：Sapienza University Rome; Maastricht University; Vrije Universiteit Amsterdam; Max Planck Society
摘要：We study the problem of assigning sporadic tasks to unrelated machines such that the tasks on each machine can be feasibly scheduled. Despite its importance for modern real-time systems, this problem has not been studied before. We present a polynomial-time algorithm which approximates the problem with a constant speedup factor of and show that any polynomial-time algorithm needs a speedup factor of at least , unless P NP. In the case of a constant number of machines we give a polynomial-time ...
-
作者：Waldspurger, Irene; d'Aspremont, Alexandre; Mallat, Stephane
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
摘要：Phase retrieval seeks to recover a signal from the amplitude of linear measurements . We cast the phase retrieval problem as a non-convex quadratic program over a complex phase vector and formulate a tractable relaxation (called PhaseCut) similar to the classical MaxCut semidefinite program. We solve this problem using a provably convergent block coordinate descent algorithm whose structure is similar to that of the original greedy algorithm in Gerchberg and Saxton (Optik 35:237-246, 1972), wh...
-
作者：Bertsimas, Dimitris; Bidkhori, Hoda
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We consider two-stage adjustable robust linear optimization problems with uncertain right hand side b belonging to a convex and compact uncertainty set u. We provide an a priori approximation bound on the ratio of the optimal affine (in b) solution to the optimal adjustable solution that depends on two fundamental geometric properties of u: (a) the symmetry and (b) the simplex dilation factor of the uncertainty set u and provides deeper insight on the power of affine policies for this class of...
-
作者：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...
