A Projected Subgradient Algorithm for Bilevel Equilibrium Problems and Applications

In this paper, we propose a new algorithm for solving a bilevel equilibrium problem in a real Hilbert space. In contrast to most other projection-type algorithms, which require to solve subproblems at each iteration, the subgradient method proposed in this paper requires only to calculate, at each iteration, two subgradients of convex functions and one projection onto a convex set. Hence, our algorithm has a low computational cost. We prove a strong convergence theorem for the proposed algorithm and apply it for solving the equilibrium problem over the fixed point set of a nonexpansive mapping. Some numerical experiments and comparisons are given to illustrate our results. Also, an application to Nash–Cournot equilibrium models of a semioligopolistic market is presented.     

An outer approximate subdifferential method for piecewise affine optimization

Piecewise affine functions arise from Lagrangian duals of integer programming problems, and optimizing them provides good bounds for use in a branch and bound method. Methods such as the subgradient method and bundle methods assume only one subgradient is available at each point, but in many situations there is more information available. We present a new method for optimizing such functions, which is related to steepest descent, but uses an outer approximation to the subdifferential to avoid some of the numerical problems with the steepest descent approach. We provide convergence results for a class of outer approximations, and then develop a practical algorithm using such an approximation for the compact dual to the linear programming relaxation of the uncapacitated facility location problem. We make a numerical comparison of our outer approximation method with the projection method of Conn and Cornuéjols, and the bundle method of Schramm and Zowe. Received September 10, 1998 / Revised version received August 1999?Published online December 15, 1999     

A class of convergent primal-dual subgradient algorithms for decomposable convex programs

In this paper we develop a primal-dual subgradient algorithm for preferably decomposable, generally nondifferentiable, convex programming problems, under usual regularity conditions. The algorithm employs a Lagrangian dual function along with a suitable penalty function which satisfies a specified set of properties, in order to generate a sequence of primal and dual iterates for which some subsequence converges to a pair of primal-dual optimal solutions. Several classical types of penalty functions are shown to satisfy these specified properties. A geometric convergence rate is established for the algorithm under some additional assumptions. This approach has three principal advantages. Firstly, both primal and dual solutions are available which prove to be useful in several contexts. Secondly, the choice of step sizes, which plays an important role in subgradient optimization, is guided more determinably in this method via primal and dual information. Thirdly, typical subgradient algorithms suffer from the lack of an appropriate stopping criterion, and so the quality of the solution obtained after a finite number of steps is usually unknown. In contrast, by using the primal-dual gap, the proposed algorithm possesses a natural stopping criterion.     

Extension of the Frank-Wolfe algorithm to concave nondifferentiable objective functions

In this paper, we provide the theoretical foundations of an extension of the Frank-Wolfe algorithm for concave continuously differentiable objective functions to concave nondifferentiable objective functions, using a subgradient approach. The main theorem extends the results of Frank and Wolfe. A key main assumption is examined in the context of some special cases via three lemmas. A comparison is made with other subgradient approaches, and consideration is given to the two subproblem optimizations arising in the modified algorithm.This work was carried out under the auspices of the University of Manchester, Manchester, England. The author thanks the referees for their very helpful comments on the original version.     

Strong convergence result for monotone variational inequalities

Our aim in this paper is to study strong convergence results for L-Lipschitz continuous monotone variational inequality but L is unknown using a combination of subgradient extra-gradient method and viscosity approximation method with adoption of Armijo-like step size rule in infinite dimensional real Hilbert spaces. Our results are obtained under mild conditions on the iterative parameters. We apply our result to nonlinear Hammerstein integral equations and finally provide some numerical experiments to illustrate our proposed algorithm.     

New subgradient extragradient methods for solving monotone bilevel equilibrium problems

ABSTRACT

