Convex and Nonsmooth Optimization

A One-Parameter Family of Middle Proximal ADMM for Constrained Separable Convex Optimization

  • Jianchao Bai
  • Hongchao Zhang
    • Categories Convex Optimization Tags , , , , , ,

    This work is devoted to studying a family of Middle Proximal Alternating Direction Method of Multipliers (MP-ADM) for solving multi-block constrained separable convex optimization. Such one-parameter family of MP-ADM combines both Jacobian and Gauss-Seidel types of alternating direction method, and proximal point techniques are only applied to the middle subproblems to promote the convergence. We … Read more

    Set-Completely-Positive Representations and Cuts for the Max-Cut Polytope and the Unit Modulus Lifting

  • Florian Jarre
  • Ya-Feng Liu
  • Felix Lieder
  • Cheng Lu
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    This paper considers a generalization of the “max-cut-polytope” $\conv\{\ xx^T\mid x\in\real^n, \ \ |x_k| = 1 \ \hbox{for} \ 1\le k\le n\}$ in the space of real symmetric $n\times n$-matrices with all-ones-diagonal to a complex “unit modulus lifting” $\conv\{xx\HH\mid x\in\complex^n, \ \ |x_k| = 1 \ \hbox{for} \ 1\le k\le n\}$ in the space of … Read more

    Characterizing and testing subdifferential regularity for piecewise smooth objective functions

  • Andreas Griewank
  • Andrea Walther
    • Categories Nonsmooth Optimization Tags , , , , , ,

    Functions defined by evaluation programs involving smooth elementals and absolute values as well as the max- and min-operator are piecewise smooth. Using piecewise linearization we derived in [7] for this class of nonsmooth functions first and second order conditions for local optimality (MIN). They are necessary and sufficient, eespectively. These generalizations of the classical KKT … Read more

    Weak Stability of $\ell_1hBcminimization Methods in Sparse Data Reconstruction

  • H. Jiang
  • Zhi-Quan Luo
  • Yun-Bin Zhao
    • Categories Convex and Nonsmooth Optimization, Data-Mining, Linear Programming Tags , , , , ,

    As one of the most plausible convex optimization methods for sparse data reconstruction, $\ell_1$-minimization plays a fundamental role in the development of sparse optimization theory. The stability of this method has been addressed in the literature under various assumptions such as restricted isometry property (RIP), null space property (NSP), and mutual coherence. In this paper, … Read more

    Pareto efficient solutions in multi-objective optimization involving forbidden regions

  • Christian Günther
    • Categories Facility Planning and Design, Generalized Convexity/Monoticity, Multi-Criteria Optimization

    In this paper, the aim is to compute Pareto efficient solutions of multi-objective optimization problems involving forbidden regions. More precisely, we assume that the vector-valued objective function is componentwise generalized-convex and acts between a real topological linear pre-image space and a finite-dimensional image space, while the feasible set is given by the whole pre-image space … Read more

    Adaptive Sampling Strategies for Stochastic Optimization

  • Raghu Bollapragada
  • Richard H. Byrd
  • Jorge Nocedal
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , ,

    In this paper, we propose a stochastic optimization method that adaptively controls the sample size used in the computation of gradient approximations. Unlike other variance reduction techniques that either require additional storage or the regular computation of full gradients, the proposed method reduces variance by increasing the sample size as needed. The decision to increase … Read more

    Convergence rates of accelerated proximal gradient algorithms under independent noise

  • Jiang Hao
  • Barrio Roberto
  • Cheng Lizhi
  • Sun Tao
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    We consider an accelerated proximal gradient algorithm for the composite optimization with “independent errors” (errors little related with historical information) for solving linear inverse problems. We present a new inexact version of FISTA algorithm considering deterministic and stochastic noises. We prove some convergence rates of the algorithm and we connect it with the current existing … Read more

    Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs

  • Gabor Pataki
  • Quoc Tran-Dinh
  • Yuzixuan (Melody) Zhu
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Semi-definite Programming

    We introduce Sieve-SDP, a simple algorithm to preprocess semidefinite programs (SDPs). Sieve-SDP belongs to the class of facial reduction algorithms. It inspects the constraints of the problem, deletes redundant rows and columns, and reduces the size of the variable matrix. It often detects infeasibility. It does not rely on any optimization solver: the only subroutine … Read more

    Exact worst-case convergence rates of the proximal gradient method for composite convex minimization

  • François Glineur
  • Julien M. Hendrickx
  • Adrien B. Taylor
    • Categories Convex Optimization, Nonsmooth Optimization

    We study the worst-case convergence rates of the proximal gradient method for minimizing the sum of a smooth strongly convex function and a non-smooth convex function whose proximal operator is available. We establish the exact worst-case convergence rates of the proximal gradient method in this setting for any step size and for different standard performance … Read more

    Complete Facial Reduction in One Step for Spectrahedra

  • Stefan Sremac
  • Henry Wolkowicz
  • Hugo J. Woerdeman
    • Categories Convex Optimization, Semi-definite Programming Tags , , ,

    A spectrahedron is the feasible set of a semidefinite program, SDP, i.e., the intersection of an affine set with the positive semidefinite cone. While strict feasibility is a generic property for random problems, there are many classes of problems where strict feasibility fails and this means that strong duality can fail as well. If the … Read more