Entropic proximal operators for nonnegative trigonometric polynomials

  • Hsiao-Han Chao
  • Lieven Vandenberghe
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming

    Signal processing applications of semidefinite optimization are often rooted in sum-of-squares representations of nonnegative trigonometric polynomials. Interior-point solvers for semidefinite optimization can handle constraints of this form with a per-iteration-complexity that is cubic in the degree of the trigonometric polynomial. The purpose of this paper is to discuss first-order methods with a lower complexity per … Read more

    Derivative-Free Optimization of Noisy Functions via Quasi-Newton Methods

  • Albert S. Berahas
  • Richard H. Byrd
  • Jorge Nocedal
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , ,

    This paper presents a finite difference quasi-Newton method for the minimization of noisy functions. The method takes advantage of the scalability and power of BFGS updating, and employs an adaptive procedure for choosing the differencing interval h based on the noise estimation techniques of Hamming (2012) and Moré and Wild (2011). This noise estimation procedure … Read more

    A Dynamic Penalty Parameter Updating Strategy for Matrix-Free Sequential Quadratic Optimization

  • James V. Burke
  • Frank E. Curtis
  • Jiashan Wang
  • Hao Wang
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , ,

    This paper focuses on the design of sequential quadratic optimization (commonly known as SQP) methods for solving large-scale nonlinear optimization problems. The most computationally demanding aspect of such an approach is the computation of the search direction during each iteration, for which we consider the use of matrix-free methods. In particular, we develop a method … Read more

    New SOCP relaxation and branching rule for bipartite bilinear programs

  • Santanu S. Dey
  • Asteroide Santana
  • Yang Wang
    • Categories Global Optimization Applications, Global Optimization Theory

    A bipartite bilinear program (BBP) is a quadratically constrained quadratic optimization problem where the variables can be partitioned into two sets such that fixing the variables in any one of the sets results in a linear program. We propose a new second order cone representable (SOCP) relaxation for BBP, which we show is stronger than … Read more

    On the Consistent Path Problem

  • David Bergman
  • Leonardo Lozano
  • Cole Smith
    • Categories 0-1 Programming, Combinatorial Optimization, Cutting Plane Approaches

    The application of decision diagrams in combinatorial optimization has proliferated in the last decade. In recent years, authors have begun to investigate how to utilize not one, but a set of diagrams, to model constraints and objective function terms. Optimizing over a collection of decision diagrams, the problem we refer to as the consistent path … Read more

    Discretization-based algorithms for generalized semi-infinite and bilevel programs with coupling equality constraints

  • Hatim Djelassi
  • Alexander Mitsos
  • Moll Glass
    • Categories Global Optimization Applications, Global Optimization Theory, Semi-infinite Programming

    Discretization-based algorithms are proposed for the global solution of mixed-integer nonlinear generalized semi-infinite (GSIP) and bilevel (BLP) programs with lower-level equality constraints coupling the lower and upper level. The algorithms are extensions, respectively, of the algorithm proposed by Mitsos and Tsoukalas (J Glob Optim 61(1):1–17, 2015. https://doi.org/10.1007/s10898-014-0146-6) and by Mitsos (J Glob Optim 47(4):557–582, 2010. … Read more

    Hadamard Directional Diff erentiability of the Optimal Value of a Linear Second-order Conic Programming Problem

  • Duan Qingsong
  • Liwei Zhang
  • Sainan Zhang
    • Categories Second-Order Cone Programming, Stochastic Programming Tags , , ,

    In this paper, we consider perturbation properties of a linear second-order conic optimization problem and its Lagrange dual in which all parameters in the problem are perturbed. We prove the upper semi-continuity of solution mappings for the primal problem and the Lagrange dual problem. We demonstrate that the optimal value function can be expressed as … Read more

    Robust Principal Component Analysis using Facial Reduction

  • Shiqian Ma
  • Linchuan Wei
  • Henry Wolkowicz
  • Fei Wang
    • Categories Data-Mining, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , , ,

    We study algorithms for robust principal component analysis (RPCA) for a partially observed data matrix. The aim is to recover the data matrix as a sum of a low-rank matrix and a sparse matrix so as to eliminate erratic noise (outliers). This problem is known to be NP-hard in general. A classical way to solve … Read more

    On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization

  • Amir Ali Ahmadi
  • Jeffrey Zhang
    • Categories Global Optimization Theory, Nonlinear Optimization, Semi-definite Programming Tags , , , , ,

    We prove that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem where the objective and constraints are given by low-degree polynomials is attained. If the degrees of these polynomials are fixed, our results along with previously-known “Frank-Wolfe type” theorems … Read more

    Projective Splitting with Forward Steps: Asynchronous and Block-Iterative Operator Splitting

  • Jonathan Eckstein
  • Patrick R. Johnstone
    • Categories Convex and Nonsmooth Optimization Tags ,

    This work is concerned with the classical problem of finding a zero of a sum of maximal monotone operators. For the projective splitting framework recently proposed by Combettes and Eckstein, we show how to replace the fundamental subproblem calculation using a backward step with one based on two forward steps. The resulting algorithms have the … Read more