An Exact Reformulation Algorithm for Large Nonconvex NLPs Involving Bilinear Terms

Many nonconvex nonlinear programming (NLP) problems of practical interest involve bilinear terms and linear constraints, as well as, potentially, other convex and nonconvex terms and constraints. In such cases, it may be possible to augment the formulation with additional linear constraints (a subset of Reformulation-Linearization Technique constraints) which do not affect the feasible region of the original NLP but tighten that of its convex relaxation to the extent that some bilinear terms may be dropped from the problem formulation. We present an efficient graph-theoretical algorithm for effecting such exact reformulations of large, sparse NLPs. The global solution of the reformulated problem using spatial Branch-and Bound algorithms is usually significantly faster than that of the original NLP. We illustrate this point by applying our algorithm to a set of pooling and blending global optimization problems.     

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.     

A SELF-ADAPTIVE ALGORITHM FOR NONLINEAR LEAST SQUARES WITH LINEAR CONSTRAINTS

An algorithm for solving nonlinear least squares problems with general linear inequality constraints is described.At each step,the problem is reduced to an unconstrained linear least squares problem in a subs pace defined by the active constraints,which is solved using the quasi-Newton method.The major update formula is similar to the one given by Dennis,Gay and Welsch (1981).In this paper,we state the detailed implement of the algorithm,such as the choice of active set,the solution of subproblem and the avoidance of zigzagging.We also prove the globally convergent property of the algorithm.     

A New Quadratic Semi-infinite Programming Algorithm Based on Dual Parametrization

The so called dual parameterization method for quadratic semi-infinite programming (SIP) problems is developed recently. A dual parameterization algorithm is also proposed for numerical solution of such problems. In this paper, we present and improved adaptive algorithm for quadratic SIP problems with positive definite objective and multiple linear infinite constraints. In each iteration of the new algorithm, only a quadratic programming problem with a limited dimension and a limited number of constraints is required to be solved. Furthermore, convergence result is given. The efficiency of the new algorithm is shown by solving a number of numerical examples.     

Theory and Computation of Best Strict Constrained Chebyshev Approximation of Discrete Data

Apart from general linear programming algorithms, the publishedtechniques for computing the Chebyshev solution of overdeterminedsystems of linear equations do not allow for linear constraintson the approximation. The necessity for such constraints arisesnaturally when functions have to be fitted to discrete data,and is a subproblem in continuous constrained Chebyshev approximation.We extend the well-known exchange algorithm to solve this problemand use numerically stable techniques to include the cases wherethe matrix of coefficients is rank-deficient and/or ill-conditioned.A simple extension of the algorithm yields the "strict" Chebyshevapproximation. Numerical examples are given which testify tothe robustness of the algorithm.     

The semi-continuous quadratic mixture design problem: Description and branch-and-bound approach

The semi-continuous quadratic mixture design problem (SCQMDP) is described as a problem with linear, quadratic and semi-continuity constraints. Moreover, a linear cost objective and an integer valued objective are introduced. The goal is to deal with the SCQMD problem from a branch-and-bound perspective generating robust solutions. Therefore, an algorithm is outlined which identifies instances where decision makers tighten requirements such that no ε-robust solution exists. The algorithm is tested on several cases derived from industry.     

An alternate implementation of Goldfarb's minimization algorithm

Goldfarb's algorithm, which is one of the most successful methods for minimizing a function of several variables subject to linear constraints, uses a single matrix to keep second derivative information and to ensure that search directions satisfy any active constraints. In the original version of the algorithm this matrix is full, but by making a change of variables so that the active constraints become bounds on vector components, this matrix is transformed so that the dimension of its non-zero part is only the number of variablesless the number of active constraints. It is shown how this transformation may be used to give a version of the algorithm that usually provides a good saving in the amount of computation over the original version. Also it allows the use of sparse matrix techniques to take advantage of zeros in the matrix of linear constraints. Thus the method described can be regarded as an extension of linear programming to allow a non-linear objective function.     

An Algorithm for Solving Optimization Problems with One Linear Objective Function and Finitely Many Constraints of Fuzzy Relation Inequalities

An optimization model with one linear objective function and fuzzy relation equation constraints was presented by Fang and Li (1999) as well as an efficient solution procedure was designed by them for solving such a problem. A more general case of the problem, an optimization model with one linear objective function and finitely many constraints of fuzzy relation inequalities, is investigated in this paper. A new approach for solving this problem is proposed based on a necessary condition of optimality given in the paper. Compared with the known methods, the proposed algorithm shrinks the searching region and hence obtains an optimal solution fast. For some special cases, the proposed algorithm reaches an optimal solution very fast since there is only one minimum solution in the shrunk searching region. At the end of the paper, two numerical examples are given to illustrate this difference between the proposed algorithm and the known ones.     

