Search

The notion of sharp minima, given by Polyak, is an important tool in studying the convergence analysis of algorithms designed to solve optimization problems. It has been studied extensively for variational inequality problems and equilibrium problems. In this paper, the convergence analysis of the sequence generated by proximal point method for quasi-equilibrium problem (QEP) will be established under sharp minima conditions. Further, the characterizations of weak sharp solution for QEP are provided. We also introduce an inexact proximal point method and demonstrate the convergence of the sequence for solving the QEP. Finally, we deduce the proximal point approximation for generalized Nash equilibrium problem. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a generalized inexact scalarized proximal point algorithm to find Pareto-Clarke critical points and Pareto efficient solutions of quasiconvex multivalued functions defined on Hadamard manifolds considering vectorial and scalar errors to find a critical point of the regularized proximal function in each iteration. Under some assumptions on the problem, we obtain the global convergence of the sequence to a Pareto-Clarke critical point and assuming an extra condition on the proximal parameters we establish convergence to a Pareto efficient solution, approximately linear/superlinear rate of convergence and finite termination of the algorithm. In the convex case, we prove the convergence to a Pareto efficient solution point (more than a weak Pareto efficient solution point). The results of the paper are new even in the Euclidean space. [ABSTRACT FROM AUTHOR]

In this work, an inexact proximal point algorithm is proposed for solving unconstrained multiobjective optimization problems with locally Lipschitz and quasi-convex objective functions. In this algorithm, we use quasi-distance in the regularization term and consider the ε -approximate solution of the scalarization subproblem as well as the ε -subdifferential in the optimality condition of the subproblem. This algorithm is shown to be well-defined. Then, it is proved that each accumulation point, if any, of the sequence generated by the algorithm is a Pareto-Clarke critical point of the problem. [ABSTRACT FROM AUTHOR]

In this work, we propose an inexact proximal point method for solving unconstrained quasiconvex multiobjective optimization problems. Two error criteria (the absolute one and the relative one) of the algorithm are considered, and it is proved under some mild assumptions that the sequence generated by the algorithm in both cases converges to a Pareto stationary point when the objective functions are continuously differentiable, while to a weak Pareto optimal point of the problem when the objective functions are proper convex and lower semicontinuous. Moreover, by using an additional growth condition, we show that the convergence rate of the method under the relative error criteria is linear if the regularization parameters are bounded, and further superlinear if these parameters converge to zero. The main results established in the present work generalize and improve some corresponding ones existing in the literature. Some numerical experiments are also presented. [ABSTRACT FROM AUTHOR]

This paper deals with local criteria for the convergence to a global minimiser for gradient flow trajectories and their discretisations. To obtain quantitative estimates on the speed of convergence, we consider variations on the classical Kurdyka–Łojasiewicz inequality for a large class of parameter functions. Our assumptions are given in terms of the initial data, without any reference to an equilibrium point. The main results are convergence statements for gradient flow curves and proximal point sequences to a global minimiser, together with sharp quantitative estimates on the speed of convergence. These convergence results apply in the general setting of lower semicontinuous functionals on complete metric spaces, generalising recent results for smooth functionals on \mathbb {R}^n. While the non-smooth setting covers very general spaces, it is also useful for (non)-smooth functionals on \mathbb {R}^n. [ABSTRACT FROM AUTHOR]

This paper has two parts. In the mathematical part, we present two inexact versions of the proximal point method for solving quasi-equilibrium problems (QEP) in Hilbert spaces. Under mild assumptions, we prove that the methods find a solution to the quasi-equilibrium problem with an approximated computation of each iteration or using a perturbation of the regularized bifunction. In the behavioral part, we justify the choice of the new perturbation, with the help of the main example that drives quasi-equilibrium problems: the Cournot duopoly model, which founded game theory. This requires to exhibit a new QEP reformulation of the Cournot model that will appear more intuitive and rigorous. It leads directly to the formulation of our perturbation function. Some numerical experiments show the performance of the proposed methods. [ABSTRACT FROM AUTHOR]

