Search

In this paper, we propose a modified Fletcher–Reeves conjugate gradient method. The new search direction is calculated in such a way that it is close to a three term PRP conjugate gradient method. In particular, we introduce a parameter that adjusts the weight applied to the standard FR method, ensuring that our CG method satisfies the sufficient descent property. Global convergence is established under the strong Wolfe line search. The method is tested on a set of unconstrained optimization problems and the results demonstrate the new method's competency against existing methods. Furthermore, the new method is implemented to solve an image restoration problem of removing impulse noise from a digital image. [ABSTRACT FROM AUTHOR]

Minimization of the order-value function is part of a large family of problems involving functions whose value is calculated by sorting values from a set or subset of other functions. The order-value function has as particular cases the minimum and maximum functions of a set of functions and is well suited for applications involving robust estimation. In this paper, a first-order method with quadratic regularization to solve the problem of minimizing the order-value function is proposed. An optimality condition for the problem and theoretical results of iteration complexity and evaluation complexity for the proposed method are presented. The applicability of the problem and method to parameter estimation problems with outliers is illustrated. [ABSTRACT FROM AUTHOR]

In this paper, we investigate a class of unconstrained multiobjective optimization problems (abbreviated as, MPQs), where the components of the objective function are locally Lipschitz and quasiconvex. To solve MPQs, we introduce an inexact proximal point method with Bregman distances (abbreviated as, IPPMB) via Mordukhovich limiting subdifferentials. We establish the well-definedness of the sequence generated by the IPPMB algorithm. Based on two versions of error criteria, we introduce two variants of IPPMB, namely, IPPMB1 and IPPMB2. Moreover, we establish that the sequences generated by the IPPMB1 and IPPMB2 algorithms converge to the Pareto–Mordukhovich critical point of the problem MPQ. In addition, we derive that if the components of the objective function of MPQ are convex, then the sequences converge to the weak Pareto efficient solution of MPQ. Furthermore, we discuss the linear and superlinear convergence of the sequence generated by the IPPMB2 algorithm. We furnish several non-trivial numerical examples to demonstrate the effectiveness of the proposed algorithms and solve them by employing MATLAB R2023b. To demonstrate the applicability and significance of the IPPMB algorithm, we solve a nonsmooth large-scale sparse quasiconvex multiobjective optimization by employing MATLAB R2023b. [ABSTRACT FROM AUTHOR]

In this paper, we consider constrained optimization problems where both the objective and constraint functions are of the black-box type. Furthermore, we assume that the nonlinear inequality constraints are non-relaxable, i.e. the values of the objective function and constraints cannot be computed outside of the feasible region. This situation happens frequently in practice especially in the black-box setting where function values are typically computed by means of complex simulation programs which may fail to execute if the considered point is outside of the feasible region. For such problems, we propose a new derivative-free optimization method which is based on the use of a merit function that handles inequality constraints by means of a log-barrier approach and equality constraints by means of an exterior penalty approach. We prove the convergence of the proposed method to KKT stationary points of the problem under standard assumptions (we do not require any convexity assumption). Furthermore, we also carry out a preliminary numerical experience on standard test problems and comparison with state-of-the-art solvers showing the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

Optimization problems involving mixed variables (i.e., variables of numerical and categorical nature) can be challenging to solve, especially in the presence of mixed-variable constraints. Moreover, when the objective function is the result of a complicated simulation or experiment, it may be expensive-to-evaluate. This paper proposes a novel surrogate-based global optimization algorithm to solve linearly constrained mixed-variable problems up to medium size (around 100 variables after encoding). The proposed approach is based on constructing a piecewise affine surrogate of the objective function over feasible samples. We assume the objective function is black-box and expensive-to-evaluate, while the linear constraints are quantifiable, unrelaxable, a priori known, and are cheap to evaluate. We introduce two types of exploration functions to efficiently search the feasible domain via mixed-integer linear programming solvers. We also provide a preference-based version of the algorithm designed for situations where only pairwise comparisons between samples can be acquired, while the underlying objective function to minimize remains unquantified. The two algorithms are evaluated on several unconstrained and constrained mixed-variable benchmark problems. The results show that, within a small number of required experiments/simulations, the proposed algorithms can often achieve better or comparable results than other existing methods. [ABSTRACT FROM AUTHOR]

This paper proposes a new approach for solving Quadratically Constrained Feasibility Problems (QCFPs). We introduce an isomorphic mapping (one-to-one and onto correspondence), which equivalently converts the QCFP to an optimization problem called the Inside-Ellipsoids Outside-Sphere Problem (IEOSP). This mapping preserves the convexity of convex constraints, but it converts all non-convex constraints to convex ones. The QCFP is a feasibility problem with non-convex constraints, while the IEOSP is an optimization problem with a convex feasible region and a non-convex objective function. It is shown that the global optimal solution of IEOSP is a feasible solution of the QCFP. Comparing the structures of QCFP and the proposed IEOSP, the second model only has one extra variable compared to the original QCFP because it employs one slack variable for the mapping. Thus, the problem dimension approximately remains unchanged. Due to the convexity of all constraints in IEOSP, it has a well-defined feasible region. Therefore, it can be solved much easier than the original QCFP. This paper proposes a solution algorithm for IEOSP that iteratively solves a convex optimization problem. The algorithm is mathematically shown to reach either a feasible solution of the QCFP or a local solution of the IEOSP. To illustrate our theoretical developments, a comprehensive numerical experiment is performed, and 500 different QCFPs are studied. All these numerical experiments confirm the promising performance and applicability of our theoretical developments in the current paper. [ABSTRACT FROM AUTHOR]

