Search

This paper considers a stochastic optimization problem over the fixed point sets of quasinonexpansive mappings on Riemannian manifolds. The problem enables us to consider Riemannian hierarchical optimization problems over complicated sets, such as the intersection of many closed convex sets, the set of all minimizers of a nonsmooth convex function, and the intersection of sublevel sets of nonsmooth convex functions. We focus on adaptive learning rate optimization algorithms, which adapt step-sizes (referred to as learning rates in the machine learning field) to find optimal solutions quickly. We then propose a Riemannian stochastic fixed point optimization algorithm, which combines fixed point approximation methods on Riemannian manifolds with the adaptive learning rate optimization algorithms. We also give convergence analyses of the proposed algorithm for nonsmooth convex and smooth nonconvex optimization. The analysis results indicate that, with small constant step-sizes, the proposed algorithm approximates a solution to the problem. Consideration of the case in which step-size sequences are diminishing demonstrates that the proposed algorithm solves the problem with a guaranteed convergence rate. This paper also provides numerical comparisons that demonstrate the effectiveness of the proposed algorithms with formulas based on the adaptive learning rate optimization algorithms, such as Adam and AMSGrad. [ABSTRACT FROM AUTHOR]

In this paper, a method is developed for solving nonsmooth nonconvex minimization problems. This method extends the classical BFGS framework. First, we generalize the Wolfe conditions for locally Lipschitz functions and prove that this generalization is well defined. Then, a line search algorithm is presented to find a step length satisfying the generalized Wolfe conditions. Next, the Goldstein e-subgradient is approximated by an iterative method and a descent direction is computed using a positive definite matrix. This matrix is updated using the BFGS method. Finally, a minimization algorithm based on the BFGS method is described. The algorithm is implemented in MATLAB and numerical results using it are reported. [ABSTRACT FROM AUTHOR]

In this paper, we propose Linesearch methods for solving a bilevel split variational inequality problem (BSVIP) involving a strongly monotone mapping in the upper-level problem and pseudomonotone mappings in the lower-level one. A strongly convergent algorithm for such a BSVIP is proposed and analyzed. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to introduce a general iterative method for finding a common element of the set of common fixed points of an infinite family of nonexpansive mappings and the set of split variational inclusion problem in the framework Hilbert spaces. Strong convergence theorem of the sequences generated by the purpose iterative scheme is obtained. In the last section, we present some computational examples to illustrate the assumptions of the proposed algorithms. [ABSTRACT FROM AUTHOR]

In this paper, a new filled function method for finding a global minimizer of global optimization is proposed. The proposed filled function is continuously differentiable and only contains one parameter. It has no parameter sensitive terms. As a result, a general classical local optimization method can be used to find a better minimizer of the proposed filled function with easy parameter adjustment. Numerical experiments show that the proposed filled function method is effective. [ABSTRACT FROM AUTHOR]

The limited memory BFGS method (L-BFGS) is an adaptation of the BFGS method for large-scale unconstrained optimization. However, The L-BFGS method need not converge for nonconvex objective functions and it is inefficient on highly ill-conditioned problems. In this paper, we proposed a regularization strategy on the L-BFGS method, where the used regularization parameter may play a compensation role in some sense when the condition number of Hessian approximation tends to become ill-conditioned. Then we proposed a regularized L-BFGS method and established its global convergence even when the objective function is nonconvex. Numerical results show that the proposed method is efficient. [ABSTRACT FROM AUTHOR]

This paper presents a modified ODE-based algorithm for unconstrained optimization problems. It combines the idea of IMPBOT algorithm with nonmonotone and subspace techniques. The main feature of this method is that at each iteration, a lower dimensional system of linear equations is solved to obtain a trial step. Under some standard assumptions, the method is proven to be globally convergent. Numerical results show the efficiency of this proposed method in practical computation. [ABSTRACT FROM AUTHOR]

In this paper, we proposed an implementation of stochastic perturbation of reduced gradient and bisection (SPRGB) method for optimizing a non-convex differentiable function subject to linear equality constraints and non-negativity bounds on the variables. In particular, at each iteration, we compute a search direction by reduced gradient, and optimal line search by bisection algorithm along this direction yields a decrease in the objective value. SPRGB method is desired to establish the global convergence of the algorithm. An implementation and tests of SPRGB algorithm are given, and some numerical results of large-scale problems are presented, which show the efficient of this approach. [ABSTRACT FROM AUTHOR]

