-
作者：Dahl, Joachim; Andersen, Erling D.
摘要：A new primal-dual interior-point algorithm applicable to nonsymmetric conic optimization is proposed. It is a generalization of the famous algorithm suggested by Nesterov and Todd for the symmetric conic case, and uses primal-dual scalings for nonsymmetric cones proposed by Tuncel. We specialize Tuncel's primal-dual scalings for the important case of 3 dimensional exponential-cones, resulting in a practical algorithm with good numerical performance, on level with standard symmetric cone (e.g.,...
-
作者：Homem-de-Mello, Tito; Kopa, Milos; Morton, David P.
作者单位：Universidad Adolfo Ibanez; Charles University Prague; Northwestern University
-
作者：Gupta, Anupam; Kumar, Amit; Nagarajan, Viswanath; Shen, Xiangkun
作者单位：Carnegie Mellon University; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi; University of Michigan System; University of Michigan; Yahoo! Inc
摘要：We study stochastic combinatorial optimization problems where the objective is to minimize the expected maximum load (a.k.a. the makespan). In this framework, we have a set of n tasks and m resources, where each task j uses some subset of the resources. Tasks have random sizes X-j, and our goal is to non-adaptively select t tasks to minimize the expected maximum load over all resources, where the load on any resource i is the total size of all selected tasks that use i. For example, when resou...
-
作者：Frank, Andras; Murota, Kazuo
作者单位：Eotvos Lorand University; Tokyo Metropolitan University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan
摘要：This paper is concerned with algorithms and applications of decreasing minimization on an M-convex set, which is the set of integral elements of an integral base-polyhedron. Based on a recent characterization of decreasingly minimal (dec-min) elements, we develop a strongly polynomial algorithm for computing a dec-min element of an M-convex set. The matroidal feature of the set of dec-min elements makes it possible to compute a minimum cost dec-min element, as well. Our second goal is to exhib...
-
作者：Laiu, M. Paul; Tits, Andre L.
作者单位：United States Department of Energy (DOE); Oak Ridge National Laboratory; University System of Maryland; University of Maryland College Park; University System of Maryland; University of Maryland College Park
摘要：A framework is proposed for solving general convex quadratic programs (CQPs) from an infeasible starting point by invoking an existing feasible-start algorithm tailored for inequality-constrained CQPs. The central tool is an exact penalty function scheme equipped with a penalty-parameter updating rule. The feasible-start algorithm merely has to satisfy certain general requirements, and so is the updating rule. Under mild assumptions, the framework is proved to converge on CQPs with both inequa...
-
作者：Maehara, Takanori; Nakashima, So; Yamaguchi, Yutaro
作者单位：RIKEN; University of Tokyo; Kyushu University
摘要：We consider a problem of maximizing a monotone DR-submodular function under multiple order-consistent knapsack constraints on a distributive lattice. Because a distributive lattice is used to represent a dependency constraint, the problem can represent a dependency constrained version of a submodular maximization problem on a set. We propose a (1-1/e)-approximation algorithm for this problem. To achieve this result, we generalize the continuous greedy algorithm to distributive lattices: We cho...
-
作者：Quoc Tran-Dinh; Pham, Nhan H.; Phan, Dzung T.; Nguyen, Lam M.
作者单位：University of North Carolina; University of North Carolina Chapel Hill; International Business Machines (IBM); IBM USA
摘要：We introduce a new approach to develop stochastic optimization algorithms for a class of stochastic composite and possibly nonconvex optimization problems. The main idea is to combine a variance-reduced estimator and an unbiased stochastic one to create a new hybrid estimator which trades-off the variance and bias, and possesses useful properties for developing new algorithms. We first introduce our hybrid estimator and investigate its fundamental properties to form a foundational theory for a...
-
作者：Lan, Guanghui
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Stochastic dual dynamic programming is a cutting plane type algorithm for multi-stage stochastic optimization originated about 30 years ago. In spite of its popularity in practice, there does not exist any analysis on the convergence rates of this method. In this paper, we first establish the number of iterations, i.e., iteration complexity, required by a basic dual dynamic programming method for solving single-scenario multi-stage optimization problems, by introducing novel mathematical tools...
-
作者：Dowson, O.; Morton, D. P.; Downward, A.
作者单位：Northwestern University; University of Auckland
摘要：We propose an algorithm for solving a class of bi-objective multistage stochastic linear programs. We show that the cost-to-go functions are saddle functions, and we exploit this structure, developing a new variant of the stochastic dual dynamic programming algorithm. Our algorithm is implemented in the open-source stochastic programming solver SDDP.jl. We apply our algorithm to a hydro-thermal scheduling problem using data from the Brazilian Interconnected Power System. We also propose and im...
-
作者：Shi, Xueyu; Prokopyev, Oleg A.; Zeng, Bo
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
摘要：We study the polyhedral structure of a mixed 0-1 set arising from the submodular maximization problem, given by P = ((w, x) is an element of R x (0, 1)(n) : w <= f (x), x is an element of X), where submodular function f (x) is represented by a concave function composed with an affine function, and X is the feasible region of binary variables x. For X = (0, 1)(n), two families of facet-defining inequalities are proposed for the convex hull of P through restriction and lifting using submodular i...
