Search

It has been proven that the conjugate gradient (CG) method by Rivaie, Mustafa, Ismail and Leong (RMIL) (Appl. Math. Comput. 218 (2012) 11323–11332), does not satisfy the sufficient descent condition, and its global convergence is attained only by employing the exact line search (ELS) procedure. In this study, two RMIL-type algorithms are proposed for system of monotone nonlinear equations, where both properties hold regardless of the line search strategy used. Two approximations of the nonnegative parameter that is embedded in search directions of the algorithms are determined by analysing eigenvalues and singular values of their iteration matrices. The new solvers are also ideal for nonsmooth problems. Four recent solvers are employed to show effectiveness of the new methods. Furthermore, the schemes are used to solve some signal and image recovery problems. [ABSTRACT FROM AUTHOR]

It is widely known that the inertial technique of the heavy-ball method can accelerate its convergence speed. In this paper, by embedding the inertial technique in the famous PRP conjugate gradient method, we propose a modified PRP conjugate gradient method with inertial extrapolation (PRPCG-IE) for sparse signal reconstruction. Its direction satisfies the sufficient descent property, which is independent of any line search. Global convergence of PRPCG-IE is established under some standard conditions. PRPCG-IE is applied to two sparse signal reconstruction problems with noise, and preliminary experimental results demonstrate the effectiveness of PRPCG-IE. [ABSTRACT FROM AUTHOR]

In this paper, we characterize Lipschitzian properties of different multiplier-free and multiplier-dependent perturbation mappings associated with the stationarity system of a so-called generalized nonlinear program popularized by Rockafellar. Special emphasis is put on the investigation of the isolated calmness property at and around a point. The latter is decisive for the locally fast convergence of the so-called semismooth* Newton-type method by Gfrerer and Outrata. Our central result is the characterization of the isolated calmness at a point of a multiplier-free perturbation mapping via a combination of an explicit condition and a rather mild assumption, automatically satisfied e.g. for standard nonlinear programs. Isolated calmness around a point is characterized analogously by a combination of two stronger conditions. These findings are then related to so-called criticality of Lagrange multipliers, as introduced by Izmailov and extended to generalized nonlinear programming by Mordukhovich and Sarabi. We derive a new sufficient condition (a characterization for some problem classes) of nonexistence of critical multipliers, which has been also used in the literature as an assumption to guarantee local fast convergence of Newton-, SQP-, or multiplier-penalty-type methods. The obtained insights about critical multipliers seem to complement the vast literature on the topic. [ABSTRACT FROM AUTHOR]

Conic linear programs in locally convex Hausdorff topological vector spaces are addressed in this paper. Solution existence for the dual problem, as well as solution existence for the primal problem, and strong duality, are proved under minimal regularity assumptions. Namely, to get the results and a Farkas-type theorem for infinite-dimensional conic linear inequalities, we employ the generalized Slater condition either for the primal problem or for the dual problem, as well as proper separation and the concept of quasi-regularity of convex sets. Illustrative examples are presented. [ABSTRACT FROM AUTHOR]

Direct search methods represent a robust and reliable class of algorithms for solving black-box optimization problems. In this paper, the application of those strategies is exported to Riemannian optimization, wherein minimization is to be performed with respect to variables restricted to lie on a manifold. More specifically, classic and linesearch extrapolated variants of direct search are considered, and tailored strategies are devised for the minimization of both smooth and nonsmooth functions, by making use of retractions. A class of direct search algorithms for minimizing nonsmooth objectives on a Riemannian manifold without having access to (sub)derivatives is analyzed for the first time in the literature. Along with convergence guarantees, a set of numerical performance illustrations on a standard set of problems is provided. [ABSTRACT FROM AUTHOR]