In this paper, making use a exponential integral filter, a new algorithm for unconstrained global optimization is proposed. Compared with Yang's absolute value type integral filter method (Yang et al., Appl Math Comput 18:173-180, ), this algorithm is more effective and more sensitive. Numerical results for some typical examples show that in most cases, this algorithm works effectively and reliably. [ABSTRACT FROM AUTHOR]

Practical Nonlinear Programming algorithms may converge to infeasible points. It is sensible to detect this situation as quickly as possible, in order to have time to change initial approximations and parameters, with the aim of obtaining convergence to acceptable solutions in further runs. In this paper, a recently introduced Augmented Lagrangian algorithm is modified in such a way that the probability of quick detection of asymptotic infeasibility is enhanced. The modified algorithm preserves the property of convergence to stationary points of the sum of squares of infeasibilities without harming the convergence to KKT points in feasible cases. [ABSTRACT FROM AUTHOR]

Kernel functions play an important role in the design and analysis of primal-dual interior-point algorithms. They are not only used for determining the search directions but also for measuring the distance between the given iterate and the μ-center for the algorithms. In this paper we present a unified kernel function approach to primal-dual interior-point algorithms for convex quadratic semidefinite optimization based on the Nesterov and Todd symmetrization scheme. The iteration bounds for large- and small-update methods obtained are analogous to the linear optimization case. Moreover, this unifies the analysis for linear, convex quadratic and semidefinite optimizations. [ABSTRACT FROM AUTHOR]

A correction to the article "Comments on another hybrid conjugate gradient algorithm for unconstrained optimization by Andrei" that was published online on September 8, 2015 is presented.

In this paper, a new nonmonotone inexact line search rule is proposed and applied to the trust region method for unconstrained optimization problems. In our line search rule, the current nonmonotone term is a convex combination of the previous nonmonotone term and the current objective function value, instead of the current objective function value . We can obtain a larger stepsize in each line search procedure and possess nonmonotonicity when incorporating the nonmonotone term into the trust region method. Unlike the traditional trust region method, the algorithm avoids resolving the subproblem if a trial step is not accepted. Under suitable conditions, global convergence is established. Numerical results show that the new method is effective for solving unconstrained optimization problems. [ABSTRACT FROM AUTHOR]

In the framework of multistart and local search algorithms that find the global minimum of a real function f( x), $ x \in S\subseteq R^n$, Gaviano et alias proposed a rule for deciding, as soon as a local minimum has been found, whether to perform or not a new local minimization. That rule was designed to minimize the average local computational cost $eval_1(\cdotp)$ required to move from the current local minimum to a new one. In this paper the expression of the cost $eval_2(\cdotp)$ of the entire process of getting a global minimum is found and investigated; it is shown that $eval_2(\cdotp)$ has among its components $eval_1(\cdotp)$ and can be only monotonically increasing or decreasing; that is, it exhibits the same property of $eval_1(\cdotp)$. Moreover, a counterexample is given that shows that the optimal values given by $eval_1(\cdotp)$ and $eval_2(\cdotp)$ might not agree. Further, computational experiments of a parallel algorithm that uses the above rule are carried out in a MatLab environment. [ABSTRACT FROM AUTHOR]

In this paper we present a deterministic method for tracing the Pareto frontier in non-linear bi-objective optimization problems with equality and inequality constraints. We reformulate the bi-objective optimization problem as a parametric single-objective optimization problem with an additional Normalized Normal Equality Constraint (NNEC) similar to the existing Normal Boundary Intersection (NBI) and the Normalized Normal Constraint method (NNC). By computing the so called Defining Initial Value Problem (DIVP) for segments of the Pareto front and solving a continuation problem with a standard integrator for ordinary differential equations (ODE) we can trace the Pareto front. We call the resulting approach ODE NNEC method and demonstrate numerically that it can yield the entire Pareto frontier to high accuracy. Moreover, due to event detection capabilities available for common ODE integrators, changes in the active constraints can be automatically detected. The features of the current algorithm are illustrated for two case studies whose ® code is available as Electronic Supplementary Material to this article. [ABSTRACT FROM AUTHOR]

In this paper, we propose a non-monotone line search multidimensional filter-SQP method for general nonlinear programming based on the Wächter-Biegler methods for nonlinear equality constrained programming. Under mild conditions, the global convergence of the new method is proved. Furthermore, with the non-monotone technique and second order correction step, it is shown that the proposed method does not suffer from the Maratos effect, so that fast local convergence to second order sufficient local solutions is achieved. Numerical results show that the new approach is efficient. [ABSTRACT FROM AUTHOR]

