-
作者：Stewart, David E.
作者单位：University of Iowa
摘要：In this paper we consider the question of which matrices M give unique solutions for Differential Complementarity Problems (Mandelbaum 1989, unpublished manuscript) of the form dw/dt = Mz + q(t), w(0) = w(0) K ?? z(t) perpendicular to w(t) is an element of K* for all t, for all q and w(0) is an element of K* where K is a closed convex cone. Explicit descriptions of the set of such matrices are given for the 2 x 2 case; the set of such M's independent of K is a strict subset of the set of posit...
-
作者：Kiwiel, K. C.; Lemarechal, C.
作者单位：Inria
摘要：We give a bundle method for constrained convex optimization. Instead of using penalty functions, it shifts iterates towards feasibility, by way of a Slater point, assumed to be known. Besides, the method accepts an oracle delivering function and subgradient values with unknown accuracy. Our approach is motivated by a number of applications in column generation, in which constraints are positively homogeneous-so that zero is a natural Slater point-and an exact oracle may be time consuming. Fina...
-
作者：Attouch, Hedy; Cominetti, Roberto; Teboulle, Marc
作者单位：Universidad de Chile; Universite de Montpellier; Tel Aviv University
-
作者：Cornuejols, Gerard; Margot, Francois
作者单位：Carnegie Mellon University; Aix-Marseille Universite
摘要：In this paper we consider an infinite relaxation of the mixed integer linear program with two integer variables, nonnegative continuous variables and two equality constraints, and we give a complete characterization of its facets. We also derive an analogous characterization of the facets of the underlying finite integer program.
-
作者：Babonneau, F.; Vial, J. -P.
作者单位：University of Geneva
摘要：This paper proposes an implementation of a constrained analytic center cutting plane method to solve nonlinear multicommodity flow problems. The new approach exploits the property that the objective of the Lagrangian dual problem has a smooth component with second order derivatives readily available in closed form. The cutting planes issued from the nonsmooth component and the epigraph set of the smooth component form a localization set that is endowed with a self-concordant augmented barrier....
-
作者：Guerkan, Guel; Pang, Jong-Shi
作者单位：Tilburg University; Rensselaer Polytechnic Institute
摘要：Inspired by previous works on approximations of optimization problems and recent papers on the approximation of Walrasian and Nash equilibria and on stochastic variational inequalities, the present paper investigates the approximation of Nash equilibria and clarifies the conditions required for the convergence of the approximate equilibria via a direct approach, a variational approach, and an optimization approach. Besides directly addressing the issue of convergence of Nash equilibria via app...
-
作者：Kim, Sunyoung; Kojima, Masakazu; Toint, Philippe
作者单位：Ewha Womans University; Institute of Science Tokyo; Tokyo Institute of Technology; University of Namur
摘要：Exploiting sparsity is essential to improve the efficiency of solving large optimization problems. We present a method for recognizing the underlying sparsity structure of a nonlinear partially separable problem, and show how the sparsity of the Hessian matrices of the problem's functions can be improved by performing a nonsingular linear transformation in the space corresponding to the vector of variables. A combinatorial optimization problem is then formulated to increase the number of zeros...
-
作者：Polyak, Roman A.
作者单位：George Mason University; George Mason University
摘要：We introduce the regularized Newton method (rnm) for unconstrained convex optimization. For any convex function, with a bounded optimal set, the rnm generates a sequence that converges to the optimal set from any starting point. Moreover the rnm requires neither strong convexity nor smoothness properties in the entire space. If the function is strongly convex and smooth enough in the neighborhood of the solution then the rnm sequence converges to the unique solution with asymptotic quadratic r...
-
作者：Belloni, Alexandre; Freund, Robert M.
作者单位：Massachusetts Institute of Technology (MIT); Duke University
摘要：In this paper we study the homogeneous conic system F : Ax = 0, is an element of C\{0}. We choose a point (s) over bar. is an element of intC* that serves as a normalizer and consider computational properties of the normalized system F (s) over bar : Ax = 0, s(-T) x = 1, x is an element of C. We show that the computational complexity of solving F via an interior-point method depends only on the complexity value v of the barrier for C and on the symmetry of the origin in the image set H ((s)) o...
-
作者：Tseng, Paul; Yun, Sangwoon
作者单位：University of Washington; University of Washington Seattle
摘要：We consider the problem of minimizing the sum of a smooth function and a separable convex function. This problem includes as special cases bound-constrained optimization and smooth optimization with l(1)-regularization. We propose a (block) coordinate gradient descent method for solving this class of nonsmooth separable problems. We establish global convergence and, under a local Lipschitzian error bound assumption, linear convergence for this method. The local Lipschitzian error bound holds u...