Linearly constrained minimax optimization

We present an algorithm for nonlinear minimax optimization subject to linear equality and inequality constraints which requires first order partial derivatives. The algorithm is based on successive linear approximations to the functions defining the problem. The resulting linear subproblems are solved in the minimax sense subject to the linear constraints. This ensures a feasible-point algorithm. Further, we introduce local bounds on the solutions of the linear subproblems, the bounds being adjusted automatically, depending on the quality of the linear approximations. It is proved that the algorithm will always converge to the set of stationary points of the problem, a stationary point being defined in terms of the generalized gradients of the minimax objective function. It is further proved that, under mild regularity conditions, the algorithm is identical to a quadratically convergent Newton iteration in its final stages. We demonstrate the performance of the algorithm by solving a number of numerical examples with up to 50 variables, 163 functions, and 25 constraints. We have also implemented a version of the algorithm which is particularly suited for the solution of restricted approximation problems.This work has been supported by the Danish Natural Science Research Council, Grant No. 511-6874.     

Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints

The well known DIRECT (DIviding RECTangles) algorithm for global optimization requires bound constraints on variables and does not naturally address additional linear or nonlinear constraints. A feasible region defined by linear constraints may be covered by simplices, therefore simplicial partitioning may tackle linear constraints in a very subtle way. In this paper we demonstrate this advantage of simplicial partitioning by applying a recently proposed deterministic simplicial partitions based DISIMPL algorithm for optimization problems defined by general linear constraints (Lc-DISIMPL). An extensive experimental investigation reveals advantages of this approach to such problems comparing with different constraint-handling methods, proposed for use with DIRECT. Furthermore the Lc-DISIMPL algorithm gives very competitive results compared to a derivative-free particle swarm algorithm (PSwarm) which was previously shown to give very promising results. Moreover, DISIMPL guarantees the convergence to the global solution, whereas the PSwarm algorithm sometimes fails to converge to the global minimum.     

基于松弛策略解半无限规划模型的显式修正算法

讨论了一类线性半无限最优规划模型的求解算法.采用松弛方法解其系列子问题LP(T_k)及DLP(T_k),基于松弛策略和在适当的假设条件下,提出了一个我们称之为显式算法的新型算法.新算法的主要改进之处是算法在每一步迭代计算时,允许丢弃一些不必要的约束.在这种方式下,算法避免了求解系列太大规模的子问题.最后,基于提出的显式修正算法,并与传统割平面方法和已有文献中的松弛修正算法、对同一问题作了初步的数值比较实验.     

A ROBUST SUPERLINEARLY CONVERGENT ALGORITHM FOR LINEARLY CONSTRAINED OPTIMIZATION PROBLEMS UNDER DEGENERACY

