有界约束半光滑方程组的非单调投影信赖域方法

投影信赖域策略结合非单调线搜索算法解有界约束非线性半光滑方程组.基于简单有界约束的非线性优化问题构建信赖域子问题,半光滑类牛顿步在可行域投影得到投影牛顿的试探步,获得新的搜索方向,结合非单调线搜索技术得到回代步,获得新的步长.在合理的条件下,证明算法不仅具有整体收敛性且保持超线性收敛速率.引入非单调技术能克服高度非线性的病态问题,加速收敛性进程,得到超线性收敛速率.     

仿射内点既约投影Hessian算法解非线性约束优化

本文结合非单调内点回代技术,提供了新的仿射信赖域方法解含有非负变量约束和非线性等式约束的优化问题.为求解大规模问题,采用等式约束的Jacobian矩阵的QR分解和两块校正的双边既约Hessian矩阵投影,将问题分解成零空间和值空间两个信赖域子问题.零空间的子问题为通常二次目标函数只带椭球约束的信赖域子问题,而值空间的子问题使用满足信赖域约束参数的值空间投影向量方向.通过引入Fletcher罚函数作为势函数,将由两个子问题结合信赖域策略构成的合成方向,并使用非单调线搜索技术回代于可接受的非负约束内点步长.在合理的条件下,算法具有整体收敛性且两块校正的双边既约Hessian投影法将保持超线性收敛速率.非单调技术将克服高度非线性情况,加快收敛进展.     

仿射内点既约投影Hessian算法解非线性约束优化

本文结合非单调内点回代技术,提供了新的仿射信赖域方法解含有非负变量约束和非线性等式约束的优化问题.为求解大规模问题,采用等式约束的Jacobian矩阵的QR分解和两块校正的双边既约Hessian矩阵投影,将问题分解成零空间和值空间两个信赖域子问题.零空间的子问题为通常二次目标函数只带椭球约束的信赖域子问题,而值空间的子问题使用满足信赖域约束参数的值空间投影向量方向.通过引入Fletcher罚函数作为势函数,将由两个子问题结合信赖域策略构成的合成方向,并使用非单调线搜索技术回代于可接受的非负约束内点步长.在合理的条件下,算法具有整体收敛性且两块校正的双边既约Hessian投影法将保持超线性收敛速率.非单调技术将克服高度非线性情况,加快收敛进展.     

等式约束优化非单调信赖域算法

设计了一个新的求解等式约束优化问题的非单调信赖域算法.该算法不需要罚函数也无需滤子.在每次迭代过程中只需求解满足下降条件的拟法向步及切向步.新算法产生的迭代步比滤子方法更易接受,计算量比单调算法小.在一般条件下,算法具有全局收敛性.     

带非线性不等式约束优化问题的信赖域算法

借助于KKT条件和NCP函数,提出了求解带非线性不等式约束优化问题的信赖域算法.该算法在每一步迭代时,不必求解带信赖域界的二次规划子问题,仅需求一线性方程组系统.在适当的假设条件下,它还是整体收敛的和局部超线性收敛的.数值实验结果表明该方法是有效的.     

一种约束非光滑优化问题的信赖域算法

提出了一种易实施的求解带线性约束的非光滑优化问题的信赖域算法，并在一定的条件下证明了该算法所产生的迭代序列的任何聚点都是原问题的稳定点．有限的数值例子表明，该方法是行之有效的．     

一类优化问题的非单调信赖域算法

本文提出了一类带不等式约束和简单边界的非线性优化问题的非单调信赖域算法,在一定的条件下,证明了算法的全局收敛性,并通过数值实验验证了算法的合理性。     

张量方法在信赖域算法中的应用

信赖域算法是求解无约束优化问题的一种有效的算法.对于该算法的子问题,本文将原来目标函数的二次模型扩展成四次张量模型,提出了一个带信赖域约束的四次张量模型优化问题的求解算法.该方法的最大特点是:不仅在张量模型的非稳定点可以得到下降方向及相应的迭代步长,而且在非局部极小值点的稳定点也可以得到下降方向及相应的迭代步长,从而在算法产生的迭代点列中存在一个子列收敛到信赖域子问题的局部极小值点.     

