一类凸优化的加速混合下降算法

凸优化问题的混合下降算法利用近似条件的已知信息和随机数扩张预测校正步得到了一组下降方向.而前向加速收缩算法利用高斯赛德尔迭代算法的技术,结合邻近点算法和近似邻近点算法的思想,构造了富有扩张性的下降方向.本文借鉴混合下降算法和前向加速收缩算法的思想,利用已有近似规则信息改善了混合下降算法的下降方向,得到了一类凸优化问题的加速混合下降算法.随后利用Markov不等式、凸函数性质和投影的基本性质等,实现了算法的依概率收敛证明.一系列数值试验表明了加速混合下降算法的有效性和效率性.     

An LQP-based descent method for structured monotone variational inequalities

This paper proposes a descent method to solve a class of structured monotone variational inequalities. The descent directions are constructed from the iterates generated by a prediction-correction method [B.S. He, Y. Xu, X.M. Yuan, A logarithmic-quadratic proximal prediction-correction method for structured monotone variational inequalities, Comput. Optim. Appl. 35 (2006) 19-46], which is based on the logarithmic-quadratic proximal method. In addition, the optimal step-sizes along these descent directions are identified to accelerate the convergence of the new method. Finally, some numerical results for solving traffic equilibrium problems are reported.     

A sufficient descent LS conjugate gradient method for unconstrained optimization problems

In this paper, we make a modification to the Liu-Storey (LS) conjugate gradient method and propose a descent LS method. The method can generate sufficient descent directions for the objective function. This property is independent of the line search used. We prove that the modified LS method is globally convergent with the strong Wolfe line search. The numerical results show that the proposed descent LS method is efficient for the unconstrained problems in the CUTEr library.     

一种求解单调变分不等式的部分并行分裂LQP交替方向法

LQP交替方向法是求解可分离结构型单调变分不等式问题的一种非常有效的方法.它不仅可以充分地利用目标函数的可分结构,将原问题分解为多个更易求解的子问题,还更适合求解大规模问题.对于带有三个可分离算子的单调变分不等式问题,结合增广拉格朗日算法和LQP交替方向法提出了一种部分并行分裂LQP交替方向法,构造了新算法的两个下降方向,结合这两个下降方向得到了一个新的下降方向,沿着这个新的下降方向给出了最优步长.并在较弱的假设条件下,证明了新算法的全局收敛性.     

一类线性约束下不可微最优化问题的可行下降方法

本文给出了一类线性约束下不可微量优化问题的可行下降方法，这类问题的目标函数是凸函数和可微函数的合成函数，算法通过解系列二次规划寻找可行下降方向，新的迭代点由不精确线搜索产生，在较弱的条件下，我们证明了算法的全局收敛性     

On the sufficient descent property of the Shanno’s conjugate gradient method

Satisfying in the sufficient descent condition is a strength of a conjugate gradient method. Here, it is shown that under the Wolfe line search conditions the search directions generated by the memoryless BFGS conjugate gradient algorithm proposed by Shanno satisfy the sufficient descent condition for uniformly convex functions.     

一个充分下降的有效共轭梯度法

对于大规模无约束优化问题,本文提出了一个充分下降的共轭梯度法公式,并建立相应的算法.该算法在不依赖于任何线搜索条件下,每步迭代都能产生一个充分下降方向.若采用标准Wolfe非精确线搜索求步长,则在常规假设条件下可获得算法良好的全局收敛性最后,对算法进行大规模数值试验,并采用Dolan和More的性能图对试验效果进行刻画,结果表明该算法是有效的.     

Multiple subgradient descent bundle method for convex nonsmooth multiobjective optimization

The aim of this paper is to propose a new multiple subgradient descent bundle method for solving unconstrained convex nonsmooth multiobjective optimization problems. Contrary to many existing multiobjective optimization methods, our method treats the objective functions as they are without employing a scalarization in a classical sense. The main idea of this method is to find descent directions for every objective function separately by utilizing the proximal bundle approach, and then trying to form a common descent direction for every objective function. In addition, we prove that the method is convergent and it finds weakly Pareto optimal solutions. Finally, some numerical experiments are considered.     

A short note on the global convergence of the unmodified PRP method

To guarantee global convergence of the standard (unmodified) PRP nonlinear conjugate gradient method for unconstrained optimization, the exact line search or some Armijo type line searches which force the PRP method to generate descent directions have been adopted. In this short note, we propose a non-descent PRP method in another way. We prove that the unmodified PRP method converges globally even for nonconvex minimization by the use of an approximate descent inexact line search.     

Direct search algorithm for bilevel programming problems

In this paper, we study the application of a class of direct search methods to bilevel programming with convex lower level problems with strongly stable optimal solutions. In those methods, directions of descent in each iterations are selected within a finite set of directions. To guarantee the existence of such a finite set, we investigate the relation between the aperture of a descent cone at a non stationary point and the vector density of a finite set of directions. It is shown that the direct search method converges to a Clarke stationary point of the bilevel programming problem.     

结合修正Curry-Altman步长搜索一个新的共轭梯度算法的收敛性

