An algorithm for linear least squares problems with equality and nonnegativity constraints

We present a new algorithm for solving a linear least squares problem with linear constraints. These are equality constraint equations and nonnegativity constraints on selected variables. This problem, while appearing to be quite special, is the core problem arising in the solution of the general linearly constrained linear least squares problem. The reduction process of the general problem to the core problem can be done in many ways. We discuss three such techniques.The method employed for solving the core problem is based on combining the equality constraints with differentially weighted least squares equations to form an augmented least squares system. This weighted least squares system, which is equivalent to a penalty function method, is solved with nonnegativity constraints on selected variables.Three types of examples are presented that illustrate applications of the algorithm. The first is rank deficient, constrained least squares curve fitting. The second is concerned with solving linear systems of algebraic equations with Hilbert matrices and bounds on the variables. The third illustrates a constrained curve fitting problem with inconsistent inequality constraints.     

The computer as an aid to physical distribution management

The optimal use of storage and distribution facilities is an important application of the general stock-cutting problem. A variety of techniques have been proposed in the literature to generate feasible layouts for a given box on a given pallet but this article is concerned with the practical problems which are faced by those concerned with product design and distribution once solutions to the stock-cutting problem are available. The analysis required in the two-dimensional situation is illustrated and it is shown that the solution in two dimensions may not result in the best overall solution when height restrictions are applied. Examples of this situation are given and some unexpected results quoted. The amount of analysis to fully explore the problem is shown to be prohibitively lengthy when carried out manually and the value of computerisation of the procedures is illustrated. In addition the interaction of the computer with the decision maker is shown to be beneficial as the constraints upon the design and distribution system may be difficult to define in a quantitative way.     

S-curve regression model in fuzzy environment

The purpose of this paper is to discuss the problem for least squares fitting of fuzzy-valued data, which are expressed as fuzzy numbers, and to develop an S-shaped curve regression model for fitting this type of data. It is shown that the solution of the S-curve regression model is equivalent to the solution of the corresponding linear equations, and, furthermore, the solution can be explicitly obtained by solving the linear equations.     

Optimal Simplification of Cartographic Lines Using Shortest-path Formulations

Line simplification is a process by which unnecessary detail in cartographic data is eliminated. In the past, a variety of heuristics have been implemented to simplify lines. This paper describes practical algorithms which have been developed to provide optimal solutions. The line simplification problem is shown to have the special structure of an acyclic shortest-path problem. Three formulations are presented, which differ in the form of their objectives and/or constraints, and a solution algorithm is outlined for each formulation. Issues associated with implementation are addressed by using each algorithm to perform various degrees of simplification on a large example line. Possibilities for future research related to optimal line simplification are also discussed.     

A new method for interpolating in a convex subset of a Hilbert space

In this paper, interpolating curve or surface with linear inequality constraints is considered as a general convex optimization problem in a Reproducing Kernel Hilbert Space. The aim of the present paper is to propose an approximation method in a very general framework based on a discretized optimization problem in a finite-dimensional Hilbert space under the same set of constraints. We prove that the approximate solution converges uniformly to the optimal constrained interpolating function. Numerical examples are provided to illustrate this result in the case of boundedness and monotonicity constraints in one and two dimensions.     

Curve fitting with a Sobolev gradient method

Consider the problem of constructing a mathematical representation of a curve that satisfies constraints such as interpolation of specified points. This problem arises frequently in the context of both data fitting and Computer Aided Design. We treat the most general problem: the curve may or may not be constrained to lie in a plane; the constraints may involve specified points, tangent vectors, normal vectors, and/or curvature vectors, periodicity, or nonlinear inequalities representing shapepreservation criteria. Rather than the usual piecewise parametric polynomial (B-spline) or rational (NURB) formulation, we represent the curve by a discrete sequence of vertices along with first, second, and third derivative vectors at each vertex, where derivatives are with respect to arc length. This provides third-order geometric continuity and maximizes flexibility with an arbitrarily large number of degrees of freedom. The free parameters are chosen to minimize a fairness measure defined as a weighted sum of curve length, total curvature, and variation of curvature. We thus obtain a very challenging constrained optimization problem for which standard methods are ineffective. A Sobolev gradient method, however, is particularly effective. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Curve Fitting with Piecewise Polynomials

Polynomials and splines are frequently used as approximatingfunctions in curve fitting. This paper discusses curve fittingwith the more general piecewise polynomials employed as theapproximating functions. Various representations of piecewisepolynomials are discussed and one particular form is selectedas providing a basis for a well-conditioned formulation of theleast-squares curve-fitting problem. Continuous and discontinuousapproximations with fixed and free knots are considered fromthe points of view of existence, uniqueness and characterizationof solutions. Two general algorithms are suggested for the continuouscase with arbitrary degree and continuity with fixed knots.The imposition of end conditions is shown to be straightforward.Using the principles of dynamic programming a method is proposedthat enables global solutions to be obtained economically inthe case of discontinuous approximating functions with freeknots.     

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.     

Analysis of mathematical programming problems prior to applying the simplex algorithm

