This paper develops an iterative algorithm to solve nonsmooth nonconvex optimization problems on complete Riemannian manifolds. The algorithm is based on the combination of the well known trust region and bundle metho...
详细信息
This paper develops an iterative algorithm to solve nonsmooth nonconvex optimization problems on complete Riemannian manifolds. The algorithm is based on the combination of the well known trust region and bundle methods. According to the process of the most bundle methods, the objective function is approximated by a piecewise linear working model which is updated by adding cutting planes at unsuccessful trial steps. Then at each iteration, by solving a subproblem that employs the working model in the objective function subject to the trust region, a candidate descent direction is obtained. We study the algorithm from both theoretical and practical points of view and its global convergence is verified to stationary points for locally Lipschitz functions. Moreover, in order to demonstrate the reliability and efficiency, a MATLAB implementation of the proposed algorithm is prepared and results of numerical experiments are reported.
We propose a new algorithm for minimizing locally Lipschitz functions that combines both the bundle and trust region techniques. Based on the bundle methods the objective function is approximated by a piecewise linear...
详细信息
We propose a new algorithm for minimizing locally Lipschitz functions that combines both the bundle and trust region techniques. Based on the bundle methods the objective function is approximated by a piecewise linear working model which is updated by adding cutting planes at unsuccessful trial steps. The algorithm defines, at each iteration, a new trial point by solving a subproblem that employs the working model in the objective function subject to a region, which is called the trust region. The algorithm is studied from both theoretical and practical points of view. Under a lower -C1 assumption on the objective function, global convergence of it is verified to stationary points. In order to demonstrate the reliability and efficiency of the proposed algorithm, a MATLAB implementation of it is prepared and numerical experiments have been made using some academic nonsmooth test problems. Computational results show that the developed method is efficient for solving nonsmooth and nonconvex optimization problems.
When a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate and solve the master problem as a linear program. Seen in the dual space, this results in th...
详细信息
When a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate and solve the master problem as a linear program. Seen in the dual space, this results in the algorithm known in the nonlinear programming community as the cutting-plane algorithm of Kelley and Cheney-Goldstein. However, more stable methods with better theoretical convergence rates are known and have been used as alternatives to this standard. One of them is the bundle method;our aim is to illustrate its differences with Kelley's method. In the process we review alternative stabilization techniques used in column generation, comparing them from both primal and dual points of view. Numerical comparisons are presented for five applications: cutting stock (which includes bin packing), vertex coloring, capacitated vehicle routing, multi-item lot sizing, and traveling salesman. We also give a sketchy comparison with the volume algorithm.
In the paper, the question is investigated if a bundle algorithm can be used to compute approximate solutions for bilevel programming problems where the lower level optimal solution is in general not uniquely determin...
详细信息
In the paper, the question is investigated if a bundle algorithm can be used to compute approximate solutions for bilevel programming problems where the lower level optimal solution is in general not uniquely determined. To give a positive answer to this question, an appropriate regularization approach is used in the lower level. In the general case, the resulting algorithm computes an approximate solution. If the problem proves to have strongly stable lower level solutions for all parameter values in a certain neighborhood of the stationary solutions of the bilevel problem, convergence to stationary solutions can be shown.
The bilevel programming problem (BLPP) is equivalent to a two-person Stackelberg game in which the leader and follower pursue individual objectives. Play is sequential and the choices of one affect the choices and att...
详细信息
The bilevel programming problem (BLPP) is equivalent to a two-person Stackelberg game in which the leader and follower pursue individual objectives. Play is sequential and the choices of one affect the choices and attainable payoffs of the other. The purpose of this paper is to investigate an extension of the linear BLPP where the objective functions of both players are bilinear. To overcome certain discontinuities in the master problem, a regularized term is added to the follower objective function. Using ideas from parametric programming, the generalized Jacobian and the pseudodifferential of the regularized follower solution function are computed. This allows us to develop a bundle trust-region algorithm. Convergence analysis of the proposed methodology is given.
In this paper, we analyze a class of methods for minimizing a proper lower semicontinuous extended-valued convex function f: R-n--> R boolean OR {infinity}. Instead of the original objective function f, we employ a...
详细信息
In this paper, we analyze a class of methods for minimizing a proper lower semicontinuous extended-valued convex function f: R-n--> R boolean OR {infinity}. Instead of the original objective function f, we employ a convex approximation f(k+1) at the kth iteration. Some global convergence rate estimates are obtained. We illustrate our approach by proposing (i) a new family of proximal point algorithms which possesses the global convergence rate estimate f(x(k)) - min(x is an element of Rn) f(x) = O(1/(Sigma(j=0)(k-1)root lambda(j))(2)) even if the iteration points are calculated approximately, where {lambda(k)}(k=0)(infinity) are the proximal parameters, and (ii) a variant proximal bundle method. Applications to stochastic programs are discussed.
暂无评论