A note on a generalized network flow model for manufacturing process

Manufacturing network flow （MNF） is a generalized network model that overcomes the limitation of an ordinary network flow in modeling more complicated manufacturing scenarios, in particular the synthesis of different materials into one product and/or the distilling of one type of material into many different products. Though a network simplex method for solving a simplified version of MNF has been outlined in the literature, more research work is still needed to give a complete answer whether some classical duality and optimality results of the classical network flow problem can be extended in MNF. In this paper, we propose an algorithmic method for obtaining an initial basic feasible solution to start the existing network simplex algorithm, and present a network-based approach to checking the dual feasibility conditions. These results are an extension of those of the ordinary network flow problem.     

A proximal point algorithm revisit on the alternating direction method of multipliers

The alternating direction method of multipliers(ADMM)is a benchmark for solving convex programming problems with separable objective functions and linear constraints.In the literature it has been illustrated as an application of the proximal point algorithm(PPA)to the dual problem of the model under consideration.This paper shows that ADMM can also be regarded as an application of PPA to the primal model with a customized choice of the proximal parameter.This primal illustration of ADMM is thus complemental to its dual illustration in the literature.This PPA revisit on ADMM from the primal perspective also enables us to recover the generalized ADMM proposed by Eckstein and Bertsekas easily.A worst-case O(1/t)convergence rate in ergodic sense is established for a slight extension of Eckstein and Bertsekas’s generalized ADMM.     

Surface Acoustic Wave Characterization of Equivalent Young's Moduli for Patterned Films北大核心CSCD

Based on the equivalent elasticity theory for layered materials, the micro-mechanics equivalent models for single and dual damascene structures were established. The equivalent elastic constant of the patterned structure was introduced, to establish the propagation model for the surface acoustic waves propagating in the layered structure of the patterned film/ substrate, and the theoretical dispersion curves of the surface acoustic waves were calculated with Green’s function and the matrix method. The finite element method was used to calculate 24 numerical examples of damascene structures with different volume ratios, and the results were compared with those of the strain energy method. The results show that, the average relative errors of the equivalent Young’s moduli of the 300 nm-thick dual damascene film and the 100 nm-thick single damascene film are 2.06% and 2.27%, respectively. The research verifies the correctness of the equivalent patterned structure model and the feasibility of the surface acoustic wave method to characterize the mechanical properties of patterned films, and provides a reference for the development of suitable chemico-mechanical polishing technologies for patterned films under low pressure. © 2023 Editorial Office of Applied Mathematics and Mechanics. All rights reserved.     

A DUAL NON-LINEAR PROGRAM

In the paper a dual of a nonlinear fractional functional programming problem has beenformulated.This problem can be used to obtain a solution of the mixed 0—1 integer linearprogramming problem.Some properties related to the primal and dual have been given.     

Improved twin support vector machine

We improve the twin support vector machine(TWSVM)to be a novel nonparallel hyperplanes classifier,termed as ITSVM(improved twin support vector machine),for binary classification.By introducing the diferent Lagrangian functions for the primal problems in the TWSVM,we get an improved dual formulation of TWSVM,then the resulted ITSVM algorithm overcomes the common drawbacks in the TWSVMs and inherits the essence of the standard SVMs.Firstly,ITSVM does not need to compute the large inverse matrices before training which is inevitable for the TWSVMs.Secondly,diferent from the TWSVMs,kernel trick can be applied directly to ITSVM for the nonlinear case,therefore nonlinear ITSVM is superior to nonlinear TWSVM theoretically.Thirdly,ITSVM can be solved efciently by the successive overrelaxation(SOR)technique or sequential minimization optimization(SMO)method,which makes it more suitable for large scale problems.We also prove that the standard SVM is the special case of ITSVM.Experimental results show the efciency of our method in both computation time and classification accuracy.     

A PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. Recently, Mehrotra suggested a predictor-corrector variant of primal-dual interior point method for linear programming. It is currently the interior-point method of the choice for linear programming. In this work we propose a predictor-corrector interior-point algorithm for convex quadratic programming. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require that the initial primal and dual points be feasible. Numerical experiments are made.     

求解两块可分离凸极小化问题的惯性交替方向乘子法

The alternating direction method of multipliers(ADMM)is a widely used method for solving many convex minimization models arising in signal and image processing.In this paper,we propose an inertial ADMM for solving a two-block separable convex minimization problem with linear equality constraints.This algorithm is obtained by making use of the inertial Douglas-Rachford splitting algorithm to the corresponding dual of the primal problem.We study the convergence analysis of the proposed algorithm in infinite-dimensional Hilbert spaces.Furthermore,we apply the proposed algorithm on the robust principal component analysis problem and also compare it with other state-of-the-art algorithms.Numerical results demonstrate the advantage of the proposed algorithm.     

一类基于变量分离的稳定化混合有限元方法

Based on a seperated model for saddle-point problems, we develop a new sta-bilized mixed finite element method. Such a model consists of two subproblems with respect to the primal and the dual variables, respectively. We show that the new method is coercive and that optimal error bounds hold. As an application,the nearly incompressible elastic problem is analyzed with our method.     

Properties and Iterative Methods for the Lasso and Its Variants

The lasso of Tibshirani （1996） is a least-squares problem regularized by the l1 norm. Due to the sparseness promoting property of the l1 norm, the lasso has been received much attention in recent years. In this paper some basic properties of the lasso and two variants of it are exploited. Moreover, the proximal method and its variants such as the relaxed proximal algorithm and a dual method for solving the lasso by iterative algorithms are presented.     

Non-stationary subdivision for exponential polynomials reproduction

In this paper we develop a novel approach to construct non-stationary subdivision schemes with a tension control parameter which can reproduce functions in a finite-dimensional subspace of exponential polynomials. The construction process is mainly implemented by solving linear systems for primal and dual subdivision schemes respectively, which are based on different parameterizations. We give the theoretical basis for the existence, uniqueness, and refinement rules of schemes proposed in this paper. The convergence and smoothness of the schemes are analyzed as well. Moreover, conics reproducing schemes are analyzed based on our theory, and a new idea that the tensor parameter ωk of the schemes can be adjusted for conics generation is proposed.     

第一阶段原有单纯形和对偶单纯形算法的计算比较

线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法.     

An overview on the simplex algorithm

In this paper, the simplex algorithm and its variants are investigated. First, we define a new concept called formal tableau, which leads to derive easily the dual solution from the latest primal table; without any distinction between the original variables and the slack ones. Second, we propose a new method for initializing the simplex algorithm. Unlike the two-phase and the big-M methods, our technique does not involve artificial variables. The computational results reveal that this new method is very favorable especially when the number of artificial variables is significant. Finally, this method will be combined with the notion of formal tableau leading naturally to a second new approach.     

A dual approach to primal degeneracy

The Revised Primal Simplex algorithm, in its simplest form, has no defence against degeneracy. Various forms of the perturbation method are usually effective, but most offer no guarantee of avoiding all degeneracy, and can lead to numerical difficulties. This paper presents a method that avoids cycling and circling by taking a dual approach.The degenerate subproblem consists of all the original variables, but only the degenerate transformed constraints. The current primal objective, which may be mixed, is used. This subproblem may be solved using the dual simplex algorithm, starting from the current dual infeasible solution, and with a zero dual objective. If the dual algorithm terminates optimally then the whole problem is optimal (subject to primal feasibility). Otherwise the final solution provides a non-basic direction which improves the value of the mixed primal objective and moves away from the degenerate vertex. A purification algorithm then renders the solution basic and further improves the mixed objective.     

一种原始——对偶单纯形算法的枢轴准则选择