求解非光滑凸规划的一种混合束方法

提出一种求解非光滑凸规划问题的混合束方法. 该方法通过对目标函数增加迫近项, 且对可行域增加信赖域约束进行迭代, 做为迫近束方法与信赖域束方法的有机结合, 混合束方法自动在二者之间切换, 收敛性分析表明该方法具有全局收敛性. 最后的数值算例验证了算法的有效性．     

线性不等式约束的广义非线性互补问题的仿射内点信赖域方法

提供了一种新的非单调内点回代线搜索技术的仿射内点信赖域方法解线性不等式约束的广义非线性互补问题(GCP).基于广义互补问题构成的半光滑方程组的广义Jacobian矩阵,算法使用l_2范数作为半光滑方程组的势函数,形成的信赖域子问题为一个带椭球约束的线性化的二次模型.利用广义牛顿方程计算试探迭代步,通过内点映射回代技术确保迭代点是严格内点,保证了算法的整体收敛性.在合理的条件下,证明了信赖域算法在接近最优点时可转化为广义拟牛顿步,进而具有局部超线性收敛速率.非单调技术将克服高度非线性情况加速收敛进展.最后,数值结果表明了算法的有效性.     

A New Nonmonotonic Trust Region Algorithm for A Class of Unconstrained Nonsmooth Optimization

This paper presents a new trust region algorithm for solving a class of composite nonsmooth optimizations. It is distinguished by the fact that this method does not enforce strict monotonicity of the objective function values at successive iterates and that this method extends the existing results for this type of nonlinear optimization with smooth, or piecewise smooth, or convex objective functions or their composition. It is proved that this algorithm is globally convergent under certain conditions. Finally, some numerical results for several optimization problems are reported which show that the nonmonotonic trust region method is competitive with the usual trust region method.     

A New Nonmonotonic Trust Region Algorithm for A Class of Unconstraied Nonsmooth Optimization

This paper preasents a new trust region algorithm for solving a class of composite nonsmooth optimizations.It is distinguished by the fact that this method does not enforce strict monotonicity of the objective function values at successive itereates and that this method extends the existing results for this type of nonlinear optimization with smooth ,or piecewis somooth,or convex objective functions or their composition It is pyoved that this algorithm is globally convergent under certain conditions.Finally,some numerical results for several optimization problems are reported which show that the nonmonotonic trust region method is competitive with the usual trust region method.     

Inexact proximal stochastic gradient method for convex composite optimization

We study an inexact proximal stochastic gradient (IPSG) method for convex composite optimization, whose objective function is a summation of an average of a large number of smooth convex functions and a convex, but possibly nonsmooth, function. Variance reduction techniques are incorporated in the method to reduce the stochastic gradient variance. The main feature of this IPSG algorithm is to allow solving the proximal subproblems inexactly while still keeping the global convergence with desirable complexity bounds. Different subproblem stopping criteria are proposed. Global convergence and the component gradient complexity bounds are derived for the both cases when the objective function is strongly convex or just generally convex. Preliminary numerical experiment shows the overall efficiency of the IPSG algorithm.     

On the convergence rate of a forward-backward type primal-dual splitting algorithm for convex optimization problems

In this paper, we analyse the convergence rate of the sequence of objective function values of a primal-dual proximal-point algorithm recently introduced in the literature for solving a primal convex optimization problem having as objective the sum of linearly composed infimal convolutions, nonsmooth and smooth convex functions and its Fenchel-type dual one. The theoretical part is illustrated by numerical experiments in image processing.     

Compositions of convex functions and fully linear models

Derivative-free optimization (DFO) is the mathematical study of the optimization algorithms that do not use derivatives. One branch of DFO focuses on model-based DFO methods, where an approximation of the objective function is used to guide the optimization algorithm. Proving convergence of such methods often applies an assumption that the approximations form fully linear models—an assumption that requires the true objective function to be smooth. However, some recent methods have loosened this assumption and instead worked with functions that are compositions of smooth functions with simple convex functions (the max-function or the \(\ell _1\) norm). In this paper, we examine the error bounds resulting from the composition of a convex lower semi-continuous function with a smooth vector-valued function when it is possible to provide fully linear models for each component of the vector-valued function. We derive error bounds for the resulting function values and subgradient vectors.     

