Search

A new subspace minimization conjugate gradient algorithm with a nonmonotone Wolfe line search is proposed and analyzed. In the scheme, we propose two choices of the search direction by minimizing a quadratic approximation of the objective function in special subspaces, and state criterions on how to choose the direction. Under given conditions, we obtain the significant conclusion that each choice of the direction satisfies the sufficient descent property. Based on the idea on how the function is close to a quadratic function, a new strategy for choosing the initial stepsize is presented for the line search. With the used nonmonotone Wolfe line search, we prove the global convergence of the proposed method for general nonlinear functions under mild assumptions. Numerical comparisons are given with well-known CGOPT and CG_DESCENT and show that the proposed algorithm is very promising. [ABSTRACT FROM AUTHOR]

Abstract: A simple three-term conjugate gradient algorithm which satisfies both the descent condition and the conjugacy condition is presented. This algorithm is a modification of the Hestenes and Stiefel algorithm (Hestenes and Stiefel, 1952) [10], or that of Hager and Zhang (Hager and Zhang, 2005) [23] in such a way that the search direction is descent and it satisfies the conjugacy condition. These properties are independent of the line search. Also, the algorithm could be considered as a modification of the memoryless BFGS quasi-Newton method. The new approximation of the minimum is obtained by the general Wolfe line search, now using a standard acceleration technique developed by Andrei (2009) [27]. For uniformly convex functions, under standard assumptions, the global convergence of the algorithm is proved. Numerical comparisons of the suggested three-term conjugate gradient algorithm versus six other three-term conjugate gradient algorithms, using a set of 750 unconstrained optimization problems, show that all these computational schemes have similar performances, the suggested one being slightly faster and more robust. The proposed three-term conjugate gradient algorithm substantially outperforms the well-known Hestenes and Stiefel conjugate gradient algorithm, as well as the more elaborate CG_DESCENT algorithm. Using five applications from the MINPACK-2 test problem collection (Averick et al., 1992) [25], with variables, we show that the suggested three-term conjugate gradient algorithm is the top performer versus CG_DESCENT. [Copyright &y& Elsevier]

Abstract: The solution of the augmented Lagrangian related system is a key ingredient of many iterative algorithms for the solution of saddle-point problems in constrained optimization with quasi-Newton methods. However, such problems are ill-conditioned when the penalty parameter tends to zero, whereas the error vanishes as . We present a new fast method based on a splitting penalty scheme to solve such problems with a judicious prediction–correction method. We prove that, due to the adapted right-hand side, the solution of the correction step only requires the approximation of operators independent of , when is taken sufficiently small. Hence, the proposed method is as cheaper as tends to zero. We apply the two-step scheme to efficiently solve the saddle-point problem with a penalty method. Indeed, that fully justifies the interest of the vector penalty-projection methods recently proposed by Angot et al. (2008) to solve the unsteady incompressible Navier–Stokes equations, for which we give the stability result and some quasi-optimal error estimates. Moreover, the numerical experiments confirm both the theoretical analysis and the efficiency of the proposed method which produces a fast splitting solution to augmented Lagrangian or penalty problems, possibly used as a suitable preconditioner to the fully coupled system. [Copyright &y& Elsevier]

Abstract: In this paper, we give new results on the Alienor method of dimension reduction. This technique is used to solve multidimensional global optimization problems of type min x∈X f(x) where f is a non convex Lipschitz function and X a compact set of defined by Lipschitz constraints. The idea is to construct an α-dense curve h in the feasible set X. The global minimum of f on X is then approximated by the global minimum of f on the curve h. That is, our problem has become a one-dimensional problem which can be solved by the Piyavskii–Shubert method. Examples of these curves and numerical implementations on several test functions are given. [Copyright &y& Elsevier]

In this article we consider an equilibrium problem for a differentiable bifunction which is not necessarily monotone. We present an implementable projection method. At each iteration, only one inexact projection onto a simple approximation of the constraint set is performed, such as a polyhedron, which renders it numerically attractive. The algorithm can identify, in practice, a subsequence that converges to a solution under reasonable assumptions. Some numerical results are reported showing the performance of our algorithm. [ABSTRACT FROM PUBLISHER]

Abstract: In this paper we propose an iterative algorithm to solve large size linear inverse ill posed problems. The regularization problem is formulated as a constrained optimization problem. The dual Lagrangian problem is iteratively solved to compute an approximate solution. Before starting the iterations, the algorithm computes the necessary smoothing parameters and the error tolerances from the data. The numerical experiments performed on test problems show that the algorithm gives good results both in terms of precision and computational efficiency. [Copyright &y& Elsevier]

Abstract: In this paper, a new smoothing Newton method is proposed for solving constrained nonlinear equations. We first transform the constrained nonlinear equations to a system of semismooth equations by using the so-called absolute value function of the slack variables, and then present a new smoothing Newton method for solving the semismooth equations by constructing a new smoothing approximation function. This new method is globally and quadratically convergent. It needs to solve only one system of unconstrained equations and to perform one line search at each iteration. Numerical results show that the new algorithm works quite well. [Copyright &y& Elsevier]

