Simulated annealing with asymptotic convergence for nonlinear constrained optimization

In this paper, we present constrained simulated annealing (CSA), an algorithm that extends conventional simulated annealing to look for constrained local minima of nonlinear constrained optimization problems. The algorithm is based on the theory of extended saddle points (ESPs) that shows the one-to-one correspondence between a constrained local minimum and an ESP of the corresponding penalty function. CSA finds ESPs by systematically controlling probabilistic descents in the problem-variable subspace of the penalty function and probabilistic ascents in the penalty subspace. Based on the decomposition of the necessary and sufficient ESP condition into multiple necessary conditions, we present constraint-partitioned simulated annealing (CPSA) that exploits the locality of constraints in nonlinear optimization problems. CPSA leads to much lower complexity as compared to that of CSA by partitioning the constraints of a problem into significantly simpler subproblems, solving each independently, and resolving those violated global constraints across the subproblems. We prove that both CSA and CPSA asymptotically converge to a constrained global minimum with probability one in discrete optimization problems. The result extends conventional simulated annealing (SA), which guarantees asymptotic convergence in discrete unconstrained optimization, to that in discrete constrained optimization. Moreover, it establishes the condition under which optimal solutions can be found in constraint-partitioned nonlinear optimization problems. Finally, we evaluate CSA and CPSA by applying them to solve some continuous constrained optimization benchmarks and compare their performance to that of other penalty methods.     

The primal-dual algorithm as a constraint-set-manipulation device

A general primal—dual algorithm for linearly constrained optimization problems is formulated in which the dual variables are updated by a dual algorithmic operator. Convergence is proved under the assumption that the dual algorithmic operator implies asymptotic feasibility of the primal iterates with respect to the linear constraints. A general result relating the minimal values of an infinite sequence of constrained problems to the minimal value of a limiting problem (constrained by the limit of the sequence of constraints sets) is established and invoked. The applicability of the general theory is demonstrated by analyzing a specific dual algorithmic operator. This leads to the MART algorithm for constrained entropy maximization used in image reconstruction from projections.     

An extension of the Caratheodory—Kalman variational method

We apply the Caratheodory method to variational problems posed in a Banach space. A treatment of the problem of Lagrange leads to the necessary conditions for constrained optimal control problems. Specialization of the space leads to recovery of the usual necessary conditions and extension of the necessary conditions to a class of problems for systems with distributed parameters. The spaces are not restricted to be reflexive, thus permitting consideration of control problems in queuing theory and transport theory. An application to certain queuing processes completes the paper.This work was performed partly under the auspices of the US Atomic Energy Commission and partly under National Science Foundation Grant No. GP-3900.     

A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis

A recently introduced graph-theoretic notion of signed hypergraph is studied. In particular, a structural characterization of balanced signed hypergraphs is given, and two optimization problems related to the balance property — the maximum balance and the minimum covering problems — are introduced and characterized. It is shown that both problems are NP-complete in general. Applications of the theory of signed hypergraphs to two VLSI optimization problems, namely via minimization and constrained logic encoding, are described.     

Lexicographical order and duality in multiobjective programming

This paper studies the applications of lexicographical order relation for vectors in the mathematical theory of multiobjective programming. We show that any Pareto minimum of an unconstrained convex. problem is the lexicographical minimum for the problem associated to a matrix multiplier having lexicographical positive columns. A similar result is also obtained for inequality constrained problems.Our approach to the theory of duality follows the pattern of Jahn [3], but we substitute vectors by matrices in the formulation of the dual problem and the usual scalar order relation by the lexicographical order relation. This allows us to state the Strong Duality Theorem in terms of Pareto minima and to eliminate some regularity assumptions.     

Boundary-value problems of the asymmetric theory of elasticity for thin plates

Boundary-value problems of the three-dimensional asymmetric micropolar, moment theory of elasticity with free rotation are considered for thin plates. It is assumed that the total stress-strain state is the sum of the internal stress-strain state and the boundary layers, which are determined in an approximation using asymptotic analysis. Three different asymptotic forms are constructed for the three-dimensional boundary-value problem posed, depending on the values of dimensionless physical constants of the plate material. The initial approximation for the first asymptotic form leads to a theory of micropolar plates with free rotation, the initial approximation for the second asymptotic form leads to a theory of micropolar plates with constrained rotation, and the initial approximation for the third asymptotic form leads to a theory of micropolar plates with “small shear stiffness.” The corresponding micropolar boundary layers are constructed and studied. The regions of applicability of each of the theories of micropolar plates constructed are indicated.     

Nonlinear Lagrangian Theory for Nonconvex Optimization

The Lagrangian function in the conventional theory for solving constrained optimization problems is a linear combination of the cost and constraint functions. Typically, the optimality conditions based on linear Lagrangian theory are either necessary or sufficient, but not both unless the underlying cost and constraint functions are also convex.We propose a somewhat different approach for solving a nonconvex inequality constrained optimization problem based on a nonlinear Lagrangian function. This leads to optimality conditions which are both sufficient and necessary, without any convexity assumption. Subsequently, under appropriate assumptions, the optimality conditions derived from the new nonlinear Lagrangian approach are used to obtain an equivalent root-finding problem. By appropriately defining a dual optimization problem and an alternative dual problem, we show that zero duality gap will hold always regardless of convexity, contrary to the case of linear Lagrangian duality.     

