-
作者：Bian, Wei; Chen, Xiaojun
作者单位：Harbin Institute of Technology; Hong Kong Polytechnic University
摘要：In this paper, we consider a class of constrained optimization problems where the feasible set is a general closed convex set, and the objective function has a nonsmooth, nonconvex regularizer. Such a regularizer includes widely used SCAD, MCP, logistic, fraction, hard thresholding, and non-Lipschitz L-p penalties as special cases. Using the theory of the generalized directional derivative and the tangent cone, we derive a first order necessary optimality condition for local minimizers of the ...
-
作者：He, Shuangchi; Yao, Dacheng; Zhang, Hanqin
作者单位：National University of Singapore; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; National University of Singapore
摘要：We consider a continuous-review inventory system in which the setup cost of each order is a general function of the order quantity and the demand process is modeled as a Brownian motion with a positive drift. Assuming the holding and shortage cost to be a convex function of the inventory level, we obtain the optimal ordering policy that minimizes the long-run average cost by a lower bound approach. To tackle some technical issues in the lower bound approach under the quantity-dependent setup c...
-
作者：Iriarte, Benjamin
作者单位：Massachusetts Institute of Technology (MIT)
摘要：Given an underlying undirected simple graph, we consider the set of its acyclic orientations. Each of these orientations induces a partial order on the vertices of our graph and, therefore, we can count the number of linear extensions of these posets. We want to know which choice of orientation maximizes the number of linear extensions of the corresponding poset, and this problem will be solved essentially for comparability graphs and odd cycles, presenting several proofs. The corresponding en...
-
作者：de Klerk, Etienne; Lasserre, Jean B.; Laurent, Monique; Sun, Zhao
作者单位：Tilburg University; Delft University of Technology; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Centrum Wiskunde & Informatica (CWI)
摘要：We provide a monotone nonincreasing sequence of upper bounds f(k)(H) (k >= 1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube in R-n. The novelty with respect to the converging sequence of upper bounds in Lasserre [Lasserre JB (2010) A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21: 864-885] is that only elementary computations are required. For optimization over the hypercube [0,1](n), we show that the new boun...
-
作者：Fujishige, Satoru; Goemans, Michel X.; Harks, Tobias; Peis, Britta; Zenklusen, Rico
作者单位：Kyoto University; Massachusetts Institute of Technology (MIT); University of Augsburg; RWTH Aachen University; Swiss Federal Institutes of Technology Domain; ETH Zurich; Johns Hopkins University
摘要：The famous Braess paradox describes the counterintuitive phenomenon in which, in certain settings, an increase of resources, such as a new road built within a congested network, may in fact lead to larger costs for the players in an equilibrium. In this paper, we consider general nonatomic congestion games and give a characterization of the combinatorial property of strategy spaces for which the Braess paradox does not occur. In short, matroid bases are precisely the required structure. We pro...
-
作者：De Angelis, Tiziano; Federico, Salvatore; Ferrari, Giorgio
作者单位：University of Leeds; University of Siena; University of Bielefeld
摘要：This paper examines a Markovian model for the optimal irreversible investment problem of a firm aiming at minimizing total expected costs of production. We model market uncertainty and the cost of investment per unit of production capacity, as two independent one-dimensional regular diffusions, and we consider a general convex running cost function. The optimization problem is set as a three-dimensional degenerate singular stochastic control problem. We provide the optimal control as the solut...
-
作者：Fawzi, Hamza; Saunderson, James; Parrilo, Pablo A.
作者单位：University of Cambridge; Monash University; Massachusetts Institute of Technology (MIT)
摘要：Given a polytope P subset of R-n, we say that P has a positive semidefinite lift (psd lift) of size d if one can express P as the projection of an affine slice of the d x d positive semidefinite cone. Such a representation allows us to solve linear optimization problems over P using a semidefinite program of size d and can be useful in practice when d is much smaller than the number of facets of P. If a polytope P has symmetry, we can consider equivariant psd lifts, i.e., those psd lifts that ...
-
作者：Duer, Mirjam; Jargalsaikhan, Bolor; Still, Georg
作者单位：Universitat Trier; University of Groningen; University of Twente
摘要：This paper is concerned with so-called generic properties of general linear conic programs. Many results have been obtained on this subject during the last two decades. For example, it is known that uniqueness, strict complementarity, and nondegeneracy of optimal solutions hold for almost all problem instances. Strong duality holds generically in a stronger sense, i.e., it holds for a generic subset of problem instances. In this paper, we survey known results and present new ones. In particula...
-
作者：Averkov, Gennadiy; Kruempelmann, Jan; Weltge, Stefan
作者单位：Otto von Guericke University; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：Lattice-free sets and their applications for cutting-plane methods in mixed-integer optimization have been studied in recent literature. The family of all integral lattice-free polyhedra that are not properly contained in another integral lattice-free polyhedron has been of particular interest. We call these polyhedra Z(d)-maximal. For fixed d, the family of Z(d)-maximal integral lattice-free polyhedra is finite up to unimodular equivalence. In view of possible applications in cutting-plane th...
-
作者：Dutting, Paul; Gkatzelis, Vasilis; Roughgarden, Tim
作者单位：University of London; London School Economics & Political Science; Drexel University; Stanford University
摘要：Deferred-acceptance auctions are mechanisms whose allocation rule can be implemented using an adaptive reverse greedy algorithm. Milgrom and Segal recently introduced these auctions and proved that they satisfy remarkable incentive guarantees: in addition to being dominant strategy and incentive compatible, they are weakly group-strategyproof and can be implemented by ascending-clock auctions. Neither forward greedy mechanisms nor the VCG mechanism generally possess any of these additional inc...
