On the degree and separability of nonconvexity and applications to optimization problems

We study qualitative indications for d.c. representations of closed sets in and functions on Hilbert spaces. The first indication is an index of nonconvexity which can be regarded as a measure for the degree of nonconvexity. We show that a closed set is weakly closed if this indication is finite. Using this result we can prove the solvability of nonconvex minimization problems. By duality a minimization problem on a feasible set in which this indication is low, can be reduced to a quasi-concave minimization over a convex set in a low-dimensional space. The second indication is the separability which can be incorporated in solving dual problems. Both the index of nonconvexity and the separability can be characteristics to “good” d.c. representations. For practical computation we present a notion of clouds which enables us to obtain a good d.c. representation for a class of nonconvex sets. Using a generalized Caratheodory’s theorem we present various applications of clouds.     

Geometry and asymptotics of wavefronts

Methods of convex analysis and differential geometry are applied to the study of properties of nonconvex sets in the plane. Constructions of the theory of α-sets are used as a tool for investigation of problems of the control theory and the theory of differential games. The notions of the bisector and of a pseudovertex of a set introduced in the paper, which allow ones to study the geometry of sets and compute their measure of nonconvexity, are of independent interest. These notions are also useful in studies of evolution of sets of attainability of controllable systems and in constructing of wavefronts. In this paper, we develop a numerically-analytical approach to finding pseudovertices of a curve, computation of the measure of nonconvexity of a plane set, and constructing front sets on the basis these data.In the paper, we give the results of numerical constructing of bisectors and wavefronts for plane sets. We demonstrate the relation between nonsmoothness of wavefronts and singularity of the geometry of the initial set. We also single out a class of sets whose bisectors have an asymptote.     

An incremental clustering algorithm based on hyperbolic smoothing

Clustering is an important problem in data mining. It can be formulated as a nonsmooth, nonconvex optimization problem. For the most global optimization techniques this problem is challenging even in medium size data sets. In this paper, we propose an approach that allows one to apply local methods of smooth optimization to solve the clustering problems. We apply an incremental approach to generate starting points for cluster centers which enables us to deal with nonconvexity of the problem. The hyperbolic smoothing technique is applied to handle nonsmoothness of the clustering problems and to make it possible application of smooth optimization algorithms to solve them. Results of numerical experiments with eleven real-world data sets and the comparison with state-of-the-art incremental clustering algorithms demonstrate that the smooth optimization algorithms in combination with the incremental approach are powerful alternative to existing clustering algorithms.     

On Nonconvexity of Graphs of Polynomials of Several Real Variables

We consider transversal (orthogonal) perturbations of finite-dimensional convex sets and estimate the degree of nonconvexity of resulting sets, i.e. we estimate the nonconvexity of graphs of continuous functions. We prove that a suitable estimate of nonconvexity of graphs over all lines induces a nice estimate of the nonconvexity of graphs of the entire function. Here, the term nice means that in the well-known Michael selection theorem it is possible to replace convex sets of a multivalued mapping by such nonconvex sets. As a corollary, we obtain positive results for polynomials of degree two under some restrictions on coefficients. Our previous results concerned the polynomials of degree one and Lipschitz functions. We show that for a family of polynomials of degree three such estimate of convexity in general does not exist. Moreover, for degree 9 we show that the nonconvexity of the unique polynomial P(x,y)=x⁹+x³y realizes the worst possible case.     

The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation

We propose an inexact proximal bundle method for constrained nonsmooth nonconvex optimization problems whose objective and constraint functions are known through oracles which provide inexact information. The errors in function and subgradient evaluations might be unknown, but are merely bounded. To handle the nonconvexity, we first use the redistributed idea, and consider even more difficulties by introducing inexactness in the available information. We further examine the modified improvement function for a series of difficulties caused by the constrained functions. The numerical results show the good performance of our inexact method for a large class of nonconvex optimization problems. The approach is also assessed on semi-infinite programming problems, and some encouraging numerical experiences are provided.     

Robust support vector regression with generic quadratic nonconvex ε-insensitive loss

In this paper, we propose a robust support vector regression with a novel generic nonconvex quadratic ε-insensitive loss function. The proposed method is robust to outliers or noise since it can adaptively control the loss value and decrease the negative influence of outliers or noise on the decision function by adjusting the elastic interval parameter and adaptive robustification parameter. Given the nature of the nonconvexity of the optimization problem, a concave-convex programming procedure is employed to solve the proposed problem. Experimental results on two artificial data sets and three real-world data sets indicate that the proposed method outperforms support vector regression, L₁-norm support vector regression, least squares support vector regression, robust least squares support vector regression, and support vector regression with the Huber loss function on both robustness and generalization ability.     

