Smooth minimization of non-smooth functions

In this paper we propose a new approach for constructing efficient schemes for non-smooth convex optimization. It is based on a special smoothing technique, which can be applied to functions with explicit max-structure. Our approach can be considered as an alternative to black-box minimization. From the viewpoint of efficiency estimates, we manage to improve the traditional bounds on the number of iterations of the gradient schemes from keeping basically the complexity of each iteration unchanged.This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Ministers Office, Science Policy Programming. The scientific responsibility is assumed by the author.     

Sparse optimization on measures with over-parameterized gradient descent

Mathematical Programming - Minimizing a convex function of a measure with a sparsity-inducing penalty is a typical problem arising, e.g., in sparse spikes deconvolution or two-layer neural networks...     

Bibliography on non-differentiable optimization and non-smooth analysis

This bibliography lists about four hundred references to published papers, theses, and books which deal with non-differentiable optimization problems or contribute to the field of (non-convex) non-smooth analysis useful for the study of such optimization problems.     

Inertial alternating direction method of multipliers for non-convex non-smooth optimization

Computational Optimization and Applications - In this paper, we propose an algorithmic framework, dubbed inertial alternating direction methods of multipliers (iADMM), for solving a class of...     

A comparison of complete global optimization solvers

Results are reported of testing a number of existing state of the art solvers for global constrained optimization and constraint satisfaction on a set of over 1000 test problems in up to 1000 variables, collected from the literature.The test problems are available online in AMPL and were translated into the input formats of the various solvers using routines from the COCONUT environment. These translators are available online, too.     

Smooth and non-smooth travelling waves in a nonlinearly dispersive Boussinesq equation

The dynamical behavior and special exact solutions of nonlinear dispersive Boussinesq equation (B(m,n) equation), u_tt−u_xx−a(uⁿ)_xx+b(u^m)_xxxx=0, is studied by using bifurcation theory of dynamical system. As a result, all possible phase portraits in the parametric space for the travelling wave system, solitary wave, kink and anti-kink wave solutions and uncountably infinite many smooth and non-smooth periodic wave solutions are obtained. It can be shown that the existence of singular straight line in the travelling wave system is the reason why smooth waves converge to cusp waves, finally. When parameter are varied, under different parametric conditions, various sufficient conditions guarantee the existence of the above solutions are given.     

求解带箱子集约束的非光滑全局优化问题的填充函数方法

提出了一个求解带箱子集约束的非光滑全局优化问题的填充函数方法.构造的填充函数只包含一个参数,且此参数在迭代过程中容易调节.分析了填充函数的理论性质,在此基础上设计了填充函数算法.数值计算验证了该算法的有效性.     

Vector variational-like inequalities and non-smooth vector optimization problems

In this paper, we establish relationships between vector variational-like inequality problems and non-smooth vector optimization problems under non-smooth invexity. We identify the vector critical points, the weakly efficient points and the solutions of the non-smooth weak vector variational-like inequality problems, under non-smooth pseudo-invexity assumptions. These conditions are more general than those existing in the literature.     

From differential equation solvers to accelerated first-order methods for convex optimization

Mathematical Programming - Convergence analysis of accelerated first-order methods for convex optimization problems are developed from the point of view of ordinary differential equation solvers. A...     

Accelerated gradient sliding for structured convex optimization

Computational Optimization and Applications - Our main goal in this paper is to show that one can skip gradient computations for gradient descent type methods applied to certain structured convex...     

Fast interior point solvers for H1-regularized PDE-constrained optimization problems

We consider Newton systems arising from the interior point solution of PDE-constrained optimization problems. In particular, we examine problems where the control variable is regularized by an H¹-norm within the cost functional. We present preconditioned iterative methods for the resulting matrix systems, and justify the potency of our approach through numerical experiments. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Necessary and sufficient conditions for weak efficiency in non-smooth vectorial optimization problems

By using the concepts of local cone approximations and K-directional derivatives, we obtain necessary conditions of optimality for the weak efficiency of the vectorial optimization problems with the inequalities and abstract constraints. We introduce the notion of stationary point (weak and strong) and we prove that, under suitable hypotheses of K-invexity, the stationary points are weakly efficient solutions (global).     

Partitioned variable metric updates for large structured optimization problems

