A computational method for the indefinite quadratic programming problem

We present an algorithm for the quadratic programming problem of determining a local minimum of ?(x)=$\text{1}\text{2}$x^TQx+c^Tx such that A^Tx?b where Q ymmetric matrix which may not be positive definite. Our method combines the active constraint strategy of Murray with the Bunch-Kaufman algorithm for the stable decomposition of a symmetric matrix. Under the active constraint strategy one solves a sequence of equality constrained problems, the equality constraints being chosen from the inequality constraints defining the original problem. The sequence is chosen so that ?(x) continues to decrease and x remains feasible. Each equality constrained subproblem requires the solution of a linear system with the projected Hessian matrix, which is symmetric but not necessarily positive definite. The Bunch-Kaufman algorithm computes a decomposition which facilitates the stable determination of the solution to the linear system. The heart of this paper is a set of algorithms for updating the decomposition as the method progresses through the sequence of equality constrained problems. The algorithm has been implemented in a FORTRAN program, and a numerical example is given.     

Separable nonlinear least squares fitting with linear bound constraints and its application in magnetic resonance spectroscopy data quantification

An application in magnetic resonance spectroscopy quantification models a signal as a linear combination of nonlinear functions. It leads to a separable nonlinear least squares fitting problem, with linear bound constraints on some variables. The variable projection (VARPRO) technique can be applied to this problem, but needs to be adapted in several respects. If only the nonlinear variables are subject to constraints, then the Levenberg–Marquardt minimization algorithm that is classically used by the VARPRO method should be replaced with a version that can incorporate those constraints. If some of the linear variables are also constrained, then they cannot be projected out via a closed-form expression as is the case for the classical VARPRO technique. We show how quadratic programming problems can be solved instead, and we provide details on efficient function and approximate Jacobian evaluations for the inequality constrained VARPRO method.     

Spline smoothing under constraints on derivatives

An efficient algorithm for computing a smoothing polynomial splines under inequality constraints on derivatives is introduced where both order and breakpoints ofs can be prescribed arbitrarily. By using the B-spline representation ofs, the original semi-infinite constraints are replaced by stronger finite ones, leading to a least squares problem with linear inequality constraints. Then these constraints are transformed into simple box constraints by an appropriate substitution of variables so that efficient standard techniques for solving such problems can be applied. Moreover, the smoothing term commonly used is replaced by a cheaply computable approximation. All matrix transformations are realized by numerically stable Givens rotations, and the band structure of the problem is exploited as far as possible.     

An efficient curvilinear method for the minimization of a nonlinear function subject to linear inequality constraints

An algorithm is presented that minimizes a continuously differentiable function in several variables subject to linear inequality constraints. At each step of the algorithm an arc is generated along which a move is performed until either a point yielding a sufficient descent in the function value is determined or a constraint boundary is encountered. The decision to delite a constraint from the list of active constraints is based upon periodic estimates of the Kuhn-Tucker multipliers. The curvilinear search paths are obtained by solving a linear approximation to the differential equation of the continuous steepest descent curve for the objective function on the equality constrained region defined by the constraints which are required to remain binding. If the Hessian matrix of the objective function has certain properties and if the constraint gradients are linearly independent, the sequence generated by the algorithm converges to a point satisfying the Kuhn-Tucker optimality conditions at a rate that is at least quadratic.     

Preconditioned conjugate gradient algorithms for nonconvex problems with box constraints

The paper describes new conjugate gradient algorithms for large scale nonconvex problems with box constraints. In order to speed up convergence the algorithms employ scaling matrices which transform the space of original variables into the space in which Hessian matrices of the problem’s functionals have more clustered eigenvalues. This is done by applying limited memory BFGS updating matrices. Once the scaling matrix is calculated, the next few conjugate gradient iterations are performed in the transformed space. The box constraints are treated efficiently by the projection. We also present a limited memory quasi-Newton method which is a special version of our general algorithm. The presented algorithms have strong global convergence properties, in particular they identify constraints active at a solution in a finite number of iterations. We believe that they are competitive to the L-BFGS-B method and present some numerical results which support our claim.     

Reformulation and solution approach for non-separable integer quadratic programs

