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.     

Procedures for calculating the nonconvexity measures of a plane set

The geometry of nonconvex sets is analyzed. The measure of nonconvexity of a closed set that has the sense of an angle is considered. Characteristic manifolds of nonconvex sets are constructed. Procedures for calculating the measure of nonconvexity are proposed for a class of plane sets.     

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.     

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.     

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.     

Successive approximation and linear stability involving convergent sequences of optimization problems

A certain convergence notion for extended real-valued functions, which has been studied by a number of authors in various applied contexts since the latter 1960s, is examined here in relation to abstract optimization problems in normed linear spaces. The main facts concerning behavior of the optimal values, the optimal solution sets and the -optimal solution sets corresponding to “convergent” sequences of such problems are developed. General linear perturbations are incorporated explicitly into the problems of the sequence, lending a stability-theoretic character to the results. Most of the results apply to nonconvex minimization.     

Minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint

In this paper, we consider the problem of minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint. A key difficulty with this problem is its nonconvexity. Using Lagrange duality, we show that under a mild assumption, this problem can be solved by solving a linearly constrained convex univariate minimization problem. Finally, the superior efficiency of the new approach compared to the known semidefinite relaxation and a known approach from the literature is demonstrated by solving several randomly generated test problems.     

Complete Solutions and Extremality Criteria to Polynomial Optimization Problems

This paper presents a set of complete solutions to a class of polynomial optimization problems. By using the so-called sequential canonical dual transformation developed in the author’s recent book [Gao, D.Y. (2000), Duality Principles in Nonconvex Systems: Theory, Method and Applications, Kluwer Academic Publishers, Dordrecht/Boston/London, xviii + 454 pp], the nonconvex polynomials in can be converted into an one-dimensional canonical dual optimization problem, which can be solved completely. Therefore, a set of complete solutions to the original problem is obtained. Both global minimizer and local extrema of certain special polynomials can be indentified by Gao-Strang’s gap function and triality theory. For general nonconvex polynomial minimization problems, a sufficient condition is proposed to identify global minimizer. Applications are illustrated by several examples.     

AnR danalogue of Valentine’s theorem on 3-convex sets

This paper deals with anR ^danalogue of a theorem of Valentine which states that a closed 3-convex setS in the plane is decomposable into 3 or fewer closed convex sets. In Valentine’s proof, the points of local nonconvexity ofS are treated as vertices of a polygonP contained in the kernel ofS, yielding a decomposition ofS into 2 or 3 convex sets, depending on whetherP has an even or odd number of edges. Thus the decomposition actually depends onc(P′), the chromatic number of the polytopeP′ dual toP. A natural analogue of this result is the following theorem: LetS be a closed subset ofR ^d, and letQ denote the set of points of local nonconvexity ofS. We require thatQ be contained in the kernel ofS and thatQ coincide with the set of points in the union of all the (d − 2)-dimensional faces of somed-dimensional polytopeP. ThenS is decomposable intoc(P′) closed convex sets.     

Convexity and a certain propertyP m

The propertyP _m (directly analogous to Valentine’s propertyP ₃) is used to prove several curious results concerning subsets of a topological linear space, among them the following: (a) If a closed setS has propertyP _m and containsk points of local nonconvexity no distinct pair of which can see each other viaS, thenS is the union ofm − k − 1 or fewer starshaped sets. (b) Any closed connected set with propertyP _m is polygonally connected. (c) A closed connected setS with propertyP _m is anL _m−1 set (each pair of points may be joined by a polygonal arc ofm − 1 of fewer sides inS). (d) A finite-dimensional set with propertyP _m is anL _{2m − 3} set. A new proof of Tietze’s theorem on locally convex sets is given, and various examples refute certain plausible conjectures.     

Connectedness of efficient points in convex and convex transformable vector optimization

Given a convex vector optimization problem with respect to a closed ordering cone, we show the connectedness of the efficient and properly efficient sets. The Arrow–Barankin–Blackwell theorem is generalized to nonconvex vector optimization problems, and the connectedness results are extended to convex transformable vector optimization problems. In particular, we show the connectedness of the efficient set if the target function f is continuously transformable, and of the properly efficient set if f is differentiably transformable. Moreover, we show the connectedness of the efficient and properly efficient sets for quadratic quasiconvex multicriteria optimization problems.     

A General Nonconvex Multiduality Principle

