Attractive force search algorithm for piecewise convex maximization problems

We consider mathematical programming problems with the so-called piecewise convex objective functions. A solution method for this interesting and important class of nonconvex problems is presented. This method is based on Newton??s law of universal gravitation, multicriteria optimization and Helly??s theorem on convex bodies. Numerical experiments using well known classes of test problems on piecewise convex maximization, convex maximization as well as the maximum clique problem show the efficiency of the approach.     

Q-subdifferential and Q-conjugate for global optimality

Normal cone and subdifferential have been generalized through various continuous functions; in this article, we focus on a non separable Q-subdifferential version. Necessary and sufficient optimality conditions for unconstrained nonconvex problems are revisited accordingly. For inequality constrained problems, Q-subdifferential and the lagrangian multipliers, enhanced as continuous functions instead of scalars, allow us to derive new necessary and sufficient optimality conditions. In the same way, the Legendre-Fenchel conjugate is generalized into Q-conjugate and global optimality conditions are derived by Q-conjugate as well, leading to a tighter inequality.     

Piecewise convex formulations of binary and permutation problems

It is well known that the problem of maximization of any difference of convex functions can be turned into a convex maximization problem; here, the aim is a piecewise convex maximization problem instead. Although this may seem harder, sometimes the dimension may be reduced by 1, and the local search may be improved by using extreme points of the closure of the convex hull of better points. We show that it is always the case for both binary and permutation problems and give, as such instances, piecewise convex formulations for the maximum clique problem and the quadratic assignment problem.     

Piecewise Convex Maximization Problems: Piece Adding Technique

In this article, we provide a global search algorithm for maximizing a piecewise convex function F over a compact D. We propose to iteratively refine the function F at local solution y by a virtual cutting function p _y (⋅) and to solve max {min {F(x)−F(y),p _y (x)}∣x∈D} instead. We call this function either a patch, when it avoids returning back to the same local solutions, or a pseudo patch, when it possibly yields a better point. It is virtual in the sense that the role of cutting constraints is played by additional convex pieces in the objective function. We report some computational results, that represent an improvement on previous linearization based techniques.     

Piece adding technique for convex maximization problems

In this article we provide an algorithm, where to escape from a local maximum y of convex function f over D, we (locally) solve piecewise convex maximization max{min{f (x) − f (y), p _y (x)} | x ∈ D} with an additional convex function p _y (·). The last problem can be seen as a strictly convex improvement of the standard cutting plane technique for convex maximization. We report some computational results, that show the algorithm efficiency.     

Piecewise-Convex Maximization Problems

A function F:Rⁿ R is called a piecewise convex function if it can be decomposed into , where f _j:Rⁿ R is convex for all jM={1,2...,m}. We consider subject to xD. It generalizes the well-known convex maximization problem. We briefly review global optimality conditions for convex maximization problems and carry one of them to the piecewise-convex case. Our conditions are all written in primal space so that we are able to proposea preliminary algorithm to check them.     

Team decision theory and integral equations

The coordination of decisions under uncertainty in a team leads to optimality conditions that are integral equations. A specific example of a two-division firm is developed to illustrate these conditions. Numerical imbedding techniques are used to solve the firm's decision problem. Extensions toward more general techniques and applications are indicated.     

Testing the ℜ- strategy for a Reverse Convex Problem

This paper is devoted to solving a reverse-convex problem. The approach presented here is based on Global Optimality Conditions. We propose a general conception of a Global Search Algorithm and develop each part of it. The results of numerical experiments with the dimension up to 400 are also given. This revised version was published online in July 2006 with corrections to the Cover Date.