Extended convergence results for the method of multipliers for nonstrictly binding inequality constraints

In this paper, we extend the classical convergence and rate of convergence results for the method of multipliers for equality constrained problems to general inequality constrained problems, without assuming the strict complementarity hypothesis at the local optimal solution. Instead, we consider an alternative second-order sufficient condition for a strict local minimum, which coincides with the standard one in the case of strict complementary slackness. As a consequence, new stopping rules are derived in order to guarantee a local linear rate of convergence for the method, even if the current Lagrangian is only asymptotically minimized in this more general setting. These extended results allow us to broaden the scope of applicability of the method of multipliers, in order to cover all those problems admitting loosely binding constraints at some optimal solution. This fact is not meaningless, since in practice this kind of problem seems to be more the rule rather than the exception.In proving the different results, we follow the classical primaldual approach to the method of multipliers, considering the approximate minimizers for the original augmented Lagrangian as the exact solutions for some adequate approximate augmented Lagrangian. In particular, we prove a general uniform continuity property concerning both their primal and their dual optimal solution set maps, a property that could be useful beyond the scope of this paper. This approach leads to very simple proofs of the preliminary results and to a straight-forward proof of the main results.The author gratefully acknowledges the referees for their helpful comments and remarks. This research was supported by FONDECYT (Fondo Nacional de Desarrollo Científico y Technológico de Chile).     

On the image of a constrained extremum problem and some applications to the existence of a minimum

A new approach to constrained optimization, which has appeared recently under various forms and in several contexts, is presented in a general and unifying setting. This approach is then employed to establish some new conditions for the existence of the minimum of a constrained minimum problem.     

Modified Kuhn-tucker conditions when a minimum is not attained

The Kuhn-Tucker conditions for constrained minimization assume that the minimum is attained. When there is a finite infimum, but a minimum is not attained, an asymptotic version of Kuhn-Tucker conditions is obtained for linear problems, in general in infinite dimensions, with some restriction on the feasible set. This result is extended to some nonlinear problems, not necessarily convex, with some further restriction on differentiability.     

On the role of continuously differentiable exact penalty functions in constrained global optimization

The aim of this paper is to show that the new continuously differentiable exact penalty functions recently proposed in literature can play an important role in the field of constrained global optimization. In fact they allow us to transfer ideas and results proposed in unconstrained global optimization to the constrained case.First, by drawing our inspiration from the unconstrained case and by using the strong exactness properties of a particular continuously differentiable penalty function, we propose a sufficient condition for a local constrained minimum point to be global.Then we show that every constrained local minimum point satisfying the second order sufficient conditions is an attraction point for a particular implementable minimization algorithm based on the considered penalty function. This result can be used to define new classes of global algorithms for the solution of general constrained global minimization problems. As an example, in this paper we describe a simulated annealing algorithm which produces a sequence of points converging in probability to a global minimum of the original constrained problem.     

Characterizations of set order relations and constrained set optimization problems via oriented distance function

Set-valued optimization problems are important and fascinating field of optimization theory and widely applied to image processing, viability theory, optimal control and mathematical economics. There are two types of criteria of solutions for the set-valued optimization problems: the vector criterion and the set criterion. In this paper, we adopt the set criterion to study the optimality conditions of constrained set-valued optimization problems. We first present some characterizations of various set order relations using the classical oriented distance function without involving the nonempty interior assumption on the ordered cones. Then using the characterizations of set order relations, necessary and sufficient conditions are derived for four types of optimal solutions of constrained set optimization problem with respect to the set order relations. Finally, the image space analysis is employed to study the c-optimal solution of constrained set optimization problems, and then optimality conditions and an alternative result for the constrained set optimization problem are established by the classical oriented distance function.     

Well-posed optimization problems for integral functionals

A necessary and sufficient condition for the correctness of minimum problems defined by integral functionals over pointwise constrained summable functions is that the integrand defines a well-posed minimum problem over the constraint region.This work was supported by the Laboratorio per la Matematica Applicata, Consiglio Nazionale delle Ricerche (CNR).     

A polynomial algorithm for minimum quadratic cost flow problems

Network flow problems with quadratic separable costs appear in a number of important applications such as; approximating input-output matrices in economy; projecting and forecasting traffic matrices in telecommunication networks; solving nondifferentiable cost flow problems by subgradient algorithms. It is shown that the scaling technique introduced by Edmonds and Karp (1972) in the case of linear cost flows for deriving a polynomial complexity bound for the out-of-kilter method, may be extended to quadratic cost flows and leads to a polynomial algorithm for this class of problems. The method may be applied to the solution of singly constrained quadratic programs and thus provides an alternative approach to the polynomial algorithm suggested by Helgason, Kennington and Lall (1980).     

Modified barrier functions (theory and methods)

