Acceleration Tools for Diagonal Information Global Optimization Algorithms

In this paper we face a classical global optimization problem—minimization of a multiextremal multidimensional Lipschitz function over a hyperinterval. We introduce two new diagonal global optimization algorithms unifying the power of the following three approaches: efficient univariate information global optimization methods, diagonal approach for generalizing univariate algorithms to the multidimensional case, and local tuning on the behaviour of the objective function (estimates of the local Lipschitz constants over different subregions) during the global search. Global convergence conditions of a new type are established for the diagonal information methods. The new algorithms demonstrate quite satisfactory performance in comparison with the diagonal methods using only global information about the Lipschitz constant.     

Banach空间集值映射的度量正则性与变分方程的Lipschitz稳定性

综述了集值映射的某些概念,例如度量正则性、伪Lipschitz性质(Aubin性质)、度量次正则性和Calm性质和这些概念的相互关系以及某些判据.也给出了他们在变分方程解的鲁棒Lipschitz稳定性、约束优化问题的最优性条件、集合族的线性正则性质和广义方程迭代过程的收敛性.     

Supercalm Multifunctions For Convergence Analysis

Calmness of multifunctions is a well-studied concept of generalized continuity in which single-valued selections from the image sets of the multifunction exhibit a restricted type of local Lipschitz continuity where the base point is fixed as one point of comparison. Generalized continuity properties of multifunctions like calmness can be applied to convergence analysis when the multifunction appropriately represents the iterates generated by some algorithm. Since it involves an essentially linear relationship between input and output, calmness gives essentially linear convergence results when it is applied directly to convergence analysis. We introduce a new continuity concept called ‘supercalmness’ where arbitrarily small calmness constants can be obtained near the base point, which leads to essentially superlinear convergence results. We also explore partial supercalmness and use a well-known generalized derivative to characterize both when a multifunction is supercalm and when it is partially supercalm. To illustrate the value of such characterizations, we explore in detail a new example of a general primal sequential quadratic programming method for nonlinear programming and obtain verifiable conditions to ensure convergence at a superlinear rate.     

On constraint qualifications in terms of approximate Jacobians for nonsmooth continuous optimization problems

Constraint qualifications in terms of approximate Jacobians are investigated for a nonsmooth constrained optimization problem, in which the involved functions are continuous but not necessarily locally Lipschitz. New constraint qualifications in terms of approximate Jacobians, weaker than the generalized Robinson constraint qualification (GRCQ) in Jeyakumar and Yen [V. Jeyakumar, N.D. Yen, Solution stability of nonsmooth continuous systems with applications to cone-constrained optimization, SIAM J. Optim. 14 5 (2004) 1106-1127], are introduced and some examples are provided to show the utility of constrained qualifications introduced. Since the calmness condition is regarded as the basic condition for optimality conditions, the relationships between the constraint qualifications proposed and the calmness of solution mapping are also studied.     

Optimal algorithms for global optimization in case of unknown Lipschitz constant

We consider the global optimization problem for d-variate Lipschitz functions which, in a certain sense, do not increase too slowly in a neighborhood of the global minimizer(s). On these functions, we apply optimization algorithms which use only function values. We propose two adaptive deterministic methods. The first one applies in a situation when the Lipschitz constant L is known. The second one applies if L is unknown. We show that for an optimal method, adaptiveness is necessary and that randomization (Monte Carlo) yields no further advantage. Both algorithms presented have the optimal rate of convergence.     

复合凸优化的快速邻近点算法

在大数据时代,随着数据采集手段的不断提升,大规模复合凸优化问题大量的出现在包括统计数据分析,机器与统计学习以及信号与图像处理等应用中.本文针对大规模复合凸优化问题介绍了一类快速邻近点算法.在易计算的近似准则和较弱的平稳性条件下,本文给出了该算法的全局收敛与局部渐近超线性收敛结果.同时,我们设计了基于对偶原理的半光滑牛顿法来高效稳定求解邻近点算法所涉及的重要子问题.最后,本文还讨论了如何通过深入挖掘并利用复合凸优化问题中由非光滑正则函数所诱导的非光滑二阶信息来极大减少半光滑牛顿算法中求解牛顿线性系统所需的工作量,从而进一步加速邻近点算法.     