Conjugate gradient optimization algorithms depend on the search directions with different choices for the parameter in the search directions. In this note, conditions are given on the parameter in the conjugate gradient directions to ensure the descent property of the search directions. Global convergence of such a class of methods is discussed. It is shown that, using reverse modulus of continuity function and forcing function, the new method for solving unconstrained optimization can work for a continuously differentiable function with a modification of the Curry-Altman‘s step-size rule and a bounded level set. Combining PR method with our new method, PR method is modified to have global convergence property.Numerical experiments show that the new methods are efficient by comparing with FR conjugate gradient method.     

解非线性对称方程组问题的具有下降方向的近似高斯-牛顿基础的BFGS方法

本本文给出了一个解非线性对称方程组问题的具有下降方向的近似高斯一牛顿基础BFGS方法。无论使用何种线性搜索此方法产生的方向总是下降的。在适当的条件下我们将证明此方法的全局收敛性和超线性收敛性。并给出数值检验结果。     

Modifications of the Wolfe Line Search Rules to Satisfy Second-Order Optimally Conditions in Unconstrained Optimization

The line search method incorporating the Wolfe conditions is modified to ensure that a descent algorithm terminates in a finite number of steps at an approximate stationary point where the second-order conditions of optimality are satisfied. A simple procedure based on conjugate directions is proposed to determine directions of negative curvature.     

A constrained optimization reformulation and a feasible descent direction method for L_{1/2} regularization

In this paper, we first propose a constrained optimization reformulation to the \(L_{1/2}\) regularization problem. The constrained problem is to minimize a smooth function subject to some quadratic constraints and nonnegative constraints. A good property of the constrained problem is that at any feasible point, the set of all feasible directions coincides with the set of all linearized feasible directions. Consequently, the KKT point always exists. Moreover, we will show that the KKT points are the same as the stationary points of the \(L_{1/2}\) regularization problem. Based on the constrained optimization reformulation, we propose a feasible descent direction method called feasible steepest descent method for solving the unconstrained \(L_{1/2}\) regularization problem. It is an extension of the steepest descent method for solving smooth unconstrained optimization problem. The feasible steepest descent direction has an explicit expression and the method is easy to implement. Under very mild conditions, we show that the proposed method is globally convergent. We apply the proposed method to solve some practical problems arising from compressed sensing. The results show its efficiency.     

A method for minimizing the sum of a convex function and a continuously differentiable function

This paper presents a method for minimizing the sum of a possibly nonsmooth convex function and a continuously differentiable function. As in the convex case developed by the author, the algorithm is a descent method which generates successive search directions by solving quadratic programming subproblems. An inexact line search ensures global convergence of the method to stationary points.     

共轭下降法的全局收敛性

本文提出了一种Armijo型的线搜索，并在这种线搜索下讨论了共轭下降法的全局收敛性，且可得方法在每次迭代均产生一个下降搜索方向．     

A new LQP alternating direction method for solving variational inequality problems with separable structure

We presented a new logarithmic-quadratic proximal alternating direction scheme for the separable constrained convex programming problem. The predictor is obtained by solving series of related systems of non-linear equations in a parallel wise. The new iterate is obtained by searching the optimal step size along a new descent direction. The new direction is obtained by the linear combination of two descent directions. Global convergence of the proposed method is proved under certain assumptions. We show the O(1 / t) convergence rate for the parallel LQP alternating direction method.     

Greatest Descent Algorithms in Unconstrained Optimization

We show that, for an unconstrained optimization problem, the long-term optimal trajectory consists of a sequence of greatest descent directions and a Newton method in the final iteration. The greatest descent direction can be computed approximately by using a Levenberg-Marquardt like formula. This implies the view that the Newton method approximates a Levenberg-Marquardt like formula at a finite distance from the minimum point, instead of the standard view that the Levenberg-Marquadt formula is a way to approximate the Newton method. With the insight gained from this analysis, we develop a two-dimensional version of a Levenberg-Marquardt like formula. We make use of the two numerically largest components of the gradient vector to define here new search directions. In this way, we avoid the need of inverting a high-dimensional matrix. This reduces also the storage requirements for the full Hessian matrix in problems with a large number of variables. The author thanks Mark Wu, Professors Sanyang Liu, Junmin Li, Shuisheng Zhou and Feng Ye for support and help in this research as well as the referees for helpful comments.     

<Emphasis Type="Italic">ε</Emphasis>-subgradient algorithms for locally lipschitz functions on Riemannian manifolds

This paper presents a descent direction method for finding extrema of locally Lipschitz functions defined on Riemannian manifolds. To this end we define a set-valued mapping \(x\rightarrow \partial _{\varepsilon } f(x)\) named ε-subdifferential which is an approximation for the Clarke subdifferential and which generalizes the Goldstein- ε-subdifferential to the Riemannian setting. Using this notion we construct a steepest descent method where the descent directions are computed by a computable approximation of the ε-subdifferential. We establish the global convergence of our algorithm to a stationary point. Numerical experiments illustrate our results.