Data assimilation combines prior (or background) information with observations to estimate the initial state of a dynamical system over a given time-window. A common application is in numerical weather prediction where a previous forecast and atmospheric observations are used to obtain the initial conditions for a numerical weather forecast. In four-dimensional variational data assimilation (4D-Var), the problem is formulated as a nonlinear least-squares problem, usually solved using a variant of the classical Gauss-Newton (GN) method. However, we show that GN may not converge if poorly initialized. In particular, we show that this may occur when there is greater uncertainty in the background information compared to the observations, or when a long time-window is used in 4D-Var allowing more observations. The difficulties GN encounters may lead to inaccurate initial state conditions for subsequent forecasts. To overcome this, we apply two convergent GN variants (line search and regularization) to the long time-window 4D-Var problem and investigate the cases where they locate a more accurate estimate compared to GN within a given budget of computational time and cost. We show that these methods are able to improve the estimate of the initial state, which may lead to a more accurate forecast. Highlights Poor initialization of Gauss-Newton method may result in failure to converge. Safeguarded Gauss-Newton improves initial state estimate within limited time/cost. Results using twin experiments with long time-window and chaotic Lorenz models. Apply state of the art least-squares convergence theory to data assimilation. Improvements to initial state estimate may lead to a more accurate forecast. [ABSTRACT FROM AUTHOR]

This note provides a counterexample to a theorem announced in the last part of the paper (Vicente and Custódio Math Program 133:299–325, 2012). The counterexample involves an objective function f : R → R which satisfies all the assumptions required by the theorem but contradicts some of its conclusions. A corollary of this theorem is also affected by this counterexample. The main flaw revealed by the counterexample is the possibility that a directional direct search method (dDSM) generates a sequence of trial points (x k) k ∈ N converging to a point x ∗ where f is discontinuous, lower semicontinuous and whose objective function value f (x ∗) is strictly less than lim k → ∞ f (x k) . Moreover the dDSM generates trial points in only one of the continuity sets of f near x ∗ . This note also investigates the proof of the theorem to highlight the inexact statements in the original paper. Finally this work introduces a modification of the dDSM that allows, in usual cases, to recover the properties broken by the counterexample. [ABSTRACT FROM AUTHOR]

This paper considers optimization problems where the objective is the sum of a function given by an expectation and a closed convex function, and proposes stochastic composite proximal bundle (SCPB) methods for solving it. Complexity guarantees are established for them without requiring knowledge of parameters associated with the problem instance. Moreover, it is shown that they have optimal complexity when these problem parameters are known. To the best of our knowledge, this is the first proximal bundle method for stochastic programming able to deal with continuous distributions. Finally, we present computational results showing that SCPB substantially outperforms the robust stochastic approximation method in all instances considered. [ABSTRACT FROM AUTHOR]

Manifold optimization has recently gained significant attention due to its wide range of applications in various areas. This paper introduces the first Riemannian trust region method for minimizing an SC 1 function, which is a differentiable function that has a semismooth gradient vector field, on manifolds with convergence guarantee. We provide proof of both global and local convergence results, along with demonstrating the local superlinear convergence rate of our proposed method. As an application and to demonstrate our motivation, we utilize our trust region method as a subproblem solver within an augmented Lagrangian method for minimizing nonsmooth nonconvex functions over manifolds. This represents the first approach that fully explores the second-order information of the subproblem in the context of augmented Lagrangian methods on manifolds. Numerical experiments confirm that our method outperforms existing methods. [ABSTRACT FROM AUTHOR]

First-order directional differentiability of the optimal value function for parametric quadratic programming problems in Hilbert spaces is investigated. We derive an explicit formula for computing the directional derivative of the optimal value function for problems whose quadratic part of the objective function is in Legendre form. [ABSTRACT FROM AUTHOR]

In this paper, a subgradient projection method for quasiconvex minimization problems is provided. By employing strong subdifferentials, it is proved that the generated sequence of the proposed algorithm converges to the solution of the minimization problem of a proper, lower semicontinuous, and strongly quasiconvex function (in the sense of Polyak in Soviet Math 7:72–75, 1966), under the same assumptions as those required for convex functions with the convex subdifferentials. Furthermore, a quasi-linear convergence rate of the iterates, extending similar results for the general quasiconvex case, is also provided. [ABSTRACT FROM AUTHOR]

Recently, the proximal Newton-type method and its variants have been generalized to solve composite optimization problems over the Stiefel manifold whose objective function is the summation of a smooth function and a nonsmooth function. In this paper, we propose an adaptive quadratically regularized proximal quasi-Newton method, named ARPQN, to solve this class of problems. Under some mild assumptions, the global convergence, the local linear convergence rate and the iteration complexity of ARPQN are established. Numerical experiments and comparisons with other state-of-the-art methods indicate that ARPQN is very promising. We also propose an adaptive quadratically regularized proximal Newton method, named ARPN. It is shown the ARPN method has a local superlinear convergence rate under certain reasonable assumptions, which demonstrates attractive convergence properties of regularized proximal Newton methods. [ABSTRACT FROM AUTHOR]

