Stochastic penalty function methods for nonsmooth constrained minimization

This paper presents a stochastic algorithm with proper stopping rules for nonsmooth inequality-constrained minimization problems. The algorithm is based on an augmented Lagrangian dual problem transformed from a primal one, and it consists of two loops: an outer loop, which is the iteration for the approximate Lagrange multipliers, and an inner loop, which is a nonsmooth unconstrained minimization subroutine. Under mild assumptions, the algorithm is proved to be almost surely convergent.This work was partially supported by the Science Foundation of Ningbo University. The author is grateful to Professor D. Q. Mayne for his help with this work and to two referees for their helpful comments.     

A scatter search based hyper-heuristic for sequencing a mixed-model assembly line

We address a mixed-model assembly-line sequencing problem with work overload minimization criteria. We consider time windows in work stations of the assembly line (closed stations) and different versions of a product to be assembled in the line, which require different processing time according to the work required in each work station. In a paced assembly line, products are feeded in the line at a predetermined constant rate (cycle time). Then, if many products with processing time greater than cycle time are feeded consecutively, work overload can be produced when the worker has insufficient time to finish his/her job. We propose a scatter search based hyper-heuristic for this NP-hard problem. In the low-level, the procedure makes use of priority rules through a constructive procedure. Computational experiments over a wide range of instances from the literature show the effectiveness of the proposed hyper-heuristics when compared to existing heuristics. The relevance of the priority rules was evaluated as well.     

Nonlinear programming using minimax techniques

A minimax approach to nonlinear programming is presented. The original nonlinear programming problem is formulated as an unconstrained minimax problem. Under reasonable restrictions, it is shown that a point satisfying the necessary conditions for a minimax optimum also satisfies the Kuhn-Tucker necessary conditions for the original problem. A leastpth type of objective function for minimization with extremely large values ofp is proposed to solve the problem. Several numerical examples compare the present approach with the well-known SUMT method of Fiacco and McCormick. In both cases, a recent minimization algorithm by Fletcher is used.This paper is based on work presented at the 5th Hawaii International Conference on System Sciences, Honolulu, Hawaii, 1972. The authors are greatly indebted to V. K. Jha for his programming assistance and J. H. K. Chen who obtained some of the numerical results. This work was supported in part by the National Research Council of Canada under Grant No. A7239, by a Frederick Gardner Cottrell Grant from the Research Corporation, and through facilities and support from the Communications Research Laboratory of McMaster University.     

Restricted linear constrained minimization of quadratic functionals

In this work, a linearly constrained minimization of a positive semidefinite quadratic functional is examined. We propose two different approaches to this problem. Our results are concerning infinite dimensional real Hilbert spaces, with a singular positive semidefinite operator related to the functional, and considering as constraint a singular operator. The difference between the proposed approaches for the minimization and previous work on this problem is that it is considered for all vectors belonging to the least squares solutions set, or to the vectors perpendicular to the kernel of the related operator or matrix.     

IMAGE SEGMENTATION BY PIECEWISE CONSTANT MUMFORD-SHAH MODEL WITHOUT ESTIMATING THE CONSTANTS

In this work, we try to use the so-called Piecewise Constant Level Set Method （PCLSM） for the Mumford-Shah segmentation model. For image segmentation, the Mumford-Shah model needs to find the regions and the constant values inside the regions for the segmen- tation. In order to use PCLSM for this purpose, we need to solve a minimization problem using the level set function and the constant values as minimization variables. In this work, we test on a model such that we only need to minimize with respect to the level set function, i.e., we do not need to minimize with respect to the constant values. Gradient descent method and Newton method are used to solve the Euler-Lagrange equation for the minimization problem. Numerical experiments are given to show the efficiency and advantages of the new model and algorithms.     

Bank Balance-Sheet Management: An Alternative Multi-Objective Model

