Strongly Convex Maximization via the Frank-Wolfe Algorithm with the Kurdyka-Łojasiewicz Inequality

Fatih S. Aktaş, Christian Kroer · 2025

Read Strongly Convex Maximization via the Frank-Wolfe Algorithm with the Kurdyka-Łojasiewicz Inequality by Fatih S. Aktaş, Christian Kroer (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-2505-00221.txt.

Introduction

Aktaş and Kroer study in twenty twenty-five a greedy algorithm for maximising a strongly convex function over a bounded set. Such maximisation is unusual, since most tools assume minimisation. The greedy method moves step by step toward the best corner point at each stage, with a full step each time.

Under smoothness and a key slope condition, they prove the method's outputs settle at the right limit from any start. They also derive a speed rate that depends on the shape of the problem. To show the value, they prove new results for a sparse data method and a sensing method. They also design a new method for a relaxed form of a classic graph cut problem.

Catalog record

CREATORFatih S. Aktaş, Christian Kroer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-00221

Browse the full library · About the Tower of Babel

Full text

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

Strongly Convex Maximization via the Frank-Wolfe Algorithm with the Kurdyka-Łojasiewicz Inequality Fatih S. Aktaş, Christian Kroer Abstract We study the convergence properties of the “greedy” Frank-Wolfe algorithm with a unit step size, for a convex maximization problem over a compact set. We assume the function satisfies smoothness and strong convexity. These assumptions together with the Kurdyka-Łojasiewicz (KL) property allow us to derive global asymptotic convergence for the sequence generated by the algorithm. Furthermore, we also derive a convergence rate that depends on the geometric properties of the problem. To illustrate the implications of the convergence result obtained, we prove a new convergence result for a sparse principal component analysis algorithm, propose a convergent reweighted ℓ 1 \ell_{1} minimization algorithm for compressed sensing, and design a new algorithm for the semidefinite relaxation of the Max-Cut problem. Keywords Frank-Wolfe algorithm, Conditional Gradient algorithm, Convex Maximization, Kurdyka-Łojasiewicz inequality, Max-Cut algorithm AMS 2020 Subject Classification 90C26, 90C30, 49M37, 65K05 1 Introduction In this paper, we study the following convex maximization model \begin{array}[]{ll@{}ll}\underset{x}{\max}&g(x)\\ \text{st.}&x\in\setX,\\ \end{array} (1) where the following assumptions are made for this model. Assumption 1.1 . Our blanket assumptions are: 1. The function g:{\mathbb{R}}^{n}\mapsto{\mathbb{R}} is strongly convex and smooth i.e. \nabla g(x) is Lipschitz continuous. 2. The constraint set \setX\subseteq\R^{n} is a nonempty compact set. Notice that we do not assume the convexity of the feasible set \setX . Applications of convex maximization problems are ubiquitous. For example, in optimization models where the objective satisfies economies of scale, the problem becomes a convex maximization problem, and similarly, many binary linear optimization problems can be equivalently modeled as a convex maximization problem (in particular with a quadratic objective) [ 1 ] . Many machine learning problems can also be formulated as a convex maximization problem. In [ 2 ] , misclassification minimization and feature selection problems are formulated as convex maximization problems. The classical statistical analysis technique principal component analysis (PCA) can be formulated as a convex quadratic maximization problem. Extensions of the PCA algorithm (without using semidefinite relaxations) are also convex maximization problems, such as sparse PCA [ 3 ] , nonnegative PCA, and nonnegative sparse PCA [ 4 ] . Furthermore, reweighted \ell_{1} norm type algorithms used in compressed sensing problems [ 5 ] , low-rank matrix recovery [ 6 ] , and sparse PCA [ 7 ] are derived from convex maximization problems. Convex maximization problems also naturally arise in graph theory problems, such as the famous Max-Cut problem [ 8 ] . In Section 4 , we show that even the computational models for the SDP relaxation of the Max-Cut problem can be represented as a convex maximization problem. In [ 9 ] and references therein, applications of convex maximization problems are discussed in detail, and many examples of integer linear and integer quadratic programs are shown to be equivalent to convex maximization. Another area where convex maximization naturally emerges is robust optimization when computing the worst-case scenario for a constraint that is convex in the uncertain parameter [ 10 , 11 ] . Additionally, as discussed in [ 12 ] , in the difference of convex functions (DC) framework, early approaches reformulate the problem as a convex maximization. Finally, the convex-concave procedure (CCP) is shown to be a special case of the Frank-Wolfe (FW) algorithm applied to a convex maximization problem in [ 13 ] . Maximizing a convex function is NP-hard for simple models such as maximizing a quadratic function over a hypercube, and even checking local optimality is NP-hard [ 14 ] . Thus, early approaches have been mostly based on linear approximations as overviewed in [ 15 ] . The main drawback of these approaches is that the subproblem cost at each iteration grows, making it computationally inefficient in practice. In [ 16 , 17 ] , an overview of all methods to solve convex quadratic maximization problems such as cutting plane, numerical approaches, and decomposition of the feasible set are given. A more recent approach given in [ 10 ] adapts methods from robust optimization literature for convex maximization problems with polyhedra as the feasible region or a single nonlinear constraint. Additionally, a two-stage algorithm was proposed in [ 11 ] that computes a good initial point and then uses the gradient ascent algorithm described in [ 18 ] . In this paper, we focus on the Frank-Wolfe (FW) algorithm or the conditional gradient (CG) algorithm. The FW algorithm is a famous algorithm in machine learning and optimization [ 19 ] . The original algorithm was proposed to minimize a quadratic function over a polytope [ 20 ] . Later, the algorithm was extended to more general settings [ 21 , 22 ] . Yet the popularity of the algorithm in machine learning came much later [ 23 , 24 ] . We refer to [ 25 , 26 , 27 ] for recent developments. Using the FW algorithm for convex maximization over a polyhedron with a unit step size to generate a finite algorithm that converges to a stationary point was suggested in [ 2 ] . In [ 28 ] , under the assumption of strong convexity of g or strong convexity of the set \setX and a lower bound on the norm of the subgradients of g for the non-differentiable case, a bound on the number of iterates required to produce pair of iterates (x_{k+1},x_{k}) with small \ell_{2} distance was constructed. This was generalized to Bregman distances by utilizing the relatively strong convexity concept in [ 29 ] . A more generic analysis of the conditional gradient algorithm with a unit step size for convex maximization problems was given in [ 18 ] . The main contribution of this paper is to prove new convergence results based on the Kurdyka-Łojasiewicz (KL) inequality under strong convexity and smoothness assumptions. Using the KL property, we prove convergence of the point sequence \{x_{k}\}_{k\in{\mathbb{N}}} and also derive a convergence rate in some cases. To the best of our knowledge, this is the first last-iterate convergence result outside the polyhedral setting. Next, we investigate three applications and derive a new algorithm based on this result. For the use of the KL inequality in optimization, we refer to [ 30 , 31 , 32 , 33 ] and references therein. This paper is organized as follows. In Section 2.1 , we briefly overview the FW algorithm and adapt it for maximizing a strongly convex function. Then we discuss the design choices within the algorithm and their consequences for the model assumptions. Then, we give the classical results regarding the FW algorithm for convex maximization problems. Moreover, we give a global convergence result under the KL assumption and also study its convergence rate. In Section 4 , we first give examples of the functions that satisfy the KL property. Next, we recognize previously proposed algorithms as a special case of the GFW algorithm. Finally, to our knowledge, we derive a new algorithm for the SDP relaxation of the Max-Cut problem. We follow standard notation and concepts which can be found in [ 30 , 18 ] . 2 Review of Existing Results In this section, we briefly review the Frank-Wolfe algorithm, the existing results for the analysis of the

Read the complete text