A class of problems where dual bounds beat underestimation bounds

We investigate the problem of minimizing a nonconvex function with respect to convex constraints, and we study different techniques to compute a lower bound on the optimal value: The method of using convex envelope functions on one hand, and the method of exploiting nonconvex duality on the other hand. We investigate which technique gives the better bound and develop conditions under which the dual bound is strictly better than the convex envelope bound. As a byproduct, we derive some interesting results on nonconvex duality.     

Delay Perturbed Sweeping Process

This paper is devoted to the study of a nonconvex perturbed sweeping process with time delay in the infinite dimensional setting. On the one hand, the moving subset involved is assumed to be prox-regular and to move in an absolutely continuous way. On the other hand, the perturbation which contains the delay is single-valued, separately measurable, and separately Lipschitz. We prove, without any compactness assumption, that the problem has one and only one solution.     

Impulsive Boundary Value Problems for First-order Ordinary Differential Inclusions

In this paper, we investigate the existence of solutions for impulsive first order ordinary differential inclusions which admitting nonconvex valued right hand side. We present two classes of results. In the first one, we rely on a fixed point theorem for contraction multivalued maps due to Covitz and Nadler, and for the second one, we use Schacfer＇s fixed point theorem combined with lower semi-continuous multivalued operators with decomposable values under weaker conditions.     

Index information algorithm with local tuning for solving multidimensional global optimization problems with multiextremal constraints

 Multidimensional optimization problems where the objective function and the constraints are multiextremal non-differentiable Lipschitz functions (with unknown Lipschitz constants) and the feasible region is a finite collection of robust nonconvex subregions are considered. Both the objective function and the constraints may be partially defined. To solve such problems an algorithm is proposed, that uses Peano space-filling curves and the index scheme to reduce the original problem to a H?lder one-dimensional one. Local tuning on the behaviour of the objective function and constraints is used during the work of the global optimization procedure in order to accelerate the search. The method neither uses penalty coefficients nor additional variables. Convergence conditions are established. Numerical experiments confirm the good performance of the technique. Received: April 2002 / Accepted: December 2002 Published online: March 21, 2003 RID="⋆" ID="⋆" This research was supported by the following grants: FIRB RBNE01WBBB, FIRB RBAU01JYPN, and RFBR 01–01–00587. Key Words. global optimization – multiextremal constraints – local tuning – index approach     

An axiomatization of the inner core

We axiomatize the inner core in a similar way as the one proposed by Aumann (1985) in order to characterize the NTU value. Received: March 2002/Revised: March 2003     

Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods

The paper extends prior work by the authors on loqo, an interior point algorithm for nonconvex nonlinear programming. The specific topics covered include primal versus dual orderings and higher order methods, which attempt to use each factorization of the Hessian matrix more than once to improve computational efficiency. Results show that unlike linear and convex quadratic programming, higher order corrections to the central trajectory are not useful for nonconvex nonlinear programming, but that a variant of Mehrotra’s predictor-corrector algorithm can definitely improve performance. Received: May 3, 1999 / Accepted: January 24, 2000?Published online March 15, 2000     

Algebraic unimodular counting

 We study algebraic algorithms for expressing the number of non-negative integer solutions to a unimodular system of linear equations as a function of the right hand side. Our methods include Todd classes of toric varieties via Gr?bner bases, and rational generating functions as in Barvinok's algorithm. We report polyhedral and computational results for two special cases: counting contingency tables and Kostant's partition function. Received: April 23, 2001 / Accepted: October 2001 Published online: March 28, 2003 Mathematics Subject Classification (1991): 52B11, 52B55, 90C57, 14Q99     

Iterative algorithms for systems of extended regularized nonconvex variational inequalities and fixed point problems

This paper points out some fatal errors in the equivalent formulations used in Noor 2011 [Noor MA. Projection iterative methods for solving some systems of general nonconvex variational inequalities. Applied Analysis. 2011;90:777–786] and consequently in Noor 2009 [Noor MA. System of nonconvex variational inequalities. Journal of Advanced Research Optimization. 2009;1:1–10], Noor 2010 [Noor MA, Noor KI. New system of general nonconvex variational inequalities. Applied Mathematics E-Notes. 2010;10:76–85] and Wen 2010 [Wen DJ. Projection methods for a generalized system of nonconvex variational inequalities with different nonlinear operators. Nonlinear Analysis. 2010;73:2292–2297]. Since these equivalent formulations are the main tools to suggest iterative algorithms and to establish the convergence results, the algorithms and results in the aforementioned articles are not valid. It is shown by given some examples. To overcome with the problems in these papers, we consider a new system of extended regularized nonconvex variational inequalities, and establish the existence and uniqueness result for a solution of the aforesaid system. We suggest and analyse a new projection iterative algorithm to compute the unique solution of the system of extended regularized nonconvex variational inequalities which is also a fixed point of a nearly uniformly Lipschitzian mapping. Furthermore, the convergence analysis of the proposed iterative algorithm under some suitable conditions is studied. As a consequence, we point out that one can derive the correct version of the algorithms and results presented in the above mentioned papers.     

On the convexification of nonlinear programming problems: An applications-oriented survey

Some important classes of decision models give rise to nonconvex minimization problems that, by domain or range transformation, are transformable into convex problems. Thus the powerful theoretical results and the efficiency of algorithms in convex programming can be exploited for a wide range of problems. If no convexifying transformation is at hand, one often requires to approximate a nonconvex objective by a convex one. Then a priori as well as post-computational errorbounds are of interest. The purpose of this paper is to outline briefly some of the ideas and results on convexification that may be useful in practice.     

