Limited memory discrete gradient bundle method for nonsmooth derivative-free optimization

Typically, practical nonsmooth optimization problems involve functions with hundreds of variables. Moreover, there are many practical problems where the computation of even one subgradient is either a difficult or an impossible task. In such cases derivative-free methods are the better (or only) choice since they do not use explicit computation of subgradients. However, these methods require a large number of function evaluations even for moderately large problems. In this article, we propose an efficient derivative-free limited memory discrete gradient bundle method for nonsmooth, possibly nonconvex optimization. The convergence of the proposed method is proved for locally Lipschitz continuous functions and the numerical experiments to be presented confirm the usability of the method especially for medium size and large-scale problems.     

A Geometric Integration Approach to Nonsmooth,Nonconvex Optimisation

The optimisation of nonsmooth, nonconvex functions without access to gradients is a particularly challenging problem that is frequently encountered, for example in model parameter optimisation problems. Bilevel optimisation of parameters is a standard setting in areas such as variational regularisation problems and supervised machine learning. We present efficient and robust derivative-free methods called randomised Itoh–Abe methods. These are generalisations of the Itoh–Abe discrete gradient method, a well-known scheme from geometric integration, which has previously only been considered in the smooth setting. We demonstrate that the method and its favourable energy dissipation properties are well defined in the nonsmooth setting. Furthermore, we prove that whenever the objective function is locally Lipschitz continuous, the iterates almost surely converge to a connected set of Clarke stationary points. We present an implementation of the methods, and apply it to various test problems. The numerical results indicate that the randomised Itoh–Abe methods can be superior to state-of-the-art derivative-free optimisation methods in solving nonsmooth problems while still remaining competitive in terms of efficiency.

     

An Inexact PRP Conjugate Gradient Method for Symmetric Nonlinear Equations

In this article, without computing exact gradient and Jacobian, we proposed a derivative-free Polak-Ribière-Polyak (PRP) method for solving nonlinear equations whose Jacobian is symmetric. This method is a generalization of the classical PRP method for unconstrained optimization problems. By utilizing the symmetric structure of the system sufficiently, we prove global convergence of the proposed method with some backtracking type line search under suitable assumptions. Moreover, we extend the proposed method to nonsmooth equations by adopting the smoothing technique. We also report some numerical results to show its efficiency.     

Canonical Dual Transformation Method and Generalized Triality Theory in Nonsmooth Global Optimization*

This paper presents, within a unified framework, a potentially powerful canonical dual transformation method and associated generalized duality theory in nonsmooth global optimization. It is shown that by the use of this method, many nonsmooth/nonconvex constrained primal problems in ⁿ can be reformulated into certain smooth/convex unconstrained dual problems in ^m with m n and without duality gap, and some NP-hard concave minimization problems can be transformed into unconstrained convex minimization dual problems. The extended Lagrange duality principles proposed recently in finite deformation theory are generalized suitable for solving a large class of nonconvex and nonsmooth problems. The very interesting generalized triality theory can be used to establish nice theoretical results and to develop efficient alternative algorithms for robust computations.     

Lagrangian bounds in multiextremal polynomial and discrete optimization problems

Many polynomial and discrete optimization problems can be reduced to multiextremal quadratic type models of nonlinear programming. For solving these problems one may use Lagrangian bounds in combination with branch and bound techniques. The Lagrangian bounds may be improved for some important examples by adding in a model the so-called superfluous quadratic constraints which modify Lagrangian bounds. Problems of finding Lagrangian bounds as a rule can be reduced to minimization of nonsmooth convex functions and may be successively solved by modern methods of nondifferentiable optimization. This approach is illustrated by examples of solving polynomial-type problems and some discrete optimization problems on graphs.     

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.     

Diagonal discrete gradient bundle method for derivative free nonsmooth optimization

Typically, practical nonsmooth optimization problems involve functions with hundreds of variables. Moreover, there are many practical problems where the computation of even one subgradient is either a difficult or an impossible task. In such cases, the usual subgradient-based optimization methods cannot be used. However, the derivative free methods are applicable since they do not use explicit computation of subgradients. In this paper, we propose an efficient diagonal discrete gradient bundle method for derivative-free, possibly nonconvex, nonsmooth minimization. The convergence of the proposed method is proved for semismooth functions, which are not necessarily differentiable or convex. The method is implemented using Fortran 95, and the numerical experiments confirm the usability and efficiency of the method especially in case of large-scale problems.     