Tight global linear convergence rate bounds for Douglas–Rachford splitting

Recently, several authors have shown local and global convergence rate results for Douglas–Rachford splitting under strong monotonicity, Lipschitz continuity, and cocoercivity assumptions. Most of these focus on the convex optimization setting. In the more general monotone inclusion setting, Lions and Mercier showed a linear convergence rate bound under the assumption that one of the two operators is strongly monotone and Lipschitz continuous. We show that this bound is not tight, meaning that no problem from the considered class converges exactly with that rate. In this paper, we present tight global linear convergence rate bounds for that class of problems. We also provide tight linear convergence rate bounds under the assumptions that one of the operators is strongly monotone and cocoercive, and that one of the operators is strongly monotone and the other is cocoercive. All our linear convergence results are obtained by proving the stronger property that the Douglas–Rachford operator is contractive.     

Optimization methods for Dirichlet control problems

We discuss several optimization procedures to solve finite element approximations of linear-quadratic Dirichlet optimal control problems governed by an elliptic partial differential equation posed on a 2D or 3D Lipschitz domain. The control is discretized explicitly using continuous piecewise linear approximations. Unconstrained, control-constrained, state-constrained and control-and-state constrained problems are analysed. A preconditioned conjugate method for a reduced problem in the control variable is proposed to solve the unconstrained problem, whereas semismooth Newton methods are discussed for the solution of constrained problems. State constraints are treated via a Moreau–Yosida penalization. Convergence is studied for both the continuous problems and the finite dimensional approximations. In the finite dimensional case, we are able to show convergence of the optimization procedures even in the absence of Tikhonov regularization parameter. Computational aspects are also treated and several numerical examples are included to illustrate the theoretical results.     

Parametric Method for Global Optimization

This paper considers constrained and unconstrained parametric global optimization problems in a real Hilbert space. We assume that the gradient of the cost functional is Lipschitz continuous but not smooth. A suitable choice of parameters implies the linear or superlinear (supergeometric) convergence of the iterative method. From the numerical experiments, we conclude that our algorithm is faster than other existing algorithms for continuous but nonsmooth problems, when applied to unconstrained global optimization problems. However, because we solve 2n + 1 subproblems for a large number n of independent variables, our algorithm is somewhat slower than other algorithms, when applied to constrained global optimization.This work was partially supported by the NATO Outreach Fellowship - Mathematics 219.33.We thank Professor Hans D. Mittelmann, Arizona State University, for cooperation and support.     

Golden ratio algorithms with new stepsize rules for variational inequalities

In this paper, we introduce two golden ratio algorithms with new stepsize rules for solving pseudomonotone and Lipschitz variational inequalities in finite dimensional Hilbert spaces. The presented stepsize rules allow the resulting algorithms to work without the prior knowledge of the Lipschitz constant of operator. The first algorithm uses a sequence of stepsizes that is previously chosen, diminishing, and nonsummable, while the stepsizes in the second one are updated at each iteration and by a simple computation. A special point is that the sequence of stepsizes generated by the second algorithm is separated from zero. The convergence and the convergence rate of the proposed algorithms are established under some standard conditions. Also, we give several numerical results to show the behavior of the algorithms in comparison with other algorithms.     

Weakly upper Lipschitz multifunctions and applications in parametric optimization

