Search

Given a convex objective function on a Banach space, which is Lipschitz on bounded sets, we consider the class of regular vector fields introduced in our previous work on descent methods. We analyz...

Given a Lipschitz convex and coercive objective function on a Banach space, we revisit the class of regular vector fields introduced in our previous work on descent methods. Taking into account com...

In this paper, we study properties of a special class of ordered median functions, called block-functions. These are ordered median functions which belong to a generating binary (row)-vector of the form called a block vector. The aim of this paper is to explicitly determine the simplicial complexes and all steepest descent and ascent directions of descent and ascent cones of ordered median block-function.

In this paper, we show how a nonlinear scalarization functional can be used in order to characterize several well-known set order relations and which thus plays a key role in set optimization. By means of this functional, we derive characterizations for minimal elements of set-valued optimization problems using a set approach. Our methods do not rely on any convexity assumptions on the considered sets. Furthermore, we develop a derivative-free descent method for set optimization problems without convexity assumptions to verify the usefulness of our results.

An ordered median functions is a continuous piecewise-linear function. It is well known that in finite dimensional spaces every continuous piecewise-linear function admits a max-min representation in terms of its linear functions. An explicit representation of an ordered median function in max-min form is given by the authors and will appear in a forthcoming issue of this journal. Based on this representation, we give a topological classification of ordered median functions through their simplicial complex of ascent (resp. descent) cones.

The equilibrium problem (EP) can be formulated as an unconstrained minimization problem through the D-gap function. We present a descent type algorithm for solving EP based on the generalized D-gap function. We discuss the convergence properties of the proposed algorithm under suitable assumptions while supporting our approach with appropriate examples. We construct an error bound for the equilibrium problem interms of the generalized D-gap function which gives a significant modification to the error bound given by Konnov et al.

New algorithms for solving unconstrained optimization problems are presented based on the idea of combining two types of descent directions: the direction of anti-gradient and either the Newton or quasi-Newton directions. The use of latter directions allows one to improve the convergence rate. Global and superlinear convergence properties of these algorithms are established. Numerical experiments using some unconstrained test problems are reported. Also, the proposed algorithms are compared with some existing similar methods using results of experiments. This comparison demonstrates the efficiency of the proposed combined methods.

In this article we propose two algorithms for minimization of quasiconvex functions. The first one is of type subgradient. In the second one, we consider the steepest descent method with Armijo's rule. In both, we use elements from Plastria's lower subdifferential. Under certain conditions, we prove that the sequence generated by these algorithms globally converges to a solution. We provide a counter-example showing that the choice of the minus gradient direction does not assure the global convergence of the descent method to a solution. This counter-example is related to a mistake in the proof of the Theorem 3.1 of J.P. Dussault, [Convergence of implementable descent algorithms for unconstrained optimization (technical note), J. Optim. Theory Appl. 104 (2000), pp. 739–745]. We also point out the mistake in the proof of that theorem.

It was earlier demonstrated, by the so-called main (or simplest) problem of the Calculus of Variations, that the Theory of Exact Penalties allows one not only to derive fundamental results of the Calculus of Variations but also to construct new direct numerical methods for solving variational problems based on the notions of subgradient and hypogradient of the exact penalty function (which is essentially nonsmooth even if all initial data are smooth). In this article Exact Penalties are used to solve isoperimetric problems of the Calculus of Variations. New direct numerical methods are described (e.g. the method of hypodifferential descent). Several numerical examples are discussed.

For solving monotone variational inequalities with separate structures, Ye and Yuan [A descent method for stuctured monotone variational inequalities, Optim. Methods Softw. 22 (2007), 329–338] used the iterates generated by the well-known alternating directions method to design a descent direction, and thus presented a contraction method. This article continues on this study. By observing an improved descent direction and, selecting the corresponding optimal step sizes, a new contraction method is presented. In addition to proving the algorithm's convergence under mild assumptions, we compare the improved contraction method to Ye and Yuan's method (which is generalized) and achieve the superiority of the new method in theoretical senses.

The notions of exhaustive families of upper convex and lower concave approximations (in the sense of Pschenichnyi) were introduced by Rubinov. For some classes of nonsmooth functions, these tools appeared to be very productive and constructive (e.g., in the case of quasidifferentiable functions). Dual tools – the upper exhauster and the lower exhauster – can be employed to describe optimality conditions and to find directions of the steepest ascent and descent. If a proper exhauster is known (for minimality conditions we need an upper exhauster, while for maximality ones a lower exhauster is required), the above problems are reduced to the problems of finding the nearest points to convex sets. If we study, e.g., the minimization problem and a lower exhauster is available, it is required to convert it into an upper one. In the present article it is shown how to use a lower exhauster to get conditions for a minimum without converting the lower exhauster into an upper one.