Optimal subgradient algorithms for large-scale convex optimization in simple domains

This paper describes two optimal subgradient algorithms for solving structured large-scale convex constrained optimization. More specifically, the first algorithm is optimal for smooth problems with Lipschitz continuous gradients and for Lipschitz continuous nonsmooth problems, and the second algorithm is optimal for Lipschitz continuous nonsmooth problems. In addition, we consider two classes of problems: (i) a convex objective with a simple closed convex domain, where the orthogonal projection onto this feasible domain is efficiently available; and (ii) a convex objective with a simple convex functional constraint. If we equip our algorithms with an appropriate prox-function, then the associated subproblem can be solved either in a closed form or by a simple iterative scheme, which is especially important for large-scale problems. We report numerical results for some applications to show the efficiency of the proposed schemes.     

A Fast Space-decomposition Scheme for Nonconvex Eigenvalue Optimization

In this paper, a nonsmooth bundle algorithm to minimize the maximum eigenvalue function of a nonconvex smooth function is presented. The bundle method uses an oracle to compute separately the function and subgradient information for a convex function, and the function and derivative values for the smooth mapping. Using this information, in each iteration, we replace the smooth inner mapping by its Taylor-series linearization around the current serious step. To solve the convex approximate eigenvalue problem with affine mapping faster, we adopt the second-order bundle method based on ????-decomposition theory. Through the backtracking test, we can make a better approximation for the objective function. Quadratic convergence of our special bundle method is given, under some additional assumptions. Then we apply our method to some particular instance of nonconvex eigenvalue optimization, specifically: bilinear matrix inequality problems.     

Gradient-type penalty method with inertial effects for solving constrained convex optimization problems with smooth data

We consider the problem of minimizing a smooth convex objective function subject to the set of minima of another differentiable convex function. In order to solve this problem, we propose an algorithm which combines the gradient method with a penalization technique. Moreover, we insert in our algorithm an inertial term, which is able to take advantage of the history of the iterates. We show weak convergence of the generated sequence of iterates to an optimal solution of the optimization problem, provided a condition expressed via the Fenchel conjugate of the constraint function is fulfilled. We also prove convergence for the objective function values to the optimal objective value. The convergence analysis carried out in this paper relies on the celebrated Opial Lemma and generalized Fejér monotonicity techniques. We illustrate the functionality of the method via a numerical experiment addressing image classification via support vector machines.     

An optimal method for stochastic composite optimization

This paper considers an important class of convex programming (CP) problems, namely, the stochastic composite optimization (SCO), whose objective function is given by the summation of general nonsmooth and smooth stochastic components. Since SCO covers non-smooth, smooth and stochastic CP as certain special cases, a valid lower bound on the rate of convergence for solving these problems is known from the classic complexity theory of convex programming. Note however that the optimization algorithms that can achieve this lower bound had never been developed. In this paper, we show that the simple mirror-descent stochastic approximation method exhibits the best-known rate of convergence for solving these problems. Our major contribution is to introduce the accelerated stochastic approximation (AC-SA) algorithm based on Nesterov’s optimal method for smooth CP (Nesterov in Doklady AN SSSR 269:543–547, 1983; Nesterov in Math Program 103:127–152, 2005), and show that the AC-SA algorithm can achieve the aforementioned lower bound on the rate of convergence for SCO. To the best of our knowledge, it is also the first universally optimal algorithm in the literature for solving non-smooth, smooth and stochastic CP problems. We illustrate the significant advantages of the AC-SA algorithm over existing methods in the context of solving a special but broad class of stochastic programming problems.     

Barrier method in nonsmooth convex optimization without convex representation

In this article we want to demonstrate that under mild conditions the barrier method is an effective solution approach for convex optimization problems whose objective is nonsmooth and whose feasible set is described by smooth inequality constraints in which all the constraint functions need not be convex.