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

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

A new method for solving fully fuzzy linear programming problems

Lotfi et al. [Solving a full fuzzy linear programming using lexicography method and fuzzy approximate solution, Appl. Math. Modell. 33 (2009) 3151–3156] pointed out that there is no method in literature for finding the fuzzy optimal solution of fully fuzzy linear programming (FFLP) problems and proposed a new method to find the fuzzy optimal solution of FFLP problems with equality constraints. In this paper, a new method is proposed to find the fuzzy optimal solution of same type of fuzzy linear programming problems. It is easy to apply the proposed method compare to the existing method for solving the FFLP problems with equality constraints occurring in real life situations. To illustrate the proposed method numerical examples are solved and the obtained results are discussed.     

线性等式约束多目标规划的一个降维算法

本文提出具有线性等式约束多目标规划问题的一个降维算法．当目标函数全是二次或线性但至少有一个二次型时，用线性加权法转化原问题为单目标二次规划，再用降维方法转化为求解一个线性方程组．若目标函数非上述情形，首先用线性加权法将原问题转化为具有线性等式约束的非线性规划，然后，对这一非线性规划的目标函数二次逼近，构成线性等式约束二次规划序列，用降维法求解，直到满足精度要求为止．     

A linear programming-based optimization algorithm for solving nonlinear programming problems

In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems.     

Bivariate least squares approximation with linear constraints

In this article linear least squares problems with linear equality constraints are considered, where the data points lie on the vertices of a rectangular grid. A fast and efficient computational method for the case when the linear equality constraints can be formulated in a tensor product form is presented. Using the solution of several univariate approximation problems the solution of the bivariate approximation problem can be derived easily. AMS subject classification (2000)  65D05, 65D07, 65D10, 65F05, 65F20     

线性空间中集值映射向量优化问题的最优性条件与Lagrangian乘子

本文在广义次似凸性假设下,利用择一性定理,在线性空间中获得了含等式与不等式约式集值向量最优化问题的Kuhn-Tucker型最优性条件及Lagrangian乘子定理。     

线性无关假设如何影响非线性约束最优化算法

首先综述非线性约束最优化最近的一些进展. 首次定义了约束最优化算法的全局收敛性. 注意到最优性条件的精确性和算法近似性之间的差异, 并回顾等式约束最优化的原始的Newton 型算法框架, 即可理解为什么约束梯度的线性无关假设应该而且可以被弱化. 这些讨论被扩展到不等式约束最优化问题. 然后在没有线性无关假设条件下, 证明了一个使用精确罚函数和二阶校正技术的算法可具有超线性收敛性. 这些认知有助于接下来开发求解包括非线性半定规划和锥规划等约束最优化问题的更加有效的新算法.     

线性约束三次规划问题的全局最优性必要条件和最优化算法

讨论了带线性不等式约束三次规划问题的最优性条件和最优化算法. 首先, 讨论了带有线性不等式约束三次规划问题的 全局最优性必要条件. 然后, 利用全局最优性必要条件, 设计了解线性约束三次规划问题的一个新的局部最优化算法(强局部最优化算法). 再利用辅助函数和所给出的新的局部最优化算法, 设计了带有线性不等式约束三 规划问题的全局最优化算法. 最后, 数值算例说明给出的最优化算法是可行的、有效的.     

两个线性模型间最优线性无偏预测的等价性

设M1和M2是两个带有预测量的线性模型,通过使用矩阵秩方法,本文给出了模型M1下预测量的最优线性无偏预测同时也是模型M2下的最优线性无偏预测的充分必要条件.作为这个结果的应用,我们给出了两个线性混合模型间最优线性无偏预测等价性的充分必要条件.     

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 transformation technique for optimal control problems with partially linear state inequality constraints

This paper considers optimal control problems involving the minimization of a functional subject to differential constraints, terminal constraints, and a state inequality constraint. The state inequality constraint is of a special type, namely, it is linear in some or all of the components of the state vector.A transformation technique is introduced, by means of which the inequality-constrained problem is converted into an equality-constrained problem involving differential constraints, terminal constraints, and a control equality constraint. The transformation technique takes advantage of the partial linearity of the state inequality constraint so as to yield a transformed problem characterized by a new state vector of minimal size. This concept is important computationally, in that the computer time per iteration increases with the square of the dimension of the state vector.In order to illustrate the advantages of the new transformation technique, several numerical examples are solved by means of the sequential gradient-restoration algorithm for optimal control problems involving nondifferential constraints. The examples show the substantial savings in computer time for convergence, which are associated with the new transformation technique.This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-76-3075, and by the National Science Foundation, Grant No. MCS-76-21657.     

Linear least squares problems with data over incomplete grids

The paper addresses bivariate surface fitting problems, where data points lie on the vertices of a rectangular grid. Efficient and stable algorithms can be found in the literature to solve such problems. If data values are missing at some grid points, there exists a computational method for finding a least squares spline by fixing appropriate values for the missing data. We extended this technique to arbitrary least squares problems as well as to linear least squares problems with linear equality constraints. Numerical examples are given to show the effectiveness of the technique presented. AMS subject classification (2000)  65D05, 65D07, 65D10, 65F05, 65F20     

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.     

