Disciplined quasiconvex programming
- PDF / 311,564 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 72 Downloads / 293 Views
Disciplined quasiconvex programming Akshay Agrawal1 · Stephen Boyd1 Received: 25 September 2019 / Accepted: 22 February 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We present a composition rule involving quasiconvex functions that generalizes the classical composition rule for convex functions. This rule complements well-known rules for the curvature of quasiconvex functions under increasing functions and pointwise maximums. We refer to the class of optimization problems generated by these rules, along with a base set of quasiconvex and quasiconcave functions, as disciplined quasiconvex programs. Disciplined quasiconvex programming generalizes disciplined convex programming, the class of optimization problems targeted by most modern domain-specific languages for convex optimization. We describe an implementation of disciplined quasiconvex programming that makes it possible to specify and solve quasiconvex programs in CVXPY 1.0. Keywords Quasiconvex programming · Convex optimization · Domain-specific languages
1 Introduction A real-valued function f is quasiconvex if its domain C is convex, and for any α ∈ R, its α-sublevel sets { x ∈ C | f (x) ≤ α } are convex [5, §3.4]. A function f is quasiconcave if − f is quasiconvex, and it is quasilinear if it is both quasiconvex and quasiconcave. A quasiconvex program (QCP) is a mathematical optimization problem in which the objective is to minimize a quasiconvex function over a convex set. Because every convex function is also quasiconvex, QCPs generalize convex programs. Though QCPs are in general nonconvex, many can nonetheless be solved efficiently by a bisection method that involves solving a sequence of convex programs [5, §4.2.5], or by subgradient methods [21,22].
B
Akshay Agrawal [email protected] Stephen Boyd [email protected]
1
Department of Electrical Engineering, Stanford University, 450 Serra Mall, Stanford, CA 94305, USA
123
A. Agrawal, S. Boyd
The study of quasiconvex functions is several decades old [10,24,25]. Quasiconvexity has been of particular interest in economics, where it arose in the study of competitive equilibria and the modeling of utility functions [3,16]. More recently, quasiconvex programming has been applied to control [6,15,28], model order reduction [29], computer vision [19,20], computational geometry [9], and machine learning [17]. While QCPs have many applications, it remains difficult for non-experts to specify and solve them in practice. The point of this paper is to close that gap. Domain-specific languages (DSLs) have made convex optimization widely accessible. DSLs let users specify their programs in natural mathematical notation, abstracting away the process of canonicalizing problems to standard forms for numerical solvers. The syntax of most DSLs for convex optimization, including CVX [12], CVXPY [1,8], Convex.jl [30], and CVXR [11], is determined by a grammar known as disciplined convex programming (DCP) [13]. DCP includes a set of functions with known curvature (affine, convex, or
Data Loading...