Bank balance-sheet management entails considering competing and conflicting objectives such as maximization of returns and minimization of risks associated with alternative portfolio combinations. Traditional multi-objective models simply provide the decision-maker with the entire set of non-dominated solutions; the decision-maker must then choose, unaided, the best solution based on his subjective trade-offs, experience and judgement. This paper develops an alternative multi-objective balance-sheet management model which allows the explicit incorporation of the decision-maker's trade-offs between conflicting objectives, and attempts to reduce his cognitive burden while ensuring that the solution obtained belongs to the set of non-dominated points.     

Efficient numerical methods for entropy-linear programming problems

Entropy-linear programming (ELP) problems arise in various applications. They are usually written as the maximization of entropy (minimization of minus entropy) under affine constraints. In this work, new numerical methods for solving ELP problems are proposed. Sharp estimates for the convergence rates of the proposed methods are established. The approach described applies to a broader class of minimization problems for strongly convex functionals with affine constraints.     

The minimization property for spaces that are normed over semifields

We show that if each nonempty subset of a space X, normed over a pair of topological semifields, has the minimization property, then X is a real normed space (up to an isomorphism).Translated from Matematicheskie Zametki, Vol. 5, No. 3, pp. 297–304, March, 1969.The author expresses his appreciation to L. P. Vlasov for his helpful advice and criticisms.     

Local convergence of the diagonalized method of multipliers

In this study, we consider a modification of the method of multipliers of Hestenes and Powell in which the iteration is diagonalized, that is, only a fixed finite number of iterations of Newton's method are taken in the primal minimization stage. Conditions are obtained for quadratic convergence of the standard method, and it is shown that a diagonalization where two Newton steps are taken preserves the quadratic convergence for all multipler update formulas satisfying these conditions.This work constitutes part of the author's doctoral dissertation in the Department of Mathematical Sciences, Rice University, under the direction of Professor R. A. Tapia and was supported in part by ERDA Contract No. E-(40-1)-5046.The author would like to thank Professor Richard Tapia for his comments, suggestions, and discussions on this material.     

Design and analysis of two discrete-time ZD algorithms for time-varying nonlinear minimization

Nonlinear minimization, as a subcase of nonlinear optimization, is an important issue in the research of various intelligent systems. Recently, Zhang et al. developed the continuous-time and discrete-time forms of Zhang dynamics (ZD) for time-varying nonlinear minimization. Based on this previous work, another two discrete-time ZD (DTZD) algorithms are proposed and investigated in this paper. Specifically, the resultant DTZD algorithms are developed for time-varying nonlinear minimization by utilizing two different types of Taylor-type difference rules. Theoretically, each steady-state residual error in the DTZD algorithm changes in an O(τ ³) manner with τ being the sampling gap. Comparative numerical results are presented to further substantiate the efficacy and superiority of the proposed DTZD algorithms for time-varying nonlinear minimization.     

A unified approach to parallel space decomposition methods

We consider (relaxed) additive and multiplicative iterative space decomposition methods for the minimization of sufficiently smooth functionals without constraints. We develop a general framework which unites existing approaches from both parallel optimization and finite elements. Specifically this work unifies earlier research on the parallel variable distribution method in minimization, space decomposition methods for convex functionals, algebraic Schwarz methods for linear systems and splitting methods for linear least squares. We develop a general convergence theory within this framework, which provides several new results as well as including known convergence results.     

Retailer’s optimal replenishment and payment policies in the EPQ model under cash discount and two-level trade credit policy

The main purpose of this paper is to investigate the retailer’s optimal cycle time and optimal payment time under the supplier’s cash discount and trade credit policy within the economic production quantity (EPQ) framework. In this paper, we assume that the retailer will provide a full trade credit to his/her good credit customers and request his/her bad credit customers pay for the items as soon as receiving them. Under this assumption, we model the retailer’s inventory system as a cost minimization problem to determine the retailer’s optimal inventory cycle time and optimal payment time under the replenishment rate is finite. Then, an algorithm is established to obtain the optimal strategy. Finally, numerical examples are given to illustrate the theoretical results and obtain some managerial phenomena.     

