Search

We consider the composite minimization problem with the objective function being the sum of a continuously differentiable and a merely lower semicontinuous and extended-valued function. The proximal gradient method is probably the most popular solver for this class of problems. Its convergence theory typically requires that either the gradient of the smooth part of the objective function is globally Lipschitz continuous or the (implicit or explicit) a priori assumption that the iterates generated by this method are bounded. Some recent results show that, without these assumptions, the proximal gradient method, combined with a monotone stepsize strategy, is still globally convergent with a suitable rate-of-convergence under the Kurdyka-Lojasiewicz property. For a nonmonotone stepsize strategy, there exist some attempts to verify similar convergence results, but, so far, they need stronger assumptions. This paper is the first which shows that nonmonotone proximal gradient methods for composite optimization problems share essentially the same nice global and rate-of-convergence properties as its monotone counterparts, still without assuming a global Lipschitz assumption and without an a priori knowledge of the boundedness of the iterates.

In this paper, we introduce an inexact regularized proximal Newton method (IRPNM) that does not require any line search. The method is designed to minimize the sum of a twice continuously differentiable function $f$ and a convex (possibly non-smooth and extended-valued) function $\varphi$. Instead of controlling a step size by a line search procedure, we update the regularization parameter in a suitable way, based on the success of the previous iteration. The global convergence of the sequence of iterations and its superlinear convergence rate under a local H\"olderian error bound assumption are shown. Notably, these convergence results are obtained without requiring a global Lipschitz property for $ \nabla f $, which, to the best of the authors' knowledge, is a novel contribution for proximal Newton methods. To highlight the efficiency of our approach, we provide numerical comparisons with an IRPNM using a line search globalization and a modern FISTA-type method., Comment: 32 pages

We consider the general nonlinear optimization problem where the objective function has an additional term defined by the $ \ell_0 $-quasi-norm in order to promote sparsity of a solution. This problem is highly difficult due to its nonconvexity and discontinuity. We generalize some recent work and present a whole class of reformulations of this problem consisting of smooth nonlinear programs. This reformulated problem is shown to be equivalent to the original $ \ell_0 $-sparse optimization problem both in terms of local and global minima. The reformulation contains a complementarity constraint, and exploiting the particular structure of this reformulated problem, we introduce several problem-tailored constraint qualifications, first- and second-order optimality conditions and develop an exact penalty-type method which is shown to work extremely well on a whole bunch of different applications.

In this paper, we denoise a given noisy image by minimizing a smoothness promoting function over a set of local similarity measures which compare the mean of the given image and some candidate image on a large collection of subboxes. The associated convex optimization problem possesses a huge number of constraints which are induced by extended real-valued functions stemming from the Kullback--Leibler divergence. Alternatively, these nonlinear constraints can be reformulated as affine ones, which makes the model seemingly more tractable. For the numerical treatment of both formulations of the model (i.e., the original one as well as the one with affine constraints), we propose a rather general augmented Lagrangian method which is capable of handling the huge amount of constraints. A self-contained, derivative-free, global convergence theory is provided, allowing an extension to other problem classes. For the solution of the resulting subproblems in the setting of our suggested image denoising models, we make use of a suitable stochastic gradient method. Results of several numerical experiments are presented in order to compare both formulations and the associated augmented Lagrangian methods., Comment: 38 pages, 6 figures, 3 tables

We consider a composite optimization problem where the sum of a continuously differentiable and a merely lower semicontinuous function has to be minimized. The proximal gradient algorithm is the classical method for solving such a problem numerically. The corresponding global convergence and local rate-of-convergence theory typically assumes, besides some technical conditions, that the smooth function has a globally Lipschitz continuous gradient and that the objective function satisfies the Kurdyka-{\L}ojasiewicz property. Though this global Lipschitz assumption is satisfied in several applications where the objective function is, e.g., quadratic, this requirement is very restrictive in the non-quadratic case. Some recent contributions therefore try to overcome this global Lipschitz condition by replacing it with a local one, but, to the best of our knowledge, they still require some extra condition in order to obtain the desired global and rate-of-convergence results. The aim of this paper is to show that the local Lipschitz assumption together with the Kurdyka-{\L}ojasiewicz property is sufficient to recover these convergence results., Comment: 23 pages

We consider the sparse optimization problem with nonlinear constraints and an objective function, which is given by the sum of a general smooth mapping and an additional term defined by the $ \ell_0 $-quasi-norm. This term is used to obtain sparse solutions, but difficult to handle due to its nonconvexity and nonsmoothness (the sparsity-improving term is even discontinuous). The aim of this paper is to present two reformulations of this program as a smooth nonlinear program with complementarity-type constraints. We show that these programs are equivalent in terms of local and global minima and introduce a problem-tailored stationarity concept, which turns out to coincide with the standard KKT conditions of the two reformulated problems. In addition, a suitable constraint qualification as well as second-order conditions for the sparse optimization problem are investigated. These are then used to show that three Lagrange-Newton-type methods are locally fast convergent. Numerical results on different classes of test problems indicate that these methods can be used to drastically improve sparse solutions obtained by some other (globally convergent) methods for sparse optimization problems.

