Hybrid spectral gradient method for the unconstrained minimization problem

We present a hybrid algorithm that combines a genetic algorithm with the Barzilai–Borwein gradient method. Under specific assumptions the new method guarantees the convergence to a stationary point of a continuously differentiable function, from any arbitrary initial point. Our preliminary numerical results indicate that the new methodology finds efficiently and frequently the global minimum, in comparison with the globalized Barzilai–Borwein method and the genetic algorithm of the Toolbox of Genetic Algorithms of MatLab.      

Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization

In this paper, a HGA (hybrid genetic algorithm) is proposed for permutation flowshop scheduling problems (PFSP) with total flowtime minimization, which are known to be NP-hard. One of the chromosomes in the initial population is constructed by a suitable heuristic and the others are yielded randomly. An artificial chromosome is generated by a weighted simple mining gene structure, with which a new crossover operator is presented. Additionally, two effective heuristics are adopted as local search to improve all generated chromosomes in each generation. The HGA is compared with one of the most effective heuristics and a recent meta-heuristic on 120 benchmark instances. Experimental results show that the HGA outperforms the other two algorithms for all cases. Furthermore, HGA obtains 115 best solutions for the benchmark instances, 92 of which are newly discovered.     

Empirical minimization

We investigate the behavior of the empirical minimization algorithm using various methods. We first analyze it by comparing the empirical, random, structure and the original one on the class, either in an additive sense, via the uniform law of large numbers, or in a multiplicative sense, using isomorphic coordinate projections. We then show that a direct analysis of the empirical minimization algorithm yields a significantly better bound, and that the estimates we obtain are essentially sharp. The method of proof we use is based on Talagrand's concentration inequality for empirical processes. Research partially supported by NSF under award DMS-0434393. Research partially supported by the Australian Research Council Discovery Porject DP0343616.     

Misclassification minimization

The problem of minimizing the number of misclassified points by a plane, attempting to separate two point sets with intersecting convex hulls inn-dimensional real space, is formulated as a linear program with equilibrium constraints (LPEC). This general LPEC can be converted to an exact penalty problem with a quadratic objective and linear constraints. A Frank-Wolfe-type algorithm is proposed for the penalty problem that terminates at a stationary point or a global solution. Novel aspects of the approach include: (i) A linear complementarity formulation of the step function that counts misclassifications, (ii) Exact penalty formulation without boundedness, nondegeneracy or constraint qualification assumptions, (iii) An exact solution extraction from the sequence of minimizers of the penalty function for a finite value of the penalty parameter for the general LPEC and an explicitly exact solution for the LPEC with uncoupled constraints, and (iv) A parametric quadratic programming formulation of the LPEC associated with the misclassification minimization problem.This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grants CCR-9101801 and CDA-9024618.     

Hybrid methods with regularization for minimization problems and asymptotically strict pseudocontractive mappings in the intermediate sense

In this paper we introduce an iterative algorithm for finding a common element of the fixed point set of an asymptotically strict pseudocontractive mapping S in the intermediate sense and the solution set of the minimization problem (MP) for a convex and continuously Frechet differentiable functional in Hilbert space. The iterative algorithm is based on several well-known methods including the extragradient method, CQ method, Mann-type iterative method and hybrid gradient projection algorithm with regularization. We obtain a strong convergence theorem for three sequences generated by our iterative algorithm. In addition, we also prove a new weak convergence theorem by a modified extragradient method with regularization for the MP and the mapping S.     

Break minimization

A break in a {0, 1}-matrix is defined as a 0 with at least one 1 to its left and at least one 1 to its right in the same row. This paper is concerned with {0, 1}-matrices with given column sums and an upper limit for the row sums. In addition, there are limits on the distance from the first to the last 1 in a row. The problem that is considered is to find a {0, 1}-matrix satisfying the conditions such that the total number of breaks is minimum. An algorithm for solving this problem is presented. Computational results illustrate the effectiveness of the algorithm. The investigation originated in a problem of crew rostering.     

Submodular function minimization

Submodular functions often arise in various fields of operations research including discrete optimization, game theory, queueing theory and information theory. In this survey paper, we give overview on the fundamental properties of submodular functions and recent algorithmic devolopments of their minimization.      

The jackknife procedure for the probabilities of misclassification

Seven estimators for the probabilities of misclassification associated with the linear discriminant function are considered. Four of them are known in the literature. The remaining three are constructed through the Jackknife Procedure. An empirical investigation is conducted to evaluate the relative merits of these estimators. Summary of the results is presented.     

A loss minimization problem

The optimal stopping problem is considered in the presence of random losses with decision making concerning non-recurrent involvement of an external financial-protection mechanism. The presence of an utility function determining the attitude of the decision-making person to a risk is taken into account. It is shown that, using the Bellman equation, optimal threshold functions can be constructed numerically and, for certain types of the utility function, such functions can even be constructed in an analytical form.     

Evaluating bound-constrained minimization software

Bound-constrained minimization is a subject of active research. To assess the performance of existent solvers, numerical evaluations and comparisons are carried on. Arbitrary decisions that may have a crucial effect on the conclusions of numerical experiments are highlighted in the present work. As a result, a?detailed evaluation based on performance profiles is applied to the comparison of bound-constrained minimization solvers. Extensive numerical results are presented and analyzed.     

On submodular function minimization

Earlier work of Bixby, Cunningham, and Topkis is extended to give a combinatorial algorithm for the problem of minimizing a submodular function, for which the amount of work is bounded by a polynomial in the size of the underlying set and the largest function value (not its length). Research partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada.     

