-
作者：Kuecuekyavuz, Simge
作者单位：University System of Ohio; Ohio State University
摘要：The mixing set with a knapsack constraint arises in deterministic equivalent of chance-constrained programming problems with finite discrete distributions. We first consider the case that the chance-constrained program has equal probabilities for each scenario. We study the resulting mixing set with a cardinality constraint and propose facet-defining inequalities that subsume known explicit inequalities for this set. We extend these inequalities to obtain valid inequalities for the mixing set ...
-
作者：Aloise, Daniel; Hansen, Pierre; Liberti, Leo
作者单位：Universidade Federal do Rio Grande do Norte; Universite de Montreal; HEC Montreal; Institut Polytechnique de Paris; Ecole Polytechnique
摘要：Given a set of entities associated with points in Euclidean space, minimum sum-of-squares clustering (MSSC) consists in partitioning this set into clusters such that the sum of squared distances from each point to the centroid of its cluster is minimized. A column generation algorithm for MSSC was given by du Merle et al. in SIAM Journal Scientific Computing 21:1485-1505. The bottleneck of that algorithm is the resolution of the auxiliary problem of finding a column with negative reduced cost....
-
作者：Ben Gharbia, Ibtihel; Gilbert, J. Charles
作者单位：Universite PSL; Universite Paris-Dauphine
摘要：The plain Newton-min algorithm to solve the linear complementarity problem (LCP for short) can be viewed as a semismooth Newton algorithm without globalization technique to solve the system of piecewise linear equations min(x, Mx + q) = 0, which is equivalent to the LCP. When M is an M-matrix of order n, the algorithm is known to converge in at most n iterations. We show in this paper that this result no longer holds when M is a P-matrix of order a parts per thousand yen 3, since then the algo...
-
作者：Goering, Frank; Helmberg, Christoph; Reiss, Susanna
作者单位：Technische Universitat Chemnitz
摘要：In analogy to the absolute algebraic connectivity of Fiedler, we study the problem of minimizing the maximum eigenvalue of the Laplacian of a graph by redistributing the edge weights. Via semidefinite duality this leads to a graph realization problem in which nodes should be placed as close as possible to the origin while adjacent nodes must keep a distance of at least one. We prove three main results for a slightly generalized form of this embedding problem. First, given a set of vertices par...
-
作者：Alvarez, Felipe; Bolte, Jerome; Bonnans, J. Frederic; Silva, Francisco J.
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; Institut Polytechnique de Paris; Ecole Polytechnique; Universidad de Chile; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universidad de Chile; Universite PSL; Ecole des Hautes Etudes en Sciences Sociales (EHESS); Universite de Toulouse; Universite Toulouse 1 Capitole; Centre National de la Recherche Scientifique (CNRS); Toulouse School of Economics; Sapienza University Rome
摘要：We consider a quadratic optimal control problem governed by a nonautonomous affine ordinary differential equation subject to nonnegativity control constraints. For a general class of interior penalty functions, we provide a first order expansion for the penalized states and adjoint states around the state and adjoint state of the original problem. Our main argument relies on the following fact: if the optimal control satisfies strict complementarity conditions for its Hamiltonian except for a ...
-
作者：Avrachenkov, K.; Burachik, R. S.; Filar, J. A.; Gaitsgory, V.
作者单位：University of South Australia; Inria
摘要：In this paper we study a linear programming problem with a linear perturbation introduced through a parameter epsilon > 0. We identify and analyze an unusual asymptotic phenomenon in such a linear program. Namely, discontinuous limiting behavior of the optimal objective function value of such a linear program may occur even when the rank of the coefficient matrix of the constraints is unchanged by the perturbation. We show that, under mild conditions, this phenomenon is a result of the classic...
-
作者：Buergisser, Peter; Amelunxen, Dennis
作者单位：University of Paderborn
摘要：We perform a smoothed analysis of the GCC-condition number C(A) of the linear programming feasibility problem there exists x is an element of Rm+1 Ax < 0. Suppose that <(A)over bar> is any matrix with rows (a) over bar (i) of euclidean norm 1 and, independently for all i, let a(i) be a random perturbation of (a) over bar (i) following the uniform distribution in the spherical disk in S-m of angular radius arcsin sigma and centered at (a) over bar (i). We prove that E(ln C(A)) = O(mn/sigma). A ...
-
作者：Lan, Guanghui
作者单位：State University System of Florida; University of Florida
摘要：This paper considers an important class of convex programming (CP) problems, namely, the stochastic composite optimization (SCO), whose objective function is given by the summation of general nonsmooth and smooth stochastic components. Since SCO covers non-smooth, smooth and stochastic CP as certain special cases, a valid lower bound on the rate of convergence for solving these problems is known from the classic complexity theory of convex programming. Note however that the optimization algori...
-
作者：Frankowska, Helene; Quincampoix, Marc
作者单位：Centre National de la Recherche Scientifique (CNRS); Sorbonne Universite; Universite de Bretagne Occidentale; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
摘要：This paper is devoted to metric regularity of set-valued maps from a complete metric space to a Banach space. In particular we extend a known characterization of the regularity modulus to maps defined on reflexive spaces. The higher order metric regularity, i.e. an extension of metric regularity to Holder context, is also investigated using high order variations of set-valued maps and results of similar nature are obtained for conical metric regularity.
-
作者：Stein, Oliver
作者单位：Helmholtz Association; Karlsruhe Institute of Technology
摘要：We present a new smoothing approach for mathematical programs with complementarity constraints, based on the orthogonal projection of a smooth manifold. We study regularity of the lifted feasible set and, since the corresponding optimality conditions are inherently degenerate, introduce a regularization approach involving a novel concept of tilting stability. A correspondence between the C-index in the original problem and the quadratic index in the lifted problem is shown. In particular, a lo...