Stochastic sequential quadratic optimization (SQP) methods for solving continuous optimization problems with nonlinear equality constraints have attracted attention recently, such as for solving large-scale data-fitting problems subject to nonconvex constraints. However, for a recently proposed subclass of such methods that is built on the popular stochastic-gradient methodology from the unconstrained setting, convergence guarantees have been limited to the asymptotic convergence of the expected value of a stationarity measure to zero. This is in contrast to the unconstrained setting in which almost-sure convergence guarantees (of the gradient of the objective to zero) can be proved for stochastic-gradient-based methods. In this paper, new almost-sure convergence guarantees for the primal iterates, Lagrange multipliers, and stationarity measures generated by a stochastic SQP algorithm in this subclass of methods are proved. It is shown that the error in the Lagrange multipliers can be bounded by the distance of the primal iterate to a primal stationary point plus the error in the latest stochastic gradient estimate. It is further shown that, subject to certain assumptions, this latter error can be made to vanish by employing a running average of the Lagrange multipliers that are computed during the run of the algorithm. The results of numerical experiments are provided to demonstrate the proved theoretical guarantees. [ABSTRACT FROM AUTHOR]

For over 10 years, the constraint integer programming framework SCIP has been extended by capabilities for the solution of convex and nonconvex mixed-integer nonlinear programs (MINLPs). With the recently published version 8.0, these capabilities have been largely reworked and extended. This paper discusses the motivations for recent changes and provides an overview of features that are particular to MINLP solving in SCIP. Further, difficulties in benchmarking global MINLP solvers are discussed and a comparison with several state-of-the-art global MINLP solvers is provided. [ABSTRACT FROM AUTHOR]

There is growing interest in nonconvex minimax problems that is driven by an abundance of applications. Our focus is on nonsmooth, nonconvex-strongly concave minimax, thus departing from the more common weakly convex and smooth models assumed in the recent literature. We present proximal gradient schemes with either parallel or alternating steps. We show that both methods can be analyzed through a single scheme within a unified analysis that relies on expanding a general convergence mechanism used for analyzing nonconvex, nonsmooth optimization problems. In contrast to the current literature, which focuses on the complexity of obtaining nearly approximate stationary solutions, we prove subsequence convergence to a critical point of the primal objective and global convergence when the latter is semialgebraic. Furthermore, the complexity results we provide are with respect to approximate stationary solutions. Lastly, we expand the scope of problems that can be addressed by generalizing one of the steps with a Bregman proximal gradient update, and together with a few adjustments to the analysis, this allows us to extend the convergence and complexity results to this broader setting. Funding: The research of E. Cohen was partially supported by a doctoral fellowship from the Israel Science Foundation [Grant 2619-20] and Deutsche Forschungsgemeinschaft [Grant 800240]. The research of M. Teboulle was partially supported by the Israel Science Foundation [Grant 2619-20] and Deutsche Forschungsgemeinschaft [Grant 800240]. [ABSTRACT FROM AUTHOR]

The primary objective of this study is to establish the convergence theorem associated with the modified inertial projected forward–backward algorithm using line search techniques. Many applications in applied sciences can be modeled as constrained convex minimization problems. Our numerical experiments offer practical applications for resolving image deblurring issues. The results of our numerical analysis conclusively indicate that the proposed algorithms exhibit greater efficiency than those previously introduced in the literature. [ABSTRACT FROM AUTHOR]

We design new projective forward–backward algorithms for constrained minimization problems. We then discuss its weak convergence via a new linesearch that the hypothesis on the Lipschitz constant of the gradient of functions is avoided. We provide its applications to solve image deblurring and image inpainting. Finally, we discuss the optimal selection of parameters that are proposed in algorithms in terms of PSNR and SSIM. It reveals that our new algorithm outperforms some recent methods introduced in the literature. [ABSTRACT FROM AUTHOR]

In this study, we introduce a new nonmonotone trust region method with a simple cubic model to solve the unconstrained optimization problems (UCM). We improved the adaptive cubic regularization method by using a real positive definite scalar matrix instead of the exact Hessian and combining it with the nonmonotone technique. In addition, under some proper assumptions, the global convergence of the introduced method is established. Numerical tests on a set of standard minimization problems are reported and show that the proposed algorithm is efficient and robust compared to the other given methods. [ABSTRACT FROM AUTHOR]

Finding the optimal design of experiments in the Bayesian setting typically requires estimation and optimization of the expected information gain functional. This functional consists of one outer and one inner integral, separated by the logarithm function applied to the inner integral. When the mathematical model of the experiment contains uncertainty about the parameters of interest and nuisance uncertainty, (i.e., uncertainty about parameters that affect the model but are not themselves of interest to the experimenter), two inner integrals must be estimated. Thus, the already considerable computational effort required to determine good approximations of the expected information gain is increased further. The Laplace approximation has been applied successfully in the context of experimental design in various ways, and we propose two novel estimators featuring the Laplace approximation to alleviate the computational burden of both inner integrals considerably. The first estimator applies Laplace’s method followed by a Laplace approximation, introducing a bias. The second estimator uses two Laplace approximations as importance sampling measures for Monte Carlo approximations of the inner integrals. Both estimators use Monte Carlo approximation for the remaining outer integral estimation. We provide four numerical examples demonstrating the applicability and effectiveness of our proposed estimators. [ABSTRACT FROM AUTHOR]