Inertial procedures attached to classical methods for solving monotone inclusion and optimization problems, which arise from an implicit discretization of second-order differential equations, have shown a remarkable acceleration effect with respect to these classical algorithms. Among these classical methods, one can mention steepest descent, alternate directions, and the proximal point methods. For the problem of finding zeroes of set-valued operators, the convergence analysis of all existing inertial-proximal methods requires the monotonicity of the operator. We present here a new inertial-proximal point algorithm for finding zeroes of set-valued operators, whose convergence is established for a relevant class of nonmonotone operators, namely the hypomonotone ones. [ABSTRACT FROM AUTHOR]

In this paper, we investigate and analyse the strong convergence of the sequence generated by an inexact proximal point method with possible unbounded errors for finding zeros of monotone operators in Hadamard spaces. We show that the boundedness of the generated sequence is equivalent to the zero set of the operator to be nonempty. In this case, we prove the strong convergence of the generated sequence to a zero of the operator. We also provide some applications of our main results and give a numerical example to show the performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Minimax optimization has become a central tool in machine learning with applications in robust optimization, reinforcement learning, GANs, etc. These applications are often nonconvex–nonconcave, but the existing theory is unable to identify and deal with the fundamental difficulties this poses. In this paper, we study the classic proximal point method (PPM) applied to nonconvex–nonconcave minimax problems. We find that a classic generalization of the Moreau envelope by Attouch and Wets provides key insights. Critically, we show this envelope not only smooths the objective but can convexify and concavify it based on the level of interaction present between the minimizing and maximizing variables. From this, we identify three distinct regions of nonconvex–nonconcave problems. When interaction is sufficiently strong, we derive global linear convergence guarantees. Conversely when the interaction is fairly weak, we derive local linear convergence guarantees with a proper initialization. Between these two settings, we show that PPM may diverge or converge to a limit cycle. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of minimizing a continuously differentiable function on the Stiefel manifold. To solve this problem, we develop a geodesic-free proximal point algorithm equipped with Euclidean distance that does not require use of the Riemannian metric. The proposed method can be regarded as an iterative fixed-point method that repeatedly applies a proximal operator to an initial point. In addition, we establish the global convergence of the new approach without any restrictive assumption. Numerical experiments on linear eigenvalue problems and the minimization of sums of heterogeneous quadratic functions show that the developed algorithm is competitive with some procedures existing in the literature. [ABSTRACT FROM AUTHOR]

In this study, a convex proximal point algorithm (CPPA) is considered for solving constrained non-convex problems, and new theoretical results are proposed. It is proved that every cluster point of CPPA is a stationary point, and the initial point of CPPA is key to global optimization. Several sufficient conditions for the initial point selection are provided for CPPA to find the global minimum. Motivated by these results, numerical experiments were conducted on non-convex quadratic programming problems with convex quadratic constraints. The performance of CPPAs was compared, with the initial point randomly selected or obtained through the Lagrangian dual problem. The numerical results demonstrate that the quality of the CPPA with the computed Lagrangian dual initial point is much better than that with the random initial point, in terms of the objective function value. [ABSTRACT FROM AUTHOR]

Stochastic optimization problems often involve data distributions that change in reaction to the decision variables. This is the case, for example, when members of the population respond to a deployed classifier by manipulating their features so as to improve the likelihood of being positively labeled. Recent works on performative prediction identify an intriguing solution concept for such problems: find the decision that is optimal with respect to the static distribution that the decision induces. Continuing this line of work, we show that, in the strongly convex setting, typical stochastic algorithms—originally designed for static problems—can be applied directly for finding such equilibria with little loss in efficiency. The reason is simple to explain: the main consequence of the distributional shift is that it corrupts algorithms with a bias that decays linearly with the distance to the solution. Using this perspective, we obtain convergence guarantees for popular algorithms, such as stochastic gradient, clipped gradient, prox-point, and dual averaging methods, along with their accelerated and proximal variants. In realistic applications, deployment of a decision rule is often much more expensive than sampling. We show how to modify the aforementioned algorithms so as to maintain their sample efficiency when performing only logarithmically many deployments. Funding: This work was supported by the Division of Computing and Communication Foundations [Grant 1740551] and Division of Mathematical Sciences [Grant 1651851]. [ABSTRACT FROM AUTHOR]

