Nonsmooth Optimization

Approximating Stationary Points of Stochastic Mathematical Programs with Equilibrium Constraints via Sample Averaging

  • Huifu Xu
  • Jane J. Ye
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization, Stochastic Programming Tags , , , , ,

    We investigate sample average approximation of a general class of one-stage stochastic mathematical programs with equilibrium constraints. By using graphical convergence of unbounded set-valued mappings, we demonstrate almost sure convergence of a sequence of stationary points of sample average approximation problems to their true counterparts as the sample size increases. In particular we show the … Read more

    Accelerated Block-Coordinate Relaxation for Regularized Optimization

  • Stephen Wright
    • Categories Nonsmooth Optimization, Statistics Tags , ,

    We discuss minimization of a smooth function to which is added a separable regularization function that induces structure in the solution. A block-coordinate relaxation approach with proximal linearized subproblems yields convergence to critical points, while identification of the optimal manifold (under a nondegeneracy condition) allows acceleration techniques to be applied on a reduced space. The … Read more

    Optimality conditions for various efficient solutions involving coderivatives: from set-valued optimization problems to set-valued equilibrium problems

  • Xuan Duc Ha Truong
    • Categories Complementarity and Variational Inequalities, Multi-Criteria Optimization, Nonsmooth Optimization Tags , , , , , , , , , , , , ,

    We present a new approach to the study of a set-valued equilibrium problem (for short, SEP) through the study of a set-valued optimization problem with a geometric constraint (for short, SOP) based on an equivalence between solutions of these problems. As illustrations, we adapt to SEP enhanced notions of relative Pareto efficient solutions introduced in … Read more

    Feasible and accurate algorithms for covering semidefinite programs

  • Garud Iyengar
  • Cliff Stein
  • David Phillips
    • Categories Approximation Algorithms, Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    In this paper we describe an algorithm to approximately solve a class of semidefinite programs called covering semidefinite programs. This class includes many semidefinite programs that arise in the context of developing algorithms for important optimization problems such as sparsest cut, wireless multicasting, and pattern classification. We give algorithms for covering SDPs whose dependence on … Read more

    Optimality Conditions and Duality for Nonsmooth Multiobjective Optimization Problems with Cone Constraints and Applications

  • Jiawei Chen
  • Zhong-Ping Wan
  • Zheng Yue
    • Categories Nonsmooth Optimization, Other Topics Tags , , , , , ,

    In this work, a nonsmooth multiobjective optimization problem involving generalized invexity with cone constraints and Applications (for short, (MOP)) is considered. The Kuhn-Tucker necessary and sufficient conditions for (MOP) are established by using a generalized alternative theorem of Craven and Yang. The relationship between weakly efficient solutions of (MOP) and vector valued saddle points of … Read more

    Implicit Multifunction Theorems in complete metric spaces

  • Van Ngai Huynh
  • Huu Tron Nguyen
  • Michel Thera
    • Categories Infinite Dimensional Optimization, Nonsmooth Optimization Tags , , , ,

    In this paper, we establish some new characterizations of the metric regularity of implicit multifunctions in complete metric spaces by using the lower semicontinuous envelopes of the distance functions for set-valued mappings. Through these new characterizations it is possible to investigate implicit multifunction theorems based on coderivatives and on contingent derivatives as well as the … Read more

    A Unified Approach for Minimizing Composite Norms

  • Necdet Serhat Aybat
  • Garud Iyengar
    • Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization Tags , , , , , ,

    We propose a first-order augmented Lagrangian algorithm (FALC) to solve the composite norm minimization problem min |sigma(F(X)-G)|_alpha + |C(X)- d|_beta subject to A(X)-b in Q; where sigma(X) denotes the vector of singular values of X, the matrix norm |sigma(X)|_alpha denotes either the Frobenius, the nuclear, or the L2-operator norm of X, the vector norm |.|_beta … Read more

    Generic nondegeneracy in convex optimization

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    We show that minimizers of convex functions subject to almost all linear perturbations are nondegenerate. An analogous result holds more generally, for lower-C^2 functions. CitationCornell University, School of Operations Research and Information Engineering, 206 Rhodes Hall Cornell University Ithaca, NY 14853. May 2010. ArticleDownload View PDF

    Semi-algebraic functions have small subdifferentials

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
    • Categories Nonsmooth Optimization Tags , , ,

    We prove that the subdifferential of any semi-algebraic extended-real-valued function on $\R^n$ has $n$-dimensional graph. We discuss consequences for generic semi-algebraic optimization problems. CitationCornell University, School of Operations Research and Information Engineering, 206 Rhodes Hall Cornell University Ithaca, NY 14853. April 2010.ArticleDownload View PDF