On perturbations of certain nonconvex optimization problems

Using the concept of -conjugate functions, a wide class of nonconvex optimization problems can be investigated. By generalized Lagrangians, the problems indicated and a generalized notion of stability can be treated. It is possible to give duality theorems for these problems such that the approach given by Rockafellar (1967) for convex problems can be extended to the nonconvex case.     

A note on functions whose local minima are global

In this note, a simple proof of a theorem concerning functions whose local minima are global is presented and some closedness properties of this class of functions are discussed.The authors would like to thank Dr. Tatsuro Ichiishi of CORE for outlining the new proof of Theorem 2.1.This research was done while the author was a research fellow at the Center for Operations Research and Econometrics, University of Louvain, Heverlee, Belgium.     

Global Optimization Issues in Multiparametric Continuous and Mixed-Integer Optimization Problems

In this paper, a number of theoretical and algorithmic issues concerning the solution of parametric nonconvex programs are presented. In particular, the need for defining a suitable overestimating subproblem is discussed in detail. The multiparametric case is also addressed, and a branch and bound (B&B) algorithm for the solution of parametric nonconvex programs is proposed.     

A new reformulation-linearization technique for bilinear programming problems

This paper is concerned with the development of an algorithm for general bilinear programming problems. Such problems find numerous applications in economics and game theory, location theory, nonlinear multi-commodity network flows, dynamic assignment and production, and various risk management problems. The proposed approach develops a new Reformulation-Linearization Technique (RLT) for this problem, and imbeds it within a provably convergent branch-and-bound algorithm. The method first reformulates the problem by constructing a set of nonnegative variable factors using the problem constraints, and suitably multiplies combinations of these factors with the original problem constraints to generate additional valid nonlinear constraints. The resulting nonlinear program is subsequently linearized by defining a new set of variables, one for each nonlinear term. This RLT process yields a linear programming problem whose optimal value provides a tight lower bound on the optimal value to the bilinear programming problem. Various implementation schemes and constraint generation procedures are investigated for the purpose of further tightening the resulting linearization. The lower bound thus produced theoretically dominates, and practically is far tighter, than that obtained by using convex envelopes over hyper-rectangles. In fact, for some special cases, this process is shown to yield an exact linear programming representation. For the associated branch-and-bound algorithm, various admissible branching schemes are discussed, including one in which branching is performed by partitioning the intervals for only one set of variables x or y, whichever are fewer in number. Computational experience is provided to demonstrate the viability of the algorithm. For a large number of test problems from the literature, the initial bounding linear program itself solves the underlying bilinear programming problem.This paper was presented at the II. IIASA Workshop on Global Optimization, Sopron (Hungary), December 9–14, 1990.     

Optimization based DC programming and DCA for hierarchical clustering

One of the most promising approaches for clustering is based on methods of mathematical programming. In this paper we propose new optimization methods based on DC (Difference of Convex functions) programming for hierarchical clustering. A bilevel hierarchical clustering model is considered with different optimization formulations. They are all nonconvex, nonsmooth optimization problems for which we investigate attractive DC optimization Algorithms called DCA. Numerical results on some artificial and real-world databases are reported. The results demonstrate that the proposed algorithms are more efficient than related existing methods.     

Errata Corrige: On an Optimality Condition in DC Optimization

We take care of an omission in Proposition 4.4 of Ref. 1.     

A new efficient algorithm based on DC programming and DCA for clustering

In this paper, a version of K-median problem, one of the most popular and best studied clustering measures, is discussed. The model using squared Euclidean distances terms to which the K-means algorithm has been successfully applied is considered. A fast and robust algorithm based on DC (Difference of Convex functions) programming and DC Algorithms (DCA) is investigated. Preliminary numerical solutions on real-world databases show the efficiency and the superiority of the appropriate DCA with respect to the standard K-means algorithm.      

Combining latent learning with dynamic programming in the modular anticipatory classifier system

Learning Classifier Systems (LCS) are rule based Reinforcement Learning (RL) systems which use a generalization capability. In this paper, we highlight the differences between two kinds of LCSs. Some are used to directly perform RL while others latently learn a model of the interactions between the agent and its environment. Such a model can be used to speed up the core RL process. Thus, these two kinds of learning processes are complementary. We show here how the notion of generalization differs depending on whether the system anticipates (like Anticipatory Classifier System (ACS) and Yet Another Classifier System (YACS)) or not (like XCS). Moreover, we show some limitations of the formalism common to ACS and YACS, and propose a new system, called Modular Anticipatory Classifier System (MACS), which allows the latent learning process to take advantage of new regularities. We describe how the model can be used to perform active exploration and how this exploration may be aggregated with the policy resulting from the reinforcement learning process. The different algorithms are validated experimentally and some limitations in presence of uncertainties are highlighted.     

A secret sharing scheme based on cellular automata

A new secret sharing scheme based on a particular type of discrete delay dynamical systems: memory cellular automata, is proposed. Specifically, such scheme consists of a (k, n)-threshold scheme where the text to be shared is considered as one of the k initial conditions of the memory cellular automata and the n shares to be distributed are n consecutive configurations of the evolution of such cellular automata. It is also proved to be perfect and ideal.     

Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations

We show that SDP (semidefinite programming) and SOCP (second order cone programming) relaxations provide exact optimal solutions for a class of nonconvex quadratic optimization problems. It is a generalization of the results by S. Zhang for a subclass of quadratic maximization problems that have nonnegative off-diagonal coefficient matrices of quadratic objective functions and diagonal coefficient matrices of quadratic constraint functions. A new SOCP relaxation is proposed for the class of nonconvex quadratic optimization problems by extracting valid quadratic inequalities for positive semidefinite cones. Its effectiveness to obtain optimal values is shown to be the same as the SDP relaxation theoretically. Numerical results are presented to demonstrate that the SOCP relaxation is much more efficient than the SDP relaxation.     

