-
作者：Royset, Johannes O.; Wets, Roger J. -B.
作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School; University of California System; University of California Davis
摘要：Applications in the areas of data fitting, forecasting, and estimation naturally lead to a rich class of constrained infinite-dimensional optimization problems over extended real-valued semicontinuous functions. We discuss a framework for dealing with such applications, even in the presence of nearly arbitrary constraints on the functions. We formulate computationally tractable approximating problems relying on piecewise polynomial semicontinuous approximations of the actual functions. The app...
-
作者：Soma, Tasuku; Yoshida, Yuichi
作者单位：University of Tokyo; Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan
摘要：The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice. Suppose that a nonnegative monotone submodular function f : Zn +. R+ is given via an evaluation oracle. Assume further that f satisfies the diminishing return property, which is not an immediate consequence of submodularity when the domain is the integer lattice. Giv...
-
作者：Bertsimas, Dimitris; Gupta, Vishal; Kallus, Nathan
作者单位：Massachusetts Institute of Technology (MIT); University of Southern California; Cornell University; Cornell University
摘要：Sample average approximation (SAA) is a widely popular approach to data-driven decision-making under uncertainty. Under mild assumptions, SAA is both tractable and enjoys strong asymptotic performance guarantees. Similar guarantees, however, do not typically hold in finite samples. In this paper, we propose a modification of SAA, which we term Robust SAA, which retains SAA's tractability and asymptotic properties and, additionally, enjoys strong finite-sample performance guarantees. The key to...
-
作者：Bodur, Merve; Del Pia, Alberto; Dey, Santanu S.; Molinaro, Marco; Pokutta, Sebastian
作者单位：University of Toronto; University of Wisconsin System; University of Wisconsin Madison; University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
摘要：In this paper, we study the strength of Chvatal-Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs). Aggregation cuts are obtained as follows: given an IP formulation, we first generate a single implied inequality using aggregation of the original constraints, then obtain the integer hull of the set defined by this single inequality with variable bounds, and finally use the inequalities describing the integer hull as cutting-planes. Our first ma...
-
作者：Sun, Jie; Liao, Li-Zhi; Rodrigues, Brian
作者单位：Curtin University; Curtin University; National University of Singapore; Hong Kong Baptist University; Singapore Management University
摘要：A new scheme to cope with two-stage stochastic optimization problems uses a risk measure as the objective function of the recourse action, where the risk measure is defined as the worst-case expected values over a set of constrained distributions. This paper develops an approach to deal with the case where both the first and second stage objective functions are convex linear-quadratic. It is shown that under a standard set of regularity assumptions, this two-stage quadratic stochastic optimiza...
-
作者：Cornuejols, Gerard; Lee, Dabeen
作者单位：Carnegie Mellon University
摘要：In this paper, we consider polytopes P that are contained in the unit hypercube. We provide conditions on the set of 0, 1 vectors not contained in P that guarantee that P has a small Chvatal rank. Our conditions are in terms of the subgraph induced by these infeasible 0,1 vertices in the skeleton graph of the unit hypercube. In particular, we show that when this subgraph contains no 4-cycle, the Chvatal rank is at most 3; and when it has tree width 2, the Chvatal rank is at most 4. We also giv...
-
作者：Orlin, James B.; Schulz, Andreas S.; Udwani, Rajan
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We consider a robust formulation, introduced by Krause et al. (J Artif Intell Res 42: 427- 486, 2011), of the classical cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. The robustness considered is w. r. t. adversarial removal of up to t elements from the chosen set. For the fundamental case of t = 1, we give a deterministic (1 - 1/e) - 1/T(m) approximation algorithm, where m is an input parameter and number of...
-
作者：Attouch, Hedy; Chbani, Zaki; Peypouquet, Juan; Redont, Patrick
作者单位：Universite de Montpellier; Centre National de la Recherche Scientifique (CNRS); Cadi Ayyad University of Marrakech; Universidad Tecnica Federico Santa Maria
摘要：In a Hilbert space setting H, we study the fast convergence properties as t -> +infinity of the trajectories of the second-order differential equation x(t) + alpha/t(x) over dot(t) + del Phi(x(t)) = g(t), where del Phi is the gradient of a convex continuously differentiable function Phi : H -> R, alpha is a positive parameter, and g : [t(0),+infinity[-> H is a small perturbation term. In this inertial system, the viscous damping coefficient alpha/t vanishes asymptotically, but not too rapidly....
-
作者：Guo, Lei; Ye, Jane J.
作者单位：Shanghai Jiao Tong University; University of Victoria
摘要：When the objective function is not locally Lipschitz, constraint qualifications are no longer sufficient for Karush-Kuhn-Tucker (KKT) conditions to hold at a local minimizer, let alone ensuring an exact penalization. In this paper, we extend quasi-normality and relaxed constant positive linear dependence condition to allow the non-Lipschitzness of the objective function and show that they are sufficient for KKT conditions to be necessary for optimality. Moreover, we derive exact penalization r...
-
作者：Lourenco, Bruno F.; Fukuda, Ellen H.; Fukushima, Masao
作者单位：Seikei University; Kyoto University
摘要：In this work, we derive second-order optimality conditions for nonlinear semidefinite programming (NSDP) problems, by reformulating it as an ordinary nonlinear programming problem using squared slack variables. We first consider the correspondence between Karush-Kuhn-Tucker points and regularity conditions for the general NSDP and its reformulation via slack variables. Then, we obtain a pair of no-gap second-order optimality conditions that are essentially equivalent to the ones already consid...