Non-Convex Global Minimization and False Discovery Rate Control for the TREX

The TREX is a recently introduced method for performing sparse high-dimensional regression. Despite its statistical promise as an alternative to the lasso, square-root lasso, and scaled lasso, the TREX is computationally challenging in that it requires solving a nonconvex optimization problem. This article shows a remarkable result: despite the nonconvexity of the TREX problem, there exists a polynomial-time algorithm that is guaranteed to find the global minimum. This result adds the TREX to a very short list of nonconvex optimization problems that can be globally optimized (principal components analysis being a famous example). After deriving and developing this new approach, we demonstrate that (i) the ability of the preexisting TREX heuristic to reach the global minimum is strongly dependent on the difficulty of the underlying statistical problem, (ii) the new polynomial-time algorithm for TREX permits a novel variable ranking and selection scheme, (iii) this scheme can be incorporated into a rule that controls the false discovery rate (FDR) of included features in the model. To achieve this last aim, we provide an extension of the results of Barber and Candes to establish that the knockoff filter framework can be applied to the TREX. This investigation thus provides both a rare case study of a heuristic for nonconvex optimization and a novel way of exploiting nonconvexity for statistical inference.     

一类改进的非凸二次规划有效集方法

一类改进的非凸二次规划有效集方法修乃华（河北师范学院数学系）ＡＣＬＡＳＳＯＦＩＭＰＲＯＶＥＤＡＣＴＩＶＥＳＥＴＭＥＴＨＯＤＳＦＯＲＮＯＮＣＯＮＶＥＸＱＵＡＤＲＡＴＩＣＰＲＯＧＲＡＭＭＩＮＧＰＲＯＢＬＥＭ￥ＸｉｕＮａｉ－ｈｕａ（Ｄｅｐｔ．ｏｆＭａｔｈ．...     

D.C. Representability of closed sets in reflexive Banach spaces and applications to optimization problems

A closed subsetM of a Hausdorff locally convex space is called d.c. representable if there are an extended-real valued lsc convex functionf and a continuous convex functionh such that $$M = \{ x \in X:f(x) - h(x) \leqslant 0\} .$$ Using the existence of a locally uniformly convex norm, we prove that any closed subset in a reflexive Banach space is d.c. representable. For d.c. representable subsets, we define an index of nonconvexity, which can be regarded as an indicator for the degree of nonconvexity. In fact, we show that a convex closed subset is weakly closed when it has a finite index of nonconvexity, and optimization problems on closed subsets with a low index of nonconvexity are less difficult from the viewpoint of computation.     

On a Branch and Bound Algorithm for the Solution of a Family of Softening Material Problems of Mechanics with Applications to the Analysis of Metallic Structures

The variational formulation of mechanical problems involving nonmonotone,possibly multivalued, material or boundary laws leads to hemivariationalinequalities. The solutions of the hemivariational inequalities constitutesubstationarity points of the related energy (super)potentials. For theircomputation convex and global optimization algorithms have been proposedinstead of the earlier nonlinear optimization methods, due to the lack ofsmoothness and convexity of the potential. In earlier works one of us hasproposed an approach based on the decomposition of the solutions space intoconvex parts resulting in a sequence of convex optimization subproblems withdifferent feasible sets. In this case nonconvexity of the potential wasattributed to (generalized) gradient jumps. In order to treat softeningmaterial effects, in the present paper this method is extended to cover alsoenergy functionals where nonconvexity is caused by the existence of concavesections. The nonconvex minimization problem is formulated as d.c.(difference convex) minimization and an algorithm of the branch and boundtype based on simplex partitions is adapted for its treatment. Thepartitioning scheme employed here is adapted to the large dimension of theproblem and the approximation steps are equivalent to convex minimizationsubproblems of the same structure as the ones arising in unilateral problemsof mechanics. The paper concludes with a numerical example and a discussionof the properties and the applicability of the method.     

An Iterative Coordinate Descent Algorithm for High-Dimensional Nonconvex Penalized Quantile Regression

We propose and study a new iterative coordinate descent algorithm (QICD) for solving nonconvex penalized quantile regression in high dimension. By permitting different subsets of covariates to be relevant for modeling the response variable at different quantiles, nonconvex penalized quantile regression provides a flexible approach for modeling high-dimensional data with heterogeneity. Although its theory has been investigated recently, its computation remains highly challenging when p is large due to the nonsmoothness of the quantile loss function and the nonconvexity of the penalty function. Existing coordinate descent algorithms for penalized least-squares regression cannot be directly applied. We establish the convergence property of the proposed algorithm under some regularity conditions for a general class of nonconvex penalty functions including popular choices such as SCAD (smoothly clipped absolute deviation) and MCP (minimax concave penalty). Our Monte Carlo study confirms that QICD substantially improves the computational speed in the p ? n setting. We illustrate the application by analyzing a microarray dataset.     