Optimization problems with composite functions consist of an objective function which is the sum of a smooth and a (convex) nonsmooth term. This particular structure is exploited by the class of proximal gradient methods and some of their generalizations like proximal Newton and quasi-Newton methods. In this paper, we propose a regularized proximal quasi-Newton method whose main features are: (a) the method is globally convergent to stationary points, (b) the globalization is controlled by a regularization parameter, no line search is required, (c) the method can be implemented very efficiently based on a simple observation which combines recent ideas for the computation of quasi-Newton proximity operators and compact representations of limited-memory quasi-Newton updates. Numerical examples for the solution of convex and nonconvex composite optimization problems indicate that the method outperforms several existing methods.

This paper provides a theoretical and numerical investigation of a penalty decomposition scheme for the solution of optimization problems with geometric constraints. In particular, we consider some situations where parts of the constraints are nonconvex and complicated, like cardinality constraints, disjunctive programs, or matrix problems involving rank constraints. By a variable duplication and decomposition strategy, the method presented here explicitly handles these difficult constraints, thus generating iterates which are feasible with respect to them, while the remaining (standard and supposingly simple) constraints are tackled by sequential penalization. Inexact optimization steps are proven sufficient for the esulting algorithm to work, so that it is employable even with difficult objective functions. The current work is therefore a significant generalization of existing papers on penalty decomposition methods. On the other hand, it is related to some recent publications which use an augmented Lagrangian idea to solve optimization problems with geometric constraints. Compared to these methods, the decomposition idea is shown to be numerically superior since it allows much more freedom in the choice of the subproblem solver, and since the number of certain (possibly expensive) projection steps is significantly less. Extensive numerical results on several highly complicated classes of optimization problems in vector and matrix paces indicate that the current method is indeed very efficient to solve these problems., Comment: Comput Optim Appl (2023)

We investigate finite-dimensional constrained structured optimization problems, featuring composite objective functions and set-membership constraints. Offering an expressive yet simple language, this problem class provides a modeling framework for a variety of applications. We study stationarity and regularity concepts, and propose a flexible augmented Lagrangian scheme. We provide a theoretical characterization of the algorithm and its asymptotic properties, deriving convergence results for fully nonconvex problems. It is demonstrated how the inner subproblems can be solved by off-the-shelf proximal methods, notwithstanding the possibility to adopt any solvers, insofar as they return approximate stationary points. Finally, we describe our matrix-free implementation of the proposed algorithm and test it numerically. Illustrative examples show the versatility of constrained composite programs as a modeling tool and expose difficulties arising in this vast problem class., Comment: 41 pages, 5 figures

Composite optimization problems, where the sum of a smooth and a merely lower semicontinuous function has to be minimized, are often tackled numerically by means of proximal gradient methods as soon as the lower semicontinuous part of the objective function is of simple enough structure. The available convergence theory associated with these methods (mostly) requires the derivative of the smooth part of the objective function to be (globally) Lipschitz continuous, and this might be a restrictive assumption in some practically relevant scenarios. In this paper, we readdress this classical topic and provide convergence results for the classical (monotone) proximal gradient method and one of its nonmonotone extensions which are applicable in the absence of (strong) Lipschitz assumptions. This is possible since, for the price of forgoing convergence rates, we omit the use of descent-type lemmas in our analysis., Comment: 23 pages

This paper is devoted to the theoretical and numerical investigation of an augmented Lagrangian method for the solution of optimization problems with geometric constraints. Specifically, we study situations where parts of the constraints are nonconvex and possibly complicated, but allow for a fast computation of projections onto this nonconvex set. Typical problem classes which satisfy this requirement are optimization problems with disjunctive constraints (like complementarity or cardinality constraints) as well as optimization problems over sets of matrices which have to satisfy additional rank constraints. The key idea behind our method is to keep these complicated constraints explicitly in the constraints and to penalize only the remaining constraints by an augmented Lagrangian function. The resulting subproblems are then solved with the aid of a problem-tailored nonmonotone projected gradient method. The corresponding convergence theory allows for an inexact solution of these subproblems. Nevertheless, the overall algorithm computes so-called Mordukhovich-stationary points of the original problem under a mild asymptotic regularity condition, which is generally weaker than most of the respective available problem-tailored constraint qualifications. Extensive numerical experiments addressing complementarity- and cardinality-constrained optimization problems as well as a semidefinite reformulation of MAXCUT problems visualize the power of our approach., Comment: 54 pages, 5 figures, 5 tables

Optimization theory in Banach spaces suffers from the lack of available constraint qualifications. Despite the fact that there exist only a very few constraint qualifications, they are, in addition, often violated even in simple applications. This is very much in contrast to finite-dimensional nonlinear programs, where a large number of constraint qualifications is known. Since these constraint qualifications are usually defined using the set of active inequality constraints, it is difficult to extend them to the infinite-dimensional setting. One exception is a recently introduced sequential constraint qualification based on asymptotic KKT conditions. This paper shows that this so-called asymptotic KKT regularity allows suitable extensions to the Banach space setting in order to obtain new constraint qualifications. The relation of these new constraint qualifications to existing ones is discussed in detail. Their usefulness is also shown by several examples as well as an algorithmic application to the class of augmented Lagrangian methods.

