Nonlinear rescaling and proximal-like methods in convex optimization

The nonlinear rescaling principle (NRP) consists of transforming the objective function and/or the constraints of a given constrained optimization problem into another problem which is equivalent to the original one in the sense that their optimal set of solutions coincides. A nonlinear transformation parameterized by a positive scalar parameter and based on a smooth sealing function is used to transform the constraints. The methods based on NRP consist of sequential unconstrained minimization of the classical Lagrangian for the equivalent problem, followed by an explicit formula updating the Lagrange multipliers. We first show that the NRP leads naturally to proximal methods with an entropy-like kernel, which is defined by the conjugate of the scaling function, and establish that the two methods are dually equivalent for convex constrained minimization problems. We then study the convergence properties of the nonlinear rescaling algorithm and the corresponding entropy-like proximal methods for convex constrained optimization problems. Special cases of the nonlinear rescaling algorithm are presented. In particular a new class of exponential penalty-modified barrier functions methods is introduced. Partially supported by the National Science Foundation, under Grants DMS-9201297, and DMS-9401871. Partially supported by NASA Grant NAG3-1397 and NSF Grant DMS-9403218.     

Quasi-Newton method by Hermite interpolation

This paper describes a new attempt to solve the problem of computing a local minimizer of a sufficiently often differentiable unconstrained objective function. In every step of the iteration, a special Hermite interpolant is constructed. Old iteration points serve as points of support with the function value and gradient information. This yields a quasi-Newton algorithm with quadratic convergence order.     

Locating Multiple Competitive Facilities: Spatial Interaction Models with Variable Expenditures

We develop a new framework for location of competitive facilities by introducing non-constant expenditure functions into spatial interaction location models. This framework allows us to capture two key effects – market expansion and cannibalization – within the same model.We develop algorithmic approaches for finding optimal or near-optimal solutions for several models that arise from choosing a specific form of the expenditure functions.     

On the longest circuit in an alterable digraph

Analterable digraph is a digraph with a subset of its edges marked alterable and their orientations left undecided. We say that an alterable digraph has an invariant ofk on the length of the longest circuit if it has a circuit of length at leastk regardless of the orientations over its alterable edges. Computing the maximum invariant on the length of the longest circuit in an alterable digraph is aglobal optimization problem. We show that it is hard to approximate the global optimal solution for the maximum invariant problem.Research supported in part by NSF grant CCR 9121472.     

Efficient algorithms for solving certain nonconvex programs dealing with the product of two affine fractional functions

Two algorithms for finding a global minimum of the product of two affine fractional functions over a compact convex set and solving linear fractional programs with an additional constraint defined by the product of two affine fractional functions are proposed. The algorithms are based on branch and bound techniques using an adaptive branching operation which takes place in one-dimensional intervals. Results from numerical experiments show that large scale problems can be efficiently solved by the proposed methods.     

Unification of basic and composite nondifferentiable optimization

There are two main classes of iterative methods in nondifferentiable optimization (NDO). In thebasic NDO, the information is limited to the objective function and at least one element of its subdifferential, while in thecomposite NDO, the objective function is split into a sum of a smooth and a nonsmooth function. Our work unifies these two approaches for benefiting of their respective advantages.     

Necessary optimality conditions for abnormal problems with geometric constraints

The abnormal minimization problem with a finite-dimensional image and geometric constraints is examined. In particular, inequality constraints are included. Second-order necessary conditions for this problem are established that strengthen previously known results.     

On duality bound methods for nonconvex global optimization

A counter-example is given to several recently published results on duality bound methods for nonconvex global optimization.     

Solving the maximum edge weight clique problem via unconstrained quadratic programming

The unconstrained quadratic binary program (UQP) is proving to be a successful modeling and solution framework for a variety of combinatorial optimization problems. Experience reported in the literature with several problem classes has demonstrated that this approach works surprisingly well in terms of solution quality and computational times, often rivaling and sometimes surpassing more traditional methods. In this paper we report on the application of UQP to the maximum edge-weighted clique problem. Computational experience is reported illustrating the attractiveness of the approach.     

Heuristics Based on Partial Enumeration for the Unrelated Parallel Processor Scheduling Problem

The classical deterministic scheduling problem of minimizing the makespan on unrelated parallel processors is known to be NP-hard in the strong sense. Given the mixed integer linear model with binary decision variables, this paper presents heuristic algorithms based on partial enumeration. Basically, they consist in the construction of mixed integer subproblems, considering the integrality of some subset of variables, formulated using the information obtained from the solution of the linear relaxed problem. Computational experiments are reported for a collection of test problems, showing that some of the proposed algorithms achieve better solutions than other relevant approximation algorithms published up to now.