Search

In this paper, a family of coordinate majorization descent algorithms are proposed for solving the nonconvex penalized learning problems including SCAD and MCP estimation. In the coordinate majoriz...

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.

We suggest a modification of the descent splitting methods for decomposable composite optimization problems, which maintains the basic convergence properties, but enables one to reduce the computational expenses per iteration and to provide computations in a distributed manner. It consists of making coordinate-wise steps together with a special threshold control.

Bregman iterative algorithms have been extensively used for and total variation regularization problems, allowing to obtain simple, fast and effective algorithms. In this paper, three already-available algorithms for geosounding inversion are modified by including them in a Bregman iterative procedure. The resulting algorithms are easy to implement and do not require any optimization package. Modelling results are presented for synthetic and field data, observing better convergence properties than the original versions, avoiding the need of any continuation descent procedure.

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.

We present an algorithm to locally minimize nonsmooth, nonconvex functions. In order to find descent directions, the notion of quasisecants, introduced in this paper, is applied. We prove that the algorithm converges to Clarke stationary points. Numerical results are presented demonstrating the applicability of the proposed algorithm to a wide variety of nonsmooth, nonconvex optimization problems. We also compare the proposed algorithm with the bundle method using numerical results.

A globally convergent algorithm for equilibrium problems with differentiable bifunctions is proposed. The algorithm is based on descent directions of a suitable family of gap functions. The novelty of the approach is that assumptions which guarantee that the stationary points of the gap functions are global optima are not required.

An iterative strategy for the reconstruction of objects buried in a medium and the identification of their material parameters is analysed. The algorithm alternates guesses of the domains using topological derivatives with corrections of the parameters obtained by descent techniques. Numerical experiments in geometries with multiple scatterers show that our scheme predicts the number, location and shape of objects, together with their physical parameters, with reasonable accuracy in a few steps.

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.

This article presents a descent method for solving monotone variational inequalities with separate structures. The descent direction is derived from the well-known alternating directions method. The optimal step size along the descent direction also improves the efficiency of the new method. Some numerical results demonstrate that the new method is effective in practice.

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.

The paper will build on very recent descent algorithms for solving extremely general multilevel transportation models efficiently. For simplicity we here suppose that there is just one route joining each OD pair and that the only control is a price on that route. The ideas all generalize a long way.

International audience

Global convergence theorems for a class of descent methods for unconstrained optimization problems in normed spaces, using multidirectional search, are proved. Exact and inexact search are considered and the results allow to define a globally convergent algorithm for an unconstrained optimal control problem which operates, at each step, on discrete approximations of the original continuous problem.

The problem of time-continuous meteorological data assimilation is addressed. An optimal control method is proposed and studied for a simple well-posed 2D atmospheric model and continuous in time and space observations. An existence result for the optimal control problem is given. Then the first order necessary conditions of optimality are explicited using a forced version of the linearized adjoint model; allowing the use of a classical descent method to solve the problem. The reliability of the method is shown on some numerical tests. Finally, the existence and characterization results of an optimal control are extended to the case of observations distributed in time.

In this paper, we consider the optimization method for monotone variational inequality probleln on polyhedral sets. First, we consider the mixed complementarity problem based on the original problem. Then, a merit function for the mixed complementarity problem is proposed and s desirable properties of the merit function are obtained. Under certain assumptions, we show tthat any stationary point of the merit function is a solution of the original problem. A descent metlpod for the optimization problem is proposed and the global convergence of the method is shown

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

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

We consider the application of the ABS algorithms, introduced by [I], mainly for the solution of linear algebraic systems, to constrained optimization problems with equality constraints. A general formulation of feasible direction algorithms is obtained and the ABS formulation is given of the reduced gradient method of Wolfe (1967) and of the projected gradient method of Rosen (1960)

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.

This paper is concerned with the numerical solution of optimal control problems for which each optimal control is bang-bang. Especially, the results apply to parabolic boundary control Problems. Starting from a sequence of feasible solutions converging to an optimal control u, a sequence of bang-bang controls converging to u is constructed. Bang-bang approximations of u are desirable for certain numerical reasons. Sequences of arbitrary feasible controls converging to u may be obtained by discretization or by a descent method. Numerical examples are also given.

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.