Projected Subgradient Ascent for Convex Maximization

Pedro Felzenszwalb, Heon Lee · 2025

Read Projected Subgradient Ascent for Convex Maximization by Pedro Felzenszwalb, Heon Lee (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-00741.txt.

Introduction

Pedro Felzenszwalb and Heon Lee study an unfashionable problem: maximizing a convex function over a convex set in a Hilbert space. Maximization usually hunts concave goals, so convex maximization, where the best points hide at extremes, needs its own theory. The authors analyze projected subgradient ascent, the simple loop that steps uphill and projects back into the allowed set.

For linear functions, one orthogonal projection already yields an approximate solution. For continuous convex functions, the ascent converges to a first-order stationary point even with arbitrarily large step sizes, a surprising license to stride. Sending step sizes to infinity produces a deterministic variant of the conditional gradient algorithm, with iterated linear optimization as a special case. Simple geometry, pushed hard, turns out to organize several known methods at once.

Catalog record

CREATORPedro Felzenszwalb, Heon Lee
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-00741

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Projected Subgradient Ascent for Convex Maximization Pedro Felzenszwalb, Heon Lee Abstract . We consider the problem of maximizing a convex function over a closed convex set. Classical methods solve such problems using iterative schemes that repeatedly improve a solution. For linear maximization, we show that a single orthogonal projection suffices to obtain an approximate solution. For general convex functions over convex sets, we show that projected subgradient ascent converges to a first-order stationary point when using arbitrarily large step sizes. Taking the step size to infinity leads to the conditional gradient algorithm, and iterated linear optimization as a special case. We illustrate numerical experiments using a single projection for linear optimization in the elliptope, reducing the problem to the computation of a nearest correlation matrix. 1. Introduction We consider the problem of maximizing a convex function over a nonempty closed and convex set S . Of particular interest is the case of linear optimization: (1) \max_{x\in S}\;\langle c,x\rangle This problem can be solved by various methods, including but not limited to interior-point methods, the simplex algorithm, proximal methods, and projected gradient ascent (e.g., [ 19 , 1 , 5 , 6 , 8 ] ). Here we show that one orthogonal projection suffices to obtain an approximate solution to a linear optimization problem. More generally, the approach can be viewed as a single step of projected gradient ascent using a large step size. Let P_{S}(x) denote the unique point in S closest to x . We show that P_{S}(x_{0}+\eta c) converges to the unique optimal solution of ( 1 ) closest to x_{0} as \eta\to\infty (Theorem 2.7 ). We also give tight bounds on the quality of the solution obtained using finite \eta (Lemma 2.4 ). Beyond linear objectives, we investigate the use of projected subgradient ascent for maximizing convex functions. In the convex minimization setting, projected subgradient descent requires vanishing step sizes. In contrast, we show that for convex maximization, projected subgradient ascent converges to a first-order stationary point when using arbitrarily large step sizes (Theorem 3.14 ). This result holds in infinite-dimensional spaces, and it does not require differentiability, Lipschitz continuity of the gradient, or the Kurdyka-Łojasiewicz property (see, e.g. [ 2 ] ). In practice, the large step size regime of projected subgradient ascent may lead to faster convergence and yield meaningful behavior. In the limit, projected subgradient ascent is equivalent to the conditional gradient method with unit step size (Section 3.3 ). This limit also generalizes the iterated linear optimization paradigm introduced in [ 10 ] . The idea of using a single projection for linear optimization was previously considered in [ 16 ] in the context of linear programming. It was also considered recently, and independently of our work, in [ 24 ] . Compared to [ 24 ] , the bounds shown here are tighter, and we prove convergence to a unique optimum solution besides proving convergence of the objective value. The reduction of linear optimization to orthogonal projection (Section 2 ) can be used both to understand the relative complexity of the two operations and to derive new algorithms for linear optimization using existing algorithms for projection. [ 7 ] undertook a complexity analysis and show that on many domains—the simplex, \ell_{p} -balls, nuclear-norm ball, the flow polytope, Birkhoff polytope, and permutahedron—the best known algorithms for linear optimization are asymptotically faster than the best known algorithms for orthogonal projection. The reduction of linear optimization to orthogonal projection gives further evidence that linear optimization over a convex set is never harder than projecting to the same set. While [ 7 ] and [ 24 ] suggest this as a negative result for projection-based methods, we emphasize that the reduction can be used to obtain positive results, in that efficient algorithms for projections lead to efficient algorithms for linear optimization. In Section 4 we illustrate numerical experiments using projection for linear optimization in the elliptope, and the Goemans and Williamson [ 12 ] Max-Cut algorithm. We reduce the semidefinite programming problem to orthogonal projection and use an existing method to compute the nearest correlation matrix [ 22 ] . Our experiments show the projection method has comparable accuracy but is faster in practice when compared to SCS [ 20 ] . 2. Single Projection for Linear Optimization Let \mathcal{H} be a real Hilbert space and S\subseteq\mathcal{H} be a nonempty closed and convex subset. Throughout the paper, we assume that the maximum in ( 1 ) is attained by at least one point of S . If S is weakly compact, then the maximum is always attained. Define the set of maximizers \mathcal{M}(c)=\argmax_{x\in S}\,\langle c,x\rangle. Since S is closed and convex, and \langle c,x\rangle is a linear function of x , the set of maximizers \mathcal{M}(c) is non-empty, closed, and convex. Let x_{0}\in\mathcal{H} . Denote by \|\cdot\| the norm induced by the inner product. By the Hilbert Projection Theorem, there is a unique solution in \mathcal{M}(c) closest to x_{0} , which we denote x^{*}=\argmin_{x\in\mathcal{M}(c)}\|x-x_{0}\|. Consider the orthogonal projection map P_{S}\mathrel{\mathop{\mathchar 58\relax}}\mathcal{H}\to S taking a point x\in\mathcal{H} to the unique closest point of x in S , P_{S}(x)=\argmin_{y\in S}\|y-x\|. For \eta\in\mathbb{R} , let x^{\eta}=P_{S}(x_{0}+\eta c). We show that x^{\eta}\to x^{*} as \eta\to\infty and give explicit bounds on \eta that guarantee a good approximation. This provides a method for approximating x^{*} using a single orthogonal projection. Figure 1 illustrates the convergence in the case of an ellipse in the plane with x_{0} at the origin. Since x^{\eta} is the orthogonal projection of \eta c we have that \eta c-x^{\eta} is perpendicular to the ellipse at x^{\eta} . Therefore x^{\eta} maximizes \langle\eta c-x^{\eta},x\rangle . As \eta grows, \eta c-x^{\eta} becomes parallel to c , and in the limit x^{\eta} maximizes \langle c,x\rangle . Figure 1. Linear maximization of \langle c,x\rangle via a single projection x^{\eta}=P_{S}(c\eta) with \eta\to\infty . The use of a single projection for linear optimization was considered in [ 16 ] in the context of linear programming, where projecting a suitably rescaled cost vector yields an optimal basic feasible solution. Mangasarian sought an explicit \eta that produces an exact solution in the polyhedral setting. Here we consider more general (non-polyhedral) closed convex sets in a Hilbert space and derive bounds on \eta that ensure an arbitrarily close approximation to the objective value. Note that for smooth sets, there is no finite \eta that achieves optimality. A result similar to Lemma 2.4 appears in [ 24 ] . However, our lemma provides a more precise characterization that depends on x_{0} and we prove convergence of P_{S}(x_{0}+\eta c) to a particular optimum solution, including in the case of general (non-polyhedral) convex sets S . Practical use of x^{\eta} to approximate x^{*} requires a choice for \eta . The choice should balance the computational complexity of computing the projection x^{\eta}=P_{S}(x_{0}+\eta c) and the quality of the approximation. For some convex sets, projection can be performed efficiently. Methods based on alternating projections, such as Dykstra’s algorithm [ 9 ] , can also be used in various settings. The quality of an approximate solution can be measured in terms of the difference in objective value \langle c,x^{*}\rangle-\langle c,x^{\eta}\rangle . We first provide a bound on the value of \eta sufficient for some

Read the complete text