We consider quadratic programs with pure general integer variables. The objective function is quadratic and convex and the constraints are linear. An exact solution approach is proposed. It is decomposed into two phases. In the first phase, the initial problem is reformulated into an equivalent problem with a separable objective function. This is done by use of a Gauss decomposition of the Hessian matrix of the initial problem and requires the addition of some continuous variables and constraints. In the second phase, the reformulated problem is linearized by an approximation of each squared term by a set of K linear functions that correspond to the tangents of a hyperbola in K points. We give a proof of the intuitive property that when K is large enough, the optimal value of the obtained linear program is very close to optimal value of the two previous problems, the initial problem and the reformulated separable problem. The reminder is dedicated to the implementation of a branch-and-bound algorithm for the solution of linearized problem, and its application to a set of instances. Several points are considered among which choice of the right value for parameter K and the implementation of a sophisticated heuristic solution algorithm. The numerical comparison is done with CPLEX 12.2 since, in this case, the initial problem as well as the problem reformulated by the first step can be solved by CPLEX. We show that with our approach, the total CPU time is divided by a factor ranging from 1.2 to 131.6 for instances with 40–60 variables.     

A Proportioning Based Algorithm with Rate of Convergence for Bound Constrained Quadratic Programming

The proportioning algorithm with projections turned out to be an efficient algorithm for iterative solution of large quadratic programming problems with simple bounds and box constraints. Important features of this active set based algorithm are the adaptive precision control in the solution of auxiliary linear problems and capability to add or remove many indices from the active set in one step. In this paper a modification of the algorithm is presented that enables to find its rate of convergence in terms of the spectral condition number of the Hessian matrix and avoid any backtracking. The modified algorithm is shown to preserve the finite termination property of the original algorithm for problems that are not dual degenerate.     

An algorithm for single machine sequencing with release dates to minimize total weighted completion time

Each of n jobs is to be processed without interruption on a single machine which can handle only one job at a time. Each job becomes available for processing at its release date, requires a processing time and has a positive weight. Given a processing order of the jobs, the earliest completion time for each job can be computed. The objective is to find a processing order of the jobs which minimizes the sum of weighted completion times. In this paper a branch and bound algorithm for the problem is derived. Firstly a heuristic is presented which is used in calculating the lower bound. Then the lower bound is obtained by performing a Lagrangean relaxation of the release date constraints; the Lagrange multipliers are chosen so that the sequence generated by the heuristic is an optimum solution of the relaxed problem thus yielding a lower bound. A method to increase the lower bound by deriving improved constraints to replace the original release date constraints is given. The algorithm, which includes several dominance rules, is tested on problems with up to fifty jobs. The computational results indicate that the version of the lower bound using improved constraints is superior to the original version.     

A reduced gradient method for quadratic programs with quadratic constraints and lp-constrained lp-approximation problems

A dual algorithm is developed for solving a general class of nonlinear programs that properly contains all convex quadratic programs with quadratic constraints and l_p-constrained l_p-approximation problems. The general dual program to be solved has essentially linear constraints but the objective function is nondifferentiable when certain variables equal zero. Modifications to the reduced gradient method for linearly constrained problems are presented that overcome the numerical difficulties associated with the nondifferentiable objective function. These modifications permit ‘blocks’ of variables to move to and away from zero on certain iterations even though the objective function is nondifferentiable at points having a block of variables equal to zero.     

运筹学中若干线性目标规划和线性规划的人工智能-代数解法

运筹学中的线性目标规划和线性规划问题一直分别采用修正单纯形法和单纯形法求解.当变量稍多时计算还是有些繁琐、费时,最近作者通过研究发现,可应用人工智能-代数方法求得这两类问题的解,而且具有相当广泛的适用性.若干例题说明,本法的结果和传统方法的结果由于传统算法在计算中发生的错误,除少数例外大都是一致的.本文的一个 重要目的是希望和广大读者一起研究该方法是否具有通用性.     

Mixed-integer quadratic programming