We propose an inertial proximal point method for variational inclusion involving difference of two maximal monotone vector fields in Hadamard manifolds. We prove that if the sequence generated by the method is bounded, then every cluster point is a solution of the non-monotone variational inclusion. Some sufficient conditions for boundedness and full convergence of the sequence are presented. The efficiency of the method is verified by numerical experiments comparing its performance with classical versions of the method for monotone and non-monotone problems. [ABSTRACT FROM AUTHOR]

Gradient boosting is a prediction method that iteratively combines weak learners to produce a complex and accurate model. From an optimization point of view, the learning procedure of gradient boosting mimics a gradient descent on a functional variable. This paper proposes to build upon the proximal point algorithm, when the empirical risk to minimize is not differentiable, in order to introduce a novel boosting approach, called proximal boosting. It comes with a compagnon algorithm inspired by Grubb and Bagnell (2011) and called residual proximal boosting , which is aimed at better controlling the approximation error. Theoretical convergence is proved for these two procedures under different hypotheses on the empirical risk and advantages of leveraging proximal methods for boosting are illustrated by numerical experiments on simulated and real-world data. In particular, we exhibit a favorable comparison over gradient boosting regarding convergence rate and prediction accuracy. [ABSTRACT FROM AUTHOR]

In this paper we present an inexact scalarization proximal point algorithm to solve unconstrained multiobjective minimization problems where the objective functions are quasiconvex and locally Lipschitz. Under some natural assumptions on the problem, we prove that the sequence generated by the algorithm is well defined and converges. Then providing two error criteria we obtain two versions of the algorithm and it is proved that each sequence converges to a Pareto–Clarke critical point of the problem; furthermore, it is also proved that assuming an extra condition, the convergence rate of one of these versions is linear when the regularization parameters are bounded and superlinear when these parameters converge to zero. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of minimizing a continuously differentiable function on the Stiefel manifold. To solve this problem, we develop a geodesic-free proximal point algorithm equipped with Euclidean distance that does not require use of the Riemannian metric. The proposed method can be regarded as an iterative fixed-point method that repeatedly applies a proximal operator to an initial point. In addition, we establish the global convergence of the new approach without any restrictive assumption. Numerical experiments on linear eigenvalue problems and the minimization of sums of heterogeneous quadratic functions show that the developed algorithm is competitive with some procedures existing in the literature.

The goal of this paper is to propose and investigate new iterative methods for examining an approximate solution of a fixed-point problem, an equilibrium problem, and a finite collection of variational inclusions in the Hadamard manifold's structure. Operating under some assumptions, we extend the proximal point algorithm to estimate the common solution of stated problems and obtain a strong convergence theorem for the common solution. We also present several consequences of the proposed iterative methods and their convergence results. [ABSTRACT FROM AUTHOR]

This paper introduces QPDO, a primal-dual method for convex quadratic programs which builds upon and weaves together the proximal point algorithm and a damped semismooth Newton method. The outer proximal regularization yields a numerically stable method, and we interpret the proximal operator as the unconstrained minimization of the primal-dual proximal augmented Lagrangian function. This allows the inner Newton scheme to exploit sparse symmetric linear solvers and multi-rank factorization updates. Moreover, the linear systems are always solvable independently from the problem data and exact linesearch can be performed. The proposed method can handle degenerate problems, provides a mechanism for infeasibility detection, and can exploit warm starting, while requiring only convexity. We present details of our open-source C implementation and report on numerical results against state-of-the-art solvers. QPDO proves to be a simple, robust, and efficient numerical method for convex quadratic programming. [ABSTRACT FROM AUTHOR]

