Conditions for the Absence of Local Extrema in Problems of Quantum Coherent Control

We consider a terminal control problem for quantum systems which is formulated as the problem of maximizing the objective functional at some fixed finite time. Within the framework of this problem, we discuss known results on the local maxima of the objective functional that are not global. This question is important for quantum control, since such local maxima could make it difficult to find the global maximum by local search in numerical optimization or under laboratory conditions.     

On characterization of maximal independent sets via quadratic optimization

This article investigates the local maxima properties of a box-constrained quadratic optimization formulation of the maximum independent set problem in graphs. Theoretical results characterizing binary local maxima in terms of certain induced subgraphs of the given graph are developed. We also consider relations between continuous local maxima of the quadratic formulation and binary local maxima in the Hamming distance-1 and distance-2 neighborhoods. These results are then used to develop an efficient local search algorithm that provides considerable speed-up over a typical local search algorithm for the binary Hamming distance-2 neighborhood.     

Balancing global and local search in parallel efficient global optimization algorithms

Most parallel efficient global optimization (EGO) algorithms focus only on the parallel architectures for producing multiple updating points, but give few attention to the balance between the global search (i.e., sampling in different areas of the search space) and local search (i.e., sampling more intensely in one promising area of the search space) of the updating points. In this study, a novel approach is proposed to apply this idea to further accelerate the search of parallel EGO algorithms. In each cycle of the proposed algorithm, all local maxima of expected improvement (EI) function are identified by a multi-modal optimization algorithm. Then the local EI maxima with value greater than a threshold are selected and candidates are sampled around these selected EI maxima. The results of numerical experiments show that, although the proposed parallel EGO algorithm needs more evaluations to find the optimum compared to the standard EGO algorithm, it is able to reduce the optimization cycles. Moreover, the proposed parallel EGO algorithm gains better results in terms of both number of cycles and evaluations compared to a state-of-the-art parallel EGO algorithm over six test problems.     

Local maxima of the sample functions of the N-parameter Bessel process

In this paper we show that almost every sample function of the N-parameter Bessel process associated with the N-parameter Wiener process has a local maximum. In addition some properties related to the local maxima are investigated.     

Global minimization algorithms for concave quadratic programming problems

Abstract: In this article, we consider the concave quadratic programming problem which is known to be NP hard. Based on the improved global optimality conditions by [Dür, M., Horst, R. and Locatelli, M., 1998, Necessary and sufficient global optimality conditions for convex maximization revisited, Journal of Mathematical Analysis and Applications, 217, 637–649] and [Hiriart-Urruty, J.B. and Ledyav, J.S., 1996, A note in the characterization of the global maxima of a convex function over a convex set, Journal of Convex Analysis, 3, 55–61], we develop a new approach for solving concave quadratic programming problems. The main idea of the algorithms is to generate a sequence of local minimizers either ending at a global optimal solution or at an approximate global optimal solution within a finite number of iterations. At each iteration of the algorithms we solve a number of linear programming problems with the same constraints of the original problem. We also present the convergence properties of the proposed algorithms under some conditions. The efficiency of the algorithms has been demonstrated with some numerical examples.     

Inscribed ball and enclosing box methods for the convex maximization problem

Many important classes of decision models give rise to the problem of finding a global maximum of a convex function over a convex set. This problem is known also as concave minimization, concave programming or convex maximization. Such problems can have many local maxima, therefore finding the global maximum is a computationally difficult problem, since standard nonlinear programming procedures fail. In this article, we provide a very simple and practical approach to find the global solution of quadratic convex maximization problems over a polytope. A convex function achieves its global maximum at extreme points of the feasible domain. Since an inscribed ball does not contain any extreme points of the domain, we use the largest inscribed ball for an inner approximation while a minimal enclosing box is exploited for an outer approximation of the domain. The approach is based on the use of these approximations along with the standard local search algorithm and cutting plane techniques.     

John and Loewner Ellipsoids

John’s ellipsoid criterion characterizes the unique ellipsoid of globally maximum volume contained in a given convex body C. In this article local and global maximum properties of the volume on the space of all ellipsoids in C are studied, where ultra maximality is a stronger version of maximality: the volume is nowhere stationary. The ellipsoids for which the volume is locally maximum, resp. locally ultra maximum are characterized. The global maximum is the only local maximum and for generic C it is an ultra maximum. The characterizations make use of notions originating from the geometric theory of positive quadratic forms. Part of these results generalize to the case where the ellipsoids are replaced by affine copies of a convex body D. In contrast to the ellipsoid case, there are convex bodies C and D, such that on the space of all affine images of D in C the volume has countably many local maxima. All results have dual counterparts. Extensions to the surface area and, more generally, to intrinsic volumes are mentioned.     

Packing congruent hyperspheres into a hypersphere

