Nonmonotone bundle-type scheme for convex nonsmooth minimization

In this paper, we present a general scheme for bundle-type algorithms which includes a nonmonotone line search procedure and for which global convergence can be proved. Some numerical examples are reported, showing that the nonmonotonicity can be beneficial from a computational point of view.This work was partially supported by the National Research Program on Metodi di ottimizzazione per le decisioni, Ministero dell' Universitá e della Ricerca Scientifica e Tecnologica and by ASI: Agenzia Spaziale Italiana.     

On the convergence of the exponential multiplier method for convex programming

In this paper, we analyze the exponential method of multipliers for convex constrained minimization problems, which operates like the usual Augmented Lagrangian method, except that it uses an exponential penalty function in place of the usual quadratic. We also analyze a dual counterpart, the entropy minimization algorithm, which operates like the proximal minimization algorithm, except that it uses a logarithmic/entropy proximal term in place of a quadratic. We strengthen substantially the available convergence results for these methods, and we derive the convergence rate of these methods when applied to linear programs.Research supported by the National Science Foundation under Grant DDM-8903385, and the Army Research Office under Grant DAAL03-86-K-0171.     

About a minimax theorem of Matthies,Strang and Christiansen

We give a new minisup theorem for noncompact strategy sets. Our result is of the type of the Matthies-Strang-Christiansen minimax theorem where the hyperplane should be replaced by any closed convex set. As an application, we derive a slight generalization of the Matthies-Strang-Christiansen minimax theorem.     

Geometry of optimality conditions and constraint qualifications: The convex case

The cones of directions of constancy are used to derive: new as well as known optimality conditions; weakest constraint qualifications; and regularization techniques, for the convex programming problem. In addition, the badly behaved set of constraints, i.e. the set of constraints which causes problems in the Kuhn—Tucker theory, is isolated and a computational procedure for checking whether a feasible point is regular or not is presented.This research was supported by the National Research Council of Canada and le Gouvernement du Quebec and is part of the author's Ph.D. Dissertation done at McGill University, Montreal, Que., under the guidance of Professor S. Zlobec.     

ε-optimality criteria for convex programming problems via exact penalty functions

In this paper, we present-optimality criteria for convex programming problems associated with exact penalty functions. Several authors have given various criteria under the assumption that such convex problems and the associated dual problems can be solved. We assume the solvability of neither the convex problem nor the dual problem. To derive our criteria, we estimate the size of the penalty parameter in terms of an-solution for the dual problem.     

A path following algorithm for a class of convex programming problems

We present a primal-dual path following interior algorithm for a class of linearly constrained convex programming problems with non-negative decision variables. We introduce the definition of a Scaled Lipschitz Condition and show that if the objective function satisfies the Scaled Lipschitz Condition then, at each iteration, our algorithm reduces the duality gap by at least a factor of (1–/n), where is positive and depends on the curvature of the objective function, by means of solving a system of linear equations which requires no more than O(n³) arithmetic operations. The class of functions having the Scaled Lipschitz Condition includes linear, convex quadratic and entropy functions.     

On the symmetric travelling salesman problem I: Inequalities

We investigate several classes of inequalities for the symmetric travelling salesman problem with respect to their facet-defining properties for the associated polytope. A new class of inequalities called comb inequalities is derived and their number shown to grow much faster with the number of cities than the exponentially growing number of subtour-elimination constraints. The dimension of the travelling salesman polytope is calculated and several inequalities are shown to define facets of the polytope. In part II (On the travelling salesman problem II: Lifting theorems and facets) we prove that all subtour-elimination and all comb inequalities define facets of the symmetric travelling salesman polytope.     

Convexifactors,generalized convexity and vector optimization

In this article we study a recently introduced notion of non-smooth analysis, namely convexifactors. We study some properties of the convexifactors and introduce two new chain rules. A new notion of non-smooth pseudoconvex function is introduced and its properties are studied in terms of convexifactors. We also present some optimality conditions for vector minimization in terms of convexifactors.     

Reconstruction of n-dimensional convex bodies from surface tensors

In this paper, we derive uniqueness and stability results for surface tensors. Further, we develop two algorithms that reconstruct shape of n-dimensional convex bodies. One algorithm requires knowledge of a finite number of surface tensors, whereas the other algorithm is based on noisy measurements of a finite number of harmonic intrinsic volumes. The derived stability results ensure consistency of the two algorithms. Examples that illustrate the feasibility of the algorithms are presented.     

L~p空间中的Fejér和Hermite-Hadamard型不等式

给出了二阶导数属于Lp空间时Fejér和Hermite-Hadamard型不等式的推广,得到两个新结果.