In this paper, we study online diminishing return submodular (DR-submodular for short) maximization in the bandit setting. Our focus is on problems where the reward functions can be non-monotone, and the constraint set is a general convex set. We first present the Single-sampling Non-monotone Frank-Wolfe algorithm. This algorithm only requires a single call to each reward function, and it computes the stochastic gradient to make it suitable for large-scale settings where full gradient information might not be available. We provide an analysis of the approximation ratio and regret bound of the proposed algorithm. We then propose the Bandit Online Non-monotone Frank-Wolfe algorithm to adjust for problems in the bandit setting, where each reward function returns the function value at a single point. We take advantage of smoothing approximations to reward functions to tackle the challenges posed by the bandit setting. Under mild assumptions, our proposed algorithm can reach 1 4 (1 - min x ∈ P ′ ‖ x ‖ ∞) -approximation with regret bounded by O (T 5 min { 1 , γ } + 5 6 min { 1 , γ } + 5 ) , where the positive parameter γ is related to the "safety domain" P ′ . To the best of our knowledge, this is the first work to address online non-monotone DR-submodular maximization over a general convex set in the bandit setting. [ABSTRACT FROM AUTHOR]

Direct Multisearch (DMS) is a well-established class of methods for multiobjective derivative-free optimization, where constraints are addressed by an extreme barrier approach, only evaluating feasible points. In this work, we propose the replacement of this extreme barrier approach by a filter strategy, combined with an inexact feasibility restoration step, to address constraints in the DMS framework. The filter approach treats feasibility as an additional component of the objective function that needs to be minimized. The inexact restoration step attempts to generate new feasible points, contributing to prioritize this feasibility, a requirement for the good performance of any filter approach. Theoretical results are provided, analysing the different types of sequences of points generated by the new algorithm, and numerical experiments on a set of nonlinearly constrained biobjective problems are reported, stating the good algorithmic performance of the proposed approach. [ABSTRACT FROM AUTHOR]

In this paper, we consider the weighted nonlinear complementarity problem which is the extension of the general complementarity problems and contains a wide class of optimization problems. Based on the weighted complementarity function, we reformulate the weighted nonlinear complementarity problem as an unconstrained minimization problem and present the steepest descent-based neural network to solve it. Under mild conditions, we derive some results related to the asymptotic stability of the neural network. Numerical experiments indicate that the proposed algorithm is quite effective. [ABSTRACT FROM AUTHOR]

In this work, we consider methods for large-scale and nonconvex unconstrained optimization. We propose a new trust-region method whose subproblem is defined using a so-called 'shape-changing' norm together with densely-initialized multipoint symmetric secant (MSS) matrices to approximate the Hessian. Shape-changing norms and dense initializations have been successfully used in the context of traditional quasi-Newton methods, but have yet to be explored in the case of MSS methods. Numerical results suggest that trust-region methods that use densely-initialized MSS matrices together with shape-changing norms outperform MSS with other trust-region methods. [ABSTRACT FROM AUTHOR]

Based on a new equivalent reformulation, a scalable modulus-based matrix splitting (SMMS) method is proposed to solve the vertical linear complementarity problem (VLCP). By introducing a relaxation parameter and employing the two-sweep technique, we further enhance the scalability of the method, leading to a framework of the scalable relaxation two-sweep modulus-based matrix splitting (SRTMMS) method. To theoretically demonstrate the acceleration of the convergence provided by the SMMS method, we present a comparison theorem for the case of s = 2 . Furthermore, we establish the convergence of the SRTMMS method for arbitrary s. Preliminary numerical results indicate promising performance of the SRTMMS method. [ABSTRACT FROM AUTHOR]

This paper is devoted to the analysis of worst case complexity bounds for linesearch-type derivative-free algorithms for the minimization of general non-convex smooth functions. We consider a derivative-free algorithm based on a linesearch extrapolation technique. First we prove that it enjoys the same complexity properties which have been proved for pattern and direct search algorithms, namely that the number of iterations and of function evaluations required to drive the norm of the gradient of the objective function below a given threshold ϵ for the first time is O (ϵ - 2) in the worst case. This is the first contribution proving worst-case complexity properties for derivative-free linesearch-type algorithms. Then we show that the lineasearch approach used by the described algorithm allows us to guarantee the further property that the number of iterations such that the norm of the gradient is bigger than ϵ is O (ϵ - 2) in the worst case. [ABSTRACT FROM AUTHOR]