LAHS: A novel harmony search algorithm based on learning automata

This study presents a learning automata-based harmony search (LAHS) for unconstrained optimization of continuous problems. The harmony search (HS) algorithm performance strongly depends on the fine tuning of its parameters, including the harmony consideration rate (HMCR), pitch adjustment rate (PAR) and bandwidth (bw). Inspired by the spur-in-time responses in the musical improvisation process, learning capabilities are employed in the HS to select these parameters based on spontaneous reactions. An extensive numerical investigation is conducted on several well-known test functions, and the results are compared with the HS algorithm and its prominent variants, including the improved harmony search (IHS), global-best harmony search (GHS) and self-adaptive global-best harmony search (SGHS). The numerical results indicate that the LAHS is more efficient in finding optimum solutions and outperforms the existing HS algorithm variants.     

A note on duality in disjunctive programming

We state a duality theorem for disjunctive programming, which generalizes to this class of problems the corresponding result for linear programming.This work was supported by the National Science Foundation under Grant No. MPS73-08534 A02 and by the US Office of Naval Research under Contract No. N00014-75-C-0621-NR047-048.     

Linear programming with online learning

We propose online decision strategies for time-dependent sequences of linear programs which use no distributional and minimal geometric assumptions about the data. These strategies are obtained through Vovk's aggregating algorithm which combines recommendations from a given strategy pool. We establish an average-performance bound for the resulting solution sequence.     

Global Optimization Approach to Unequal Global Optimization Approach to Unequal Sphere Packing Problems in 3D

The problem of the unequal sphere packing in a 3-dimen-sional polytope is analyzed. Given a set of unequal spheres and a poly-tope, the double goal is to assemble the spheres in such a way that (i) they do not overlap with each other and (ii) the sum of the volumes of the spheres packed in the polytope is maximized. This optimization has an application in automated radiosurgical treatment planning and can be formulated as a nonconvex optimization problem with quadratic constraints and a linear objective function. On the basis of the special structures associated with this problem, we propose a variety of algorithms which improve markedly the existing simplicial branch-and-bound algorithm for the general nonconvex quadratic program. Further, heuristic algorithms are incorporated to strengthen the efficiency of the algorithm. The computational study demonstrates that the proposed algorithm can obtain successfully the optimization up to a limiting size.     

Convexity of Nonlinear Image of a Small Ball with Applications to Optimization

Let f: XY be a nonlinear differentiable map, X,Y are Hilbert spaces, B(a,r) is a ball in X with a center a and radius r. Suppose f (x) is Lipschitz in B(a,r) with Lipschitz constant L and f (a) is a surjection: f (a)X=Y; this implies the existence of >0 such that f (a)^* yy, yY. Then, if r,/(2L), the image F=f(B(a,)) of the ball B(a,) is convex. This result has numerous applications in optimization and control. First, duality theory holds for nonconvex mathematical programming problems with extra constraint x–a. Special effective algorithms for such optimization problems can be constructed as well. Second, the reachability set for small power control is convex. This leads to various results in optimal control.     

Successive approximation technique for a class of large-scale NLP problems and its application to dynamic programming

In this paper, two successive approximation techniques are presented for a class of large-scale nonlinear programming problems with decomposable constraints and a class of high-dimensional discrete optimal control problems, respectively. It is shown that: (a) the accumulation point of the sequence produced by the first method is a Kuhn-Tucker point if the constraint functions are decomposable and if the uniqueness condition holds; (b) the sequence converges to an optimum solution if the objective function is strictly pseudoconvex and if the constraint functions are decomposable and quasiconcave; and (c) similar conclusions for the second method hold also for a class of discrete optimal control problems under some assumptions.     

A STRONG OPTIMIZATION THEOREM IN LOCALLY CONVEX SPACES

This paper presents a geometric characterization of convex sets in locally convex spaces on which a strong optimization theorem of the Stegall-type holds, and gives Collier's theorem of w Asplund spaces a localized setting.     

Optimization over the efficient set

This paper deals with the problem of maximizing a function over the efficient set of a linear multiple objective program. The approach is to formulate a biobjective program with an appropriate efficient set. The penalty function approach is motivated by an auxiliary problem due to Benson.     

A note on functions whose local minima are global

In this note, we introduce a new class of generalized convex functions and show that a real functionf which is continuous on a compact convex subsetM of ⁿ and whose set of global minimizers onM is arcwise-connected has the property that every local minimum is global if, and only if,f belongs to that class of functions.     

Novelty detection based on learning entropy

The Approximate Individual Sample Learning Entropy is based on incremental learning of a predictor , where x (k) is an input vector of a given size at time k, w is a vector of weights (adaptive parameters), and h is a prediction horizon. The basic assumption is that, after the underlying process x changes its behavior, the incrementally learning system will adapt the weights w to improve the predictor . Our goal is to detect a change in the behavior of the weight increment process. The main idea of this paper is based on the fact that weight increments △ w (k), where △ w (k) = w (k + 1) ? w (k), create a weakly stationary process until a change occurs. Once a novelty behavior of the underlying process x (k) occurs, the process △ w (k) changes its characteristics (eg, the mean or variation). We suggest using convenient characteristics of △ w (k) in a multivariate detection scheme (eg, the Hotelling's T² control chart).