In this paper, we investigate a symmetric rank-one (SR1) quasi-Newton (QN) formula in which the Hessian of the objective function has some special structure. Instead of approximating the whole Hessian via the SR1 formula, we consider an approach which only approximates part of the Hessian matrix that is not easily acquired. Although the SR1 update possesses desirable features, it is unstable in the sense that, it may not retain positive definiteness and may become undefined. Therefore, we describe some safeguards to overcome these difficulties. Since the structured SR1 method provides a more accurate Hessian approximation, therefore the proposed method reduces significantly the computational efforts needed in solving a problem. The results of a series of experiments on a typical set of standard unconstrained optimization problems are reported, which show that the structured SR1 method exhibits a clear improvement in numerical performance over some existing QN algorithms. [ABSTRACT FROM AUTHOR]

We propose a new fast algorithm for solving one of the standard approaches to ill-posed linear inverse problems (IPLIP), where a (possibly nonsmooth) regularizer is minimized under the constraint that the solution explains the observations sufficiently well. Although the regularizer and constraint are usually convex, several particular features of these problems (huge dimensionality, nonsmoothness) preclude the use of off-the-shelf optimization tools and have stimulated a considerable amount of research. In this paper, we propose a new efficient algorithm to handle one class of constrained problems (often known as basis pursuit denoising) tailored to image recovery applications. The proposed algorithm, which belongs to the family of augmented Lagrangian methods, can be used to deal with a variety of imaging IPLIP, including deconvolution and reconstruction from compressive observations (such as MRI), using either total-variation or wavelet-based (or, more generally, frame-based) regularization. The proposed algorithm is an instance of the so-called alternating direction method of multipliers, for which convergence sufficient conditions are known; we show that these conditions are satisfied by the proposed algorithm. Experiments on a set of image restoration and reconstruction benchmark problems show that the proposed algorithm is a strong contender for the state-of-the-art. [ABSTRACT FROM AUTHOR]

Abstract: The purpose of this paper is to present a new family of numerical methods for the approximation of second order hyperbolic partial differential equations submitted to a convex constraint on the solution. The main application is dynamic contact problems. The principle consists in the use of a singular mass matrix obtained by the mean of different discretizations of the solution and of its time derivative. We prove that the semi-discretized problem is well-posed and energy conserving. Numerical experiments show that this is a crucial property to build stable numerical schemes. [Copyright &y& Elsevier]

Abstract: In this paper, we propose some improvements on a new gradient-type method for solving large-scale unconstrained optimization problems, in which we use data from two previous steps to revise the current approximate Hessian. The new method which we considered, resembles to that of Barzilai and Borwein (BB) method. The innovation features of this approach consist in using approximation of the Hessian in diagonal matrix form based on the modified weak secant equation rather than the multiple of the identity matrix in the BB method. Using this approach, we can obtain a higher order accuracy of Hessian approximation when compares to other existing BB-type method. By incorporating a simple monotone strategy, the global convergence of the new method is achieved. Practical insights into the effectiveness of the proposed method are given by numerical comparison with the BB method and its variant. [Copyright &y& Elsevier]

Abstract: The balanced Procrustes problem with some special constraints such as symmetric orthogonality and symmetric idempotence are considered. By one time eigenvalue decomposition of the matrix product generated by the matrices and , the constrained solutions are constructed simply. Similar strategy is applied to the problem with the corresponding -commuting constraints with a given symmetric matrix . Numerical examples are presented to show the efficiency of the proposed methods. [Copyright &y& Elsevier]

Abstract: The Ciarlet–Raviart mixed finite element approximation is constructed to solve the constrained optimal control problem governed by the first bi-harmonic equation. The optimality conditions consisting of the state and the co-state equations is derived. Also, the a priori error estimates are analyzed. In the analysis of the a priori error estimates, the improved convergent rate of the higher order than existed results is proved. Some numerical experiments are performed to confirm the theoretical analysis for the a priori error estimate. [Copyright &y& Elsevier]

In order to find sparse approximations of signals, an appropriate generative model for the signal class has to be known. If the model is unknown, it can be adapted using a set of training samples. This paper presents a novel method for dictionary learning and extends the learning problem by introducing different constraints on the dictionary. The convergence of the proposed method to a fixed point is guaranteed, unless the accumulation points form a continuum. This holds for different sparsity measures. The majorization method is an optimization method that substitutes the original objective function with a surrogate function that is updated in each optimization step. This method has been used successfully in sparse approximation and statistical estimation [e.g., expectation-maximization (EM)] problems. This paper shows that the majorization method can be used for the dictionary learning problem too. The proposed method is compared with other methods on both synthetic and real data and different constraints on the dictionary are compared. Simulations show the advantages of the proposed method over other currently available dictionary learning methods not only in terms of average performance but also in terms of computation time. [ABSTRACT FROM AUTHOR]

We propose a pattern search method to solve a classical nonsmooth optimization problem. In a deep analogy with pattern search methods for linear constrained optimization, the set of search directions at each iteration is defined in such a way that it conforms to the local geometry of the set of points of nondifferentiability near the current iterate. This is crucial to ensure convergence. The approach presented here can be extended to wider classes of nonsmooth optimization problems. Numerical experiments seem to be encouraging. [ABSTRACT FROM AUTHOR]

This paper proposes a line search technique to satisfy a relaxed form of the strong Wolfe conditions in order to guarantee the descent condition at each iteration of the Polak-Ribière-Polyak conjugate gradient algorithm. It is proved that this line search algorithm preserves the usual convergence properties of any descent algorithm. In particular, it is shown that the Zoutendijk condition holds under mild assumptions. It is also proved that the resulting conjugate gradient algorithm is convergent under a strong convexity assumption. For the nonconvex case, a globally convergent modification is proposed. Numerical tests are presented. [ABSTRACT FROM AUTHOR]