Taking inspiration from what is commonly done in single-objective optimization, most local algorithms proposed for multiobjective optimization extend the classical iterative scalar methods and produce sequences of points able to converge to single efficient points. Recently, a growing number of local algorithms that build sequences of sets has been devised, following the real nature of multiobjective optimization, where the aim is that of approximating the efficient set. This calls for a new analysis of the necessary optimality conditions for multiobjective optimization. We explore conditions for sets of points that share the same features of the necessary optimality conditions for single-objective optimization. On the one hand, from a theoretical point of view, these conditions define properties that are necessarily satisfied by the (weakly) efficient set. On the other hand, from an algorithmic point of view, any set that does not satisfy the proposed conditions can be easily improved by using first-order information on some objective functions. We analyse both the unconstrained and the constrained case, giving some examples. [ABSTRACT FROM AUTHOR]

Global approximations of scalar optimization problems in terms of variational convergence have been studied for several decades. However, there are very few results for vector models in the literature, which are limited to epi-convergence of vector functions, nothing has been obtained for vector bifunctions. This paper is the first attempt to consider approximations of vector optimization in terms of variational convergence of bifunctions. We first consider the vector quasi-equilibrium problem since it encompasses most optimization-related models. Then, we apply the obtained results to the vector Nash quasi-game (vector generalized non-cooperative game), which is one of the most important practical problems in applied mathematics. We approach to the vector problems in question via scalarization. Our scalarization tools are the Tammer and the Hiriart-Urruty scalarization functions. By scalarizing, we define types of vector variational convergence corresponding to some types of scalar variational convergence. We show that under these types of convergence of problems approximating the vector problems under consideration, approximate solutions of the former problems tend to solutions of the latter ones in the sense of set convergence. [ABSTRACT FROM AUTHOR]

This paper is concerned with the value function approach to multiobjective bilevel optimization which exploits a lower-level frontier-type mapping in order to replace the hierarchical model of two interdependent multiobjective optimization problems by a single-level multiobjective optimization problem. As a starting point, different value-function-type reformulations are suggested and their relations are discussed. Here, we focus on the situations where the lower-level problem is solved up to efficiency or weak efficiency, and an intermediate solution concept is suggested as well. We study the graph-closedness of the associated efficiency-type and frontier-type mappings. These findings are then used for two purposes. First, we investigate existence results in multiobjective bilevel optimization. Second, for the derivation of necessary optimality conditions via the value function approach, it is inherent to differentiate frontier-type mappings in a generalized way. Here, we are concerned with the computation of upper coderivative estimates for the frontier-type mapping associated with the setting where the lower-level problem is solved up to weak efficiency. We proceed in two ways, relying, on the one hand, on a weak domination property and, on the other hand, on a scalarization approach. Illustrative examples visualize our findings and some flaws in the related literature. [ABSTRACT FROM AUTHOR]

A classical solution approach to semi-infinite programming, which is easy to implement, is based on discretizing the semi-infinite index set. The Blankenship and Falk algorithm adaptively chooses a small discretization. On every iteration, a solution based on the current discretization is calculated. In a second step, the most violated constraint is determined and added to the discretization. In a previous work, the authors showed that the algorithm has a slow convergence and introduced a new method that exhibits a quadratic rate [Seidel and Küfer, An adaptive discretization method solving semi-infinite optimization problems with quadratic rate of convergence. Optimization. 2022;71(8):2211–2239]. In this paper, we further investigate the introduced method. The method implements new constraints that can cut off parts of the feasible set. We will study the effect on local minima. We assume that in each iteration local solutions to the discretized problems are computed. We will give an example showing that in general a limit point is not necessarily a local solution of the original semi-infinite problem, but only of an approximate problem. We then study second-order conditions and show that they coincide for both problems. We use this to develop conditions under which local solutions converge to a local solution in the limit. Finally, we present quadratic convergence results for the case of local solutions. [ABSTRACT FROM AUTHOR]