In this paper, we propose new subgradient extragradient methods for finding a solution of a strongly monotone equilibrium problem over the solution set of another monotone equilibrium problem which usually is called monotone bilevel equilibrium problem in Hilbert spaces. The first proposed algorithm is based on the subgradient extragradient method presented by Censor et al. [Censor Y, Gibali A, Reich S. The subgradient extragradient method for solving variational inequalities in Hilbert space. J Optim Theory Appl. 2011;148:318–335]. The strong convergence of the algorithm is established under monotone assumptions of the cost bifunctions with Lipschitz-type continuous conditions recently presented by Mastroeni in the auxiliary problem principle. We also present a modification of the algorithm for solving an equilibrium problem, where the constraint domain is the common solution set of another equilibrium problem and a fixed point problem. Several fundamental experiments are provided to illustrate the numerical behaviour of the algorithms and to compare with others.     

手数约束和凹交易费下的离散投资组合模型及算法

本文建立带手数约束和凹交易费的离散投资组合模型,给出求解该模型的一种精确算法。该算法是一个基于拉格朗日松弛和次梯度对偶搜索的分枝定界算法。为测试算法的有效性,用随机产生的数据对模型进行数值实验。作为其应用,用沪深300指数的真实数据实证检验该模型,并与不含交易费用的离散投资组合模型进行数值比较分析。数值分析表明算法能在合理的时间内给出模型的投资组合策略, 对解决中小规模的离散投资组合问题是有效的。     

Modified subgradient extragradient method for variational inequality problems

In this paper, we introduce an algorithm as combination between the subgradient extragradient method and inertial method for solving variational inequality problems in Hilbert spaces. The weak convergence of the algorithm is established under standard assumptions imposed on cost operators. The proposed algorithm can be considered as an improvement of the previously known inertial extragradient method over each computational step. The performance of the proposed algorithm is also illustrated by several preliminary numerical experiments.     

An approximate bundle method for solving nonsmooth equilibrium problems

We present an approximate bundle method for solving nonsmooth equilibrium problems. An inexact cutting-plane linearization of the objective function is established at each iteration, which is actually an approximation produced by an oracle that gives inaccurate values for the functions and subgradients. The errors in function and subgradient evaluations are bounded and they need not vanish in the limit. A descent criterion adapting the setting of inexact oracles is put forward to measure the current descent behavior. The sequence generated by the algorithm converges to the approximately critical points of the equilibrium problem under proper assumptions. As a special illustration, the proposed algorithm is utilized to solve generalized variational inequality problems. The numerical experiments show that the algorithm is effective in solving nonsmooth equilibrium problems.     

Subgradient Method for Nonconvex Nonsmooth Optimization

In this paper, we introduce a new method for solving nonconvex nonsmooth optimization problems. It uses quasisecants, which are subgradients computed in some neighborhood of a point. The proposed method contains simple procedures for finding descent directions and for solving line search subproblems. The convergence of the method is studied and preliminary results of numerical experiments are presented. The comparison of the proposed method with the subgradient and the proximal bundle methods is demonstrated using results of numerical experiments.     

一种改进的随机次梯度方法的快速收敛性

1引言考虑如下优化问题: min f(x)=sum from i=1 to m f_i(x),s.t. x∈X (1)其中,f_i∶R~n→R是凸函数且f_i不可微,X是R~n上的非空闭凸子集．解(1)的主要方法     

Inexact subgradient methods for quasi-convex optimization problems

In this paper, we consider a generic inexact subgradient algorithm to solve a nondifferentiable quasi-convex constrained optimization problem. The inexactness stems from computation errors and noise, which come from practical considerations and applications. Assuming that the computational errors and noise are deterministic and bounded, we study the effect of the inexactness on the subgradient method when the constraint set is compact or the objective function has a set of generalized weak sharp minima. In both cases, using the constant and diminishing stepsize rules, we describe convergence results in both objective values and iterates, and finite convergence to approximate optimality. We also investigate efficiency estimates of iterates and apply the inexact subgradient algorithm to solve the Cobb–Douglas production efficiency problem. The numerical results verify our theoretical analysis and show the high efficiency of our proposed algorithm, especially for the large-scale problems.     

Cardinal functions for Legendre pseudo-spectral method for solving the integro-differential equations