1.IntroductionTheproblemconsideredinthispaperiswhereX={xER"laTx5hi,jEI={l,.'.,m}},ajeR"(jEI)areallcolumn*ThisresearchissupportedbytheNationalNaturalSciencesFoundationofChinaandNaturalSciencesFoundationofHunanProvince.vectors,hiERI(j6I)areallscalars,andf:R"-- Risacontinuouslydifferentiablefunction.Weonlyconsiderinequalityconstraintsheresinceanyequalitycanbeexpressedastwoinequalities.Withoutassumingregularityofthelinearconstraints,thereisnotanydifficultyinextendingtheresultstothegenera…     

A partitioning and bounded variable algorithm for linear programming

An interesting new partitioning and bounded variable algorithm (PBVA) is proposed for solving linear programming problems. The PBVA is a variant of the simplex algorithm which uses a modified form of the simplex method followed by the dual simplex method for bounded variables. In contrast to the two-phase method and the big M method, the PBVA does not introduce artificial variables. In the PBVA, a reduced linear program is formed by eliminating as many variables as there are equality constraints. A subproblem containing one ‘less than or equal to’ constraint is solved by executing the simplex method modified such that an upper bound is placed on an unbounded entering variable. The remaining constraints of the reduced problem are added to the optimal tableau of the subproblem to form an augmented tableau, which is solved by applying the dual simplex method for bounded variables. Lastly, the variables that were eliminated are restored by substitution. Differences between the PBVA and two other variants of the simplex method are identified. The PBVA is applied to solve an example problem with five decision variables, two equality constraints, and two inequality constraints. In addition, three other types of linear programming problems are solved to justify the advantages of the PBVA.     

用非线性方程组求解等式约束非线性规划问题的降维算法

本文研究线性和非线性等式约束非线性规划问题的降维算法.首先,利用一般等式约束问题的降维方法,将线性等式约束非线性规划问题转换成一个非线性方程组,解非线性方程组即得其解;然后,对线性和非线性等式约束非线性规划问题用Lagrange乘子法,将非线性约束部分和目标函数构成增广的Lagrange函数,并保留线性等式约束,这样便得到一个线性等式约束非线性规划序列,从而,又将问题转化为求解只含线性等式约束的非线性规划问题.     

Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming

When the follower's optimality conditions are both necessary and sufficient, the nonlinear bilevel program can be solved as a global optimization problem. The complementary slackness condition is usually the complicating constraint in such problems. We show how this constraint can be replaced by an equivalent system of convex and separable quadratic constraints. In this paper, we propose different methods for finding the global minimum of a concave function subject to quadratic separable constraints. The first method is of the branch and bound type, and is based on rectangular partitions to obtain upper and lower bounds. Convergence of the proposed algorithm is also proved. For computational purposes, different procedures that accelerate the convergence of the proposed algorithm are analysed. The second method is based on piecewise linear approximations of the constraint functions. When the constraints are convex, the problem is reduced to global concave minimization subject to linear constraints. In the case of non-convex constraints, we use zero-one integer variables to linearize the constraints. The number of integer variables depends only on the concave parts of the constraint functions.Parts of the present paper were prepared while the second author was visiting Georgia Tech and the University of Florida.     

A Dual Simplex Algorithm for Piecewise-Linear Programming

This paper presents a dual piecewise-linear simplex algorithm for minimizing convex separable piecewise-linear functions subject to linear constraints. It is an extension of Fourier's work on piecewise-linear programming to the dual piecewise-linear simplex algorithm. This algorithm has advantages over indirect methods which solve equivalent linear programs augmented by additional variables and/or constraints. Computational experience is presented which demonstrates the efficiency these advantages contribute.     

An Adaptive Dual Parametrization Algorithm for Quadratic Semi-infinite Programming Problems

The so called dual parametrization method for quadratic semi-infinite programming (SIP) problems is developed recently for quadratic SIP problems with a single infinite constraint. A dual parametrization algorithm is also proposed for numerical solution of such problems. In this paper, we consider quadratic SIP problems with positive definite objective and multiple linear infinite constraints. All the infinite constraints are supposed to be continuously dependent on their index variable on a compact set which is defined by a number equality and inequalities. We prove that in the multiple infinite constraint case, the minimu parametrization number, just as in the single infinite constraint case, is less or equal to the dimension of the SIP problem. Furthermore, we propose an adaptive dual parametrization algorithm with convergence result. Compared with the previous dual parametrization algorithm, the adaptive algorithm solves subproblems with much smaller number of constraints. The efficiency of the new algorithm is shown by solving a number of numerical examples.     

A fast algorithm for solving a linear feasibility problem with application to Intensity-Modulated Radiation Therapy

The goal of Intensity-Modulated Radiation Therapy (IMRT) is to deliver sufficient doses to tumors to kill them, but without causing irreparable damage to critical organs. This requirement can be formulated as a linear feasibility problem. The sequential (i.e., iteratively treating the constraints one after another in a cyclic fashion) algorithm ART3 is known to find a solution to such problems in a finite number of steps, provided that the feasible region is full dimensional. We present a faster algorithm called ART3+. The idea of ART3+ is to avoid unnecessary checks on constraints that are likely to be satisfied. The superior performance of the new algorithm is demonstrated by mathematical experiments inspired by the IMRT application.     

An algorithm for linearly constrained convex nondifferentiable minimization problems

A readily implementable algorithm is proposed for minimizing any convex, not necessarily differentiable, function f of several variables subject to a finite number of linear constraints. The algorithm requires only the calculation of f at designated feasible points. At each iteration a lower polyhedral approximation to f is constructed from a few previously calculated subgradients and an aggregate subgradient. The recursively updated aggregate subgradient accumulates the subgradient information to deal with nondifferentiability of f. The polyhedral approximation and the linear constraints generate constraints in the search direction finding subproblem that is a quadratic programming problem. Then a step length is found by approximate line search. It is shown that the algorithm converges to a solution, if any.     

A finite steps algorithm for solving convex feasibility problems

This paper develops a new variant of the classical alternating projection method for solving convex feasibility problems where the constraints are given by the intersection of two convex cones in a Hilbert space. An extension to the feasibility problem for the intersection of two convex sets is presented as well. It is shown that one can solve such problems in a finite number of steps and an explicit upper bound for the required number of steps is obtained. As an application, we propose a new finite steps algorithm for linear programming with linear matrix inequality constraints. This solution is computed by solving a sequence of a matrix eigenvalue decompositions. Moreover, the proposed procedure takes advantage of the structure of the problem. In particular, it is well adapted for problems with several small size constraints.