An inexact bundle variant suited to column generation

We give a bundle method for constrained convex optimization. Instead of using penalty functions, it shifts iterates towards feasibility, by way of a Slater point, assumed to be known. Besides, the method accepts an oracle delivering function and subgradient values with unknown accuracy. Our approach is motivated by a number of applications in column generation, in which constraints are positively homogeneous—so that zero is a natural Slater point—and an exact oracle may be time consuming. Finally, our convergence analysis employs arguments which have been little used so far in the bundle community. The method is illustrated on a number of cutting-stock problems. Research supported by INRIA New Investigation Grant “Convex Optimization and Dantzig–Wolfe Decomposition”.     

Higher-Order Duality in Nondifferentiable Minimax Programming with Generalized Type I Functions

A unified higher-order dual for a nondifferentiable minimax programming problem is formulated. Weak, strong and strict converse duality theorems are discussed involving generalized higher-order (F,α,ρ,d)-Type I functions. The research of second author was supported by the Department of Atomic Energy, Government of India, under the NBHM Post Doctoral Fellowship Program 40/9/2005-R&D II/2398.     

Unification of basic and composite nondifferentiable optimization

There are two main classes of iterative methods in nondifferentiable optimization (NDO). In thebasic NDO, the information is limited to the objective function and at least one element of its subdifferential, while in thecomposite NDO, the objective function is split into a sum of a smooth and a nonsmooth function. Our work unifies these two approaches for benefiting of their respective advantages.     

Variable metric methods for minimizing a class of nondifferentiable functions

We develop a class of methods for minimizing a nondifferentiable function which is the maximum of a finite number of smooth functions. The methods proceed by solving iteratively quadratic programming problems to generate search directions. For efficiency the matrices in the quadratic programming problems are suggested to be updated in a variable metric way. By doing so, the methods possess many attractive features of variable metric methods and can be viewed as their natural extension to the nondifferentiable case. To avoid the difficulties of an exact line search, a practical stepsize procedure is also introduced. Under mild assumptions the resulting method converge globally.Research supported by National Science Foundation under grant number ENG 7903881.     

An algorithm for the minimization of convex,nondifferentiable functionals in Hilbert space

In this paper, an algorithm for minimizing a convex functionalF(x), defined by the maximum of convex smooth functionalsF _i (x), is described. The sequence of valuesF(x _n ) is monotonically decreasing, the algorithm is convergent, and it attains quadratic convergence near the solution.This work was supported by the National Research Council of Italy.     

On generalized gradients

In this paper we present a concept of the construction of generalized gradients by considering a development of directional derivatives into spherical harmonics. This leads to a derivation system as a system of generalized partial derivatives. Necessary conditions for local extrema for a broad class of not necessarily differentiable function can be given and a characterization of points of differentiability can be proved by using generalized gradients.     

不可微非线性规划的 L_1-精确罚函数法

本文提出求解不可微非线性不等式约束极小化问题的 L_1-精确罚函数算法。在有关函数为半光滑的假设下,给出了收敛性结果。     

Improving the rate of convergence of Newton methods on Banach spaces with a convergence structure and applications

In this note, we use inexact Newton-like methods to find solutions of nonlinear operator equations on Banach spaces with a convergence structure. Our technique involves the introduction of a generalized norm as an operator from a linear space into a partially ordered Banach space. In this way, the metric properties of the examined problem can be analyzed more precisely. Moreover, this approach allows us to derive from the same theorem, on the one hand, semilocal results of Kantorovich-type, and on the other hand, global results based on monotonicity considerations. By imposing very general Lipschitz-like conditions on the operators involved, on the one hand, we cover a wider range of problems, and on the other hand, by choosing our operators appropriately, we can find sharper error bounds on the distances involved than before. Furthermore, we show that special cases of our results reduce to the corresponding ones already in the literature. Finally, several examples are being provided where our results compare favorably with earlier ones.     

The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches

We propose a generalized version of the Prize Collecting Steiner Tree Problem (PCSTP), which offers a fundamental unifying model for several well-known -hard tree optimization problems. The PCSTP also arises naturally in a variety of network design applications including cable television and local access networks. We reformulate the PCSTP as a minimum spanning tree problem with additional packing and knapsack constraints and we explore various nondifferentiable optimization algorithms for solving its Lagrangian dual. We report computational results for nine variants of deflected subgradient strategies, the volume algorithm (VA), and the variable target value method used in conjunction with the VA and with a generalized Polyak–Kelley cutting plane technique. The performance of these approaches is also compared with an exact stabilized constraint generation procedure.     

不可微规划的极大熵不动点算法

本文将极大熵逼近方法和不动点计算方法有机地结合,提出了一种不可微规划计算方法．该方法同样也适用于求解可微规划,而后给出了该方法的收敛性