This paper deals with regularized Newton methods, a flexible class of unconstrained optimization algorithms that is competitive with line search and trust region methods and potentially combines attractive elements of both. The particular focus is on combining regularization with limited memory quasi-Newton methods by exploiting the special structure of limited memory algorithms. Global convergence of regularization methods is shown under mild assumptions and the details of regularized limited memory quasi-Newton updates are discussed including their compact representations. Numerical results using all large-scale test problems from the CUTEst collection indicate that our regularized version of L-BFGS is competitive with state-of-the-art line search and trust-region L-BFGS algorithms and previous attempts at combining L-BFGS with regularization, while potentially outperforming some of them, especially when nonmonotonicity is involved., Comment: 23 pages, 4 figures

This paper deals with quasi-variational inequality problems (QVIs) in a generic Banach space setting. We provide a theoretical framework for the analysis of such problems which is based on two key properties: the pseudomonotonicity (in the sense of Brezis) of the variational operator and a Mosco-type continuity of the feasible set mapping. We show that these assumptions can be used to establish the existence of solutions and their computability via suitable approximation techniques. In addition, we provide a practical and easily verifiable sufficient condition for the Mosco-type continuity property in terms of suitable constraint qualifications. Based on the theoretical framework, we construct an algorithm of augmented Lagrangian type which reduces the QVI to a sequence of standard variational inequalities. A full convergence analysis is provided which includes the existence of solutions of the subproblems as well as the attainment of feasibility and optimality. Applications and numerical results are included to demonstrate the practical viability of the method., Comment: 27 pages, 3 figures

Switching-constrained optimization problems form a difficult class of mathematical programs since their feasible set is almost disconnected while standard constraint qualifications are likely to fail at several feasible points. That is why the application of standard methods from nonlinear programming does not seem to be promising in order to solve such problems. In this paper, we adapt the relaxation method from Kanzow and Schwartz (SIAM J. Optim., 23(2):770-798, 2013) for the numerical treatment of mathematical programs with complementarity constraints to the setting of switching-constrained optimization. It is shown that the proposed method computes M-stationary points under mild assumptions. Furthermore, we comment on other possible relaxation approaches which can be used to tackle mathematical programs with switching constraints. As it turns out, adapted versions of Scholtes' global relaxation scheme as well as the relaxation scheme of Steffensen and Ulbrich only find W-stationary points of switching-constrained optimization problems in general. Some computational experiments visualize the performance of the proposed relaxation method., Comment: 33 pages, 8 figures

We propose a variant of the classical augmented Lagrangian method for constrained optimization problems in Banach spaces. Our theoretical framework does not require any convexity or second-order assumptions and allows the treatment of inequality constraints with infinite-dimensional image space. Moreover, we discuss the convergence properties of our algorithm with regard to feasibility, global optimality, and KKT conditions. Some numerical results are given to illustrate the practical viability of the method., Comment: 23 pages

We propose an augmented Lagrangian-type algorithm for the solution of generalized Nash equilibrium problems (GNEPs). Specifically, we discuss the convergence properties with regard to both feasibility and optimality of limit points. This is done by introducing a secondary GNEP as a new optimality concept. In this context, special consideration is given to the role of suitable constraint qualifications that take into account the particular structure of GNEPs. Furthermore, we consider the behaviour of the method for jointly-convex GNEPs and describe a modification which is tailored towards the computation of variational equilibria. Numerical results are included to illustrate the practical performance of the overall method., Comment: 25 pages

This paper deals with a general form of variational problems in Banach spaces which encompasses variational inequalities as well as minimization problems. We prove a characterization of local error bounds for the distance to the (primal-dual) solution set and give a sufficient condition for such an error bound to hold. In the second part of the paper, we consider an algorithm of augmented Lagrangian type for the solution of such variational problems. We give some global convergence properties of the method and then use the error bound theory to provide estimates for the rate of convergence and to deduce boundedness of the sequence of penalty parameters. Finally, numerical results for optimal control, Nash equilibrium problems, and elliptic parameter estimation problems are presented., Comment: 27 pages

This paper concerns developing a numerical method of the Newton type to solve systems of nonlinear equations described by nonsmooth continuous functions. We propose and justify a new generalized Newton algorithm based on graphical derivatives, which have never been used to derive a Newton-type method for solving nonsmooth equations. Based on advanced techniques of variational analysis and generalized differentiation, we establish the well-posedness of the algorithm, its local superlinear convergence, and its global convergence of the Kantorovich type. Our convergence results hold with no semismoothness assumption, which is illustrated by examples. The algorithm and main results obtained in the paper are compared with well-recognized semismooth and $B$-differentiable versions of Newton's method for nonsmooth Lipschitzian equations.