The sharp local minimality of feasible points of nonlinear optimization problems is known to possess a characterization by a strengthened version of the Karush–Kuhn–Tucker conditions, as long as the Mangasarian–Fromovitz constraint qualification holds. This strengthened condition is not easy to check algorithmically since it involves the topological interior of some set. In this article, we derive an algorithmically tractable version of this condition, called strong Karush–Kuhn–Tucker condition. We show that the Guignard constraint qualification is the weakest condition under which a feasible point is a strong Karush–Kuhn–Tucker point for every continuously differentiable objective function possessing the point as a sharp local minimizer. As an application, our results yield an algebraic characterization of strict local minimizers of linear programs with cardinality constraints. [ABSTRACT FROM AUTHOR]

In this article, we investigate the higher-order nonsmooth optimality conditions for vector optimization problems with inequality, equality and set constraints in terms of the higher-order Gâteaux derivatives. First, we propose various higher-order Mangasarian–Fromovitz nonsmooth constraint qualifications for such problems. Second, we formulate higher-order KKT-type necessary optimality conditions for the local weak efficient solutions of the nonsmooth vector equilibrium problem with constraints (CVEP) and its special cases. An application of the result to the resources assignment problem with set, inequality, equality constraints is derived. Under some suitable assumptions involving a set constraint, the higher-order nonsmooth necessary optimality conditions become the higher-order sufficient optimality conditions via the higher-order directional/Gâteaux derivatives. [ABSTRACT FROM AUTHOR]

Stochastic gradient descent method and its variants constitute the core optimization algorithms that achieve good convergence rates for solving machine learning problems. These rates are obtained especially when these algorithms are fine-tuned for the application at hand. Although this tuning process can require large computational costs, recent work has shown that these costs can be reduced by line search methods that iteratively adjust the step length. We propose an alternative approach to stochastic line search by using a new algorithm based on forward step model building. This model building step incorporates second-order information that allows adjusting not only the step length but also the search direction. Noting that deep learning model parameters come in groups (layers of tensors), our method builds its model and calculates a new step for each parameter group. This novel diagonalization approach makes the selected step lengths adaptive. We provide convergence rate analysis, and experimentally show that the proposed algorithm achieves faster convergence and better generalization in well-known test problems. More precisely, SMB requires less tuning, and shows comparable performance to other adaptive methods. [ABSTRACT FROM AUTHOR]

The following article presents and corroborates an outcome space branch-and-bound algorithm for solving the general linear multiplicative programming problem (GLMPP). In this new algorithm, GLMPP is transformed into its equivalent problem by introducing auxiliary variables. To compute the tight upper bound for the optimal value of GLMPP, the linear relaxation programming problem is assembled by using bound and hull linear approximations. Furthermore, the global convergence and computational complexity of the algorithm are demonstrated. Finally, the soundness and advantage of the proposed algorithm are validated by solving a demonstrative linear multiplicative problem. [ABSTRACT FROM AUTHOR]

Conjugate gradient (CG) methods are a popular class of iterative methods for solving linear systems of equations and nonlinear optimization problems. Motivated by the construction of some modern CG methods, we propose two modified CG methods, named DHS* and DPRP*. Under the strong Wolfe line search (SWLS), the two presented methods are proven to be sufficient descent and globally convergent. Preliminary numerical results show that the DHS* and DPRP* methods are effective for the given test problems. [ABSTRACT FROM AUTHOR]

