-
作者：Borgwardt, Steffen; Finhold, Elisabeth; Hemmecke, Raymond
作者单位：Technical University of Munich
摘要：Both the combinatorial and the circuit diameter of polyhedra are of interest to the theory of linear programming for their intimate connection to a best-case performance of linear programming algorithms. We study the diameters of dual network flow polyhedra associated to b-flows on directed graphs and prove quadratic upper bounds for both of them: the minimum of and for the combinatorial diameter, and for the circuit diameter. Previously, bounds on these diameters have only been known for bipa...
-
作者：Byrd, Richard H.; Chin, Gillian M.; Nocedal, Jorge; Oztoprak, Figen
作者单位：University of Colorado System; University of Colorado Boulder; Northwestern University; Istanbul Bilgi University
摘要：This paper is concerned with the minimization of an objective that is the sum of a convex function f and an regularization term. Our interest is in active-set methods that incorporate second-order information about the function f to accelerate convergence. We describe a semismooth Newton framework that can be used to generate a variety of second-order methods, including block active set methods, orthant-based methods and a second-order iterative soft-thresholding method. The paper proposes a n...
-
作者：Gfrerer, Helmut; Klatte, Diethard
作者单位：Johannes Kepler University Linz; University of Zurich
摘要：This paper studies stability aspects of solutions of parametric mathematical programs and generalized equations, respectively, with disjunctive constraints. We present sufficient conditions that, under some constraint qualifications ensuring metric subregularity of the constraint mapping, continuity results of upper Lipschitz and upper Holder type, respectively, hold. Furthermore, we apply the above results to parametric mathematical programs with equilibrium constraints and demonstrate, how s...
-
作者：Fountoulakis, Kimon; Gondzio, Jacek
作者单位：University of Edinburgh; University of Edinburgh; Heriot Watt University
摘要：In this paper a robust second-order method is developed for the solution of strongly convex -regularized problems. The main aim is to make the proposed method as inexpensive as possible, while even difficult problems can be efficiently solved. The proposed approach is a primal-dual Newton conjugate gradients (pdNCG) method. Convergence properties of pdNCG are studied and worst-case iteration complexity is established. Numerical results are presented on synthetic sparse least-squares problems a...
-
作者：Sanjeevi, Sujeevraja; Masihabadi, Sina; Kianfar, Kiavash
作者单位：Texas A&M University System; Texas A&M University College Station
摘要：Based on a bijective mapping between two mixed integer sets, we introduce a new perspective on developing cuts for the mixed integer polyhedral conic (MIPC) set by establishing a one-to-one correspondence between the cuts for this set and those for a related mixed integer knapsack (MIK) set. The face/facet-defining properties of the corresponding cuts are identical for their respective sets. We further show that the cut generation approach for the MIPC set resulting from this new perspective a...
-
作者：Wolsey, Laurence A.; Yaman, Hande
作者单位：Universite Catholique Louvain; Ihsan Dogramaci Bilkent University
摘要：We study two continuous knapsack sets and with integer, one unbounded continuous and bounded continuous variables in either or form. When the coefficients of the integer variables are integer and divisible, we show in both cases that the convex hull is the intersection of the bound constraints and polyhedra arising as the convex hulls of continuous knapsack sets with a single unbounded continuous variable. The latter convex hulls are completely described by an exponential family of partition i...
-
作者：Carrizo, Gabriel A.; Lotito, Pablo A.; Maciel, Maria C.
作者单位：National University of the South; Instituto de Investigaciones en Ingenieria Electrica (IIIE); Comision Nacional de Energia Atomica (CNEA)
摘要：A trust-region-based algorithm for the nonconvex unconstrained multiobjective optimization problem is considered. It is a generalization of the algorithm proposed by Fliege et al. (SIAM J Optim 20:602-626, 2009), for the convex problem. Similarly to the scalar case, at each iteration a subproblem is solved and the step needs to be evaluated. Therefore, the notions of decrease condition and of predicted reduction are adapted to the vectorial case. A rule to update the trust region radius is int...
-
作者：Kucukyavuz, Simge; Noyan, Nilay
作者单位：University System of Ohio; Ohio State University; Sabanci University
摘要：We consider a class of stochastic optimization problems that features benchmarking preference relations among random vectors representing multiple random performance measures (criteria) of interest. Given a benchmark random performance vector, preference relations are incorporated into the model as constraints, which require the decision-based random vector to be preferred to the benchmark according to a relation based on multivariate conditional value-at-risk (CVaR) or second-order stochastic...
-
作者：Baes, Michel; Oertel, Timm; Weismantel, Robert
作者单位：University of Zurich; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We extend in two ways the standard Karush-Kuhn-Tucker optimality conditions to problems with a convex objective, convex functional constraints, and the extra requirement that some of the variables must be integral. While the standard Karush-Kuhn-Tucker conditions involve separating hyperplanes, our extension is based on mixed-integer-free polyhedra. Our optimality conditions allow us to define an exact dual of our original mixed-integer convex problem.
-
作者：Condat, Laurent
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：A new algorithm is proposed to project, exactly and in finite time, a vector of arbitrary size onto a simplex or an -norm ball. It can be viewed as a Gauss-Seidel-like variant of Michelot's variable fixing algorithm; that is, the threshold used to fix the variables is updated after each element is read, instead of waiting for a full reading pass over the list of non-fixed elements. This algorithm is empirically demonstrated to be faster than existing methods.