We consider a variational inequality problem, where the cost mapping is the sum of a single-valued mapping and the subdifferential mapping of a convex function. For this problem we introduce a new class of equivalent optimi7ation formulations; based on them, we also provide the first convergence analysis of descent algorithms for the problem. The optimization formulations constitute generalizations of those presented by Auchmuty [Auc89]. and the descent algorithms are likewise generalizations of those of Fukushima [Fuk92], Larsson and Patriksson [LaP94] and several others, for variational inequality problems with single-valued cost mappings

In a compa nion paper (A new algorithm to solve calculus of variations problems using Wolfe's convergence theory. Part I: Theory and algorithm), a new a lgorithm with the proper ties of guaranteed finite term in ati on and global co nvergence was p roposed to so lve calculus of variations problems. A detailed impleme ntation of the algori thm is presented here . Th e impl ementat ion proposes a variable dimension method and incorp orat es a stable procedure to solve for the descent search direction . Numerical examples are given to illustrate the algorithm

Necessary minimum conditions on an equality-type constraint and various steepest decent (or descent) directions are studied with respect to the dependence on the special form of a quasidifferential. It turns out that all of them are independent of the different equivalent quasidifferentials

The paper deals with nonsmooth quasiconvex functions and develops a quasidifferential analysis for this class of functions. Therefore, in terms of sub and superdifferentials, first order approximations of the functions are derived, optimality conditions are stated and directions of descent (either simple feasible or of steepest descent) are determined. Moreover, a relation among positively homogeneous convex and quasiconvex functions is established

A stationary point of a constrained optimization problem is called critical, if the first order necessary optimality conditions are fulfilled but the stationary point cannot be classified using second order optimality conditions. In this paper the problem of classifying a critical stationary point is reduced to the application of higher order optimality conditions for a special unconstrained optimization problem. This is possible using implicit automatic differentiation. Theoretical and computational aspects of descending from saddlepoints are considered

In this paper we present a test to characterize the optimal solutions for the continuous semi-infinite linear programming problem. This optimality characterization is a condition of Kuhn–Tucker type. The resolution of a linear program permits to check the optimality of a feasible point,to detect the unboundedness of the problem and to find descent directions. We give some illustrative examples. We show that the local Mangasarian–Fromovitz constraint qualification is almost equivalent to Slater qualification for this problem. Furthermore, it follows from our study that this optimality condition is always necessary for a wide class of semi-infinite linear programming problems

In this paper we give a necessary and sufficient condition for a quasidifferentiable function to be continuously codifferentiable. Using this result we present a conceptual descent method for the class of continuously codifferentiable functions, based on the idea of V. F. De-Myanov, S. Gamidov and T. I. Sivelina [5].

Stochastic approximation procedures, e.g. stochastic gradient methods, can be accelerated considerably by using deterministic descent directions or more exact gradient estimations at certain iteration points. Having several methods for finding (feasible) deterministic directions of decrease or improved search directions, the remaining problem is now to find an appropriate sequence of step sizes. Using the standard assumptions of (pure) stochastic approximation methods and developing corresponding conditions (“descent direction qualifications”) for the deterministic descent directions, recurrence relations for the computation of upper and lower bounds for the estimation errors are derived first. The geometrical meaning of the descent direction qualifications is discussed in detail. Minimizing then the mean square argument errors, the mean criterial errors, resp., arising during the semi-stochastic approximation process with respect to the step sizes, recursions for the resulting optimal error bounds are ob...

Several descent methods have recently been proposed for minimizing smooth compositions of max-type functions. The methods generate many search directions at each iteration. It is shown here that a random choice of only two search directions at each iteration suffices to retain convergence to in#-stationary points with probability 1. Use of this technique may significantly decrease the effort involved in quadratic programming and line searches, thus allowing efficient implementations of the methods. This paper is a contribution to research on non-smooth optimization currently underway in the System and Decision Sciences Program.

A finite descent method is proposed to solve the problem of determining an inpolygon with minimal circumference. The algorithm is based on Schwabz' reflection principle and the idea of coordinate-wise descent. Four examples illustrate the efficiency of the algorithm.

For solving nonlinear constrained optimization problems the reduced gradient method is used. The computation of the descent directions is performed similar to the way applied for linear constraints. Contrary to the method of Abadie/Carpentier, in every iteration point the obtained direction is not only a descent direction but also a feasible direction.

There have been several algorithms in the literature that use Clabke's generalized gradients to find descent directions for minimizing Lipschitz functions, The result used to find these directions states that if zero is not a generalized gradient to a Lipschitz function f at xthen there is an y that is a direction of descent for f at all points in a neighborhood of x. In this paper it is shown that, even though there may not be descent directions, there are paths of descent if f is lower semicontinuous. This is done using a characterization of Clabke'S tangent cone in terms of Lipschitz paths.