We consider how to solve a class of non-Lipschitz mathematical programs with equilibrium constraints (MPEC) where the objective function involves a non-Lipschitz sparsity-inducing function and other functions are smooth. Solving the non-Lipschitz MPEC is highly challenging since the standard constraint qualifications fail due to the existence of equilibrium constraints and the subdifferential of the objective function is unbounded due to the existence of the non-Lipschitz function. On the one hand, for tackling the non-Lipschitzness of the objective function, we introduce a novel class of locally Lipschitz approximation functions that consolidate and unify a diverse range of existing smoothing techniques for the non-Lipschitz function. On the other hand, we use the Kanzow and Schwartz regularization scheme to approximate the equilibrium constraints since this regularization can preserve certain perpendicular structure as in equilibrium constraints, which can induce better convergence results. Then an approximation method is proposed for solving the non-Lipschitz MPEC and its convergence is established under weak conditions. In contrast with existing results, the proposed method can converge to a better stationary point under weaker qualification conditions. Finally, a computational study on the sparse solutions of linear complementarity problems is presented. The numerical results demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In this study, we investigate a class of linear multiplicative programs with positive exponents. By introducing p additional variables, the original problem is reformulated into an equivalent problem (EP) within the output space. Subsequently, a novel global optimization algorithm is introduced to tackle EP. The algorithm primarily leverages two key techniques. One is the outer approximation technique, which tightens the relaxed feasible region of EP and improves the upper bound by carefully examining suitable feasible points. The other is the branch and bound technique to guarantee the global optimality of the solution. Numerical results confirm the effectiveness and practicality of the proposed algorithm, thereby underscoring its potential for real-world applications. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a modified Tseng's extragradient method with a new step-length rule to solve pseudo-monotone variational inequalities in real Hilbert spaces. Under suitable conditions, the sequence generated by this algorithm strongly converges to the common elements of the solution set of pseudo-monotone variational inequality problems and the fixed point set of k-demicontractive mappings. Finally, we give some numerical experiments to illustrate the effectiveness of the proposed algorithm. The main results of this paper generalize and improve some known results in the literature. [ABSTRACT FROM AUTHOR]

In this paper, for solving a broad class of large-scale nonconvex and nonsmooth optimization problems, we propose a stochastic two-step inertial Bregman proximal alternating linearized minimization (STiBPALM) algorithm with variance-reduced stochastic gradient estimators. And we show that SAGA and SARAH are variance-reduced gradient estimators. Under expectation conditions with the Kurdyka–Łojasiewicz property and some suitable conditions on the parameters, we obtain that the sequence generated by the proposed algorithm converges to a critical point. And the general convergence rate is also provided. Numerical experiments on sparse nonnegative matrix factorization and blind image-deblurring are presented to demonstrate the performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The tensor equation A x m - 1 = b with the tensor A of order m and dimension n and the vector b , has practical applications in several fields including signal processing, high-dimensional PDEs, high-order statistics, and so on. In this paper, a class of exponential accelerated iterative methods is proposed for solving the tensor equation mentioned above in the sense that the coefficient tensor A is a symmetric and nonsingular or singular M -tensor. The obtained iterative schemes involve the classical Newton's method as a special case. It is shown that the proposed method for nonsingular case is superlinearly convergent, while for singular cases, it is linearly convergent. The performed numerical experiments demonstrate that our methods outperform some existing ones. [ABSTRACT FROM AUTHOR]

The problem considered in this paper is a sequence of two optimization problems in which the feasible region of the upper-level optimization problem is determined implicitly by the solution set of the lower-level optimization problem. Using the optimal value reformulation, together with the partial calmness property, we give necessary optimality conditions in terms of tangential subdifferentials. An example that illustrates our finding is also given. [ABSTRACT FROM AUTHOR]

Conjugate gradient (CG) methods are a popular class of iterative methods for solving linear systems of equations and nonlinear optimization problems. In this paper, a new hybrid conjugate gradient (CG) method is presented and analyzed for solving unconstrained optimization problems, where the parameter β k is a convex combination of β k WYL and β k CD . Under the strong Wolfe line search, the new method possesses the sufficient descent condition and the global convergence properties. The preliminary numerical results show the efficiency of our method in comparison with other CG methods. Furthermore, the proposed algorithm HWYLCD was extended to solve the problem of a mode function. [ABSTRACT FROM AUTHOR]

