Convex and Nonsmooth Optimization

$\varepsilon- Subdifferential of Set-valued Map and Its Application

  • Yu Li
    • Categories Convex Optimization

    In this paper, firstly, the concept of $\varepsilon-$strictly efficient subdifferential for set-valued map is introduced in Hausdorff locally convex topological vector spaces. Secondly, a characterization of this subdifferential by scalarization and the generalized $\varepsilon-$ Moreau-Rockafellar type theorem for set-valued maps are established. Finally, the necessary optimality condition of the constraint set-valued optimization problem for $\varepsilon-$ … Read more

    Global Convergence of Unmodified 3-Block ADMM for a Class of Convex Minimization Problems

  • Tianyi Lin
  • Shiqian Ma
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    The alternating direction method of multipliers (ADMM) has been successfully applied to solve structured convex optimization problems due to its superior practical performance. The convergence properties of the 2-block ADMM have been studied extensively in the literature. Specifically, it has been proven that the 2-block ADMM globally converges for any penalty parameter $\gamma>0$. In this … Read more

    An Inexact Proximal Algorithm for Pseudomonotone and Quasimonotone Variational Inequalities

  • Lennin Mallma Ramirez
  • Paulo Roberto Oliveira
  • Erik Alex Papa Quiroz
    • Categories Nonsmooth Optimization Tags , , ,

    In this paper we introduce an inexact proximal point algorithm using proximal distances for solving variational inequality problems when the mapping is pseudomonotone or quasimonotone. Under some natural assumptions we prove that the sequence generates by the algorithm is convergent for the pseudomonotone case and weakly convergent for the quasimonotone ones. This approach unifies the … Read more

    A New Perspective on Boosting in Linear Regression via Subgradient Optimization and Relatives

  • Robert M. Freund
  • Rahul Mazumder
  • Paul Grigas
    • Categories Data-Mining, Nonsmooth Optimization, Statistics Tags , , , ,

    In this paper we analyze boosting algorithms in linear regression from a new perspective: that of modern first-order methods in convex optimization. We show that classic boosting algorithms in linear regression, namely the incremental forward stagewise algorithm (FS-epsilon) and least squares boosting (LS-Boost-epsilon), can be viewed as subgradient descent to minimize the loss function defined … Read more

    First-Order Algorithms for Convex Optimization with Nonseparate Objective and Coupled Constraints

  • Xiang Gao
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    In this paper we consider a block-structured convex optimization model, where in the objective the block-variables are nonseparable and they are further linearly coupled in the constraint. For the 2-block case, we propose a number of first-order algorithms to solve this model. First, the alternating direction method of multipliers (ADMM) is extended, assuming that it … Read more

    Solving nonsmooth convex optimization with complexity (\eps^{-1/2})$

  • Masoud Ahookhosh
  • Arnold Neumaier
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization

    This paper describes an algorithm for solving structured nonsmooth convex optimization problems using OSGA, a first-order method with the complexity $O(\eps^{-2})$ for Lipschitz continuous nonsmooth problems and $O(\eps^{-1/2})$ for smooth problems with Lipschitz continuous gradient. If the nonsmoothness of the problem is manifested in a structured way, we reformulate the problem in a form that … Read more

    Distributionally robust expectation inequalities for structured distributions

  • Paul J. Goulart
  • Bart Paul Gerard Van Parys
  • Manfred Morari
    • Categories Convex Optimization, Semi-definite Programming, Stochastic Programming Tags , , ,

    Quantifying the risk of unfortunate events occurring, despite limited distributional information, is a basic problem underlying many practical questions. Indeed, quantifying constraint violation probabilities in distributionally robust programming or judging the risk of financial positions can both be seen to involve risk quantification, notwithstanding distributional ambiguity. In this work we discuss worst-case probability and conditional … Read more

    First order optimality conditions for mathematical programs with second-order cone complementarity constraints

  • Jane J. Ye
  • Jinchuan Zhou
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization, Second-Order Cone Programming Tags , , , , ,

    In this paper we consider a mathematical program with second-order cone complementarity constraints (SOCMPCC). The SOCMPCC generalizes the mathematical program with complementarity constraints (MPCC) in replacing the set of nonnegative reals by a second-order cone. We show that if the SOCMPCC is considered as an optimization problem with convex cone constraints, then Robinson’s constraint qualification … Read more

    An O(1/k) Convergence Rate for the Variable Stepsize Bregman Operator Splitting Algorithm

  • William W. Hager
  • Maryam Yashtini
  • Hongchao Zhang
    • Categories Nonsmooth Optimization Tags , , , , ,

    An earlier paper proved the convergence of a variable stepsize Bregman operator splitting algorithm (BOSVS) for minimizing $\phi(Bu)+H(u)$ where $H$ and $\phi$ are convex functions, and $\phi$ is possibly nonsmooth. The algorithm was shown to be relatively efficient when applied to partially parallel magnetic resonance image reconstruction problems. In this paper, the convergence rate of … Read more

    Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making

  • Amir Ali Ahmadi
  • Anirudha Majumdar
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We demonstrate applications of algebraic techniques that optimize and certify polynomial inequalities to problems of interest in the operations research and transportation engineering communities. Three problems are considered: (i) wireless coverage of targeted geographical regions with guaranteed signal quality and minimum transmission power, (ii) computing real-time certificates of collision avoidance for a simple model of … Read more