Nonlinear Stability of Stationary Discrete Shocks for Nonconvex Scalar Conservation Laws

This paper is to study the asymptotic stability of stationary discrete shocks for the Lax-Friedrichs scheme approximating nonconvex scalar conservation laws, provided that the summations of the initial perturbations equal to zero. The result is proved by using a weighted energy method based on the nonconvexity. Moreover, the stability is also obtained. The key points of our proofs are to choose a suitable weight function.

     

Local convexity and starshaped sets

Previously [7] we proved among other results that a closed connected set inE _n which has a unique point of local nonconvexity is starshaped. Here we characterize a fairly large class of plane sets whose points of local nonconvexity are so arranged that starshapedness follows. This theory determines as a special case the simple closed polygonal regions which are starshaped. In order to proceed simply we utilize the following notations and definitions. The preparation of this paper was supported in part by NSF Grant GP-1988.     

A sequential method for a class of box constrained quadratic programming problems

The aim of this paper is to propose an algorithm, based on the optimal level solutions method, which solves a particular class of box constrained quadratic problems. The objective function is given by the sum of a quadratic strictly convex separable function and the square of an affine function multiplied by a real parameter. The convexity and the nonconvexity of the problem can be characterized by means of the value of the real parameter. Within the algorithm, some global optimality conditions are used as stopping criteria, even in the case of a nonconvex objective function. The results of a deep computational test of the algorithm are also provided. This paper has been partially supported by M.I.U.R.     

On the Relation between the Nonconvexity of a Set and the Nonconvexity of Its ɛ-Neighborhoods

To each closed subset P of a Banach space, a real function characterizing the nonconvexity of this set is associated. Inequalities of the type _P(.),)< \nomathbreak an extensor, etc. In this paper, examples of sets whose nonconvexity functions substantially differ from the nonconvexity functions of arbitrarily small neighborhoods of these sets are constructed. On the other hand, it is shown that, in uniformly convex Banach spaces, conditions of the type the function of nonconvexity is less than one are stable with respect to taking -neighborhoods of sets.     

Generalizations of fixed point theorems and computation

As a powerful mechanism, fixed point theorems have many applications in mathematical and economic analysis. In this paper, the well-known Brouwer fixed point theorem and Kakutani fixed point theorem are generalized to a class of nonconvex sets and a globally convergent homotopy method is developed for computing fixed points on this class of nonconvex sets.     

Minimizing the sum of a convex function and a specially structured nonconvex function

A lineraly constrained global optimization problem is studied, where the objective function is the saum of a convex function g(x)a nd a nonconvex function f(x) satisfying a rank two condition. Roughly speaking, the latter means that all the nonconvexity of f(x) is concentrated on a linear manifold of dimension 2. A solution method based on exploiting this special structure is prop     

组合同伦方法在无界域上的收敛性

组合同伦内点法由Feng等提出，是求解有界区域上的非凸数学规划的一种大范围收敛性方法，本文证明此算法适用于某些无界区域上的非凸数学规划问题。     

Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games

The noncooperative multi-leader-follower game can be formulated as a generalized Nash equilibrium problem where each player solves a nonconvex mathematical program with equilibrium constraints. Two major deficiencies exist with such a formulation: One is that the resulting Nash equilibrium may not exist, due to the nonconvexity in each players problem; the other is that such a nonconvex Nash game is computationally intractable. In order to obtain a viable formulation that is amenable to practical solution, we introduce a class of remedial models for the multi-leader-follower game that can be formulated as generalized Nash games with convexified strategy sets. In turn, a game of the latter kind can be formulated as a quasi-variational inequality for whose solution we develop an iterative penalty method. We establish the convergence of the method, which involves solving a sequence of penalized variational inequalities, under a set of modest assumptions. We also discuss some oligopolistic competition models in electric power markets that lead to multi-leader-follower games.Jong-Shi Pang: The work of this authors research was partially supported by the National Science Foundation under grant CCR-0098013 and ECS-0080577 and by the Office of Naval Research under grant N00014-02-1-0286.Masao Fukushima: The work of this authors research was partially supported by a Grant-in-Aid for Scientific Research from the Ministry of Education, Science, Culture and Sports of Japan.     

Unified approach to some geometric results in variational analysis

Based on a study of a minimization problem, we present the following results applicable to possibly nonconvex sets in a Banach space: an approximate projection result, an extended extremal principle, a nonconvex separation theorem, a generalized Bishop-Phelps theorem and a separable point result. The classical result of Dieudonné (on separation of two convex sets in a finite-dimensional space) is also extended to a nonconvex setting.