-
作者：Vicente, L. N.; Custodio, A. L.
作者单位：Universidade de Coimbra
摘要：It is known that the Clarke generalized directional derivative is nonnegative along the limit directions generated by directional direct-search methods at a limit point of certain subsequences of unsuccessful iterates, if the function being minimized is Lipschitz continuous near the limit point. In this paper we generalize this result for discontinuous functions using Rockafellar generalized directional derivatives (upper subderivatives). We show that Rockafellar derivatives are also nonnegati...
-
作者：Dash, Sanjeeb; Fukasawa, Ricardo; Guenluek, Oktay
作者单位：International Business Machines (IBM); IBM USA; University of Waterloo
摘要：The master equality polyhedron (MEP) is a canonical set that generalizes the master cyclic group polyhedron (MCGP) of Gomory. We recently characterized a nontrivial polar for the MEP, i.e., a polyhedron T such that an inequality defines a nontrivial facet of the MEP if and only if its coefficient vector forms a vertex of T. In this paper, we study the MEP when it is defined by m > 1 rows. We define the notion of a polaroid, a set containing all nontrivial facet defining inequalities. We show h...
-
作者：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....
-
作者：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.
