A simple method for convex optimization in the oracle model

DOI10.1007/978-3-031-06901-7_12zbMATH Open1497.90147arXiv2011.08557OpenAlexW3211344788MaRDI QIDQ2164690FDOQ2164690

Authors: Daniel Dadush, Christopher Hojny, Sophie Huiberts, Stefan Weltge 

Publication date: 16 August 2022

Abstract: We give a simple and natural method for computing approximately optimal solutions for minimizing a convex function $f$ over a convex set $K$ given by a separation oracle. Our method utilizes the Frank--Wolfe algorithm over the cone of valid inequalities of $K$ and subgradients of $f$. Under the assumption that $f$ is $L$-Lipschitz and that $K$ contains a ball of radius $r$ and is contained inside the origin centered ball of radius $R$, using $O(frac(RL{)}^{2}varepsilo{n}^{2}cdotfrac{R}^2{r}^2)$ iterations and calls to the oracle, our main method outputs a point $xinK$ satisfying $f(x)leqvarepsilon+mi{n}_{zinK}f(z)$. Our algorithm is easy to implement, and we believe it can serve as a useful alternative to existing cutting plane methods. As evidence towards this, we show that it compares favorably in terms of iteration counts to the standard LP based cutting plane method and the analytic center cutting plane method, on a testbed of combinatorial, semidefinite and machine learning instances.

Full work available at URL: https://arxiv.org/abs/2011.08557

Recommendations

• Efficient convex optimization with oracles
• Oracle complexity separation in convex optimization
• On the oracle complexity of smooth strongly convex minimization
• Oracle complexity of second-order methods for smooth convex optimization
• A simple randomised algorithm for convex optimisation
• First-order methods of smooth convex optimization with inexact oracle
• Method of orthogonal simplexes and its applications to convex programming
• Fast gradient descent for convex minimization problems with an oracle producing a \(( \delta, L)\)-model of function at the requested point
• A forward convex-simplex method

zbMATH Keywords

convex optimizationcutting plane methodseparation oracle

Mathematics Subject Classification ID

Convex programming (90C25)

Cites Work

• First-order methods in optimization
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Geometric algorithms and combinatorial optimization
• A new algorithm for minimizing convex functions over convex sets
• Outline of an algorithm for integer solutions to linear programs
• The Cutting-Plane Method for Solving Convex Programs
• Maximum matching and a polyhedron with 0,1-vertices
• Title not available (Why is that?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• The maximum concurrent flow problem
• Newton's method for convex programming and Tschebyscheff approximation
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Title not available (Why is that?)
• Linear programming boosting via column generation
• A cutting plane algorithm for convex programming that uses analytic centers
• A simple polynomial-time rescaling algorithm for solving linear programs
• Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem
• A strongly polynomial algorithm for linear systems having a binary solution
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Augmented self-concordant barriers and nonlinear optimization problems with finite complexity
• An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix
• An efficient rescaled perceptron algorithm for conic systems
• An improved cutting plane method for convex optimization, convex-concave games, and its applications
• Near-linear time approximation schemes for some implicit fractional packing problems
• Rescaling algorithms for linear conic feasibility

Cited In (6)

• Efficient convex optimization with oracles
• Proximal-ACCPM: a versatile oracle based optimisation method
• A simple method for convex optimization in the oracle model
• Oracle complexity separation in convex optimization
• Catching-up algorithm with approximate projections for Moreau's sweeping processes
• Accuracy certificates for convex minimization with inexact oracle

This page was built for publication: A simple method for convex optimization in the oracle model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2164690)