Capacities of quantum channels and how to find them

 We survey what is known about the information transmitting capacities of quantum channels, and give a proposal for how to calculate some of these capacities using linear programming. Received: March 14, 2003 / Accepted: April 14, 2003 Published online: June 5, 2003     

Convex underestimation for posynomial functions of positive variables

The approximation of the convex envelope of nonconvex functions is an essential part in deterministic global optimization techniques (Floudas in Deterministic Global Optimization: Theory, Methods and Application, 2000). Current convex underestimation algorithms for multilinear terms, based on arithmetic intervals or recursive arithmetic intervals (Hamed in Calculation of bounds on variables and underestimating convex functions for nonconvex functions, 1991; Maranas and Floudas in J Global Optim 7:143–182, (1995); Ryoo and Sahinidis in J Global Optim 19:403–424, (2001)), introduce a large number of linear cuts. Meyer and Floudas (Trilinear monomials with positive or negative domains: Facets of convex and concave envelopes, pp. 327–352, (2003); J Global Optim 29:125–155, (2004)), introduced the complete set of explicit facets for the convex and concave envelopes of trilinear monomials with general bounds. This study proposes a novel method to underestimate posynomial functions of strictly positive variables.     

Effective transverse elastic moduli of composites at non-dilute concentration of a random field of aligned fibers

We consider a transversal loading of a linearly elastic isotropic media containing the identical isotropic aligned circular fibers at non-dilute concentration c. By the use of solution obtained by the Kolosov–Muskhelishvili complex potential method for two interacting circles subjected to three different applied stresses at infinity, and exact integral representations for both the stress and strain distributions in a microinhomogeneous medium, one estimates the effective moduli of the composite accurately to order c². Received: March 4, 2003; revised: August 8, 2003     

Manifolds with quadratic curvature decay and fast volume growth

 We give sufficient conditions for a noncompact Riemannian manifold, which has quadratic curvature decay, to have finite topological type with ends that are cones over spherical space forms. Received: 21 March 2001 / Revised version: 21 March 2002 / Published online: 10 February 2003 Research partially supported by NSF grant DMS-0072154 and MSRI     

A fixed-point iteration approach for multibody dynamics with contact and small friction

Acceleration–force setups for multi-rigid-body dynamics are known to be inconsistent for some configurations and sufficiently large friction coefficients (a Painleve paradox). This difficulty is circumvented by time-stepping methods using impulse-velocity approaches, which solve complementarity problems with possibly nonconvex solution sets. We show that very simple configurations involving two bodies may have a nonconvex solution set for any nonzero value of the friction coefficient. We construct two fixed-point iteration algorithms that solve convex subproblems and that are guaranteed, for sufficiently small friction coefficients, to retrieve, at a linear convergence rate, the unique velocity solution of the nonconvex linear complementarity problem whenever the frictionless configuration can be disassembled. In addition, we show that one step of one of the iterative algorithms provides an excellent approximation to the velocity solution of the original, possibly nonconvex, problem if for all contacts we have that either the friction coefficient is small or the slip velocity is small.Subject Index. 70E55, 75M10, 75M15, 90C33A partial version of this work has appeared in the proceedings of the NATO Advanced Studies Institute on Virtual Nonlinear Multibody Systems, Prague, 2002.     

States of a one dimensional quantum crystal

We construct states on a C-algebra associated to a one dimensional lattice crystal. We also compute the mean value of an observable, not necessarily bounded, such as the dilation coefficient. This implies on one hand, a careful analysis of the heat kernel of the Hamiltonian associated to the crystal and, on the other hand, the study of the quantum correlations of two observables associated to two clusters of particules. To cite this article: L. Amour et al., C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

A geometric study of duality gaps, with applications

Lagrangian relaxation is often an efficient tool to solve (large-scale) optimization problems, even nonconvex. However it introduces a duality gap, which should be small for the method to be really efficient. Here we make a geometric study of the duality gap. Given a nonconvex problem, we formulate in a first part a convex problem having the same dual. This formulation involves a convexification in the product of the three spaces containing respectively the variables, the objective and the constraints. We apply our results to several relaxation schemes, especially one called “Lagrangean decomposition” in the combinatorial-optimization community, or “operator splitting” elsewhere. We also study a specific application, highly nonlinear: the unit-commitment problem. Received: June 1997 / Accepted: December 2000?Published online April 12, 2001     

A sharp isoperimetric inequality for rank one symmetric spaces

 We prove an isoperimetric inequality for compact, regular domains in rank one symmetric spaces, which is sharp for geodesic balls. Besides volume and area of a given domain, some weak information about the second fundamental form of its boundary is involved. Received: 2 September 2002 / Revised version: 10 December 2002 Published online: 20 March 2003 Mathematics Subject Classification (2000): 53C35, 52A40, 51M25     

On duality theory for non-convex semidefinite programming

In this paper, with the help of convex-like function, we discuss the duality theory for nonconvex semidefinite programming. Our contributions are: duality theory for the general nonconvex semidefinite programming when Slater’s condition holds; perfect duality for a special case of the nonconvex semidefinite programming for which Slater’s condition fails. We point out that the results of Fan (Appl. Math. Lett. 18:1068–1073, 2005) can be regarded as a special case of our result.