The paper considers a problem of packing the maximal number of congruent nD hyperspheres of given radius into a larger nD hypersphere of given radius where n = 2, 3, . . . , 24. Solving the problem is reduced to solving a sequence of packing subproblems provided that radii of hyperspheres are variable. Mathematical models of the subproblems are constructed. Characteristics of the mathematical models are investigated. On the ground of the characteristics we offer a solution approach. For n ≤ 3 starting points are generated either in accordance with the lattice packing of circles and spheres or in a random way. For n > 3 starting points are generated in a random way. A procedure of perturbation of lattice packings is applied to improve convergence. We use the Zoutendijk feasible direction method to search for local maxima of the subproblems. To compute an approximation to a global maximum of the problem we realize a non-exhaustive search of local maxima. Our results are compared with the benchmark results for n = 2. A number of numerical results for 2 ≤ n ≤ 24 are given.     

Local approximation of functions with several variables

This paper presents the problem of local approximation of scalar functions with several variables, including points of non-differentiability. The procedure considers that the mapping displays rates of change of power type with respect to linear changes in the coordinate domain, and the exponents are not necessarily integer. The approach provides a formula describing the local variability of scalar fields which contains and generalizes Taylor’s formula of first order. The functions giving the contact are Müntz polynomials. The knowledge of their coefficients and exponents enables the finding of local extremes including cases of non-smoothness. Sufficient conditions for the existence of global maxima and minima of concave-convex functions are obtained as well.     

A nonconvex quadratic optimization approach to the maximum edge weight clique problem

The maximum edge weight clique (MEWC) problem, defined on a simple edge-weighted graph, is to find a subset of vertices inducing a complete subgraph with the maximum total sum of edge weights. We propose a quadratic optimization formulation for the MEWC problem and study characteristics of this formulation in terms of local and global optimality. We establish the correspondence between local maxima of the proposed formulation and maximal cliques of the underlying graph, implying that the characteristic vector of a MEWC in the graph is a global optimizer of the continuous problem. In addition, we present an exact algorithm to solve the MEWC problem. The algorithm is a combinatorial branch-and-bound procedure that takes advantage of a new upper bound as well as an efficient construction heuristic based on the proposed quadratic formulation. Results of computational experiments on some benchmark instances are also presented.     

Towards the global solution of the maximal correlation problem

The maximal correlation problem (MCP) aiming at optimizing correlation between sets of variables plays a very important role in many areas of statistical applications. Currently, algorithms for the general MCP stop at solutions of the multivariate eigenvalue problem for a related matrix A, which serves as a necessary condition for the global solutions of the MCP. However, the reliability of the statistical prediction in applications relies greatly on the global maximizer of the MCP, and would be significantly impacted if the solution found is a local maximizer. Towards the global solution of the MCP, we have obtained four results in the present paper. First, the sufficient and necessary condition for global optimality of the MCP when A is a positive matrix is extended to the nonnegative case. Secondly, the uniqueness of the multivariate eigenvalues in the global maxima of the MCP is proved either when there are only two sets of variables involved, or when A is nonnegative. The uniqueness of the global maximizer of the MCP for the nonnegative irreducible case is also proved. These theoretical achievements lead to our third result that if A is a nonnegative irreducible matrix, both the Horst-Jacobi algorithm and the Gauss-Seidel algorithm converge globally to the global maximizer of the MCP. Lastly, some new estimates of the multivariate eigenvalues related to the global maxima are obtained.     

Analysis of Local Search Landscapes for <Emphasis Type="Italic">k</Emphasis>-SAT Instances

Stochastic local search is a successful technique in diverse areas of combinatorial optimisation and is predominantly applied to hard problems. When dealing with individual instances of hard problems, gathering information about specific properties of instances in a pre-processing phase is helpful for an appropriate parameter adjustment of local search-based procedures. In the present paper, we address parameter estimations in the context of landscapes induced by k-SAT instances: at first, we utilise a sampling method devised by Garnier and Kallel in 2002 for approximations of the number of local maxima in landscapes generated by individual k-SAT instances and a simple neighbourhood relation. The objective function is given by the number of satisfied clauses. The procedure provides good approximations of the actual number of local maxima, with a deviation typically around 10%. Secondly, we provide a method for obtaining upper bounds for the average number of local maxima in k-SAT instances. The method allows us to obtain the upper bound \(2^{n-O(\sqrt{n/k})}\) for the average number of local maxima, if m is in the region of 2 ^k · n/k.     

Constrained stochastic simulation—generation of time series around some specific event in a normal process

The method of so-called constrained stochastic simulation is introduced. This method specifies how to efficiently generate time series around some specific event in a normal process. All events which can be expressed by means of a linear condition (constraint) can be dealt with. Two examples are given in the paper: the generation of stochastic time series around local maxima and the generation of stochastic time series around a combination of a local minimum and maximum with a specified time separation. The constrained time series turn out to be a combination of the original process and several correction terms which includes the autocorrelation function and its time derivatives. For the application concerning local maxima it is shown that the presented method is in line with properties of a normal process near a local maximum as found in literature. The method can e.g. be applied to generate wind gusts in order to assess the extreme loading of wind turbines. AMS 2000 Subject Classification Primary—60G15, 60G70, 62G32; Secondary—62P30     