Low-rank tensor approximations with closed and convex constraints, e.g., nonnegative entries or Lorentz cones, have become increasingly important and ubiquitous in the era of data analysis. Proposing a unified approach to solve this type-dependent problem is challenging. We, in this paper, present a spectral projective gradient method to find a structured tensor factorization over closed convex sets. This factorization is a non-convex optimization problem, and even finding an exact nonnegative tensor approximation of dimension 2 is NP-hard. In addition to the classical choice of steplength, an available spectral projected gradient direction is incorporated to alleviate further trial projections during the search process. Convergence properties for this updated procedure are given. In numerical results, we see that this approach exhibits a unified strategy and remarkable performance in various well-known problems. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel derivative-free projection algorithm based on the classical Polak–Ribiére–Polyak (PRP) method. This algorithm designs a search direction with sufficient descent and trust region properties, integrating an efficient line search approach and projection techniques. Under standard assumptions, the global convergence of the proposed algorithm is established. Numerical experiments demonstrate that the proposed algorithm outperforms two existing algorithms in terms of efficiency and robustness, and is successfully applied to sparse signal recovery and image denoising problems. [ABSTRACT FROM AUTHOR]

Clustering methods aim to categorize the elements of a dataset into groups according to the similarities and dissimilarities of the elements. This paper proposes the Multi-objective Clustering Algorithm (MCA), which combines clustering methods with the Nondominated Sorting Genetic Algorithm II. In this way, the proposed algorithm can automatically define the optimal number of clusters and partition the elements based on clustering measures. For this, 6 intra-clustering and 7 inter-clustering measures are explored, combining them 2-to-2, to define the most appropriate pair of measures to be used in a bi-objective approach. Out of the 42 possible combinations, 6 of them were considered the most appropriate, since they showed an explicitly conflicting behavior among the measures. The results of these 6 Pareto fronts were combined into two Pareto fronts, according to the measure of intra-clustering that the combination has in common. The elements of these Pareto fronts were analyzed in terms of dominance, so the nondominanted ones were kept, generating a hybrid Pareto front composed of solutions provided by different combinations of measures. The presented approach was validated on three benchmark datasets and also on a real dataset. The results were satisfactory since the proposed algorithm could estimate the optimal number of clusters and suitable dataset partitions. The obtained results were compared with the classical k-means and DBSCAN algorithms, and also two hybrid approaches, the Clustering Differential Evolution, and the Game-Based k-means algorithms. The MCA results demonstrated that they are competitive, mainly for the advancement of providing a set of optimum solutions for the decision-maker. [ABSTRACT FROM AUTHOR]

We develop numerically efficient methods for verifying monotonicity of 2-additive fuzzy measures. The problem is translated to verifying if a point in a high dimensional space belongs to a polytope. We take advantage of compact vertex representation of the polytope of 2-additive fuzzy measures and show polynomial solvability of that problem, as opposed to verifying an exponentially large number of linear inequalities. We formulate a method based on linear programming which is several orders of magnitude more efficient than the baseline, and then further reduce the set of inequalities and present a method with linear complexity relative to the dimension of the underlying vector space. The methods presented are benchmarked numerically. [ABSTRACT FROM AUTHOR]

This paper discusses a class of two-block smooth large-scale optimization problems with both linear equality and linear inequality constraints, which have a wide range of applications, such as economic power dispatch, data mining, signal processing, etc. Our goal is to develop a novel partially feasible distributed (PFD) sequential quadratic optimization (SQO) method (PFD-SQOM) for this kind of problems. The design of the method is based on the ideas of SQO method and augmented Lagrangian Jacobi splitting scheme as well as feasible direction method, which decomposes the quadratic optimization (QO) subproblem into two small-scale QOs that can be solved independently and parallelly. A novel disturbance contraction term that can be suitably adjusted is introduced into the inequality constraints so that the feasible step size along the search direction can be increased to 1. The new iteration points are generated by the Armijo line search and the partially augmented Lagrangian function that only contains equality constraints as the merit function. The iteration points always satisfy all the inequality constraints of the problem. The global convergence and iteration complexity O (1 / ε 2) of the proposed PFD-SQOM are obtained under appropriate assumptions without the Kurdyka–Łojasiewicz (KL) property. Furthermore, the rate of convergence such as superlinear and quadratic rates of convergence of the proposed method are analyzed when the equality constraint vanishes. Finally, the numerical effectiveness of the method is tested on a class of academic examples and an economic power dispatch problem, which shows that the proposed method is promising. [ABSTRACT FROM AUTHOR]

In this paper, we study the solvability of a truncated-perturbed Gauss–Newton method for solving underdetermined nonlinear least squares problems. Our aim is to address a new analysis of a semilocal convergence to the aforementioned method. In particular, the main theorem is established under a kind of Hölder-relaxed condition, and two special cases of this are obtained. Furthermore, the computational behavior of the considered method is illustrated with some numerical tests. [ABSTRACT FROM AUTHOR]