The nonlinear rescaling principle employs monotone and sufficiently smooth functions to transform the constraints and/or the objective function into an equivalent problem, the classical Lagrangian which has important properties on the primal and the dual spaces.The application of the nonlinear rescaling principle to constrained optimization problems leads to a class of modified barrier functions (MBF's) and MBF Methods (MBFM's). Being classical Lagrangians (CL's) for an equivalent problem, the MBF's combine the best properties of the CL's and classical barrier functions (CBF's) but at the same time are free of their most essential deficiencies.Due to the excellent MBF properties, new characteristics of the dual pair convex programming problems have been found and the duality theory for nonconvex constrained optimization has been developed.The MBFM have up to a superlinear rate of convergence and are to the classical barrier functions (CBF's) method as the Multipliers Method for Augmented Lagrangians is to the Classical Penalty Function Method. Based on the dual theory associated with MBF, the method for the simultaneous solution of the dual pair convex programming problems with up to quadratic rates of convergence have been developed. The application of the MBF to linear (LP) and quadratic (QP) programming leads to a new type of multipliers methods which have a much better rate of convergence under lower computational complexity at each step as compared to the CBF methods.The numerical realization of the MBFM leads to the Newton Modified Barrier Method (NMBM). The excellent MBF properties allow us to discover that for any nondegenerate constrained optimization problem, there exists a hot start, from which the NMBM has a better rate of convergence, a better complexity bound, and is more stable than the interior point methods, which are based on the classical barrier functions.     

An exact penalty function for nonlinear programming with inequalities

It is shown how, given a nonlinear programming problem with inequality constraints, it is possible to construct an exact penalty function with a local unconstrained minimum at any local minimum of the constrained problem. The unconstrained minimum is sufficiently smooth to permit conventional optimization techniques to be used to locate it. Numerical evidence is presented on five well-known test problems.     

A hybrid heuristic for the diameter constrained minimum spanning tree problem

We propose a hybrid GRASP and ILS based heuristic for the diameter constrained minimum spanning tree problem. The latter typically models network design applications where, under a given quality requirement, all vertices must be connected at minimum cost. An adaptation of the one time tree heuristic is used to build feasible diameter constrained spanning trees. Solutions thus obtained are then attempted to be improved through local search. Four different neighborhoods are investigated, in a scheme similar to VND. Upper bounds within 2% of optimality were obtained for problems in two test sets from the literature. Additionally, upper bounds stronger than those previously obtained in the literature are reported for OR-Library instances.     

Method of separation of variables and Hamiltonian system

In the theory of mechanics and/or mathematical physics problems in a prismatic domain, the method of separation of variables ususally leads to the Sturm–Liouville-type eigenproblems of self-adjoint operators, and then the eigenfunction expansion method can be used in equation solving. However, a number of important application problems cannot lead to self-adjoint operator for the transverse coordinate. From the minimum potential energy variational principle, by selection of the state and its dual variables, the generalized variational principle is deduced. Then, based on the analogy between the theory of structural mechanics and optimal control, the present article leads the problem to the Hamiltonian system. The finite-dimensional theory for the Hamiltonian system is extended to the corresponding theory of the Hamiltonian operator matrix and adjoint symplectic spaces. The adjoint symplectic orthonormality relation is proved for the whole state eigenfunction vectors, and then the expansion of an arbitrary whole state function vector by the eigenfunction vectors is established. Thus the range of classical method of separation of variables is considerably extended. The eigenproblem derived from a plate bending problem in a strip domain is used for illustration. © 1993 John Wiley & Sons, Inc.     

Minimum Spanning Trees with Sums of Ratios

We present an algorithm for finding a minimum spanning tree where the costs are the sum of two linear ratios. We show how upper and lower bounds may be quickly generated. By associating each ratio value with a new variable in `image space,' we show how to tighten these bounds by optimally solving a sequence of constrained minimum spanning tree problems. The resulting iterative algorithm then finds the globally optimal solution. Two procedures are presented to speed up the basic algorithm. One relies on the structure of the problem to find a locally optimal solution while the other is independent of the problem structure. Both are shown to be effective in reducing the computational effort. Numerical results are presented.     

A parameter-free multiplier method for constrained minimization problems

This paper is concerned with the development of a parameter-free method, closely related to penalty function and multiplier methods, for solving constrained minimization problems. The method is developed via the quadratic programming model with equality constraints. The study starts with an investigation into the convergence properties of a so-called “primal-dual differential trajectory”, defined by directions given by the direction of steepest descent with respect to the variables x of the problem, and the direction of steepest ascent with respect to the Lagrangian multipliers λ, associated with the Lagrangian function. It is shown that the trajectory converges to a stationary point (x*, λ*) corresponding to the solution of the equality constrained problem. Subsequently numerical procedures are proposed by means of which practical trajectories may be computed and the convergence of these trajectories are analyzed. A computational algorithm is presented and its application is illustrated by means of simple but representative examples. The extension of the method to inequality constrained problems is discussed and a non-rigorous argument, based on the Kuhn—Tucker necessary conditions for a constrained minimum, is put forward on which a practical procedure for determining the solution is based. The application of the method to inequality constrained problems is illustrated by its application to a couple of simple problems.