不等式约束二次规划的一新算法

文献[1]提出了一般等式约束非线性规划问题一种求解途径．文献[2]应用这一途径给出了等式约束二次规划问题的一种算法，本文在文献[1]和[2]的基础上对不等式约束二次规划问题提出了一种新算法．     

A Probe Method of Gradient Projection Type

§１．　ＩｎｔｒｏｄｕｃｔｉｏｎＷｅｃｏｎｓｉｄｅｒｔｈｅｆｏｌｌｏｗｉｎｇｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍ：（Ｐ）　　ｍｉｎｘ∈Ｘｆ（ｘ）（１）ｗｈｅｒｅＸ＝｛ｘ｜ｘ∈Ｅｎ,ｇｊ（ｘ）≤０,ｊ＝１,２,…,ｍ;ｇｊ（ｘ）＝０,ｊ＝ｍ＋１,…,ｍ＋ｌ｝,ｌｅｔＩ＝｛１,２,…,ｍ｝,Ｌ＝｛ｍ＋１,…,ｍ＋ｌ｝．Ｆｏｒｔｈｅｐｒｏｂｌｅｍ（Ｐ）ｗｉｔｈＬ＝,ｍａｎｙｅｆｆｉｃｉｅｎｔｐｒｏｊｅｃｔｉｏｎｔｙｐｅａｌｇｏｒｉｔｈｍｓ［１－１１］ｈａｖｅｂｅｅｎｐｒｏｐｏｓｅｄ．Ｉｎ［１２］,…     

Minimizing a Sum of Norms Subject to Linear Equality Constraints

Numerical analysis of a class of nonlinear duality problems is presented. One side of the duality is to minimize a sum of Euclidean norms subject to linear equality constraints (the constrained MSN problem). The other side is to maximize a linear objective function subject to homogeneous linear equality constraints and quadratic inequalities. Large sparse problems of this form result from the discretization of infinite dimensional duality problems in plastic collapse analysis.The solution method is based on the l ₁ penalty function approach to the constrained MSN problem. This can be formulated as an unconstrained MSN problem for which the first author has recently published an efficient Newton barrier method, and for which new methods are still being developed.Numerical results are presented for plastic collapse problems with up to 180000 variables, 90000 terms in the sum of norms and 90000 linear constraints. The obtained accuracy is of order 10^-8 measured in feasibility and duality gap.     

A feasible SQP method for nonlinear programming

In this paper, a new SQP algorithm is presented to solve the general nonlinear programs with mixed equality and inequality constraints. Quoted from P. Spellucci (see [9]), this method maybe be named sequential equality constrained quadratic programming (SECQP) algorithm. Per single iteration, based on an active set strategy ( see [9]), this SECQP algorithm requires only to solve equality constrained quadratic programming subproblems or system of linear equations. The theoretical analysis shows that global and superlinear convergence can be induced under some suitable conditions.     

Regularized Lagrangian duality for linearly constrained quadratic optimization and trust-region problems

In this paper we first establish a Lagrange multiplier condition characterizing a regularized Lagrangian duality for quadratic minimization problems with finitely many linear equality and quadratic inequality constraints, where the linear constraints are not relaxed in the regularized Lagrangian dual. In particular, in the case of a quadratic optimization problem with a single quadratic inequality constraint such as the linearly constrained trust-region problems, we show that the Slater constraint qualification (SCQ) is necessary and sufficient for the regularized Lagrangian duality in the sense that the regularized duality holds for each quadratic objective function over the constraints if and only if (SCQ) holds. A new theorem of the alternative for systems involving both equality constraints and two quadratic inequality constraints plays a key role. We also provide classes of quadratic programs, including a class of CDT-subproblems with linear equality constraints, where (SCQ) ensures regularized Lagrangian duality.     

An interior affine scaling projective algorithm for nonlinear equality and linear inequality constrained optimization

In this paper, we propose a new nonmonotonic interior point backtracking strategy to modify the reduced projective affine scaling trust region algorithm for solving optimization subject to nonlinear equality and linear inequality constraints. The general full trust region subproblem for solving the nonlinear equality and linear inequality constrained optimization is decomposed to a pair of trust region subproblems in horizontal and vertical subspaces of linearize equality constraints and extended affine scaling equality constraints. The horizontal subproblem in the proposed algorithm is defined by minimizing a quadratic projective reduced Hessian function subject only to an ellipsoidal trust region constraint in a null subspace of the tangential space, while the vertical subproblem is also defined by the least squares subproblem subject only to an ellipsoidal trust region constraint. By introducing the Fletcher's penalty function as the merit function, trust region strategy with interior point backtracking technique will switch to strictly feasible interior point step generated by a component direction of the two trust region subproblems. The global convergence of the proposed algorithm while maintaining fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion should bring about speeding up the convergence progress in some high nonlinear function conditioned cases.