Large practical linear and integer programming problems are not always presented in a form which is the most compact representation of the problem. Such problems are likely to posses generalized upper bound(GUB) and related structures which may be exploited by algorithms designed to solve them efficiently. The steps of an algorithm which by repeated application reduces the rows, columns, and bounds in a problem matrix and leads to the freeing of some variables are first presented. The ‘unbounded solution’ and ‘no feasible solution’ conditions may also be detected by this. Computational results of applying this algorithm are presented and discussed. An algorithm to detect structure is then described. This algorithm identifies sets of variables and the corresponding constraint relationships so that the total number of GUB-type constraints is maximized. Comparisons of computational results of applying different heuristics in this algorithm are presented and discussed.     

Real-time optimisation of access control lists for efficient Internet packet filtering

This paper considers an optimisation problem encountered in the implementation of traffic policies on network routers, namely the ordering of rules in an access control list to minimise or reduce processing time and hence packet latency. The problem is formulated as an objective function with constraints and shown to be NP-complete by translation to a known problem. Exact and heuristic solution methods are introduced, discussed and compared and computational results given. The emphasis throughout is on practical implementation of the optimisation process, that is within the tight constraints of a production network router seeking to reduce latency, on-line, in real-time but without the overhead of significant extra computation.     

Asymptotic Results for Random Multidimensional Assignment Problems

The multidimensional assignment problem (MAP) is an NP-hard combinatorial optimization problem occurring in applications such as data association and target tracking. In this paper, we investigate characteristics of the mean optimal solution values for random MAPs with axial constraints. Throughout the study, we consider cost coefficients taken from three different random distributions: uniform, exponential and standard normal. In the cases of uniform and exponential costs, experimental data indicates that the mean optimal value converges to zero when the problem size increases. We give a short proof of this result for the case of exponentially distributed costs when the number of elements in each dimension is restricted to two. In the case of standard normal costs, experimental data indicates the mean optimal value goes to negative infinity with increasing problem size. Using curve fitting techniques, we develop numerical estimates of the mean optimal value for various sized problems. The experiments indicate that numerical estimates are quite accurate in predicting the optimal solution value of a random instance of the MAP.     

A feasible descent SQP algorithm for general constrained optimization without strict complementarity

In this paper, a class of optimization problems with equality and inequality constraints is discussed. Firstly, the original problem is transformed to an associated simpler problem with only inequality constraints and a parameter. The later problem is shown to be equivalent to the original problem if the parameter is large enough (but finite), then a feasible descent SQP algorithm for the simplified problem is presented. At each iteration of the proposed algorithm, a master direction is obtained by solving a quadratic program (which always has a feasible solution). With two corrections on the master direction by two simple explicit formulas, the algorithm generates a feasible descent direction for the simplified problem and a height-order correction direction which can avoid the Maratos effect without the strict complementarity, then performs a curve search to obtain the next iteration point. Thanks to the new height-order correction technique, under mild conditions without the strict complementarity, the globally and superlinearly convergent properties are obtained. Finally, an efficient implementation of the numerical experiments is reported.     

Estimating the Firm Value Distribution Function by Entropy Optimization and Geometric Programming

By applying the option pricing theory ideas, this paper models the estimation of firm value distribution function as an entropy optimization problem, subject to correlation constraints. It is shown that the problem can be converted to a dual of a computationally attractive primal geometric programming (GP) problem and easily solved using publicly available software. A numerical example involving stock price data from a Japanese company demonstrates the practical value of the GP approach. Noting the use of Monte Carlo simulation in option pricing and risk analysis and its difficulties in handling distribution functions subject to correlations, the GP based method discussed here may have some computational advantages in wider areas of computational finance in addition to the application discussed here.     

Cyclic reduction,dichotomy, and the estimation of differential equations

In the estimation of ordinary differential equations given observed data it is necessary to parametrize the solutions in a computationally tractable way in order to make comparisons with the given data. Typically, this is done by adjoining initial or boundary conditions, and this requires additional information on the solution structure in order to do this in a manner that leads to stable computation of the comparison solutions. Here, an alternative approach is described in which cyclic reduction is used to reduce the estimation problem to an optimization problem subject to a fixed number of equality constraints. If orthogonal transformations are used in the cyclic reduction process then it appears that stable computations are possible without the need for the structural information needed to devise the stable imbeddings. The aim of this paper is to provide evidence in support of this claim. In particular, it is shown that the cyclic reduction process is linked to a new family of representation of the solutions of the ODE system. Some properties of members of this family are described. These provide insight into the particular advantages of the orthogonal reduction form of cyclic reduction.     

Parameter optimization using algorithmic differentiation in a reduced-form model of the Atlantic thermohaline circulation

Optimizing some model parameters a reduced-form model of the Atlantic thermohaline circulation is fitted to data provided by a comprehensive climate model. Different techniques to compute stationary states of the reduced-form model are discussed. The fitting problem is formulated as weighted least-squares optimization problem with non-linear constraints that enforce a proper representation of the present climate. Possible formulations of the optimization problem are presented and compared with respect to their numerical treatment. The technique of algorithmic or automatic differentiation (AD) is used to provide gradient information that can be used in the optimization. The application of the AD software is described in detail and numerical results are given.     

