-
作者：Marandi, Ahmadreza; den Hertog, Dick
作者单位：Tilburg University
摘要：Adjustable robust optimization (ARO) generally produces better worst-case solutions than static robust optimization (RO). However, ARO is computationally more difficult than RO. In this paper, we provide conditions under which the worst-case objective values of ARO and RO problems are equal. We prove that when the uncertainty is constraint-wise, the problem is convex with respect to the adjustable variables and concave with respect to the uncertain parameters, the adjustable variables lie in a...
-
作者：Yang, Boshi; Anstreicher, Kurt; Burer, Samuel
作者单位：Clemson University; University of Iowa
摘要：Let be a quadratically constrained, possibly nonconvex, bounded set, and let denote ellipsoids contained in with non-intersecting interiors. We prove that minimizing an arbitrary quadratic over is no more difficult than minimizing over in the following sense: if a given semidefinite-programming (SDP) relaxation for is tight, then the addition of l linear constraints derived from yields a tight SDP relaxation for . We also prove that the convex hull of equals the intersection of the convex hull...
-
作者：Xu, Huifu; Liu, Yongchao; Sun, Hailin
作者单位：University of Southampton; Dalian University of Technology; Nanjing University of Science & Technology
摘要：A key step in solving minimax distributionally robust optimization (DRO) problems is to reformulate the inner maximization w.r.t. probability measure as a semiinfinite programming problem through Lagrange dual. Slater type conditions have been widely used for strong duality (zero dual gap) when the ambiguity set is defined through moments. In this paper, we investigate effective ways for verifying the Slater type conditions and introduce other conditions which are based on lower semicontinuity...
-
作者：Raymond, Annie; Saunderson, James; Singh, Mohit; Thomas, Rekha R.
作者单位：University of Washington; University of Washington Seattle; Monash University; University System of Georgia; Georgia Institute of Technology
摘要：We consider the problem of finding sum of squares (sos) expressions to establish the non-negativity of a symmetric polynomial over a discrete hypercube whose coordinates are indexed by the k-element subsets of [n]. For simplicity, we focus on the case , but our results extend naturally to all values of . We develop a variant of the Gatermann-Parrilo symmetry-reduction method tailored to our setting that allows for several simplifications and a connection to flag algebras. We show that every sy...
-
作者：Eckstein, Jonathan; Yao, Wang
作者单位：Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick
摘要：We derive a new approximate version of the alternating direction method of multipliers (ADMM) which uses a relative error criterion. The new version is somewhat restrictive and allows only one of the two subproblems to be minimized approximately, but nevertheless covers commonly encountered special cases. The derivation exploits the long-established relationship between the ADMM and both the proximal point algorithm (PPA) and Douglas-Rachford (DR) splitting for maximal monotone operators, alon...
-
作者：Liu, Minghui; Pataki, Gabor
作者单位：SAS Institute Inc; University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
摘要：In conic linear programming-in contrast to linear programming-the Lagrange dual is not an exact dual: it may not attain its optimal value, or there may be a positive duality gap. The corresponding Farkas' lemma is also not exact (it does not always prove infeasibility). We describe exact duals, and certificates of infeasibility and weak infeasibility for conic LPs which are nearly as simple as the Lagrange dual, but do not rely on any constraint qualification. Some of our exact duals generaliz...
-
作者：Soledad Aronna, M.; Bonnans, J. Frederic; Kroner, Axel
作者单位：Getulio Vargas Foundation; Institut Polytechnique de Paris; Ecole Polytechnique; ENSTA Paris; Universite Paris Saclay
-
作者：Bertsimas, Dimitris; Georghiou, Angelos
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); McGill University
摘要：Decision rules provide a flexible toolbox for solving computationally demanding, multistage adaptive optimization problems. There is a plethora of real-valued decision rules that are highly scalable and achieve good quality solutions. On the other hand, existing binary decision rule structures tend to produce good quality solutions at the expense of limited scalability and are typically confined to worst-case optimization problems. To address these issues, we first propose a linearly parameter...
-
作者：Royset, Johannes O.
作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School
摘要：Approximation is central to many optimization problems and the supporting theory provides insight as well as foundation for algorithms. In this paper, we lay out a broad framework for quantifying approximations by viewing finite- and infinite-dimensional constrained minimization problems as instances of extended real-valued lower semicontinuous functions defined on a general metric space. Since the Attouch-Wets distance between such functions quantifies epi-convergence, we are able to obtain e...
-
作者：El Housni, Omar; Goyal, Vineet
作者单位：Columbia University
摘要：In this paper, we consider two-stage adjustable robust linear optimization problems under uncertain constraints and study the performance of piecewise static policies. These are a generalization of static policies where we divide the uncertainty set into several pieces and specify a static solution for each piece. We show that in the worst-case, there is no piecewise static policy with a polynomial number of pieces that has a significantly better performance than an optimal static policy. This...