Curet曾提出了一种有趣的原始一对偶技术,在优化对偶问题的同时单调减少原始不可行约束的数量,当原始可行性产生时也就产生了原问题的最优解.然而该算法需要一个初始对偶可行解来启动,目标行的选择也是灵活、不确定的.根据Curet的原始一对偶算法原理,提出了两种目标行选择准则,并通过数值试验进行比较和选择.对不存在初始对偶可行解的情形,通过适当改变目标函数的系数来构造一个对偶可行解,以求得一个原始可行解,再应用原始单纯形算法求得原问题的最优解.数值试验对这种算法的计算性能进行验证,通过与经典两阶段单纯形算法比较,结果表明,提出的算法在大部分问题上具有更高的计算效率.     

Some fundamental issues of basic line search algorithm for linear programming problems

In this article we present the fundamental idea, concepts and theorems of a basic line search algorithm for solving linear programming problems which can be regarded as an extension of the simplex method. However, unlike the iteration of the simplex method from a basic point to an improved adjacent basic point via pivot operation, the basic line search algorithm, also by pivot operation, moves from a basic line which contains two basic feasible points to an improved basic line which also contains two basic feasible points whose objective values are no worse than that of the two basic feasible points on the previous basic line. The basic line search algorithm may skip some adjacent vertices so that it converges to an optimal solution faster than the simplex method. For example, for a 2-dimensional problem, the basic line search algorithm can find an optimal solution with only one iteration.     

Optimal simplex tableau characterization of unique and bounded solutions of linear programs

Uniqueness and boundedness of solutions of linear programs are characterized in terms of an optimal simplex tableau. LetM denote the submatrix in an optimal simplex tableau with columns corresponding to degenerate optimal dual basic variables. A primal optimal solution is unique iff there exists a nonvacuous nonnegative linear combination of the rows ofM, corresponding to degenerate optimal primal basic variables, which is positive. The set of primal optimal solutions is bounded iff there exists a nonnegative linear combination of the rows ofM which is positive. WhenM is empty, the primal optimal solution is unique.This research was sponsored by the United States Army under Contract No. DAAG29-75-C-0024. This material is based upon work supported by the National Science Foundation under Grant No. MCS-79-01066.     

PRIMAL PERTURBATION SIMPLEX ALGORITHMS FOR LINEAR PROGRAMMING

1. IntroductionExtensive research in linear programming, such as [1,2,9,10,if, 12,13,14,19], hasbeen to improve pivot rules to reduce the number of iterations required. Relatively lesseffort was made on perturbing problem data with pivot rules unaltered (for instance, theself--dual parametric method [7] and perturbation--based methods [3,5]). And, becauseof the papametrization, the latter do not proceed as simply as the conventional simplexalgorithm itself.Recently, Pan [17] proposes new pert…     

Affine-scaling for linear programs with free variables

The affine-scaling modification of Karmarkar's algorithm is extended to solve problems with free variables. This extended primal algorithm is used to prove two important results. First the geometrically elegant feasibility algorithm proposed by Chandru and Kochar is the same algorithm as the one obtained by appending a single column of residuals to the constraint matrix. Second the dual algorithm as first described by Adler et al., is the same as the extended primal algorithm applied to the dual.     

线性规划无穷多最优解的讨论

利用线性规划单纯形表对线性规划原问题存在无穷多最优解和对偶问题存在无穷多最优解的情况进行了讨论,并分析了对偶问题存在无穷多最优解情况下的影子价格的方向性。最后以实例说明了各种情况。对初学者加深理解及决策者决策参考有一定帮助     

Sensitivity analysis in fuzzy number linear programming problems

In this paper, we generalize the concept of sensitivity analysis in fuzzy number linear programming (FLNP) problems by applying fuzzy simplex algorithms and using the general linear ranking functions on fuzzy numbers. The purpose of sensitivity analysis is to determine changes in the optimal solution of FNLP problem resulting from changes in the data. If the change affects the optimality of the basis, we perform primal pivots to achieve optimality by use of the fuzzy primal simplex method. Whenever the change destroys the feasibility of the optimal basis, we perform dual pivots to achieve feasibility by use of the fuzzy dual simplex method.