We develop a fully asynchronous proximal bundle method for solving non-smooth, convex optimization problems. The algorithm can be used as a drop-in replacement for classic bundle methods, i.e., the function must be given by a first-order oracle for computing function values and subgradients. The algorithm allows for an arbitrary number of master problem processes computing new candidate points and oracle processes evaluating functions at those candidate points. These processes share information by communication with a single supervisor process that resembles the main loop of a classic bundle method. All processes run in parallel and no explicit synchronization step is required. Instead, the asynchronous and possibly outdated results of the oracle computations can be seen as an inexact function oracle. Hence, we show the convergence of our method under weak assumptions very similar to inexact and incremental bundle methods. In particular, we show how the algorithm learns important structural properties of the functions to control the inaccuracy induced by the asynchronicity automatically such that overall convergence can be guaranteed. [ABSTRACT FROM AUTHOR]

In this article, we propose a splitting algorithm to find zeros of the sum of four maximally monotone operators in real Hilbert spaces. In particular, we consider a Lipschitz operator, a cocoercive operator, and a linear composite term. In the case where the Lipschitz operator is absent, our method reduces to the Condat-Vũ algorithm. On the other hand, when the linear composite term is absent, the algorithm reduces to the Forward-Backward-Half-Forward algorithm (FBHF). Additionally, in each case, the set of step-sizes that guarantee the weak convergence of those methods are recovered. Therefore, our algorithm can be seen as a combination of Condat-Vũ and FBHF. Moreover, we propose extensions and applications of our method in multivariate monotone inclusions and saddle point problems. Finally, we present a numerical experiment on image deblurring problems. [ABSTRACT FROM AUTHOR]

Accuracy certificates for convex minimization problems allow for online verification of the accuracy of approximate solutions and provide a theoretically valid online stopping criterion. When solving the Lagrange dual problem, accuracy certificates produce a simple way to recover an approximate primal solution and estimate its accuracy. In this paper, we generalize accuracy certificates for the setting of an inexact first-order oracle, including the setting of primal and Lagrange dual pair of problems. We further propose an explicit way to construct accuracy certificates for a large class of cutting plane methods based on polytopes. As a by-product, we show that the considered cutting plane methods can be efficiently used with a noisy oracle even though they were originally designed to be equipped with an exact oracle. Finally, we illustrate the work of the proposed certificates in the numerical experiments highlighting that our certificates provide a tight upper bound on the objective residual. [ABSTRACT FROM AUTHOR]

We devise an L-BFGS method for optimization problems in which the objective is the sum of two functions, where the Hessian of the first function is computationally unavailable while the Hessian of the second function has a computationally available approximation that allows for cheap matrix–vector products. This is a prototypical setting for many inverse problems. The proposed L-BFGS method exploits the structure of the objective to construct a more accurate Hessian approximation than in standard L-BFGS. In contrast with existing works on structured L-BFGS, we choose the first part of the seed matrix, which approximates the Hessian of the first function, as a diagonal matrix rather than a multiple of the identity. We derive two suitable formulas for the coefficients of the diagonal matrix and show that this boosts performance on real-life image registration problems, which are highly non-convex inverse problems. The new method converges globally and linearly on non-convex problems under mild assumptions in a general Hilbert space setting, making it applicable to a broad class of inverse problems. An implementation of the method is freely available. [ABSTRACT FROM AUTHOR]

In [R. J. Baraldi and D. P. Kouri, Mathematical Programming, (2022), pp. 1-40], we introduced an inexact trust-region algorithm for minimizing the sum of a smooth nonconvex and nonsmooth convex function. The principle expense of this method is in computing a trial iterate that satisfies the so-called fraction of Cauchy decrease condition—a bound that ensures the trial iterate produces sufficient decrease of the subproblem model. In this paper, we expound on various proximal trust-region subproblem solvers that generalize traditional trust-region methods for smooth unconstrained and convex-constrained problems. We introduce a simplified spectral proximal gradient solver, a truncated nonlinear conjugate gradient solver, and a dogleg method. We compare algorithm performance on examples from data science and PDE-constrained optimization. [ABSTRACT FROM AUTHOR]

In this paper, we propose the approximate Bregman proximal gradient algorithm (ABPG) for solving composite nonconvex optimization problems. ABPG employs a new distance that approximates the Bregman distance, making the subproblem of ABPG simpler to solve compared to existing Bregman-type algorithms. The subproblem of ABPG is often expressed in a closed form. Similarly to existing Bregman-type algorithms, ABPG does not require the global Lipschitz continuity for the gradient of the smooth part. Instead, assuming the smooth adaptable property, we establish the global subsequential convergence under standard assumptions. Additionally, assuming that the Kurdyka–Łojasiewicz property holds, we prove the global convergence for a special case. Our numerical experiments on the ℓ p regularized least squares problem, the ℓ p loss problem, and the nonnegative linear system show that ABPG outperforms existing algorithms especially when the gradient of the smooth part is not globally Lipschitz or even locally Lipschitz continuous. [ABSTRACT FROM AUTHOR]