A penalty approximation for a unilateral contact problem in non-linear elasticity

Using Ball's approach to non-linear elasticity, and in particular his concept of polyconvexity, we treat a unilateral three-dimensional contact problem for a hyperelastic body under volume and surface forces. Here the unilateral constraint is described by a sublinear function which can model the contact with a rigid convex cone. We obtain a solution to this generally non-convex, semicoercive Signorinin problem as a limit of solutions of related energy minimization problems involving friction normal to the contact surface where the friction coefficient goes to infinity. Thus we extend an approximation result of Duvaut and Lions for linear-elastic unilateral contact problems to finite deformations and to a class of non-linear elastic materials including the material models of Ogden and of Mooney-Rivlin for rubberlike materials. Moreover, the underlying penalty method is shown to be exact, that is a sufficiently large friction coefficient in the auxiliary energy minimization problems suffices to produce a solution of the original unilateral problem, provided a Lagrange multiplier to the unilateral constraint exists.     

Constrained matrix optimization with applications

In this work we study a minimization problem for a matrix-valued function under linear constraints, in the case of a singular matrix. The proposed method differs from others on the restriction of the minimizing matrix to the range of the corresponding quadratic function. Moreover, we present two applications of the proposed minimization method in Linear Regression and B-spline smoothing.     

A trust region algorithm for minimization of locally Lipschitzian functions

The classical trust region algorithm for smooth nonlinear programs is extended to the nonsmooth case where the objective function is only locally Lipschitzian. At each iteration, an objective function that carries both first and second order information is minimized over a trust region. The term that carries the first order information is an iteration function that may not explicitly depend on subgradients or directional derivatives. We prove that the algorithm is globally convergent. This convergence result extends the result of Powell for minimization of smooth functions, the result of Yuan for minimization of composite convex functions, and the result of Dennis, Li and Tapia for minimization of regular functions. In addition, compared with the recent model of Pang, Han and Rangaraj for minimization of locally Lipschitzian functions using a line search, this algorithm has the same convergence property without assuming positive definiteness and uniform boundedness of the second order term. Applications of the algorithm to various nonsmooth optimization problems are discussed.This author's work was supported in part by the Australian Research Council.This author's work was carried out while he was visiting the Department of Applied Mathematics at the University of New South Wales.     

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.     

On the rate of superlinear convergence of a class of variable metric methods

Summary This paper considers a class of variable metric methods for unconstrained minimization. Without requiring exact line searches each algorithm in this class converges globally and superlinearly on convex functions. Various results on the rate of the superlinear convergence are obtained.Dedicated to Professor Dr. H. Görtler on the occasion of his seventieth birthday     

A family of predictor–corrector schemes for a class of variational inequalities

This work is concerned with an abstract problem in the form of a variational inequality, or equivalently a minimization problem involving a non-differential functional. The problem is inspired by a formulation of the initial–boundary value problem of elastoplasticity. The objective of this work is to revisit the predictor–corrector algorithms that are commonly used in computational applications, and to establish conditions under which these are convergent or, at least, under which they lead to decreasing sequences of the functional for the problem. The focus is on the predictor step, given that the corrector step by definition leads to a decrease in the functional. The predictor step may be formulated as a minimization problem. Attention is given to the tangent predictor, a line search approach, the method of steepest descent, and a Newton-like method. These are all shown to lead to decreasing sequences.     

A BSDE approach to stochastic differential games with incomplete information

We consider a two-player zero-sum stochastic differential game in which one of the players has a private information on the game. Both players observe each other, so that the non-informed player can try to guess his missing information. Our aim is to quantify the amount of information the informed player has to reveal in order to play optimally: to do so, we show that the value function of this zero-sum game can be rewritten as a minimization problem over some martingale measures with a payoff given by the solution of a backward stochastic differential equation.     

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.