A General Hybrid Optimization Strategy for Curve Fitting in the Non-uniform Rational Basis Spline Framework

In this paper, a general methodology to approximate sets of data points through Non-uniform Rational Basis Spline (NURBS) curves is provided. The proposed approach aims at integrating and optimizing the full set of design variables (both integer and continuous) defining the shape of the NURBS curve. To this purpose, a new formulation of the curve fitting problem is required: it is stated in the form of a constrained nonlinear programming problem by introducing a suitable constraint on the curvature of the curve. In addition, the resulting optimization problem is defined over a domain having variable dimension, wherein both the number and the value of the design variables are optimized. To deal with this class of constrained nonlinear programming problems, a global optimization hybrid tool has been employed. The optimization procedure is split in two steps: firstly, an improved genetic algorithm optimizes both the value and the number of design variables by means of a two-level Darwinian strategy allowing the simultaneous evolution of individuals and species; secondly, the optimum solution provided by the genetic algorithm constitutes the initial guess for the subsequent gradient-based optimization, which aims at improving the accuracy of the fitting curve. The effectiveness of the proposed methodology is proven through some mathematical benchmarks as well as a real-world engineering problem.     

An algorithm for combining data sets having different frames of reference

The task of fitting a curve or surface to a number of related data sets is common in metrology. Thedata matching problem arises when sets of supplementary measurements are added to those of an underlying base set. Each supplementary set may have its own reference frame. This problem is formally equivalent to thedata splicing problem in which no one set covers the entire region of interest. In either case, the presence of reference-frame transformation parameters means that least-squares fitting of a curve to the assembled data is generally a nonlinear problem. A linear version of this problem was treated in Anthony and Harris [1].An algorithm is presented which exploits the inherent block structure of the problem, thereby reducing memory requirements and execution time. It employs the Gauss-Newton optimisation technique, returning both the fittingand reference-frame transformation parameters. The approach is quite general. Results are presented in the case of indentation analysis (for hardness testing, where the critical parameters are those of the fit). Applications also arise for which the transformation parameters are of primary interest; one such application is indicated.     

An Iterative Sparse-Group Lasso

In high-dimensional supervised learning problems, sparsity constraints in the solution often lead to better performance and interpretability of the results. For problems in which covariates are grouped and sparse structure are desired, both on group and within group levels, the sparse-group lasso (SGL) regularization method has proved to be very efficient. Under its simplest formulation, the solution provided by this method depends on two weight parameters that control the penalization on the coefficients. Selecting these weight parameters represents a major challenge. In most of the applications of the SGL, this problem is left aside, and the parameters are either fixed based on a prior information about the data, or chosen to minimize some error function in a grid of possible values. However, an appropriate choice of the parameters deserves more attention, considering that it plays a key role in the structure and interpretation of the solution. In this sense, we present a gradient-free coordinate descent algorithm that automatically selects the regularization parameters of the SGL. We focus on a more general formulation of this problem, which also includes individual penalizations for each group. The advantages of our approach are illustrated using both real and synthetic datasets. Supplementary materials for this article are available online.     

Global solution of semi-infinite programs

Optimization problems involving a finite number of decision variables and an infinite number of constraints are referred to as semi-infinite programs (SIPs). Existing numerical methods for solving nonlinear SIPs make strong assumptions on the properties of the feasible set, e.g., convexity and/or regularity, or solve a discretized approximation which only guarantees a lower bound to the true solution value of the SIP. Here, a general, deterministic algorithm for solving semi-infinite programs to guaranteed global optimality is presented. A branch-and-bound (B&B) framework is used to generate convergent sequences of upper and lower bounds on the SIP solution value. The upper-bounding problem is generated by replacing the infinite number of real-valued constraints with a finite number of constrained inclusion bounds; the lower-bounding problem is formulated as a convex relaxation of a discretized approximation to the SIP. The SIP B&B algorithm is shown to converge finitely to –optimality when the subdivision and discretization procedures used to formulate the node subproblems are known to retain certain convergence characteristics. Other than the properties assumed by globally-convergent B&B methods (for finitely-constrained NLPs), this SIP algorithm makes only one additional assumption: For every minimizer x* of the SIP there exists a sequence of Slater points x_n for which (cf. Section 5.4). Numerical results for test problems in the SIP literature are presented. The exclusion test and a modified upper-bounding problem are also investigated as heuristic approaches for alleviating the computational cost of solving a nonlinear SIP to guaranteed global optimality.     

A Semidefinite Programming Heuristic for Quadratic Programming Problems with Complementarity Constraints

The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these feasible solutions and the best resulting solution provides an estimate for the optimal solution to the quadratic program with complementarity constraints. Computational testing of such an approach is described for a problem arising in portfolio optimization.Research supported in part by the National Science Foundations VIGRE Program (Grant DMS-9983646).Research partially supported by NSF Grant number CCR-9901822.