A survey of simulated annealing as a tool for single and multiobjective optimization

This paper presents a comprehensive review of simulated annealing (SA)-based optimization algorithms. SA-based algorithms solve single and multiobjective optimization problems, where a desired global minimum/maximum is hidden among many local minima/maxima. Three single objective optimization algorithms (SA, SA with tabu search and CSA) and five multiobjective optimization algorithms (SMOSA, UMOSA, PSA, WDMOSA and PDMOSA) based on SA have been presented. The algorithms are briefly discussed and are compared. The key step of SA is probability calculation, which involves building the annealing schedule. Annealing schedule is discussed briefly. Computational results and suggestions to improve the performance of SA-based multiobjective algorithms are presented. Finally, future research in the area of SA is suggested.     

Sphere Packing, III. Extremal Cases

This paper is the third in a series of six papers devoted to the proof of the Kepler conjecture, which asserts that no packing of congruent balls in three dimensions has density greater than the face-centered cubic packing. In the previous paper in this series, a continuous function f on a compact space was defined, certain points in the domain were conjectured to give the global maxima, and the relation between this conjecture and the Kepler conjecture was established. This paper shows that those points are indeed local maxima. Various approximations to f are developed, that will be used in subsequent papers to bound the value of the function f. The function f can be expressed as a sum of terms, indexed by regions on a unit sphere. Detailed estimates of the terms corresponding to triangular and quadrilateral regions are developed.     

Unifying local–global type properties in vector optimization

It is well-known that all local minimum points of a semistrictly quasiconvex real-valued function are global minimum points. Also, any local maximum point of an explicitly quasiconvex real-valued function is a global minimum point, provided that it belongs to the intrinsic core of the function’s domain. The aim of this paper is to show that these “local min–global min” and “local max–global min” type properties can be extended and unified by a single general local–global extremality principle for certain generalized convex vector-valued functions with respect to two proper subsets of the outcome space. For particular choices of these two sets, we recover and refine several local–global properties known in the literature, concerning unified vector optimization (where optimality is defined with respect to an arbitrary set, not necessarily a convex cone) and, in particular, classical vector/multicriteria optimization.     

The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSAT problems

Heuristic algorithms, especially hill-climbing algorithms, are prone to being trapped by local optimization. Many researchers have focused on analyzing convergence and runtime of some heuristic algorithms on SAT-solving problems. However, there is rare work on analyzing success ratio (the ratio of the number of runs that find the global maxima of optimization versus the total runs) and expected fitness at each generation. Expected fitness at each generation could lead us to better understand the expected fitness of a heuristic algorithm could find on the problem to be solve at a certain generation. Success ratio help us understand with what a probability a heuristic algorithm could find the global optimization of the problem to be solved. So, this paper analyzed expected fitness and success ratio of two hill-climbing algorithms on two bimodal MaxSAT problems by using Markov chain. The theoretical and experimental results showed that though hill-climbing algorithms (both hill-climbing RandomWalk and Local (1+1)EA) converged faster, they could not always find global maxima of bimodal SAT-solving problems. The success ratios of hill-climbing algorithms usually have their own limits. The limit of success ratio is dependent on the SAT-solving problem itself and the expected distribution of initial bit string, and independent on whether hill-climbing RandomWalk or Local (1+1)EA is used.     

Maximization of submodular functions: Theory and enumeration algorithms

Submodular functions are powerful tools to model and solve either to optimality or approximately many operational research problems including problems defined on graphs. After reviewing some long-standing theoretical results about the structure of local and global maxima of submodular functions, Cherenin’s selection rules and his Dichotomy Algorithm, we revise the above mentioned theory and show that our revision is useful for creating new non-binary branching algorithms and finding either approximation solutions with guaranteed accuracy or exact ones.     

ON MAXIMA OF DUAL FUNCTION OF THE CDT SUBPROBLEM

1. IntroductionConsider the following the CDT problem Pwhere g e n", B E n"'", A E n"'", c E urn, a > 0, (2 0, B is a symmetric matrix notnecessajry positive semi--definde, and throughout this paperg the norm 11' 11 denotes the Euclideannorm. For the conveniellt of our following discussion, let F be the feasible region of the CDTsubproblem,andProblem (1.1)--(1.3) arises in some trust region algorithms for equality constrained optillilzation aiming to conquer the inconsistency between the…     

Characterization of local solutions for a class of nonconvex programs

A nonconvex programming problem, which arises in the context of application of Benders' decomposition procedure to a class of network optimization problems, is considered. Conditions which are both necessary and sufficient for a local maximum are derived. The concept of a basic local maximum is introduced, and it is shown that there is a finite number of basic local maxima and at least one such local maximum is optimal.