The choice of relaxation parameter in the projected successive overrelaxation (PSOR) method for nonnegative quadratic programming problems is problem-dependent. We present novel adaptive PSOR algorithms that adaptively control the relaxation parameter using the Wolfe conditions. The method and its variants can be applied to various problems without requiring additional assumptions, barring the positive semidefiniteness concerning the matrix that defines the objective function, and the cost for updating the parameter is negligible in the whole iteration. Numerical experiments show that the proposed methods often perform comparably to (or sometimes superior to) the PSOR method with a nearly optimal relaxation parameter. [ABSTRACT FROM AUTHOR]

This paper introduces a nonconvex approach for sparse signal recovery, proposing a novel model termed the τ 2 -model, which utilizes the squared ℓ 1 / ℓ 2 norms for this purpose. Our model offers an advancement over the ℓ 0 norm, which is often computationally intractable and less effective in practical scenarios. Grounded in the concept of effective sparsity, our approach robustly measures the number of significant coordinates in a signal, making it a powerful alternative for sparse signal estimation. The τ 2 -model is particularly advantageous due to its computational efficiency and practical applicability. We detail two accompanying algorithms based on Dinkelbach’s procedure and a difference of convex functions strategy. The first algorithm views the model as a linear-constrained quadratic programming problem in noiseless scenarios and as a quadratic-constrained quadratic programming problem in noisy scenarios. The second algorithm, capable of handling both noiseless and noisy cases, is based on the alternating direction linearized proximal method of multipliers. We also explore the model’s properties, including the existence of solutions under certain conditions, and discuss the convergence properties of the algorithms. Numerical experiments with various sensing matrices validate the effectiveness of our proposed model. [ABSTRACT FROM AUTHOR]

In this paper, an implementable descent method for nonsmooth multiobjective optimization problems on complete Riemannian manifolds is proposed. The objective functions are only assumed to be locally Lipschitz continuous instead of convexity used in the existing subgradient method for Riemannian multiobjective optimization. And the constraint manifold is a general manifold rather than some specific manifolds used in the proximal point method. The retraction mapping is introduced to avoid the use of computationally difficult geodesic. A Riemannian version of the necessary condition for Pareto optimality is proposed, which generalized the classical one in Euclidean space to the manifold setting. At every iteration, an acceptable descent direction is obtained by constructing a convex hull of some Riemannian ε-subgradients. And then a Riemannian Armijo-type line search is executed to produce the next iterate. The convergence result is established in the sense that a point satisfying the necessary condition for Pareto optimality can be generated by the algorithm in a finite number of iterations. Finally, some preliminary numerical results are reported, which show that the proposed method is efficient. [ABSTRACT FROM AUTHOR]

Let A be a square matrix with a given structure (e.g. real matrix, sparsity pattern, Toeplitz structure, etc.) and assume that it is unstable, i.e. at least one of its eigenvalues lies in the complex right half-plane. The problem of stabilizing A consists in the computation of a matrix B, whose eigenvalues have all negative real part and such that the perturbation Δ = B - A has minimal norm. The structured stabilization further requires that the perturbation preserves the structural pattern of A. This non-convex problem is solved by a two-level procedure which involves the computation of the stationary points of a matrix ODE. It is possible to exploit the underlying low-rank features of the problem by using an adaptive-rank integrator that follows rigidly the rank of the solution. Some benefits derived from the low-rank setting are shown in several numerical examples. These computational advantages also allow to deal with high dimensional problems. [ABSTRACT FROM AUTHOR]

Conjugate gradient methods are widely used for solving large-scale unconstrained optimization problems, because they do not need the storage of matrices. Based on the self-scaling memoryless Broyden-Fletcher-Goldfarb-Shanno (SSML-BFGS) method, new conjugate gradient algorithms CG-DESCENT and CGOPT have been proposed by W. Hager, H. Zhang (2005) and Y. Dai, C. Kou (2013), respectively. It is noted that the two conjugate gradient methods perform more efficiently than the SSML-BFGS method. Therefore, C. Kou, Y. Dai (2015) proposed some suitable modifications of the SSML-BFGS method such that the sufficient descent condition holds. For the sake of improvement of modified SSML-BFGS method, in this paper, we present an efficient SSML-BFGS-type three-term conjugate gradient method for solving unconstrained minimization using Ford-Moghrabi secant equation instead of the usual secant equations. The method is shown to be globally convergent under certain assumptions. Numerical results compared with methods using the usual secant equations are reported. [ABSTRACT FROM AUTHOR]

