Inhomogeneous convex approximations of nonsmooth functions

In this paper we introduce notions of inhomogeneous upper convex and lower concave approximations of an increment of a nonsmooth function defined on a normed space and study exhaustive families of these approximations. In terms of the introduced notions we establish optimality conditions for various constrained and unconstrained extremum problems.     

Convex Difference Criteria for the Quantitative Stability of Parametric Quasidifferentiable Systems

In this paper solvability and Lipschitzian stability properties for a special class of nonsmooth parametric generalized systems defined in Banach are studied via a variational analysis approach. Verifiable sufficient conditions for such properties to hold under scalar quasidifferentiability assumptions are formulated by combining *-difference and Demyanov difference of convex compact subsets of the dual space with classic quasidifferential calculus constructions. Applications to the formulation of sufficient conditions for metric regularity/open covering of nonsmooth maps, along with their employment in deriving optimality conditions for quasidifferentiable extremum problems, as well as an application to the study of semicontinuity of the optimal value function in parametric optimization are discussed. In memory of Aleksandr Moiseevich Rubinov (1940–2006).     

First and second-order optimality conditions using approximations for vector equilibrium problems with constraints

We consider various kinds of solutions to nonsmooth vector equilibrium problems with functional constraints. By using first and second-order approximations as generalized derivatives, we establish both necessary and sufficient optimality conditions. Our first-order conditions are shown to be applicable in many cases, where existing ones cannot be used. The second-order conditions are new.     

A convergence analysis of the method of codifferential descent

This paper is devoted to a detailed convergence analysis of the method of codifferential descent (MCD) developed by professor V.F. Demyanov for solving a large class of nonsmooth nonconvex optimization problems. We propose a generalization of the MCD that is more suitable for applications than the original method, and that utilizes only a part of a codifferential on every iteration, which allows one to reduce the overall complexity of the method. With the use of some general results on uniformly codifferentiable functions obtained in this paper, we prove the global convergence of the generalized MCD in the infinite dimensional case. Also, we propose and analyse a quadratic regularization of the MCD, which is the first general method for minimizing a codifferentiable function over a convex set. Apart from convergence analysis, we also discuss the robustness of the MCD with respect to computational errors, possible step size rules, and a choice of parameters of the algorithm. In the end of the paper we estimate the rate of convergence of the MCD for a class of nonsmooth nonconvex functions that arise, in particular, in cluster analysis. We prove that under some general assumptions the method converges with linear rate, and it convergence quadratically, provided a certain first order sufficient optimality condition holds true.     

Global Optimality Conditions for Some Classes of Optimization Problems

We establish new necessary and sufficient optimality conditions for global optimization problems. In particular, we establish tractable optimality conditions for the problems of minimizing a weakly convex or concave function subject to standard constraints, such as box constraints, binary constraints, and simplex constraints. We also derive some new necessary and sufficient optimality conditions for quadratic optimization. Our main theoretical tool for establishing these optimality conditions is abstract convexity.     

Second-order sequence-based necessary optimality conditions in constrained nonsmooth vector optimization and applications

Several notions of sequential directional derivatives and sequential local approximations are introduced. Under (first-order) Hadamard differentiability assumptions of the data at the point of study, these concepts are utilized to analyze second-order necessary optimality conditions, which rely on given sequences, for local weak solutions in nonsmooth vector optimization problems with constraints. Some applications to minimax programming problems are also derived.     

co-radiant集的等价表示及其在向量优化问题中的应用

作为特殊的抽象凸(凹)集,radiant集和co-radiant集在抽象凸分析和多目标优化问题理论中发挥着重要作用。首先建立radiant集co-radiant集的等价刻画,从而推导出它们的重要性质。然后,将重要性质应用到向量优化问题近似解的刻画中,得到关于近似解集的等价刻画。     

Well-posedness for vector equilibrium problems

We introduce and study two notions of well-posedness for vector equilibrium problems in topological vector spaces; they arise from the well-posedness concepts previously introduced by the same authors in the scalar case, and provide an extension of similar definitions for vector optimization problems. The first notion is linked to the behaviour of suitable maximizing sequences, while the second one is defined in terms of Hausdorff convergence of the map of approximate solutions. In this paper we compare them, and, in a concave setting, we give sufficient conditions on the data in order to guarantee well-posedness. Our results extend similar results established for vector optimization problems known in the literature.      