The main purpose of this paper is to report on our studies of the weak upper Lipschitz and weak -upper Lipschitz continuities of multifunctions. Comparisons with other related Lipschitz-type continuities and calmness are given. When the concept of the weak upper Lipschitz continuities is applied to the special cases of constraint multifunctions, such as ones defined by a systems of equalities and inequalities or by a generalized equation we obtain the equivalent conditions with linear functional error bounds. Some results on the perturbation and penalty issues in parametric optimization problems are obtained under weak upper Lipschitz continuity assumptions on the constraint multifunctions. We also discuss the weak -upper Lipschitz continuity of a inverse subdifferential.Mathematics Subject Classification (2000): 49J52, 49J53, 90C25Acknowledgement The author thanks the associate editor and the referees for their helpful suggestions and comments.     

Finding the Minimal Root of an Equation with the Multiextremal and Nondifferentiable Left-Hand Part

A problem very often arising in applications is presented: finding the minimal root of an equation with the objective function being multiextremal and nondifferentiable. Applications from the field of electronic measurements are given. Three methods based on global optimization ideas are introduced for solving this problem. The first one uses an a priori estimate of the global Lipschitz constant. The second method adaptively estimates the global Lipschitz constant. The third algorithm adaptively estimates local Lipschitz constants during the search. All the methods either find the minimal root or determine the global minimizers (in the case when the equation under consideration has no roots). Sufficient convergence conditions of the new methods to the desired solution are established. Numerical results including wide experiments with test functions, stability study, and a real-life applied problem are also presented.     

Two differential equation systems for equality-constrained optimization

This paper presents two differential systems, involving first and second order derivatives of problem functions, respectively, for solving equality-constrained optimization problems. Local minimizers to the optimization problems are proved to be asymptotically stable equilibrium points of the two differential systems. First, the Euler discrete schemes with constant stepsizes for the two differential systems are presented and their convergence theorems are demonstrated. Second, we construct algorithms in which directions are computed by these two systems and the stepsizes are generated by Armijo line search to solve the original equality-constrained optimization problem. The constructed algorithms and the Runge–Kutta method are employed to solve the Euler discrete schemes and the differential equation systems, respectively. We prove that the discrete scheme based on the differential equation system with the second order information has the locally quadratic convergence rate under the local Lipschitz condition. The numerical results given here show that Runge–Kutta method has better stability and higher precision and the numerical method based on the differential equation system with the second information is faster than the other one.     

Modified nonmonotone Armijo line search for descent method

Nonmonotone line search approach is a new technique for solving optimization problems. It relaxes the line search range and finds a larger step-size at each iteration, so as to possibly avoid local minimizer and run away from narrow curved valley. It is helpful to find the global minimizer of optimization problems. In this paper we develop a new modification of matrix-free nonmonotone Armijo line search and analyze the global convergence and convergence rate of the resulting method. We also address several approaches to estimate the Lipschitz constant of the gradient of objective functions that would be used in line search algorithms. Numerical results show that this new modification of Armijo line search is efficient for solving large scale unconstrained optimization problems.     

Modified subgradient extragradient algorithms for solving monotone variational inequalities

ABSTRACT

In this paper, we introduce two new algorithms for solving classical variational inequalities problem with Lipschitz continuous and monotone mapping in real Hilbert space. We modify the subgradient extragradient methods with a new step size, the convergence of algorithms are established without the knowledge of the Lipschitz constant of the mapping. Finally, some numerical experiments are presented to show the efficiency and advantage of the proposed algorithms.     

Some projection methods with the BB step sizes for variational inequalities

Since the appearance of the Barzilai-Borwein (BB) step sizes strategy for unconstrained optimization problems, it received more and more attention of the researchers. It was applied in various fields of the nonlinear optimization problems and recently was also extended to optimization problems with bound constraints. In this paper, we further extend the BB step sizes to more general variational inequality (VI) problems, i.e., we adopt them in projection methods. Under the condition that the underlying mapping of the VI problem is strongly monotone and Lipschitz continuous and the modulus of strong monotonicity and the Lipschitz constant satisfy some further conditions, we establish the global convergence of the projection methods with BB step sizes. A series of numerical examples are presented, which demonstrate that the proposed methods are convergent under mild conditions, and are more efficient than some classical projection-like methods.     