Approximations to noisy data are constructed to obtain unimodality of successively updated data. Precisely, a method is developed that calculates least squares monotonic increasing - decreasing approximations to n data, for successive values of n. Having fixed n, the statement of the increasing-–decreasing constraints in terms of first differences of the data subject to one sign change gives rise to a discrete search calculation, because the position of the sign change is also an unknown of the optimization problem. Although this problem may have many local minima for each value of n, the method is made quite efficient by taking advantage of two properties of the optimization calculation. The first property, for fixed n, provides necessary and sufficient conditions that reduce the optimal selection of the position to solving two sequences of monotonic approximation problems to subranges of data in the least complexity $ \mathcal {O}(n) $ O (n). The sufficiency conditions is a new result. The second property shows that the optimal position increases as n increases. Hence, if this position of a fit to the first n−1 data is available, then in order to calculate the required position of a fit to the first n data there is no need to consider data that are before the current position. A Fortran program has been written and some timings of numerical results are given for up to $ n=30{,}000 $ n = 30,000 data and various levels of noise. They seem to be proportional to n. The method is applied to data of daily Covid-19 deaths of the United Kingdom for a period that exhibits a major outbreak, and obtains insights of the evolution of the process as new data enter the calculation. The results reveal certain features of the calculation that may be helpful to supporting policy making, when used in modelling epidemic processes. Further, a procedure is proposed where our method initializes the nonlinear least squares calculation of Richards epidemiological model, and the numerical results confirm some useful advantages over the plain use of this model. One benefit of our method for unimodal smoothing of successive data and estimation of the associated turning points is that it provides a property that appears in a wide range of processes from biology, economics, finance and social sciences, for instance. [ABSTRACT FROM AUTHOR]

The global minimum point of an optimization problem is of interest in engineering fields and it is difficult to solve, especially for a nonconvex large-scale optimization problem. In this article, we consider a new memetic algorithm for this problem. That is to say, we use the continuation Newton method with the deflation technique to find multiple stationary points of the objective function and use those found stationary points as the initial seeds of the evolutionary algorithm, other than the random initial seeds of the known evolutionary algorithms. Meanwhile, in order to retain the usability of the derivative-free method and the fast convergence of the gradient-based method, we use the automatic differentiation technique to compute the gradient and replace the Hessian matrix with its finite difference approximation. According to our numerical experiments, this new algorithm works well for unconstrained optimization problems and finds their global minima efficiently, in comparison to the other representative global optimization methods such as the multi-start methods (the built-in subroutine GlobalSearch.m of MATLAB R2021b, GLODS, and VRBBO), the branch-and-bound method (Couenne, a state-of-the-art open-source solver for mixed integer nonlinear programming problems), and the derivative-free algorithms (CMA-ES and MCS). [ABSTRACT FROM AUTHOR]

Conjugate gradient methods are probably the most used methods in solving large scale unconstrained optimization problems. They have become popular because of their simplicity and low memory requirements. In this paper, we propose a hybrid conjugate gradient method based on the improved Fletcher-Reeves (IFR) and Rivaie-Mustafa-Ismail-Leong+ (RMIL+) methods and establish its global convergence under the strong Wolfe line search conditions. The new conjugate gradient direction satisfies the sufficient descent condition. The method is then compared to other methods in the literature and numerical experiments show that it is competent when solving large scale unconstrained optimization problems. Furthermore, the method is applied to solve a problem in portfolio selection. [ABSTRACT FROM AUTHOR]

Gradient tracking methods have emerged as one of the most popular approaches for solving decentralized optimization problems over networks. In this setting, each node in the network has a portion of the global objective function, and the goal is to collectively optimize this function. At every iteration, gradient tracking methods perform two operations (steps): (1) compute local gradients, and (2) communicate information with local neighbors in the network. The complexity of these two steps varies across different applications. In this paper, we present a framework that unifies gradient tracking methods and is endowed with flexibility with respect to the number of communication and computation steps. We establish unified theoretical convergence results for the algorithmic framework with any composition of communication and computation steps, and quantify the improvements achieved as a result of this flexibility. The framework recovers the results of popular gradient tracking methods as special cases, and allows for a direct comparison of these methods. Finally, we illustrate the performance of the proposed methods on quadratic functions and binary classification problems. [ABSTRACT FROM AUTHOR]

In this paper, we study the standard formulation of an optimization problem when the computation of gradient is not available. Such a problem can be classified as a "black box" optimization problem, since the oracle returns only the value of the objective function at the requested point, possibly with some stochastic noise. Assuming convex, and higher-order of smoothness of the objective function, this paper provides a zero-order accelerated stochastic gradient descent (ZO-AccSGD) method for solving this problem, which exploits the higher-order of smoothness information via kernel approximation. As theoretical results, we show that the ZO-AccSGD algorithm proposed in this paper improves the convergence results of state-of-the-art (SOTA) algorithms, namely the estimate of iteration complexity. In addition, our theoretical analysis provides an estimate of the maximum allowable noise level at which the desired accuracy can be achieved. Validation of our theoretical results is demonstrated both on the model function and on functions of interest in the field of machine learning. We also provide a discussion in which we explain the results obtained and the superiority of the proposed algorithm over SOTA algorithms for solving the original problem. [ABSTRACT FROM AUTHOR]

This paper presents a subgradient-based algorithm for constrained nonsmooth convex optimization that does not require projections onto the feasible set. While the well-established Frank–Wolfe algorithm and its variants already avoid projections, they are primarily designed for smooth objective functions. In contrast, our proposed algorithm can handle nonsmooth problems with general convex functional inequality constraints. It achieves an ϵ -suboptimal solution in O (ϵ - 2) iterations, with each iteration requiring only a single (potentially inexact) Linear Minimization Oracle call and a (possibly inexact) subgradient computation. This performance is consistent with existing lower bounds. Similar performance is observed when deterministic subgradients are replaced with stochastic subgradients. In the special case where there are no functional inequality constraints, our algorithm competes favorably with a recent nonsmooth projection-free method designed for constraint-free problems. Our approach utilizes a simple separation scheme in conjunction with a new Lagrange multiplier update rule. [ABSTRACT FROM AUTHOR]

