-
作者：Faenza, Yuri; Oriolo, Gianpaolo; Stauffer, Gautier
作者单位：Columbia University; University of Rome Tor Vergata; Kedge Business School
摘要：The maximum weighted stable set problem in claw-free graphs is a well-known generalization of the maximum weighted matching problem, and a classical problem in combinatorial optimization. In spite of the recent development of fast(er) combinatorial algorithms and some progresses in the characterization of the corresponding stable set polytope, the problem of providing a decent linear description for this polytope (Grotschel et al. in Geometric algorithms and combinatorial optimization, Springe...
-
作者：Curtis, Frank E.; Robinson, Daniel P.
作者单位：Lehigh University
摘要：A strategy is proposed for characterizing the worst-case performance of algorithms for solving nonconvex smooth optimization problems. Contemporary analyses characterize worst-case performance by providing, under certain assumptions on an objective function, an upper bound on the number of iterations (or function or derivative evaluations) required until a pth-order stationarity condition is approximately satisfied. This arguably leads to conservative characterizations based on certain objecti...
-
作者：Guo, Lei; Chen, Xiaojun
作者单位：East China University of Science & Technology; Hong Kong Polytechnic University
摘要：We consider a class of mathematical programs with complementarity constraints (MPCC) where the objective function involves a non-Lipschitz sparsity-inducing term. Due to the existence of the non-Lipschitz term, existing constraint qualifications for locally Lipschitz MPCC cannot ensure that necessary optimality conditions hold at a local minimizer. In this paper, we present necessary optimality conditions and MPCC-tailored qualifications for the non-Lipschitz MPCC. The proposed qualifications ...
-
作者：Fang, Kun; Fawzi, Hamza
作者单位：University of Cambridge
摘要：We consider the problem of maximizing a homogeneous polynomial on the unit sphere and its hierarchy of sum-of-squares relaxations. Exploiting the polynomial kernel technique, we obtain a quadratic improvement of the known convergence rate by Reznick and Doherty and Wehner. Specifically, we show that the rate of convergence is noworse than O(d(2)/l(2)) in the regime l = Omega(d) where l is the level of the hierarchy and d the dimension, solving a problem left open in the recent paper by de Kler...
-
作者：Bot, Radu Ioan; Csetnek, Ernoe Robert; Laszlo, Szilard Csaba
作者单位：University of Vienna; Technical University of Cluj Napoca
摘要：We investigate the asymptotic properties of the trajectories generated by a second-order dynamical system with Hessian driven damping and a Tikhonov regularization term in connection with the minimization of a smooth convex function in Hilbert spaces. We obtain fast convergence results for the function values along the trajectories. The Tikhonov regularization term enables the derivation of strong convergence results of the trajectory to the minimizer of the objective function of minimum norm.
-
作者：Potschka, Andreas; Bock, Hans Georg
作者单位：Ruprecht Karls University Heidelberg
摘要：We propose a sequential homotopy method for the solution of mathematical programming problems formulated in abstract Hilbert spaces under the Guignard constraint qualification. The method is equivalent to performing projected backward Euler timestepping on a projected gradient/antigradient flow of the augmented Lagrangian. The projected backward Euler equations can be interpreted as the necessary optimality conditions of a primal-dual proximal regularization of the original problem. The regula...
-
作者：Lan, Guanghui; Zhou, Zhiqiang
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：In this paper, we consider multi-stage stochastic optimization problems with convex objectives and conic constraints at each stage. We present a new stochastic first-order method, namely the dynamic stochastic approximation (DSA) algorithm, for solving these types of stochastic optimization problems. We show that DSA can achieve an optimal O(1/epsilon 4) rate of convergence in terms of the total number of required scenarios when applied to a three-stage stochastic optimization problem. We furt...
-
作者：Chen, Xin; Pittel, Boris
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University System of Ohio; Ohio State University
摘要：The standard quadratic optimization problem (StQP), i.e. the problem of minimizing a quadratic form x(T) Qx on the standard simplex {x >= 0 : x(T) e = 1}, is studied. The StQP arises in numerous applications, and it is known to be NP-hard. Chen, Peng and Zhang showed that almost certainly the StQP with a large random matrix Q = Q(T), Q(i, j), (i <= j) being independent and identically concave-distributed, attains its minimum at a point x with support size vertical bar{j : x(j) > 0}vertical bar...
-
作者：Leovey, H.; Roemisch, W.
作者单位：Humboldt University of Berlin
摘要：We consider randomized QMC methods for approximating the expected recourse in two-stage stochastic optimization problems containing mixed-integer decisions in the second stage. It is known that the second-stage optimal value function is piecewise linear-quadratic with possible kinks and discontinuities at the boundaries of certain convex polyhedral sets. This structure is exploited to provide conditions implying that first and higher order terms of the integrand's ANOVA decomposition (Math. Co...
-
作者：Dinh, N.; Goberna, M. A.; Long, D. H.; Volle, M.
作者单位：Vietnam National University Ho Chi Minh City (VNUHCM) System; Universitat d'Alacant; Vietnam National University Ho Chi Minh City (VNUHCM) System; Tien Giang University; Avignon Universite
摘要：Given an infinite family of extended real-valued functions fi, i. I, and a familyHof nonempty finite subsets of I, the H-partial robust sum of fi, i. I, is the supremum, for J. H, of the finite sums j. J f j. These infinite sums arise in a natural way in location problems as well as in functional approximation problems, and include as particular cases the well-known sup function and the so-called robust sum function, corresponding to the set H of all nonempty finite subsets of I, whose unconst...