Proximal minimization algorithm withD-functions

The original proximal minimization algorithm employs quadratic additive terms in the objectives of the subproblems. In this paper, we replace these quadratic additive terms by more generalD-functions which resemble (but are not strictly) distance functions. We characterize the properties of suchD-functions which, when used in the proximal minimization algorithm, preserve its overall convergence. The quadratic case as well as an entropy-oriented proximal minimization algorithm are obtained as special cases.The work of the first author was supported by NSF Grant CCR-8811135 and NIH Grant HL-28438, while visiting the Decision Sciences Department of the Wharton School and the Medical Image Processing Group at the Department of Radiology, both at the University of Pennsylvania, Philadelphia, Pennsylvania. The work of the second author was supported by NSF Grant CCR-91-04042 and AFOSR Grant 91-0168.The authors received valuable comments on the December 1989 and June 1990 versions of this paper, which led to considerable improvements of the results and their presentation. For this, they are indebted to D. Bertsekas, A. De Pierro, J. Eckstein, P. Eggermont, A. Iusem, M. Ferris, M. Teboulle, and three anonymous referees.     

Metrically well-set minimization problems

A concept of well-posedness, or more exactly of stability in a metric sense, is introduced for minimization problems on metric spaces generalizing the notion due to Tykhonov to situations in which there is no uniqueness of solutions. It is compared with other concepts, in particular to a variant of the notion after Hadamard reformulated via a metric semicontinuity approach. Concrete criteria of well-posedness are presented, e.g., for convex minimization problems.     

Weak minimization and duality

Sufficient and necessary optimality conditions are given for weakly minimized optimization problems in terms of a vector valued Lagrangian. Lagrangian and Wolfe type duals are constructed and duality established using an ordering that accords with the definition of a weak minimum. The results for differentiable problems continue to hold under weakened convexity assumptions and for problems which quasiminimize rather than minimize.     

Grouped coordinate minimization using Newton's method for inexact minimization in one vector coordinate

Letf(x,y) be a function of the vector variablesx R ⁿ andy R ^m. The grouped (variable) coordinate minimization (GCM) method for minimizingf consists of alternating exact minimizations in either of the two vector variables, while holding the other fixed at the most recent value. This scheme is known to be locally,q-linearly convergent, and is most useful in certain types of statistical and pattern recognition problems where the necessary coordinate minimizers are available explicitly. In some important cases, the exact minimizer in one of the vector variables is not explicitly available, so that an iterative technique such as Newton's method must be employed. The main result proved here shows that a single iteration of Newton's method solves the coordinate minimization problem sufficiently well to preserve the overall rate of convergence of the GCM sequence.The authors are indebted to Professor R. A. Tapia for his help in improving this paper.     

Conical algorithm for the global minimization of linearly constrained decomposable concave minimization problems

In this paper, we are concerned with the linearly constrained global minimization of the sum of a concave function defined on ap-dimensional space and a linear function defined on aq-dimensional space, whereq may be much larger thanp. It is shown that a conical algorithm can be applied in a space of dimensionp + 1 that involves only linear programming subproblems in a space of dimensionp +q + 1. Some computational results are given.This research was accomplished while the second author was a Fellow of the Alexander von Humboldt Foundation, University of Trier, Trier, Germany.     

Minimum variance estimators for misclassification probabilities in discriminant analysis

Let α(n₁, n₂) be the probability of classifying an observation from population Π₁ into population Π₂ using Fisher's linear discriminant function based on samples of size n₁ and n₂. A standard estimator of α, denoted by T₁, is the proportion of observations in the first sample misclassified by the discriminant function. A modification of T₁, denoted by T₂, is obtained by eliminating the observation being classified from the calculation of the discriminant function. The UMVU estimators, $\text{T}{}_1{}^1$ and $\text{T}{}_2{}^1$, of ET₁ = τ₁(n₁, n₂) and ET₂ = τ₂(n₁, n₂) = α(n₁ ? 1, n₂) are derived for the case when the populations have multivariate normal distributions with common dispersion matrix. It is shown that $\text{T}{}_1{}^1$ and $\text{T}{}_2{}^1$ are nonincreasing functions of D², the Mahalanobis sample distance. This result is used to derive the sampling distributions and moments of $\text{T}{}_1{}^1$ and $\text{T}{}_2{}^1$. It is also shown that α is a decreasing function of Δ² = (μ₁ ? μ₂)′Σ^?1(μ₁ ? μ₂). Hence, by truncating $\text{T}{}_1{}^1$ and $\text{T}{}_2{}^1$ (or any estimator) at the value of α for Σ = 0, new estimators are obtained which, for all samples, are as close or closer to α.     

Equality-constrained minimization of polynomial functions

This paper investigates the equality-constrained minimization of polynomial functions. Let R be the field of real numbers, and R[x1,..., xn] the ring of polynomials over R in variables x1,..., xn. For an f ∈ R[x1,..., xn] and a finite subset H of R[x1,..., xn], denote by V(f : H) the set {f( ˉα) | ˉα∈ Rn, and h( ˉα) =0, ? h ∈ H}. We provide an effective algorithm for computing a finite set U of non-zero univariate polynomials such that the infimum inf V(f : H) of V(f : H) is a root of some polynomial in U whenever inf V(f : H) = ±∞.The strategies of this paper are decomposing a finite set of polynomials into triangular chains of polynomials and computing the so-called revised resultants. With the aid of the computer algebraic system Maple, our algorithm has been made into a general program to treat the equality-constrained minimization of polynomials with rational coefficients.