In [L.Q. Song and W.H. Yang, J. Comput. Math., 37 (2019), pp. 240–260], a block Lanczos method for solving large-scale Celis-Dennis-Tapia (CDT) subproblem was proposed. It is an orthogonal projection method that reduces a large-scale CDT subproblem to a small-sized problem for easier solving. Moreover, Song and Yang also provided error bounds for the optimal value and for the optimal solution. However, no convergence analysis for this method was presented by them. In this paper, we develop some upper bounds for the convergence of approximate optimal function objective values, approximate optimal solutions, the KKT error, and approximate Lagrange multipliers. [ABSTRACT FROM AUTHOR]

In this paper, we propose two self-adaptive derivative-free methods with restart procedure for solving large-scale constrained nonlinear equations. The new methods combine hyperplane projection and restart strategy, and possess the following features: (i) There are low storage and derivative-free; (ii) Restart strategy is employed to add self-adaptation and improve computational efficiency; (iii) The search directions satisfy the sufficient descent condition and the trust region property; (iv) Both global convergence and convergence rate are established under some appropriate assumptions. Preliminary numerical results show that the proposed methods are effective and practical by solving constrained nonlinear equations and applying them to regularized decentralized logistic regression and signal restoration problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider a modified Levenberg–Marquardt algorithm for Low Order Value Optimization problems(LOVO). In the algorithm, we obtain the search direction by a combination of LM steps and approximate LM steps, and solve the subproblems therein by QR decomposition or cholesky decomposition. We prove the global convergence of the algorithm theoretically and discuss the worst-case complexity of the algorithm. Numerical results show that the algorithm in this paper is superior in terms of number of iterations and computation time compared to both LM-LOVO and GN-LOVO algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we provide a necessary and sufficient condition under which the compositions of finitely many firmly nonexpansive mappings in a p-uniformly convex space converge strongly. In particular, we obtain convergence results for the method of alternating projections in CAT(κ ) spaces, with κ ≥ 0 . We also study the rate of convergence of the sequence generated by the method in cases where the firmly nonexpansive mappings satisfy an error bound, and the set of fixed points of these mappings is boundedly linearly regular. [ABSTRACT FROM AUTHOR]

In this article, we study two methods for solving monotone inclusions in real Hilbert spaces involving the sum of a maximally monotone operator, a monotone-Lipschitzian operator, a cocoercive operator, and a normal cone to a vector subspace. Our algorithms split and exploits the intrinsic properties of each operator involved in the inclusion. We derive our methods by combining partial inverse techniques with the forward-half-reflected-backward algorithm and with the forward-shadow-Douglas–Rachford (FSDR) algorithm, respectively. Our methods inherit the advantages of those methods, requiring only one activation of the Lipschitzian operator, one activation of the cocoercive operator, two projections onto the closed vector subspace, and one calculation of the resolvent of the maximally monotone operator. Additionally, to allow larger step-sizes in one of the proposed methods, we revisit FSDR by extending its convergence for larger step-sizes. Furthermore, we provide methods for solving monotone inclusions involving a sum of maximally monotone operatores and for solving a system of primal-dual inclusions involving a mixture of sums, linear compositions, parallel sums, Lipschitzian operators, cocoercive operators, and normal cones. We apply our methods to constrained composite convex optimization problems as a specific example. Finally, in order to compare our methods with existing methods in the literature, we provide numerical experiments on constrained total variation least-squares optimization problems and computed tomography inverse problems. We obtain promising numerical results. [ABSTRACT FROM AUTHOR]

The late Professor M. J. D. Powell devised five trust-region methods for derivative-free optimization, namely COBYLA, UOBYQA, NEWUOA, BOBYQA, and LINCOA. He carefully implemented them into publicly available solvers, renowned for their robustness and efficiency. However, the solvers were implemented in Fortran 77 and hence may not be easily accessible to some users. We introduce the PDFO package, which provides user-friendly Python and MATLAB interfaces to Powell's code. With PDFO, users of such languages can call Powell's Fortran solvers easily without dealing with the Fortran code. Moreover, PDFO includes bug fixes and improvements, which are particularly important for handling problems that suffer from ill-conditioning or failures of function evaluations. In addition to the PDFO package, we provide an overview of Powell's methods, sketching them from a uniform perspective, summarizing their main features, and highlighting the similarities and interconnections among them. We also present experiments on PDFO to demonstrate its stability under noise, tolerance of failures in function evaluations, and potential to solve certain hyperparameter optimization problems. [ABSTRACT FROM AUTHOR]

This paper establishes necessary, sufficient, and equivalent conditions for the spherical convexity of non-homogeneous quadratic functions. By examining criteria for determining spherical convexity, we identified unique properties that differentiate spherically convex quadratic functions from their geodesically convex counterparts in both hyperbolic and Euclidean spaces. Since spherically convex functions over the entire sphere are constant, our analysis focuses on proper spherically convex subsets of the sphere. Our primary results concern non-homogeneous quadratic functions on the spherically convex set of unit vectors with positive coordinates. We also extend our findings to more general spherically convex sets. Additionally, the paper explores special cases of non-homogeneous quadratic functions where the defining matrix is of a specific type, such as positive, diagonal, or a Z-matrix. This study not only provides useful criteria for spherical convexity but also reveals surprising characteristics of spherically convex quadratic functions, contributing to a deeper understanding of convexity in spherical geometries. [ABSTRACT FROM AUTHOR]