An accelerated hybrid conjugate gradient algorithm represents the subject of this paper. The parameter β k is computed as a convex combination of $\beta_k^{HS}$ (Hestenes and Stiefel, J Res Nat Bur Stand 49:409–436, ) and $\beta_k^{DY}$ (Dai and Yuan, SIAM J Optim 10:177–182, ), i.e. $\beta_k^C =\left({1-\theta_k}\right)\beta_k^{HS} + \theta_k \beta_k^{DY}$. The parameter θ k in the convex combinaztion is computed in such a way the direction corresponding to the conjugate gradient algorithm is the best direction we know, i.e. the Newton direction, while the pair ( s k, y k) satisfies the modified secant condition given by Li et al. (J Comput Appl Math 202:523–539, ) B k + 1 s k = z k, where $z_k =y_k +\left({{\eta_k} / {\left\| {s_k} \right\|^2}} \right)s_k$, $\eta_k =2\left( {f_k -f_{k+1}} \right)+\left( {g_k +g_{k+1}} \right)^Ts_k$, s k = x k + 1 − x k and y k = g k + 1 − g k. It is shown that both for uniformly convex functions and for general nonlinear functions the algorithm with strong Wolfe line search is globally convergent. The algorithm uses an acceleration scheme modifying the steplength α k for improving the reduction of the function values along the iterations. Numerical comparisons with conjugate gradient algorithms show that this hybrid computational scheme outperforms a variant of the hybrid conjugate gradient algorithm given by Andrei (Numer Algorithms 47:143–156, ), in which the pair ( s k, y k) satisfies the classical secant condition B k + 1 s k = y k, as well as some other conjugate gradient algorithms including Hestenes-Stiefel, Dai-Yuan, Polack-Ribière-Polyak, Liu-Storey, hybrid Dai-Yuan, Gilbert-Nocedal etc. A set of 75 unconstrained optimization problems with 10 different dimensions is being used (Andrei, Adv Model Optim 10:147–161, ). [ABSTRACT FROM AUTHOR]

Abstract  Recently, Roos (SIAM J Optim 16(4):1110–1136, 2006) presented a primal-dual infeasible interior-point algorithm that uses full-Newton steps and whose iteration bound coincides with the best known bound for infeasible interior-point algorithms. In the current paper we use a different feasibility step such that the definition of the feasibility step in Mansouri and Roos (Optim Methods Softw 22(3):519–530, 2007) is a special case of our definition, and show that the same result on the order of iteration complexity can be obtained. [ABSTRACT FROM AUTHOR]

We present an arc-search infeasible interior-point algorithm for semidefinite optimization using the Nesterov-Todd search directions. The algorithm is based on the negative infinity neighborhood of the central path. The algorithm searches an ε-approximate solution of the problem along the ellipsoidal approximation of the entire central path. The convergence analysis of the algorithm is presented and shows that the algorithm has the iteration complexity bound O n 3 / 2 log ε − 1 . Here, n is the dimension of the problem and ε is the required precision. The numerical results show that our algorithm is efficient and promising. [ABSTRACT FROM AUTHOR]

We present a gradient descent algorithm with a line search procedure for solving unconstrained optimization problems which is defined as a result of applying Picard-Mann hybrid iterative process on accelerated gradient descent SM method described in Stanimirović and Miladinović (Numer. Algor. 54, 503-520, 2010). Using merged features of both analyzed models, we show that new accelerated gradient descent model converges linearly and faster then the starting SM method which is confirmed trough displayed numerical test results. Three main properties are tested: number of iterations, CPU time and number of function evaluations. The efficiency of the proposed iteration is examined for the several values of the correction parameter introduced in Khan (2013). [ABSTRACT FROM AUTHOR]

Hybridizing monotone and nonmonotone approaches, we employ a modified trust region ratio in which more information is provided about the agreement between the exact and the approximate models. Also, we use an adaptive trust region radius as well as two accelerated Armijo-type line search strategies to avoid resolving the trust region subproblem whenever a trial step is rejected. We show that the proposed algorithm is globally and locally superlinearly convergent. Comparative numerical experiments show practical efficiency of the proposed accelerated adaptive trust region algorithm. [ABSTRACT FROM AUTHOR]

