Convex Optimization

Dealing with inequality constraints in large-scale semidefinite relaxations for graph coloring and maximum clique problems

  • Federico Battista
  • Marianna De Santis
    • Categories Combinatorial Optimization, Convex Optimization, Semi-definite Programming Tags , ,

    Semidefinite programs (SDPs) can be solved in polynomial time by interior point methods. However, when the dimension of the problem gets large, interior point methods become impractical in terms of both computational time and memory requirements. Certain first-order methods, such as Alternating Direction Methods of Multipliers (ADMMs), established as suitable algorithms to deal with large-scale … Read more

    Frank-Wolfe and friends: a journey into projection-free first-order optimization methods

  • Immanuel M. Bomze
  • Francesco Rinaldi
  • Damiano Zeffiro
    • Categories Convex Optimization, Nonlinear Optimization Tags , , , ,

    Invented some 65 years ago in a seminal paper by Marguerite Straus-Frank and Philip Wolfe, the Frank-Wolfe method recently enjoys a remarkable revival, fuelled by the need of fast and reliable first-order optimization methods in Data Science and other relevant application areas. This review tries to explain the success of this approach by illustrating versatility … Read more

    Analysis of the Frank-Wolfe Method for Convex Composite Optimization involving a Logarithmically-Homogeneous Barrier

  • Robert M. Freund
  • Renbo Zhao
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , , ,

    We present and analyze a new generalized Frank-Wolfe method for the composite optimization problem (P): F*:= min_x f(Ax) + h(x), where f is a \theta-logarithmically-homogeneous self-concordant barrier and the function h has bounded domain but is possibly non-smooth. We show that our generalized Frank-Wolfe method requires O((Gap_0 + \theta + Var_h)\ln(\delta_0) + (\theta + Var_h)^2/\epsilon) … Read more

    Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient

  • David Applegate
  • Mateo Díaz
  • Haihao Lu
  • Miles Lubin
  • Oliver Hinder
  • Brendan O'Donoghue
  • Warren Schudy
    • Categories Convex Optimization, Linear Programming Tags , , ,

    We present PDLP, a practical first-order method for linear programming (LP) that can solve to the high levels of accuracy that are expected in traditional LP applications. In addition, it can scale to very large problems because its core operation is matrix-vector multiplications. PDLP is derived by applying the primal-dual hybrid gradient (PDHG) method, popularized … Read more

    Hashing embeddings of optimal dimension, with applications to linear least squares

  • Coralia Cartis
  • Jan Fiala
  • Zhen Shao
    • Categories Convex Optimization Tags , , ,

    The aim of this paper is two-fold: firstly, to present subspace embedding properties for s-hashing sketching matrices, with $s\geq 1$, that are optimal in the projection dimension $m$ of the sketch, namely, $m=O(d)$, where $d$ is the dimension of the subspace. A diverse set of results are presented that address the case when the input … Read more

    MIMO Radar Optimization With Constant-Modulus and Any p-Norm Similarity Constraints

  • Xin He
    • Categories Convex Optimization, Second-Order Cone Programming, Telecommunications Tags , , , , ,

    MIMO radar plays a key role in autonomous driving, and the similarity waveform constraint is an important constraint for radar waveform design. However, the joint constant-modulus and similarity constraint is a difficult constraint. Only the special case with $\infty$-norm similarity and constant-modulus constraints is tackled by the semidefinite relaxation (SDR) and the successive quadratic refinement … Read more

    Optimal Convergence Rates for the Proximal Bundle Method

  • Mateo Díaz
  • Benjamin Grimmer
    • Categories Convex Optimization, Unconstrained Optimization Tags , , , ,

    We study convergence rates of the classic proximal bundle method for a variety of nonsmooth convex optimization problems. We show that, without any modification, this algorithm adapts to converge faster in the presence of smoothness or a Hölder growth condition. Our analysis reveals that with a constant stepsize, the bundle method is adaptive, yet it … Read more

    An Accelerated Minimal Gradient Method with Momentum for Convex Quadratic Optimization

  • Oscar S. Dalmau
  • Rafael Herrera
  • Harry Oviedo
    • Categories Convex Optimization, Unconstrained Optimization Tags , ,

    In this article we address the problem of minimizing a strictly convex quadratic function using a novel iterative method. The new algorithm is based on the well–known Nesterov’s accelerated gradient method. At each iteration of our scheme, the new point is computed by performing a line–search scheme using a search direction given by a linear … Read more

    FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and Conditional Gradients

  • Mathieu Besançon
  • Alejandro Carderera
  • Sebastian Pokutta
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Optimization Software and Modeling Systems Tags , ,

    We present FrankWolfe.jl, an open-source implementation of several popular Frank-Wolfe and Conditional Gradients variants for first-order constrained optimization. The package is designed with flexibility and high-performance in mind, allowing for easy extension and relying on few assumptions regarding the user-provided functions. It supports Julia’s unique multiple dispatch feature, and interfaces smoothly with generic linear optimization … Read more

    Long-run market equilibria in coupled energy sectors: A study of uniqueness

  • Jonas Egerer
  • Veronika Grimm
  • Julia Grübel
  • Gregor Zöttl
    • Categories Applications - OR and Management Sciences, Convex Optimization, Finance and Economics Tags , , , ,

    We propose an equilibrium model for coupled markets of multiple energy sectors. The agents in our model are operators of sector-specific production and sector-coupling technologies, as well as price-sensitive consumers with varying demand. We analyze long-run investment in production capacity in each sector and investment in coupling capacity between sectors, as well as production decisions … Read more