A simple method for convex optimization in the oracle model

DOI10.1007/978-3-031-06901-7_12MaRDI QIDQ2164690zbMATH OpenOpenAlexFDO

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

Publication date 16 August 2022

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

zbMATH Keywords

convex optimizationcutting plane methodseparation oracle

Mathematics Subject Classification ID

Convex programming (90C25)

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.

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 ( , L)-model of function at the requested point
• A forward convex-simplex method

Cites work

• scientific article; zbMATH DE number 4041641 (Why is no real title available?)
• scientific article; zbMATH DE number 3637614 (Why is no real title available?)
• A cutting plane algorithm for convex programming that uses analytic centers
• A new algorithm for minimizing convex functions over convex sets
• A simple polynomial-time rescaling algorithm for solving linear programs
• A strongly polynomial algorithm for linear systems having a binary solution
• 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
• Augmented self-concordant barriers and nonlinear optimization problems with finite complexity
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• First-order methods in optimization
• Geometric algorithms and combinatorial optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Linear programming boosting via column generation
• Maximum matching and a polyhedron with 0,1-vertices
• Near-linear time approximation schemes for some implicit fractional packing problems
• Newton's method for convex programming and Tschebyscheff approximation
• Outline of an algorithm for integer solutions to linear programs
• Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem
• Rescaling algorithms for linear conic feasibility
• The Cutting-Plane Method for Solving Convex Programs
• The maximum concurrent flow problem

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)