In this paper, a reduced proximal-point homotopy (RPP-Hom) method is presented for large-scale non-convex box constrained quadratic programming (BQP) problems. As the outer iteration, at each step, the reduced proximal-point (RPP) algorithm applies the proximal point algorithm to a reduced BQP problem. The variables of the reduced subproblem include all free variables and variables at bound with respect to which the optimality conditions are violated. The RPP subproblem is solved by, as the inner iteration, an efficient piecewise linear homotopy path following method. A special termination criterion for the RPP algorithm is given and the global convergence as well as the locally linear convergence to a Karush-Kuhn-Tucker point is proved. Furthermore, a random perturbation procedure is given to modify RPP such that it converges to a local minimizer with probability 1. An accelerated version of RPP is also presented. Numerical experiments show that the RPP-Hom method outperforms the state-of-the-art algorithms for most of the benchmark problems, especially for training non-convex support vector machine. [ABSTRACT FROM AUTHOR]

We introduce exponential augmented Lagrangian methods for solving equilibrium problems in finite-dimensional spaces, extending the so-called quadratic augmented Lagrangian methods. Unlike the quadratic augmented Lagrangian methods that are at most first-order differentiable, our exponential augmented Lagrangian methods can be differentiable at any order. Therefore, second-order methods, such as Newton's methods, can be used to solve the subproblems generated by the augmented Lagrangian methods. We also present numerical results obtained based on implementing our proposed algorithms in Matlab. [ABSTRACT FROM AUTHOR]

In this paper we generalize the Interior Point-Proximal Method of Multipliers (IP-PMM) presented in Pougkakiotis and Gondzio (Comput Optim Appl 78:307–351, 2021. https://doi.org/10.1007/s10589-020-00240-9) for the solution of linear positive Semi-Definite Programming (SDP) problems, allowing inexactness in the solution of the associated Newton systems. In particular, we combine an infeasible Interior Point Method (IPM) with the Proximal Method of Multipliers (PMM) and interpret the algorithm (IP-PMM) as a primal-dual regularized IPM, suitable for solving SDP problems. We apply some iterations of an IPM to each sub-problem of the PMM until a satisfactory solution is found. We then update the PMM parameters, form a new IPM neighbourhood, and repeat this process. Given this framework, we prove polynomial complexity of the algorithm, under mild assumptions, and without requiring exact computations for the Newton directions. We furthermore provide a necessary condition for lack of strong duality, which can be used as a basis for constructing detection mechanisms for identifying pathological cases within IP-PMM. [ABSTRACT FROM AUTHOR]

In this paper, we study the convergence of a proximal point method for solving quasi-equilibrium problems (QEP) in Hilbert spaces. We extent the method proposed by Moudafi [Proximal point algorithm extended to equilibrium problems. J Nat Geom. 1999;15(1-2):91–100] and Iusem and Sosa [Iterative algorithms for equilibrium problems. Optimization. 2003;52(3):301–316] to the more general context of quasi-equilibrium problems. In our method a quasi-equilibrium problem is solved by computing a solution of an equilibrium problem at each iteration. We obtain weak convergence of the sequence to a solution of the QEP under some mild assumptions. Some encouraging numerical experiments are presented to show the performance of the method. [ABSTRACT FROM AUTHOR]

For solving constrained multiobjective problems with a vector-valued DC (difference of convex) objective function, we consider a vectorial Bregman regularized proximal point method which extends both the scalar proximal point method for DC functions and the vectorial proximal point method for vector-valued convex functions. By using a vectorial regularization function, our method does not use auxiliary vectorial sequences to make the method a vectorial one but providing an extra flexibility to the method. Some encouraging numerical experiments are presented. [ABSTRACT FROM AUTHOR]

The goal of this paper is to propose and investigate new iterative methods for examining an approximate solution of a fixed-point problem, an equilibrium problem, and a finite collection of variational inclusions in the Hadamard manifold’s structure. Operating under some assumptions, we extend the proximal point algorithm to estimate the common solution of stated problems and obtain a strong convergence theorem for the common solution. We also present several consequences of the proposed iterative methods and their convergence results.