Clustering has been one of the most basic and essential problems in unsupervised learning due to various applications in many critical fields. The recently proposed sum-of-norms (SON) model by Pelckmans et al. (in: PASCAL workshop on statistics and optimization of clustering, 2005), Lindsten et al. (in: IEEE statistical signal processing workshop, 2011) and Hocking et al. (in: Proceedings of the 28th international conference on international conference on machine learning, 2011) has received a lot of attention. The advantage of the SON model is the theoretical guarantee in terms of perfect recovery, established by Sun et al. (J Mach Learn Res 22(9):1–32, 2018). It also provides great opportunities for designing efficient algorithms for solving the SON model. The semismooth Newton based augmented Lagrangian method by Sun et al. (2018) has demonstrated its superior performance over the alternating direction method of multipliers and the alternating minimization algorithm. In this paper, we propose a Euclidean distance matrix model based on the SON model. Exact recovery property is achieved under proper assumptions. An efficient majorization penalty algorithm is proposed to solve the resulting model. Extensive numerical experiments are conducted to demonstrate the efficiency of the proposed model and the majorization penalty algorithm. [ABSTRACT FROM AUTHOR]

This paper studies proximal gradient iterations for addressing simple bilevel optimization problems where both the upper and the lower level cost functions are split as the sum of differentiable and (possibly nonsmooth) prox-friendly functions. We develop a novel convergence recipe for iteration-varying stepsizes that relies on Barzilai-Borwein type local estimates for the differentiable terms. Leveraging the convergence recipe, under global Lipschitz gradient continuity, we establish convergence for a nonadaptive stepsize sequence, without requiring any strong convexity or linesearch. In the locally Lipschitz differentiable setting, we develop an adaptive linesearch method that introduces a systematic adaptive scheme enabling large and nonmonotonic stepsize sequences while being insensitive to the choice of hyperparameters and initialization. Numerical simulations are provided showcasing favorable convergence speed of our methods. [ABSTRACT FROM AUTHOR]

We present a modified limited memory BFGS (L-BFGS) method that converges globally and linearly for nonconvex objective functions. Its distinguishing feature is that it turns into L-BFGS if the iterates cluster at a point near which the objective is strongly convex with Lipschitz gradients, thereby inheriting the outstanding effectiveness of the classical method. These strong convergence guarantees are enabled by a novel form of cautious updating, where, among others, it is decided anew in each iteration which of the stored pairs are used for updating and which ones are skipped. In particular, this yields the first modification of cautious updating for which all cluster points are stationary while the spectrum of the L-BFGS operator is not permanently restricted, and this holds without Lipschitz continuity of the gradient. In fact, for Wolfe–Powell line searches we show that continuity of the gradient is sufficient for global convergence, which extends to other descent methods. Since we allow the memory size to be zero in the globalized L-BFGS method, we also obtain a new globalization of the Barzilai–Borwein spectral gradient (BB) method. The convergence analysis is developed in Hilbert space under comparably weak assumptions and covers Armijo and Wolfe–Powell line searches. We illustrate the theoretical findings with numerical experiments. The experiments indicate that if one of the parameters of the cautious updating is chosen sufficiently small, then the modified method agrees entirely with L-BFGS/BB. We also discuss this in the theoretical part. An implementation of the new method is available on arXiv. [ABSTRACT FROM AUTHOR]

In this paper, we focus on the exploration of solution uniqueness, sharpness, and robust recovery in sparse regularization with a gauge J . Based on the criteria for the uniqueness of Lagrange multipliers in the dual problem, we give a characterization of the unique solution via the so-called radial cone. We establish characterizations of the isolated calmness (i.e., uniqueness of solutions combined with the calmness properties) of two types of the solution mappings and prove that they are equivalent under the assumption of metric subregularity of the subdifferentials for regularizers. Furthermore, we present sufficient and necessary conditions for a sharp solution, and show that these conditions guarantee robust recovery with a linear rate and imply local upper Lipschitzian properties of the solution mapping. Some applications of the polyhedral regularizer case such as sparse analysis regularization, weighted sorted ℓ 1 -norm sparse regularization, and non-polyhedral regularizer cases such as nuclear norm optimization, conic gauge optimization, and semidefinite conic gauge optimization are given. [ABSTRACT FROM AUTHOR]

In this paper we introduce an open-source software package written in C++ for efficiently finding solutions to quadratic programming problems with linear complementarity constraints. These problems arise in a wide range of applications in engineering and economics, and they are challenging to solve due to their structural violation of standard constraint qualifications, and highly nonconvex, nonsmooth feasible sets. This work extends a previously presented algorithm based on a sequential convex programming approach applied to a standard penalty reformulation. We examine the behavior of local convergence and introduce new algorithmic features. Competitive performance profiles are presented in comparison to state-of-the-art solvers and solution variants in both existing and new benchmarks. [ABSTRACT FROM AUTHOR]