This paper considers mixed-integer quadratic programs in which the objective function is quadratic in the integer and in the continuous variables, and the constraints are linear in the variables of both types. The generalized Benders' decomposition is a suitable approach for solving such programs. However, the program does not become more tractable if this method is used, since Benders' cuts are quadratic in the integer variables. A new equivalent formulation that renders the program tractable is developed, under which the dual objective function is linear in the integer variables and the dual constraint set is independent of these variables. Benders' cuts that are derived from the new formulation are linear in the integer variables, and the original problem is decomposed into a series of integer linear master problems and standard quadratic subproblems. The new formulation does not introduce new primary variables or new constraints into the computational steps of the decomposition algorithm.The author wishes to thank two anonymous referees for their helpful comments and suggestions for revising the paper.     

An O(n2) simplex algorithm for a class of linear programs with tree structure

In connection with the optimal design of centralized circuit-free networks linear 0–1 programming problems arise which are related to rooted trees. For each problem the variables correspond to the edges of a given rooted tree T. Each path from a leaf to the root of T, together with edge weights, defines a linear constraint, and a global linear objective is to be maximized. We consider relaxations of such problems where the variables are not restricted to 0 or 1 but are allowed to vary continouosly between these bounds. The values of the optimal solutions of such relaxations may be used in a branch and bound procedure for the original 0–1 problem. While in [10] a primal algorithm for these relaxations is discussed, in this paper, we deal with the dual linear program and present a version of the simplex algorithm for its solution which can be implemented to run in time O(n²). For balanced trees T this time can be reduced to O(n log n).     

Entropic perturbation method for solving a system of linear inequalities

The problem of finding an $\text{x∈}\text{R}{}^{\mathrm{n}}$ such that Ax⩽b and x⩾0 arises in numerous contexts. We propose a new optimization method for solving this feasibility problem. After converting Ax⩽b into a system of equations by introducing a slack variable for each of the linear inequalities, the method imposes an entropy function over both the original and the slack variables as the objective function. The resulting entropy optimization problem is convex and has an unconstrained convex dual. If the system is consistent and has an interior solution, then a closed-form formula converts the dual optimal solution to the primal optimal solution, which is a feasible solution for the original system of linear inequalities. An algorithm based on the Newton method is proposed for solving the unconstrained dual problem. The proposed algorithm enjoys the global convergence property with a quadratic rate of local convergence. However, if the system is inconsistent, the unconstrained dual is shown to be unbounded. Moreover, the same algorithm can detect possible inconsistency of the system. Our numerical examples reveal the insensitivity of the number of iterations to both the size of the problem and the distance between the initial solution and the feasible region. The performance of the proposed algorithm is compared to that of the surrogate constraint algorithm recently developed by Yang and Murty. Our comparison indicates that the proposed method is particularly suitable when the number of constraints is larger than that of the variables and the initial solution is not close to the feasible region.     

Constructing a monotonic quadratic objective function in n variables from a few two-dimensional indifferences

We develop a model for constructing quadratic objective functions in n target variables. At the input, a decision maker is asked a few simple questions about his ordinal preferences (comparing two-dimensional alternatives in terms `better', `worse', `indifferent'). At the output, the model mathematically derives a quadratic objective function used to evaluate n-dimensional alternatives.Thus the model deals with some imaginary decisions (criteria aggregates) at the input, and disaggregates the decision maker's preference into partial criteria and their cross-correlations (=a quadratic objective function). Therefore, the model provides an approximation step which is next to the disaggregation of a preference into additively separable linear criteria with weight coefficients.The model is based on least squares fitting a quadratic indifference hypersurface (if n=2, indifference curve) to several alternatives which are supposed to be equivalent in preference. The resulting ordinal preference is independent of the cardinal utility scale used in intermediate computations which implies that the model is ordinal. The monotonicity of the quadratic objective function is implemented by means of a finite number of linear constraints, so that the computational model is reduced to restricted least squares.In illustration, we construct a quadratic objective function of German economic policy in four target variables: inflation, unemployment, GNP growth, and increase in public debt. This objective function is used to evaluate the German economic development in 1980–1994.In another application, we construct a quadratic objective function of ski station customers. Then it is used to adjust prices of 10 ski stations to the South of Stuttgart.In Appendix A we provide an original fast algorithm for restricted least squares and quadratic programming used in the main model.     

线性比式和规划问题的输出空间分支定界算法

本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的.     