A Globally Derivative-Free Descent Method for Nonlinear Complementarity Problems

Based on a class of functions, which generalize the squared Fischer-Burmeister NCP function and have many desirable properties as the latter function has, we reformulate nonlinear complementarity problem (NCP for short) as an equivalent unconstrained optimization problem, for which we propose a derivative-free descent method in monotone case. We show its global convergence under some mild conditions. If $F$, the function involved in NCP, is $R_0$-function, the optimization problems has bounded level sets. A local property of the merit function is discussed. Finally,we report some numerical results.     

Derivative free optimization methods for optimizing stirrer configurations

In this paper a numerical approach for the optimization of stirrer configurations is presented. The methodology is based on a flow solver, and a mathematical optimization tool, which are integrated into an automated procedure. The flow solver is based on the discretization of the incompressible Navier–Stokes equations by means of a fully conservative finite-volume method for block-structured, boundary-fitted grids, for allowing a flexible discretization of complex stirrer geometries. Two derivative free optimization algorithms, the DFO and CONDOR are considered, they are implementations of trust region based derivative-free methods using multivariate polynomial interpolation. Both are designed to minimize smooth functions whose evaluations are considered to be expensive and whose derivatives are not available or not desirable to approximate. An exemplary application for a standard stirrer configuration illustrates the functionality and the properties of the proposed methods. It also gives a comparison of the two optimization algorithms.     

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.     

Criteria for efficiency in vector optimization

We consider unconstrained finite dimensional multi-criteria optimization problems, where the objective functions are continuously differentiable. Motivated by previous work of Brosowski and da Silva (1994), we suggest a number of tests (TEST 1–4) to detect, whether a certain point is a locally (weakly) efficient solution for the underlying vector optimization problem or not. Our aim is to show: the points, at which none of the TESTs 1–4 can be applied, form a nowhere dense set in the state space. TESTs 1 and 2 are exactly those proposed by Brosowski and da Silva. TEST 3 deals with a local constant behavior of at least one of the objective functions. TEST 4 includes some conditions on the gradients of objective functions satisfied locally around the point of interest. It is formulated as a Conjecture. It is proven under additional assumptions on the objective functions, such as linear independence of the gradients, convexity or directional monotonicity. This work was partially supported by grant 55681 of the CONACyT.     

On the Behavior of the Gradient Norm in the Steepest Descent Method

It is well known that the norm of the gradient may be unreliable as a stopping test in unconstrained optimization, and that it often exhibits oscillations in the course of the optimization. In this paper we present results descibing the properties of the gradient norm for the steepest descent method applied to quadratic objective functions. We also make some general observations that apply to nonlinear problems, relating the gradient norm, the objective function value, and the path generated by the iterates.     

A superlinear space decomposition algorithm for constrained nonsmooth convex program

A class of constrained nonsmooth convex optimization problems, that is, piecewise C² convex objectives with smooth convex inequality constraints are transformed into unconstrained nonsmooth convex programs with the help of exact penalty function. The objective functions of these unconstrained programs are particular cases of functions with primal-dual gradient structure which has connection with VU space decomposition. Then a VU space decomposition method for solving this unconstrained program is presented. This method is proved to converge with local superlinear rate under certain assumptions. An illustrative example is given to show how this method works.     

On the generalization of ECP and OA methods to nonsmooth convex MINLP problems

In this article, generalization of some mixed-integer nonlinear programming algorithms to cover convex nonsmooth problems is studied. In the extended cutting plane method, gradients are replaced by the subgradients of the convex function and the resulting algorithm shall be proved to converge to a global optimum. It is shown through a counterexample that this type of generalization is insufficient with certain versions of the outer approximation algorithm. However, with some modifications to the outer approximation method a special type of nonsmooth functions for which the subdifferential at any point is a convex combination of a finite number of subgradients at the point can be considered. Numerical results with extended cutting plane method are also reported.     