集值映射向量优化问题的锥弱有效解的镇定性和稳定性(英文)

本文研究了集值映射向量优化问题的锥弱有效解的镇定性和稳定性,我们引进了集值映射向量优化问题的镇定性和稳定性的定义,并证明了集值映射向量优化问题的镇定性和稳定性的一些主要定理.     

Numerical methods for nonlinear stochastic differential equations with jumps

We present and analyse two implicit methods for Ito stochastic differential equations (SDEs) with Poisson-driven jumps. The first method, SSBE, is a split-step extension of the backward Euler method. The second method, CSSBE, arises from the introduction of a compensated, martingale, form of the Poisson process. We show that both methods are amenable to rigorous analysis when a one-sided Lipschitz condition, rather than a more restrictive global Lipschitz condition, holds for the drift. Our analysis covers strong convergence and nonlinear stability. We prove that both methods give strong convergence when the drift coefficient is one-sided Lipschitz and the diffusion and jump coefficients are globally Lipschitz. On the way to proving these results, we show that a compensated form of the Euler–Maruyama method converges strongly when the SDE coefficients satisfy a local Lipschitz condition and the pth moment of the exact and numerical solution are bounded for some p>2. Under our assumptions, both SSBE and CSSBE give well-defined, unique solutions for sufficiently small stepsizes, and SSBE has the advantage that the restriction is independent of the jump intensity. We also study the ability of the methods to reproduce exponential mean-square stability in the case where the drift has a negative one-sided Lipschitz constant. This work extends the deterministic nonlinear stability theory in numerical analysis. We find that SSBE preserves stability under a stepsize constraint that is independent of the initial data. CSSBE satisfies an even stronger condition, and gives a generalization of B-stability. Finally, we specialize to a linear test problem and show that CSSBE has a natural extension of deterministic A-stability. The difference in stability properties of the SSBE and CSSBE methods emphasizes that the addition of a jump term has a significant effect that cannot be deduced directly from the non-jump literature.This work was supported by Engineering and Physical Sciences Research Council grant GR/T19100 and by a Research Fellowship from The Royal Society of Edinburgh/Scottish Executive Education and Lifelong Learning Department.     

Some Remarks on the Convex Feasibility Problem and Best Approximation Problem

In this paper we investigate several solution algorithms for the convex fea- sibility problem(CFP)and the best approximation problem(BAP)respectively.The algorithms analyzed are already known before,but by adequately reformulating the CFP or the BAP we naturally deduce the general projection method for the CFP from well-known steepest decent method for unconstrained optimization and we also give a natural strategy of updating weight parameters.In the linear case we show the connec- tion of the two projection algorithms for the CFP and the BAP respectively.In addition, we establish the convergence of a method for the BAP under milder assumptions in the linear case.We also show by examples a Bauschke's conjecture is only partially correct.     

一类超线性收敛的广义拟Newton算法

１引言考虑无约束最优化问题其中目标函数ｆ（ｘ）二阶连续可微,记ｆｋ＝ｆ（ｘ）,当充分小时,有如下近似关系：它们对二次函数皆严格成立．考虑选代其中Ｂ（Ｇ的近似）已知,为某种线搜索确定的步长．对Ｂ修正产生Ｂ,即Ｕ为待定ｎ阶矩阵．若要求Ｂ＋满足关系即Ｂ满足拟Ｎｅｗｔｏｎ方程,由它可导出许多著名的拟Ｎｅｗｔｏｎ算法［１－［４］）．若要求Ｂ满足关系则可导出伪Ｎｅｗｔｏｎ－δ族校正公式,它不再是Ｈｕａｎｇ族成员［６］．从信息资源的利用看,（１．６）仅利用了与信息,（１．７）仅利用了与信息．一般而言,较多的信…