-
作者：Mordukhovich, Boris S.; Perez-Aros, Pedro
作者单位：Wayne State University; Universidad de O'Higgins
摘要：This paper develops new extremal principles of variational analysis that are motivated by applications to constrained problems of stochastic programming and semi-infinite programming without smoothness and/or convexity assumptions. These extremal principles concern measurable set-valued mappings/multifunctions with values in finite-dimensional spaces and are established in both approximate and exact forms. The obtained principles are instrumental to derive via variational approaches integral r...
-
作者：Ta, Thuy Anh; Mai, Tien; Bastin, Fabian; L'Ecuyer, Pierre
作者单位：Singapore-MIT Alliance for Research & Technology Centre (SMART); Universite de Montreal; Universite de Montreal
摘要：We consider a multistage stochastic discrete program in which constraints on any stage might involve expectations that cannot be computed easily and are approximated by simulation. We study asample average approximation(SAA) approach that uses nested sampling, in which at each stage, a number of scenarios are examined and a number of simulation replications are performed for each scenario to estimate the next-stage constraints. This approach provides an approximate solution to the multistage p...
-
作者：Boehnlein, Toni; Kratsch, Stefan; Schaudt, Oliver
作者单位：University of Cologne; University of Bonn; RWTH Aachen University
摘要：In a Stackelberg Pricing Game a distinguished player, the leader, chooses prices for a set of items, and the other players, the followers, each seek to buy a minimum cost feasible subset of the items. The goal of the leader is to maximize her revenue, which is determined by the sold items and their prices. Most previously studied cases of such games can be captured by a combinatorial model where we have a base set of items, some with fixed prices, some priceable, and constraints on the subsets...
-
作者：Ouyang, Yuyuan; Xu, Yangyang
作者单位：Clemson University; Rensselaer Polytechnic Institute
摘要：On solving a convex-concave bilinear saddle-point problem (SPP), there have been many works studying the complexity results of first-order methods. These results are all about upper complexity bounds, which can determine at most how many iterations would guarantee a solution of desired accuracy. In this paper, we pursue the opposite direction by deriving lower complexity bounds of first-order methods on large-scale SPPs. Our results apply to the methods whose iterates are in the linear span of...
-
作者：Perez-Aros, Pedro; Salas, David; Vilches, Emilio
作者单位：Universidad de O'Higgins; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universidad de Chile
摘要：We show, in Hilbert space setting, that any two convex proper lower semicontinuous functions bounded from below, for which the norm of their minimal subgradients coincide, they coincide up to a constant. Moreover, under classic boundary conditions, we provide the same results when the functions are continuous and defined over an open convex domain. These results show that for convex functions bounded from below, the slopes provide sufficient first-order information to determine the function up...
-
作者：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...