Second-order optimality conditions using approximations for nonsmooth vector optimization problems under inclusion constraints

Second-order necessary conditions and sufficient conditions for optimality in nonsmooth vector optimization problems with inclusion constraints are established. We use approximations as generalized derivatives and avoid even continuity assumptions. Convexity conditions are not imposed explicitly. Not all approximations in use are required to be bounded. The results improve or include several recent existing ones. Examples are provided to show that our theorems are easily applied in situations where several known results do not work.     

Convex envelopes generated from finitely many compact convex sets

We consider the problem of constructing the convex envelope of a lower semi-continuous function defined over a compact convex set. We formulate the envelope representation problem as a convex optimization problem for functions whose generating sets consist of finitely many compact convex sets. In particular, we consider nonnegative functions that are products of convex and component-wise concave functions and derive closed-form expressions for the convex envelopes of a wide class of such functions. Several examples demonstrate that these envelopes reduce significantly the relaxation gaps of widely used factorable relaxation techniques.     

First and Second Order Optimality Conditions Using Approximations for Nonsmooth Vector Optimization in Banach Spaces

We use the first and second order approximations of mappings to establish both necessary and sufficient optimality conditions for unconstrained and constrained nonsmooth vector optimization problems. Ideal solutions, efficient solutions, and weakly efficient solutions are considered. The data of the problems need not even be continuous. Some often imposed compactness assumptions are also relaxed. Examples are provided to compare our results and some known recent results.This work was partially supported by the National Basic Research Program in Natural Sciences of Vietnam.     

Abstract convexity of extended real-valued ICR functions

The theory of non-negative increasing and co-radiant (ICR) functions defined on ordered topological vector spaces has been well developed. In this article, we present the theory of extended real-valued ICR functions defined on an ordered topological vector space X. We first give a characterization for non-positive ICR functions and examine abstract convexity of this class of functions. We also investigate polar function and subdifferential of these functions. Finally, we characterize abstract convexity, support set and subdifferential of extended real-valued ICR functions.     

Abstract subdifferentials and some characterizations of optimal solutions

We introduce and study the subdifferential of a function at a point, with respect to a primal-dual pair of optimization problems, which encompasses, as particular cases, several known concepts of subdifferential. We give a characterization of optimal solutions of the primal problem, in terms of abstract Lagrangians, and a simultaneous characterization of optimal solutions and strong duality, with the aid of abstract subdifferentials. We give some applications to unperturbational Lagrangian duality and unperturbational surrogate duality.We wish to thank H. J. Greenberg for discussions and valuable remarks on the subject of this paper, made during his visit in Bucharest, in May 1985, within the framework of the Cooperative Exchange Agreement between the National Academy of Sciences of the USA and the Romanian Academy of Sciences.     

A Trust-region Method for Nonsmooth Nonconvex Optimization

We propose a trust-region type method for a class of nonsmooth nonconvex optimization problems where the objective function is a summation of a (probably nonconvex) smooth function and a (probably nonsmooth) convex function. The model function of our trust-region subproblem is always quadratic and the linear term of the model is generated using abstract descent directions. Therefore, the trust-region subproblems can be easily constructed as well as efficiently solved by cheap and standard methods. When the accuracy of the model function at the solution of the subproblem is not sufficient, we add a safeguard on the stepsizes for improving the accuracy. For a class of functions that can be "truncated'', an additional truncation step is defined and a stepsize modification strategy is designed. The overall scheme converges globally and we establish fast local convergence under suitable assumptions. In particular, using a connection with a smooth Riemannian trust-region method, we prove local quadratic convergence for partly smooth functions under a strict complementary condition. Preliminary numerical results on a family of $\ell_1$-optimization problems are reported and demonstrate the efficiency of our approach.     

Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations

We introduce a proximal bundle method for the numerical minimization of a nonsmooth difference-of-convex (DC) function. Exploiting some classic ideas coming from cutting-plane approaches for the convex case, we iteratively build two separate piecewise-affine approximations of the component functions, grouping the corresponding information in two separate bundles. In the bundle of the first component, only information related to points close to the current iterate are maintained, while the second bundle only refers to a global model of the corresponding component function. We combine the two convex piecewise-affine approximations, and generate a DC piecewise-affine model, which can also be seen as the pointwise maximum of several concave piecewise-affine functions. Such a nonconvex model is locally approximated by means of an auxiliary quadratic program, whose solution is used to certify approximate criticality or to generate a descent search-direction, along with a predicted reduction, that is next explored in a line-search setting. To improve the approximation properties at points that are far from the current iterate a supplementary quadratic program is also introduced to generate an alternative more promising search-direction. We discuss the main convergence issues of the line-search based proximal bundle method, and provide computational results on a set of academic benchmark test problems.     

Concave programming for minimizing the zero-norm over polyhedral sets

Given a non empty polyhedral set, we consider the problem of finding a vector belonging to it and having the minimum number of nonzero components, i.e., a feasible vector with minimum zero-norm. This combinatorial optimization problem is NP-Hard and arises in various fields such as machine learning, pattern recognition, signal processing. One of the contributions of this paper is to propose two new smooth approximations of the zero-norm function, where the approximating functions are separable and concave. In this paper we first formally prove the equivalence between the approximating problems and the original nonsmooth problem. To this aim, we preliminarily state in a general setting theoretical conditions sufficient to guarantee the equivalence between pairs of problems. Moreover we also define an effective and efficient version of the Frank-Wolfe algorithm for the minimization of concave separable functions over polyhedral sets in which variables which are null at an iteration are eliminated for all the following ones, with significant savings in computational time, and we prove the global convergence of the method. Finally, we report the numerical results on test problems showing both the usefulness of the new concave formulations and the efficiency in terms of computational time of the implemented minimization algorithm.     

A globally linearly convergent method for pointwise quadratically supportable convex–concave saddle point problems

We study the Proximal Alternating Predictor–Corrector (PAPC) algorithm introduced recently by Drori, Sabach and Teboulle [8] to solve nonsmooth structured convex–concave saddle point problems consisting of the sum of a smooth convex function, a finite collection of nonsmooth convex functions and bilinear terms. We introduce the notion of pointwise quadratic supportability, which is a relaxation of a standard strong convexity assumption and allows us to show that the primal sequence is R-linearly convergent to an optimal solution and the primal-dual sequence is globally Q-linearly convergent. We illustrate the proposed method on total variation denoising problems and on locally adaptive estimation in signal/image deconvolution and denoising with multiresolution statistical constraints.     

Envelope Functions: Unifications and Further Properties

Forward–backward and Douglas–Rachford splitting are methods for structured nonsmooth optimization. With the aim to use smooth optimization techniques for nonsmooth problems, the forward–backward and Douglas–Rachford envelopes where recently proposed. Under specific problem assumptions, these envelope functions have favorable smoothness and convexity properties and their stationary points coincide with the fixed-points of the underlying algorithm operators. This allows for solving such nonsmooth optimization problems by minimizing the corresponding smooth convex envelope function. In this paper, we present a general envelope function that unifies and generalizes existing ones. We provide properties of the general envelope function that sharpen corresponding known results for the special cases. We also present a new interpretation of the underlying methods as being majorization–minimization algorithms applied to their respective envelope functions.     

Fuzzy necessary optimality conditions for vector optimization problems

The primary aim of this article is to derive Lagrange multiplier rules for vector optimization problems using a non-convex separation technique and the concept of abstract subdifferential. Furthermore, we present a method of estimation of the norms of such multipliers in very general cases and for many particular subdifferentials.     

Iterative Algorithms for Equilibrium Problems

We consider equilibrium problems in the framework of the formulation proposed by Blum and Oettli, which includes variational inequalities, Nash equilibria in noncooperative games, and vector optimization problems, for instance, as particular cases. We show that such problems are particular instances of convex feasibility problems with infinitely many convex sets, but with additional structure, so that projection algorithms for convex feasibility can be modified in order to improve their convergence properties, mainly achieving global convergence without either compactness or coercivity assumptions. We present a sequential projections algorithm with an approximately most violated constraint control strategy, and two variants where exact orthogonal projections are replaced by approximate ones, using separating hyperplanes generated by subgradients. We include full convergence analysis of these algorithms.