Adaptive cubic regularization (ARC) methods for unconstrained optimization compute steps from linear systems involving a shifted Hessian in the spirit of the Levenberg-Marquardt and trust-region methods. The standard approach consists in performing an iterative search for the shift akin to solving the secular equation in trust-region methods. Such search requires computing the Cholesky factorization of a tentative shifted Hessian at each iteration, which limits the size of problems that can be reasonably considered. We propose a scalable implementation of ARC named ARC q K in which we solve a set of shifted systems concurrently by way of an appropriate modification of the Lanczos formulation of the conjugate gradient (CG) method. At each iteration of ARC q K to solve a problem with n variables, a range of m ≪ n shift parameters is selected. The computational overhead in CG beyond the Lanczos process is thirteen scalar operations to update five vectors of length m , and two n -vector updates for each value of the shift. The CG variant only requires one Hessian-vector product and one dot product per iteration, independently of m . Solves corresponding to inadequate shift parameters are interrupted early. All shifted systems are solved inexactly. Such modest cost makes our implementation scalable and appropriate for large-scale problems. We provide a new analysis of the inexact ARC method including its worst case evaluation complexity, global and asymptotic convergence. We describe our implementation and report numerical experience that confirms that our implementation of ARC q K outperforms a classic Steihaug-Toint trust-region method, and the ARC method of the GALAHAD library. The latter solves the subproblem in nested Krylov subspaces by a Lanczos-based method, which requires the storage of a dense matrix that can be comparable to or larger than the two dense arrays required by our approach if the problem is large or requires many Lanczos iterations. Finally, we generalize our convergence results to inexact Hessians and nonlinear least-squares problems. [ABSTRACT FROM AUTHOR]

Stochastic (sub)gradient methods require step size schedule tuning to perform well in practice. Classical tuning strategies decay the step size polynomially and lead to optimal sublinear rates on (strongly) convex problems. An alternative schedule, popular in nonconvex optimization, is called geometric step decay and proceeds by halving the step size after every few epochs. In recent work, geometric step decay was shown to improve exponentially upon classical sublinear rates for the class of sharp convex functions. In this work, we ask whether geometric step decay similarly improves stochastic algorithms for the class of sharp weakly convex problems. Such losses feature in modern statistical recovery problems and lead to a new challenge not present in the convex setting: the region of convergence is local, so one must bound the probability of escape. Our main result shows that for a large class of stochastic, sharp, nonsmooth, and nonconvex problems a geometric step decay schedule endows well-known algorithms with a local linear (or nearly linear) rate of convergence to global minimizers. This guarantee applies to the stochastic projected subgradient, proximal point, and prox-linear algorithms. As an application of our main result, we analyze two statistical recovery tasks—phase retrieval and blind deconvolution—and match the best known guarantees under Gaussian measurement models and establish new guarantees under heavy-tailed distributions. [ABSTRACT FROM AUTHOR]

This paper describes a method for solving smooth nonconvex minimization problems subject to bound constraints with good worst-case complexity guarantees and practical performance. The method contains elements of two existing methods: the classical gradient projection approach for bound-constrained optimization and a recently proposed Newton-conjugate gradient algorithm for unconstrained nonconvex optimization. Using a new definition of approximate second-order optimality parametrized by some tolerance ϵ (which is compared with related definitions from previous works), we derive complexity bounds in terms of ϵ for both the number of iterations required and the total amount of computation. The latter is measured by the number of gradient evaluations or Hessian-vector products. We also describe illustrative computational results on several test problems from low-rank matrix optimization. [ABSTRACT FROM AUTHOR]

In this paper, we present convergence guarantees for a modified trust-region method designed for minimizing objective functions whose value and gradient and Hessian estimates are computed with noise. These estimates are produced by generic stochastic oracles, which are not assumed to be unbiased or consistent. We introduce these oracles and show that they are more general and have more relaxed assumptions than the stochastic oracles used in prior literature on stochastic trust-region methods. Our method utilizes a relaxed step acceptance criterion and a cautious trust-region radius updating strategy which allows us to derive exponentially decaying tail bounds on the iteration complexity for convergence to points that satisfy approximate first- and second-order optimality conditions. Finally, we present two sets of numerical results. We first explore the tightness of our theoretical results on an example with adversarial zeroth- and first-order oracles. We then investigate the performance of the modified trust-region algorithm on standard noisy derivative-free optimization problems. [ABSTRACT FROM AUTHOR]