一个新的无约束优化超记忆梯度算法

本文提出一种新的无约束优化超记忆梯度算法,算法利用当前点的负梯度和前一点的负梯度的线性组合为搜索方向,以精确线性搜索和Armijo搜索确定步长．在很弱的条件下证明了算法具有全局收敛性和线性收敛速度．因算法中避免了存贮和计算与目标函数相关的矩阵,故适于求解大型无约束优化问题．数值实验表明算法比一般的共轭梯度算法有效．     

半定优化与半光滑牛顿算法

本文讨论半光滑牛顿算法的基本概念与其在求解半定优化问题中的应用．特别地，该算法可用于求解线性或非线性半定互补问题．本文同时综述最近在矩阵方程，增广拉格朗日公式和半定优化稳定性方面的、源于半光滑牛顿算法的理论成果．     

A DIRECT SEARCH FRAME-BASED CONJUGATE GRADIENTS METHOD

A derivative-free frame-based conjugate gradients algorithm is presented.Convergenceis shown for C~1 functions,and this is verified in numerical trials.The algorithm is tested ona variety of low dimensional problems,some of which are ill-conditioned,and is also testedon problems of high dimension.Numerical results show that the algorithm is effectiveon both classes of problems.The results are compared with those from a discrete quasi-Newton method,showing that the conjugate gradients algorithm is competitive.Thealgorithm exhibits the conjugate gradients speed-up on problems for which the Hessian atthe solution has repeated or clustered eigenvalues.The algorithm is easily parallelizable.     

A unified approach to global convergence of trust region methods for nonsmooth optimization

This paper investigates the global convergence of trust region (TR) methods for solving nonsmooth minimization problems. For a class of nonsmooth objective functions called regular functions, conditions are found on the TR local models that imply three fundamental convergence properties. These conditions are shown to be satisfied by appropriate forms of Fletcher's TR method for solving constrained optimization problems, Powell and Yuan's TR method for solving nonlinear fitting problems, Zhang, Kim and Lasdon's successive linear programming method for solving constrained problems, Duff, Nocedal and Reid's TR method for solving systems of nonlinear equations, and El Hallabi and Tapia's TR method for solving systems of nonlinear equations. Thus our results can be viewed as a unified convergence theory for TR methods for nonsmooth problems.Research supported by AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Corresponding author.     

LC^1最优化问题的最优性条件

1 引言 LC~1最优化问题是一类非光滑最优化问题,它们广泛存在于运筹学的各种情形中.对于这些问题,其目标函数和约束函数一般不具有二阶可微性,但是它们是可微的,其导数是局部Lipschitz的.LC~1最优化问题的一般形式是 rminf(x) s.t.h_i(x)=0,i∈E,(1.1) g_i(x)≤0,j∈I, 其中,f:R~n→R,h:R~n→R~m,g:R~n→R~l是LC~1函数,即它们有局部Lipschitz导数,E={1,…,m},I={1,…,l}.从非线性互补问题、变分不等式和非线性规划中产生的不少问题可以形成 为非光滑方程,其中C~1条件(即连续可微条件)不成立,但LC条件(即局部Lipscchitz条件)成立,这些问题对应于LC~1最优化问题.[4],[6],[7]给出LC~1最优化问题的例子. 最优性条件对研究非光滑最优化是重要的.若干作者研究了非光滑优化的最优性条件问题,例如[1]、[2]、[4].在本文中我们将讨论LC~1最优化的最优性条件,它们包括:无约束LC~1最优化问题的二阶最优性条件和一般约束LC~1最优化问题的二阶最优性条件. 2 基本概念     

梯度法简述

梯度法是一类求解优化问题的一阶方法。梯度法形式简单、计算开销小,在大规模问题的求解中得到了广泛应用。系统地介绍了光滑无约束问题梯度法的迭代格式、理论框架。梯度法中最重要的参数是步长,步长的选取直接决定了梯度法的收敛性质与收敛速度。从线搜索框架、近似技巧、随机技巧和交替重复步长四方面介绍了梯度步长的构造思想及相应梯度法的收敛性结果,还对非光滑及约束问题的梯度法、梯度法加速技巧和随机梯度法等扩展方向做了简要介绍。