Based on the alternating direction method of multipliers (ADMM), we develop three numerical algorithms incrementally for solving the optimal control problems constrained by random Helmholtz equations. First, we apply the standard Monte Carlo technique and finite element method for the random and spatial discretization, respectively, and then ADMM is used to solve the resulting system. Next, combining the multi-modes expansion, Monte Carlo technique, finite element method, and ADMM, we propose the second algorithm. In the third algorithm, we preprocess certain quantities before the ADMM iteration, so that nearly no random variable is in the inner iteration. This algorithm is the most efficient one and is easy to implement. The error estimates of these three algorithms are established. The numerical experiments verify the efficiency of our algorithms. [ABSTRACT FROM AUTHOR]

We present a new smaller upper bound for all the elements in the associate generalized Hessian used in the smoothing quadratic regularization (SQR) algorithm proposed by Bian and Chen (SIAM J. Optim. 23: 1718-1741, ). We modify the SQR algorithm by making use of the new upper bound. Numerical results show that our new upper bound improves the performance of the SQR algorithm significantly. [ABSTRACT FROM AUTHOR]

A three-term conjugate gradient algorithm for large-scale unconstrained optimization using subspace minimizing technique is presented. In this algorithm the search directions are computed by minimizing the quadratic approximation of the objective function in a subspace spanned by the vectors: − g, s and y. The search direction is considered as: d = − g + a s + b y, where the scalars a and b are determined by minimization the affine quadratic approximate of the objective function. The step-lengths are determined by the Wolfe line search conditions. We prove that the search directions are descent and satisfy the Dai-Liao conjugacy condition. The suggested algorithm is of three-term conjugate gradient type, for which both the descent and the conjugacy conditions are guaranteed. It is shown that, for uniformly convex functions, the directions generated by the algorithm are bounded above, i.e. the algorithm is convergent. The numerical experiments, for a set of 750 unconstrained optimization test problems, show that this new algorithm substantially outperforms the known Hestenes and Stiefel, Dai and Liao, Dai and Yuan and Polak, Ribiére and Poliak conjugate gradient algorithms, as well as the limited memory quasi-Newton method L-BFGS and the discrete truncated-Newton method TN. [ABSTRACT FROM AUTHOR]

Based on two modified secant equations proposed by Yuan, and Li and Fukushima, we extend the approach proposed by Andrei, and introduce two hybrid conjugate gradient methods for unconstrained optimization problems. Our methods are hybridizations of Hestenes-Stiefel and Dai-Yuan conjugate gradient methods. Under proper conditions, we show that one of the proposed algorithms is globally convergent for uniformly convex functions and the other is globally convergent for general functions. To enhance the performance of the line search procedure, we propose a new approach for computing the initial value of the steplength for initiating the line search procedure. We give a comparison of the implementations of our algorithms with two efficiently representative hybrid conjugate gradient methods proposed by Andrei using unconstrained optimization test problems from the CUTEr collection. Numerical results show that, in the sense of the performance profile introduced by Dolan and Moré, the proposed hybrid algorithms are competitive, and in some cases more efficient. [ABSTRACT FROM AUTHOR]

Abstract  Another hybrid conjugate gradient algorithm is subject to analysis. The parameter β k is computed as a convex combination of $$ \beta ^{{HS}}_{k} $$ (Hestenes-Stiefel) and $$ \beta ^{{DY}}_{k} $$ (Dai-Yuan) algorithms, i.e. $$ \beta ^{C}_{k} = {\left( {1 - \theta _{k} } \right)}\beta ^{{HS}}_{k} \theta _{k} \beta ^{{DY}}_{k} $$. The parameter θ k in the convex combination is computed in such a way so that the direction corresponding to the conjugate gradient algorithm to be the Newton direction and the pair (s k , y k ) to satisfy the quasi-Newton equation $$ \nabla ^{2} f{\left( {x_{{k 1}} } \right)}s_{k} = y_{k} $$, where $$ s_{k} = x_{{k 1}} - x_{k} $$ and $$ y_{k} = g_{{k 1}} - g_{k} $$. The algorithm uses the standard Wolfe line search conditions. Numerical comparisons with conjugate gradient algorithms show that this hybrid computational scheme outperforms the Hestenes-Stiefel and the Dai-Yuan conjugate gradient algorithms as well as the hybrid conjugate gradient algorithms of Dai and Yuan. A set of 750 unconstrained optimization problems are used, some of them from the CUTE library. [ABSTRACT FROM AUTHOR]