In this paper, we focus on solving the decentralized optimization problem of minimizing the sum of n objective functions over a multi-agent network. The agents are embedded in an undirected graph where they can only send/receive information directly to/from their immediate neighbors. Assuming smooth and strongly convex objective functions, we propose an Optimal Gradient Tracking (OGT) method that achieves the optimal gradient computation complexity O κ log 1 ϵ and the optimal communication complexity O κ θ log 1 ϵ simultaneously, where κ and 1 θ denote the condition numbers related to the objective functions and the communication graph, respectively. To our best knowledge, OGT is the first single-loop decentralized gradient-type method that is optimal in both gradient computation and communication complexities. The development of OGT involves two building blocks that are also of independent interest. The first one is another new decentralized gradient tracking method termed "Snapshot" Gradient Tracking (SS-GT), which achieves the gradient computation and communication complexities of O κ log 1 ϵ and O κ θ log 1 ϵ , respectively. SS - G T can be potentially extended to more general settings compared to OGT. The second one is a technique termed Loopless Chebyshev Acceleration (LCA), which can be implemented "looplessly" but achieves a similar effect by adding multiple inner loops of Chebyshev acceleration in the algorithm. In addition to SS - G T , this LCA technique can accelerate many other gradient tracking based methods with respect to the graph condition number 1 θ . [ABSTRACT FROM AUTHOR]

This article presents a self-adjustable branch-and-bound algorithm for globally solving a class of linear multiplicative programming problems (LMP). In this algorithm, a self-adjustable branching rule is introduced and it can continuously update the upper bound for the optimal value of LMP by selecting suitable branching point under certain conditions, which differs from the standard bisection rule. The proposed algorithm further integrates the linear relaxation program and the self-adjustable branching rule. The dependability and robustness of the proposed algorithm are demonstrated by establishing the global convergence. Furthermore, the computational complexity of the proposed algorithm is estimated. Finally, numerical results validate the effectiveness of the self-adjustable branching rule and demonstrate the feasibility of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The notions and certain fundamental characteristics of the proximal and limiting normal cones with respect to a set are first presented in this paper. We present the ideas of the limiting coderivative and subdifferential with respect to a set of multifunctions and singleton mappings, respectively, based on these normal cones. The necessary and sufficient conditions for the Aubin property with respect to a set of multifunctions are then described by using the limiting coderivative with respect to a set. As a result of the limiting subdifferential with respect to a set, we offer the requisite optimality criteria for local solutions to optimization problems. In addition, we also provide examples to demonstrate the outcomes. [ABSTRACT FROM AUTHOR]

In this paper, we investigate sequential M-stationarity conditions for a class of nonsmooth nonconvex general optimization problems. We introduce various types of such conditions and compare them with previously established conditions in smooth or convex cases. The application of the derived results is demonstrated in the context of nonsmooth sparsity-constrained optimization problems. Additionally, we devise a Lagrangian-type algorithm for a specific case of smooth sparsity problems. Several examples are presented throughout the paper to illustrate the results. [ABSTRACT FROM AUTHOR]

In this paper, a new pair of higher-order nondifferentiable multiobjective mixed symmetric dual programs over arbitrary cones is formulated, where each of the objective functions contains a support function of a compact convex set. Usual duality theorems are established under higher-order K- (F , α , ρ , d) -convexity assumptions. Also, the example of a higher-order dual pair, which shows that higher-order provides tighter bounds for the value of the objective function of the primal and dual problem, is given in the paper. Several known results are also discussed as special cases. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new class of generalized Nash-population games (GNPGs) which can be used to capture the desired features of both population games (PGs) and generalized Nash games within the same framework. We introduce the concept of generalized inertial Nash equilibrium (GINE) for the GNPG and show the existence of GINE by using the method of the system of variational inequalities and fixed point theorems both in the compact and noncompact cases. Moreover, we introduce a slightly altruistic generalized inertial Nash equilibrium (SAGINE) as a refinement concept of the GINE and prove that the GNPG has at least an SAGINE under some mild assumptions. [ABSTRACT FROM AUTHOR]

In this work, we introduce a novel stochastic second-order method, within the framework of a non-monotone trust-region approach, for solving the unconstrained, nonlinear, and non-convex optimization problems arising in the training of deep neural networks. The proposed algorithm makes use of subsampling strategies that yield noisy approximations of the finite sum objective function and its gradient. We introduce an adaptive sample size strategy based on inexpensive additional sampling to control the resulting approximation error. Depending on the estimated progress of the algorithm, this can yield sample size scenarios ranging from mini-batch to full sample functions. We provide convergence analysis for all possible scenarios and show that the proposed method achieves almost sure convergence under standard assumptions for the trust-region framework. We report numerical experiments showing that the proposed algorithm outperforms its state-of-the-art counterpart in deep neural network training for image classification and regression tasks while requiring a significantly smaller number of gradient evaluations. [ABSTRACT FROM AUTHOR]