In this article, we present a new numerical method to solve the integro-differential equations (IDEs). The proposed method uses the Legendre cardinal functions to express the approximate solution as a finite series. In our method the operational matrix of derivatives is used to reduce IDEs to a system of algebraic equations. To demonstrate the validity and applicability of the proposed method, we present some numerical examples. We compare the obtained numerical results from the proposed method with some other methods. The results show that the proposed algorithm is of high accuracy, more simple and effective.     

Strongly sub-feasible direction method for constrained optimization problems with nonsmooth objective functions

In this paper, we propose a strongly sub-feasible direction method for the solution of inequality constrained optimization problems whose objective functions are not necessarily differentiable. The algorithm combines the subgradient aggregation technique with the ideas of generalized cutting plane method and of strongly sub-feasible direction method, and as results a new search direction finding subproblem and a new line search strategy are presented. The algorithm can not only accept infeasible starting points but also preserve the “strong sub-feasibility” of the current iteration without unduly increasing the objective value. Moreover, once a feasible iterate occurs, it becomes automatically a feasible descent algorithm. Global convergence is proved, and some preliminary numerical results show that the proposed algorithm is efficient.     

Optimization of upper semidifferentiable functions

In this paper, we present an implementable algorithm to minimize a nonconvex, nondifferentiable function in ^m . The method generalizes Wolfe's algorithm for convex functions and Mifflin's algorithm for semismooth functions to a broader class of functions, so-called upper semidifferentiable. With this objective, we define a new enlargement of Clarke's generalized gradient that recovers, in special cases, the enlargement proposed by Goldstein. We analyze the convergence of the method and discuss some numerical experiments.The author would like to thank J. B. Hiriart-Urruty (Toulouse) for having provided him with Definition 2.1 and the referees for their constructive remarks about a first version of the paper.     

A weighting subgradient algorithm for multiobjective optimization

We propose a weighting subgradient algorithm for solving multiobjective minimization problems on a nonempty closed convex subset of an Euclidean space. This method combines weighting technique and the classical projected subgradient method, using a divergent series steplength rule. Under the assumption of convexity, we show that the sequence generated by this method converges to a Pareto optimal point of the problem. Some numerical results are presented.     

On the numerical solution of second order ordinary differential equations in the high-frequency regime

We describe an algorithm for the numerical solution of second order linear ordinary differential equations in the high-frequency regime. It is based on the recent observation that solutions of equations of this type can be accurately represented using nonoscillatory phase functions. Unlike standard solvers for ordinary differential equations, the running time of our algorithm is independent of the frequency of oscillation of the solutions. We illustrate this and other properties of the method with several numerical experiments.     

A method for convex minimization based on translated first-order approximations

We describe an algorithm for minimizing convex, not necessarily smooth, functions of several variables, based on a descent direction finding procedure that inherits some characteristics both of standard bundle method and of Wolfe’s conjugate subgradient method. This is obtained by allowing appropriate upward shifting of the affine approximations of the objective function which contribute to the classic definition of the cutting plane function. The algorithm embeds a proximity control strategy. Finite termination is proved at a point satisfying an approximate optimality condition and some numerical results are provided.     

基于异步次梯度法的LR算法及其在多阶段HFSP的应用

为降低求解复杂度和缩短计算时间,针对多阶段混合流水车间总加权完成时间问题,提出了一种结合异步次梯度法的改进拉格朗日松弛算法。建立综合考虑有限等待时间和工件释放时间的整数规划数学模型,将异步次梯度法嵌入到拉格朗日松弛算法中,从而通过近似求解拉格朗日松弛问题得到一个合理的异步次梯度方向,沿此方向进行搜索,逐渐降低到最优点的距离。通过仿真实验,验证了所提算法的有效性。对比所提算法与传统的基于次梯度法的拉格朗日松弛算法,结果表明,就综合解的质量和计算效率而言,所提算法能在较短的计算时间内获得更好的近优解,尤其是对大规模问题。     

Computation of matrix functions with deflated restarting

A deflated restarting Krylov subspace method for approximating a function of a matrix times a vector is proposed. In contrast to other Krylov subspace methods, the performance of the method in this paper is better. We further show that the deflating algorithm inherits the superlinear convergence property of its unrestarted counterpart for the entire function and present the results of numerical experiments.