We introduce a (possibly infinite) collection of mutually dual nonconvex optimization problems, which share a common optimal value, and give a characterization of their global optimal solutions. As immediate consequences of our general multiduality principle, we obtain Toland–Singer duality theorem as well as an analogous result involving generalized perspective functions. Based on our duality theory, we propose an extension of an existing algorithm for the minimization of d.c. functions, which exploits Toland–Singer duality, to a more general class of nonconvex optimization problems.     

Solutions to quadratic minimization problems with box and integer constraints

This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer constraints. Results show that under Gao and Strang’s general global optimality condition, these well-known nonconvex and discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique. Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite programming method is revealed.     

Convexification, Concavification and Monotonization in Global Optimization

We show in this paper that via certain convexification, concavification and monotonization schemes a nonconvex optimization problem over a simplex can be always converted into an equivalent better-structured nonconvex optimization problem, e.g., a concave optimization problem or a D.C. programming problem, thus facilitating the search of a global optimum by using the existing methods in concave minimization and D.C. programming. We first prove that a monotone optimization problem (with a monotone objective function and monotone constraints) can be transformed into a concave minimization problem over a convex set or a D.C. programming problem via pth power transformation. We then prove that a class of nonconvex minimization problems can be always reduced to a monotone optimization problem, thus a concave minimization problem or a D.C. programming problem.     

Weakly convex sets and modulus of nonconvexity

We consider a definition of a weakly convex set which is a generalization of the notion of a weakly convex set in the sense of Vial and a proximally smooth set in the sense of Clarke, from the case of the Hilbert space to a class of Banach spaces with the modulus of convexity of the second order. Using the new definition of the weakly convex set with the given modulus of nonconvexity we prove a new retraction theorem and we obtain new results about continuity of the intersection of two continuous set-valued mappings (one of which has nonconvex images) and new affirmative solutions of the splitting problem for selections. We also investigate relationship between the new definition and the definition of a proximally smooth set and a smooth set.     

Hidden Convex Minimization

A class of nonconvex minimization problems can be classified as hidden convex minimization problems. A nonconvex minimization problem is called a hidden convex minimization problem if there exists an equivalent transformation such that the equivalent transformation of it is a convex minimization problem. Sufficient conditions that are independent of transformations are derived in this paper for identifying such a class of seemingly nonconvex minimization problems that are equivalent to convex minimization problems. Thus, a global optimality can be achieved for this class of hidden convex optimization problems by using local search methods. The results presented in this paper extend the reach of convex minimization by identifying its equivalent with a nonconvex representation.     

A generalized duality and applications

The aim of this paper is to present a nonconvex duality with a zero gap and its connection with convex duality. Since a convex program can be regarded as a particular case of convex maximization over a convex set, a nonconvex duality can be regarded as a generalization of convex duality. The generalized duality can be obtained on the basis of convex duality and minimax theorems. The duality with a zero gap can be extended to a more general nonconvex problems such as a quasiconvex maximization over a general nonconvex set or a general minimization over the complement of a convex set. Several applications are given.On leave from the Institute of Mathematics, Hanoi, Vietnam.     

Convexification procedures and decomposition methods for nonconvex optimization problems

In order for primal-dual methods to be applicable to a constrained minimization problem, it is necessary that restrictive convexity conditions are satisfied. In this paper, we consider a procedure by means of which a nonconvex problem is convexified and transformed into one which can be solved with the aid of primal-dual methods. Under this transformation, separability of the type necessary for application of decomposition algorithms is preserved. This feature extends the range of applicability of such algorithms to nonconvex problems. Relations with multiplier methods are explored with the aid of a local version of the notion of a conjugate convex function.This work was carried out at the Coordinated Science Laboratory, University of Illinois, Urbana, Illinois, and was supported by the National Science Foundation under Grant ENG 74-19332.     

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.     

On sets having finitely many points of local nonconvexity and propertyP m

If a pointq ofS has the property that each neighborhood ofq contains pointsx andy such that the segmentxy is not contained byS, q is called a point of local nonconvexity ofS. LetQ denote the set of points of local nonconvexity ofS. Tietze’s well known theorem that a closed connected setS in a linear topological space is convex ifQ=φ is generalized in the result:If S is a closed set in a linear topological space such that S ∼ Q is connected and |Q|=n<∞,then S is the union of n+1or fewer closed convex sets. Letk be the minimal number of convex sets needed in a convex covering ofS. Bounds fork in terms ofm andn are obtained for sets having propertyP _m and |Q|=n.