-
作者：Yu, Jing; Anitescu, Mihai
作者单位：University of Chicago; United States Department of Energy (DOE); Argonne National Laboratory
摘要：We present a numerical method for approximating the solution of convex integer programs stemming from optimal experimental design. The statistical setup consists of a Bayesian framework for linear inverse problems for which the direct relationship is described by a discretized integral equation. Specifically, we aim to find the optimal sensor placement from a set of candidate locations where data are collected with measurement error. The convex objective function is a measure of the uncertaint...
-
作者：Zhan, Yang; Dang, Chuangyin
作者单位：Nanjing University; City University of Hong Kong
摘要：In the general equilibrium with incomplete asset markets (GEI) model, the excess demand functions are typically not continuous at the prices for which the assets have redundant returns. The reason is that, at these prices, the return matrix drops rank and households' budget sets collapse suddenly. This discontinuity results in a serious problem for the existence and computation of general equilibrium. In this paper, we show that this problem can be resolved with a new return matrix, which has ...
-
作者：Kocvara, Michal
作者单位：University of Birmingham; Czech Academy of Sciences; Institute of Information Theory & Automation of the Czech Academy of Sciences
摘要：Decomposition of large matrix inequalities for matrices with chordal sparsity graph has been recently used by Kojima et al. (Math Program 129(1):33-68, 2011) to reduce problem size of large scale semidefinite optimization (SDO) problems and thus increase efficiency of standard SDO software. A by-product of such a decomposition is the introduction of new dense small-size matrix variables. We will show that for arrow type matrices satisfying suitable assumptions, the additional matrix variables ...
-
作者：Dinh The Luc; Volle, Michel
作者单位：Ton Duc Thang University; Ton Duc Thang University; Avignon Universite
摘要：We establish necessary and sufficient conditions for strong duality of extended monotropic optimization problems with possibly infinite sum of separable functions. The results are applied to a minimization problem of the infinite sum of proper convex functions. We consider a truncation method for duality and obtain the zero duality gap by using only dual variable of finite support. An application to minimum cost flow problems in infinite networks is also discussed.
-
作者：Beer, G.; Canovas, M. J.; Lopez, M. A.; Parra, J.
作者单位：California State University System; California State University Los Angeles; Universidad Miguel Hernandez de Elche; Universitat d'Alacant; Federation University Australia
摘要：This paper analyzes the Lipschitz behavior of the feasible set mapping associated with linear and convex inequality systems in R-n. To start with, we deal with the parameter space of linear (finite/semi-infinite) systems identified with the corresponding sets of coefficient vectors, which are assumed to be closed subsets of Rn+1. In this framework the size of perturbations is measured by means of the (extended) Hausdorff distance. A direct antecedent, extensively studied in the literature, com...
-
作者：Letchford, Adam N.; Vu, Anh N.
作者单位：Lancaster University
摘要：We present a new tool for generating cutting planes for NP\-hard combinatorial optimisation problems. It is based on the concept of gadgets-small subproblems that are glued together to form hard problems-which we borrow from the literature on computational complexity. Using gadgets, we are able to derive huge (exponentially large) new families of strong (and sometimes facet-defining) cutting planes, accompanied by efficient separation algorithms. We illustrate the power of this approach on the...
-
作者：Xia, Yong; Yang, Meijia; Wang, Shu
作者单位：Beihang University; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：We study the n-dimensional problem of finding the smallest ball enclosing the intersection of p given balls, the so-called Chebyshev center problem (CCB). It is a minimax optimization problem and the inner maximization is a uniform quadratic optimization problem (UQ). When p = n, (UQ) is known to enjoy a strong duality and consequently (CCB) is solved via a standard convex quadratic programming (SQP). In this paper, we first prove that (CCB) is NP-hard and the special case when n = 2 is polyno...
-
作者：Davarnia, Danial; Van Hoeve, Willem-Jan
作者单位：Iowa State University; Carnegie Mellon University
摘要：As an alternative to traditional integer programming (IP), decision diagrams (DDs) provide a new solution technology for discrete problems exploiting their combinatorial structure and dynamic programming representation. While the literature mainly focuses on the competitive aspects of DDs as a stand-alone solver, we investigate their complementary role by introducing IP techniques that can be derived from DDs and used in conjunction with IP to enhance the overall performance. This perspective ...
-
作者：Chen, X.; Toint, Ph L.
作者单位：Hong Kong Polytechnic University; University of Namur
摘要：This paper studies high-order evaluation complexity for partially separable convexly-constrained optimization involving non-Lipschitzian group sparsity terms in a nonconvex objective function. We propose a partially separable adaptive regularization algorithm using a pth order Taylor model and show that the algorithm needs at most O((p+1)/(p-q+1)) evaluations of the objective function and its first p derivatives (whenever they exist) to produce an (d)-approximate qth-order stationary point. Ou...
