-
作者：Bandeira, A. S.; Scheinberg, K.; Vicente, L. N.
作者单位：Lehigh University; Princeton University; Universidade de Coimbra
摘要：Interpolation-based trust-region methods are an important class of algorithms for Derivative-Free Optimization which rely on locally approximating an objective function by quadratic polynomial interpolation models, frequently built from less points than there are basis components. Often, in practical applications, the contribution of the problem variables to the objective function is such that many pairwise correlations between variables are negligible, implying, in the smooth case, a sparse s...
-
作者：Laraki, R.; Lasserre, J. B.
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; Centre National de la Recherche Scientifique (CNRS); Sorbonne Universite; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier
摘要：We consider two min-max problems (1) minimizing the supremum of finitely many rational functions over a compact basic semi-algebraic set and (2) solving a 2-player zero-sum polynomial game in randomized strategies with compact basic semi-algebraic sets of pure strategies. In both problems the optimal value can be approximated by solving a hierarchy of semidefinite relaxations, in the spirit of the moment approach developed in Lasserre (SIAM J Optim 11:796-817, 2001; Math Program B 112:65-92, 2...
-
作者：Chan, Yuk Hei; Lau, Lap Chi
作者单位：Chinese University of Hong Kong
摘要：The hypergraph matching problem is to find a largest collection of disjoint hyperedges in a hypergraph. This is a well-studied problem in combinatorial optimization and graph theory with various applications. The best known approximation algorithms for this problem are all local search algorithms. In this paper we analyze different linear and semidefinite programming relaxations for the hypergraph matching problem, and study their connections to the local search method. Our main results are th...
-
作者：Schuette, Christof; Winkelmann, Stefanie; Hartmann, Carsten
作者单位：Free University of Berlin
摘要：A numerical scheme for solving high-dimensional stochastic control problems on an infinite time horizon that appear relevant in the context of molecular dynamics is outlined. The scheme rests on the interpretation of the corresponding Hamilton-Jacobi-Bellman equation as a nonlinear eigenvalue problem that, using a logarithmic transformation, can be recast as a linear eigenvalue problem, for which the principal eigenvalue and its eigenfunction are sought. The latter can be computed efficiently ...
-
作者：Gouveia, Joao; Laurent, Monique; Parrilo, Pablo A.; Thomas, Rekha
作者单位：University of Washington; University of Washington Seattle; Universidade de Coimbra; Centrum Wiskunde & Informatica (CWI); Tilburg University; Massachusetts Institute of Technology (MIT)
摘要：The theta bodies of a polynomial ideal are a series of semidefinite programming relaxations of the convex hull of the real variety of the ideal. In this paper we construct the theta bodies of the vanishing ideal of cycles in a binary matroid. Applied to cuts in graphs, this yields a new hierarchy of semidefinite programming relaxations of the cut polytope of the graph. If the binary matroid avoids certain minors we can characterize when the first theta body in the hierarchy equals the cycle po...
-
作者：Pang, Jong-Shi; Han, Lanshan; Ramadurai, Gitakrishnan; Ukkusuri, Satish
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Purdue University System; Purdue University; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Madras
摘要：This paper formally introduces a linear complementarity system (LCS) formulation for a continuous-time, multi-user class, dynamic user equilibrium (DUE) model for the determination of trip timing decisions in a simplified single bottleneck model. Existence of a Lipschitz solution trajectory to the model is established by a constructive time-stepping method whose convergence is rigorously analyzed. The solvability of the time-discretized subproblems by Lemke's algorithm is also proved. Combinin...
-
作者：von Heusinger, Anna; Kanzow, Christian; Fukushima, Masao
作者单位：University of Wurzburg; Kyoto University
摘要：We consider the generalized Nash equilibrium problem (GNEP), where not only the players' cost functions but also their strategy spaces depend on the rivals' decision variables. Existence results for GNEPs are typically shown by using a fixed point argument for a certain set-valued function. Here we use a regularization of this set-valued function in order to obtain a single-valued function that is easier to deal with from a numerical point of view. We show that the fixed points of the latter f...
-
作者：Zheng, Xi Yin; Ng, Kung Fu
作者单位：Yunnan University; Chinese University of Hong Kong
摘要：We first consider subsmoothness for a function family and provide formulas of the subdifferential of the pointwise supremum of a family of subsmooth functions. Next, we consider subsmooth infinite and semi-infinite optimization problems. In particular, we provide several dual and primal characterizations for a point to be a sharp minimum or a weak sharp minimum for such optimization problems.
-
作者：Byrd, Richard H.; Lopez-Calva, Gabriel; Nocedal, Jorge
作者单位：Northwestern University; University of Colorado System; University of Colorado Boulder; Northwestern University
摘要：Line search algorithms for nonlinear programming must include safeguards to enjoy global convergence properties. This paper describes an exact penalization approach that extends the class of problems that can be solved with line search sequential quadratic programming methods. In the new algorithm, the penalty parameter is adjusted at every iteration to ensure sufficient progress in linear feasibility and to promote acceptance of the step. A trust region is used to assist in the determination ...
-
作者：Lu, Zhaosong; Monteiro, Renato D. C.; Yuan, Ming
作者单位：Simon Fraser University; University System of Georgia; Georgia Institute of Technology
摘要：In this paper, we study convex optimization methods for computing the nuclear (or, trace) norm regularized least squares estimate in multivariate linear regression. The so-called factor estimation and selection method, recently proposed by Yuan et al. (J Royal Stat Soc Ser B (Statistical Methodology) 69(3):329-346, 2007) conducts parameter estimation and factor selection simultaneously and have been shown to enjoy nice properties in both large and finite samples. To compute the estimates, howe...
