On saddle points in nonconvex semi-infinite programming

In this paper we apply two convexification procedures to the Lagrangian of a nonconvex semi-infinite programming problem. Under the reduction approach it is shown that, locally around a local minimizer, this problem can be transformed equivalently in such a way that the transformed Lagrangian fulfills saddle point optimality conditions, where for the first procedure both the original objective function and constraints (and for the second procedure only the constraints) are substituted by their pth powers with sufficiently large power p. These results allow that local duality theory and corresponding numerical methods (e.g. dual search) can be applied to a broader class of nonconvex problems.     

A note on the existence of saddle points of p-th power Lagrangian for constrained nonconvex optimization

Li and Sun [D. Li and X.L. Sun, Existence of a saddle point in nonconvex constrained optimization, J. Global Optim. 21 (2001), pp. 39--50; D. Li and X.L. Sun, Convexification and existence of saddle point in a p-th-power reformulation for nonconvex constrained optimization, Nonlinear Anal. 47 (2001), pp. 5611--5622], present the existence of a global saddle point of the p-th power Lagrangian functions for constrained nonconvex optimization, under second-order sufficiency conditions and additional conditions that the feasible set is compact and the global solution of the primal problem is unique. In this article, it is shown that the same results can be obtained under additional assumptions that do not require the compactness of the feasible set and the uniqueness of global solution of the primal problem.     

Pseudo-duality and saddle points

Results associated with saddle-type stationary points are described. It is shown that barrier-type functions are pseudo-duals of generalized Lagrangian functions, while augmented Lagrangians are pseudo-duals of the regular Lagrangian function. An application of pseudo-duality to a min-max problem is illustrated, together with several other examples.     

Proper minimal points of nonconvex sets in Banach spaces in terms of the limiting normal cone

In this paper, proper minimal elements of a given nonconvex set in a real ordered Banach space are defined utilizing the limiting (Mordukhovich) normal cone. The newly defined points are called limiting proper minimal (LPM) points. It is proved that each LPM is a proper minimal in the sense of Borwein under some assumptions. The converse holds in Asplund spaces. The relation of LPM points with Benson, Henig, super and proximal proper minimal points are established. Under appropriate assumptions, it is proved that the set of robust elements is a subset of the set of LPM points, and the set of LPM points is dense in that of minimal points. Another part of the paper is devoted to scalarization-based and distance function-based characterizations of the LPM points. The paper is closed by some results about LPM solutions of a set-valued optimization problem via variational analysis tools. Clarifying examples are given in addition to the theoretical results.     

Computing proximal points of nonconvex functions

The proximal point mapping is the basis of many optimization techniques for convex functions. By means of variational analysis, the concept of proximal mapping was recently extended to nonconvex functions that are prox-regular and prox-bounded. In such a setting, the proximal point mapping is locally Lipschitz continuous and its set of fixed points coincide with the critical points of the original function. This suggests that the many uses of proximal points, and their corresponding proximal envelopes (Moreau envelopes), will have a natural extension from convex optimization to nonconvex optimization. For example, the inexact proximal point methods for convex optimization might be redesigned to work for nonconvex functions. In order to begin the practical implementation of proximal points in a nonconvex setting, a first crucial step would be to design efficient methods of approximating nonconvex proximal points. This would provide a solid foundation on which future design and analysis for nonconvex proximal point methods could flourish. In this paper we present a methodology based on the computation of proximal points of piecewise affine models of the nonconvex function. These models can be built with only the knowledge obtained from a black box providing, for each point, the function value and one subgradient. Convergence of the method is proved for the class of nonconvex functions that are prox-bounded and lower- ${\mathcal{C}}^2$ and encouraging preliminary numerical testing is reported.     

Remarks on solutions to a nonconvex quadratic programming test problem

A recent paper of Tuy and Hoai-Phuong published in JOGO (2007) 37:557–569 presents an algorithm for nonconvex quadratic programming with quadratic constraints. Performance of this algorithm is illustrated by solving, among others, a test problem from a paper of Audet, Hansen, Jaumard and Savard published in Mathematical Programming, Ser. A (2000) 87:131–152. This test problem is a reformulation of a problem from a paper of Dembo published in Mathematical Programming (1976) 10:192–213. Tuy and Hoai-Phuong observe that the optimal solution reported by Audet et al. is very far from the optimal one for this reformulation. The discrepancy between the reported optimal solutions is not due to selection of an almost feasible solution far from the optimal one nor to cumulation of termwise approximation errors. It is, in fact, simply due to a typographical error.     

Lagrange Multipliers and saddle points in multiobjective programming

In this paper, we present several conditions for the existence of a Lagrange multiplier or a weak saddle point in multiobjective optimization. Relations between a Lagrange multiplier and a weak saddle point are established. A sufficient condition is also given for the equivalence of the Benson proper efficiency and the Borwein proper efficiency.This research was supported by NSFC under Grant No. 78900011 and by BMADIS. The authors are grateful to two referees for supplying valuable comments and pointing out detailed corrections to the draft paper. The authors also wish to thank Dr. P. L. Yu for valuable comments and suggestions.The revised version of this paper was completed while the second author visited the Faculty of Technical Mathematics and Informatics, Delft University of Technology, Delft, The Netherlands.     

Separation theorems for nonconvex sets and application in optimization

The aim of this paper is to present separation theorems for two disjoint closed sets, without convexity condition. First, a separation theorem for a given closed cone and a point outside from this cone, is proved and then it is used to prove a separation theorem for two disjoint sets. Illustrative examples are provided to highlight the important aspects of these theorems. An application to optimization is also presented to prove optimality condition for a nonconvex optimization problem.     

Remarks about disjoint dominating sets

We prove several structural and hardness results concerning pairs of disjoint sets in graphs which are dominating or independent and dominating.     

Pseudo-similar points in ordered sets

Two points l and h in an ordered set P are called pseudo-similar iff P?{l} is isomorphic to P?{h} and there is no automorphism of P that maps l to h. This paper provides a characterization of ordered sets with at least two pseudo-similar points. Special attention is given to ordered sets with pseudo-similar points l and h so that one of the points is minimal and the other is maximal. These sets will play a key role in the reconstruction of the rank of the removed element in a non-extremal card.     

Remarks on exceptional points and differentiation bases

In spite of the Lebesgue density theorem, there is a positive \({\delta}\) such that, for every measurable set \({A \subset \mathbb{R}}\) with \({\lambda (A) > 0}\) and \({\lambda (\mathbb{R} \setminus A) > 0}\), there is a point at which both the lower densities of \({A}\) and of the complement of \({A}\) are at least \({\delta}\). The problem of determining the supremum of possible values of this \({\delta}\) was studied by V. I. Kolyada, A. Szenes and others. It seems that the authors considered this quantity a feature of density. We show that it is connected rather with a choice of a differentiation basis.