Summary This paper presents a minimization method based on the idea of partitioned updating of the Hessian matrix in the case where the objective function can be decomposed in a sum of convex element functions. This situation occurs in a large class of practical problems including nonlinear finite elements calculations. Some theoretical and algorithmic properties of the update are discussed and encouraging numerical results are presented.Work supported by a research grant of the Deutsche Forschungsgemeinschaft, Bonn, FRG     

A one-layer recurrent neural network for non-smooth convex optimization subject to linear inequality constraints

In this paper, a one-layer recurrent network is proposed for solving a non-smooth convex optimization subject to linear inequality constraints. Compared with the existing neural networks for optimization, the proposed neural network is capable of solving more general convex optimization with linear inequality constraints. The convergence of the state variables of the proposed neural network to achieve solution optimality is guaranteed as long as the designed parameters in the model are larger than the derived lower bounds.     

Smooth and non-smooth traveling wave solutions of the Fornberg-Whitham equation with linear dispersion term

In this paper, the Fornberg-Whitham equation with linear dispersion term is investigated by employing the bifurcation method of dynamical systems. As a result, the existence of smooth and non-smooth traveling wave solutions is obtained. And the analytic expressions of solitary wave solutions, periodic cusp wave solutions and peakons are given under some parameter conditions.     

A unified approach to error bounds for structured convex optimization problems

Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper convex function. Such a class encapsulates not only fairly general constrained minimization problems but also various regularized loss minimization formulations in machine learning, signal processing, and statistics. Using our framework, we show that a number of existing error bound results can be recovered in a unified and transparent manner. To further demonstrate the power of our framework, we apply it to a class of nuclear-norm regularized loss minimization problems and establish a new error bound for this class under a strict complementarity-type regularity condition. We then complement this result by constructing an example to show that the said error bound could fail to hold without the regularity condition. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems.     

An augmented Lagrangian method for optimization problems with structured geometric constraints

This paper is devoted to the theoretical and numerical investigation of an augmented Lagrangian method for the solution of optimization problems with geometric constraints. Specifically, we study situations where parts of the constraints are nonconvex and possibly complicated, but allow for a fast computation of projections onto this nonconvex set. Typical problem classes which satisfy this requirement are optimization problems with disjunctive constraints (like complementarity or cardinality constraints) as well as optimization problems over sets of matrices which have to satisfy additional rank constraints. The key idea behind our method is to keep these complicated constraints explicitly in the constraints and to penalize only the remaining constraints by an augmented Lagrangian function. The resulting subproblems are then solved with the aid of a problem-tailored nonmonotone projected gradient method. The corresponding convergence theory allows for an inexact solution of these subproblems. Nevertheless, the overall algorithm computes so-called Mordukhovich-stationary points of the original problem under a mild asymptotic regularity condition, which is generally weaker than most of the respective available problem-tailored constraint qualifications. Extensive numerical experiments addressing complementarity- and cardinality-constrained optimization problems as well as a semidefinite reformulation of MAXCUT problems visualize the power of our approach.

     

Optimality conditions for non-smooth semi-infinite programming

This article deals with a class of non-smooth semi-infinite programming (SIP) problems in which the index set of the inequality constraints is an arbitrary set not necessarily finite. We introduce several kinds of constraint qualifications for these non-smooth SIP problems and we study the relationships between them. Finally, necessary and sufficient optimality conditions are investigated.     

Exact Max-SAT solvers for over-constrained problems

We present a new generic problem solving approach for over-constrained problems based on Max-SAT. We first define a Boolean clausal form formalism, called soft CNF formulas, that deals with blocks of clauses instead of individual clauses, and that allows one to declare each block either as hard (i.e., must be satisfied by any solution) or soft (i.e., can be violated by some solution). We then present two Max-SAT solvers that find a truth assignment that satisfies all the hard blocks of clauses and the maximum number of soft blocks of clauses. Our solvers are branch and bound algorithms equipped with original lazy data structures, powerful inference techniques, good quality lower bounds, and original variable selection heuristics. Finally, we report an experimental investigation on a representative sample of instances (random 2-SAT, Max-CSP, graph coloring, pigeon hole and quasigroup completion) which provides experimental evidence that our approach is very competitive compared with the state-of-the-art approaches developed in the CSP and SAT communities. Research partially supported by projects TIN2004-07933-C03-03 and TIC2003-00950 funded by the Ministerio de Educación y Ciencia. The second author is supported by a grant Ramón y Cajal.