The balanced linear programming problem

The Balanced Linear Programming Problem (BLPP) arises in situations which require equitable distribution of a scarce resource. The BLPP can be transformed to the standard form of the linear programming problem by introducing 2∥N∥ + 2 additional variables and 2∥N∥ additional constraints. This transformation is not desirable from the computational point of view for larger values of ∥N∥ as it increases the problem size substantially. It is also undesirable from a theoretical perspective as it might affect the special structure of the constraint matrix. In this paper, we develop an algorithm for the BLPP which does not require problem enlargement. The algorithm is based on the relationship between the BLPP and the minimax linear programming problem, and solving the latter problem parametrically. Our algorithm, in essence, performs steps that are similar to those performed in the parametric simplex method with parametric right hand side. We then adapt our algorithm for the network flow problem and this specialized algorithm can be applied on the network directly without maintaining the simplex tableau.     

Lower bounds for nonlinear assignment problems using many body interactions

This paper concerns lower bounding techniques for the general α-adic assignment problem. The nonlinear objective function is linearized by the introduction of additional variables and constraints, thus yielding a mixed integer linear programming formulation of the problem. The concept of many body interactions is introduced to strengthen this formulation and incorporated in a modified formulation obtained by lifting the original representation to a higher dimensional space. This process involves two steps — (i) addition of new variables and constraints and (ii) incorporation of the new variables in the objective function. If this lifting process is repeated β times on an α-adic assignment problem along with the incorporation of higher order interactions, it results in the mixed-integer formulation of an equivalent (α + β)-adic assignment problem. The incorporation of many body interactions in the higher dimensional formulation improves its degeneracy properties and is also critical to the derivation of decomposition methods for the solution of these large scale mathematical programs in the higher dimensional space. It is shown that a lower bound to the optimal solution of the corresponding linear programming relaxation can be obtained by dualizing a subset of constraints in this formulation and solving O(N^2(α+β−1)) linear assignment problems, whose coefficients depend on the dual values. Moreover, it is proved that the optimal solution to the LP relaxation is obtained if we use the optimal duals for the solution of the linear assignment problems. This concept of many body interactions could be applied in designing algorithms for the solution of formulations obtained by lifting general MILP's. We illustrate all these concepts on the quadratic assignment problems With these decomposition bounds, we have found the provably optimal solutions of two unsolved QAP's of size 32 and have also improved upon existing lower bounds for other QAP's.     

Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows

In this paper, we develop a simultaneous column-and-row generation algorithm that could be applied to a general class of large-scale linear programming problems. These problems typically arise in the context of linear programming formulations with exponentially many variables. The defining property for these formulations is a set of linking constraints, which are either too many to be included in the formulation directly, or the full set of linking constraints can only be identified, if all variables are generated explicitly. Due to this dependence between columns and rows, we refer to this class of linear programs as problems with column-dependent-rows. To solve these problems, we need to be able to generate both columns and rows on-the-fly within an efficient solution approach. We emphasize that the generated rows are structural constraints and distinguish our work from the branch-and-cut-and-price framework. We first characterize the underlying assumptions for the proposed column-and-row generation algorithm. These assumptions are general enough and cover all problems with column-dependent-rows studied in the literature up until now to the best of our knowledge. We then introduce in detail a set of pricing subproblems, which are used within the proposed column-and-row generation algorithm. This is followed by a formal discussion on the optimality of the algorithm. To illustrate our approach, the paper is concluded by applying the proposed framework to the multi-stage cutting stock and the quadratic set covering 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.     

Piecewise-linear programming: The compact (CPLP) algorithm

A compact algorithm is presented for solving the convex piecewise-linear-programming problem, formulated by means of a separable convex piecewise-linear objective function (to be minimized) and a set of linear constraints. This algorithm consists of a finite sequence of cycles, derived from the simplex method, characteritic of linear programming, and the line search, characteristic of nonlinear programming. Both the required storage and amount of calculation are reduced with respect to the usual approach, based on a linear-programming formulation with an expanded tableau. The tableau dimensions arem×(n+1), wherem is the number of constraints andn the number of the (original) structural variables, and they do not increase with the number of breakpoints of the piecewise-linear terms constituting the objective function.