A Minimax Approach to Errors-in-Variables Linear Models

The paper considers a simple Errors-in-Variables (EiV) model Y_i = a + bX_i + εξ_i; Z_i= X_i + σζ_i, where ξ_i, ζ_i are i.i.d. standard Gaussian random variables, X_i ∈ ? are unknown non-random regressors, and ε, σ are known noise levels. The goal is to estimates unknown parameters a, b ∈ ? based on the observations {Y_i, Z_i, i = 1, …, n}. It is well known [3] that the maximum likelihood estimates of these parameters have unbounded moments. In order to construct estimates with good statistical properties, we study EiV model in the large noise regime assuming that n → ∞, but \({\epsilon ^2} = \sqrt n \epsilon _ \circ ^2,{\sigma ^2} = \sqrt n \sigma _ \circ ^2\) with some \(\epsilon_\circ^2, \sigma_\circ^2>0\). Under these assumptions, a minimax approach to estimating a, b is developed. It is shown that minimax estimates are solutions to a convex optimization problem and a fast algorithm for solving it is proposed.     

线性方程组逼近双障碍问题

针对双障碍问题,本文提出了与其等价的B可微方程的类Broyden算法,并 在一定条件下证明了该算法的全局收敛性和超线性收敛性.经数值实验表明该算法是 有效的.     

The Numerical Solution of Constrained Linear Least-squares Problems

The paper describes a numerically stable algorithm to solveconstrained linear least-squares problems and allows rank deficientor underdetermined observation matrices. The method starts withthe calculation of the rank of the observation matrix and thetransformation into a least distance problem. The proposed techniquefor solving the least distance problem can be considered asa generalization of the projection method of Stoer (1971). Startingwith a feasible point, a sequence of iterates is calculatedby minimizing the objective function on the linear boundarymanifold determined by the active constraints. Numerical examplesshow the feasibility of the algorithm.     

The Minimax Solution of Linear Equations Subject to Linear Constraints

This paper presents an efficient active set method for computingthe l_m solution of linear equations subject to linear constraints.The search direction of the proposed method is obtained viathe solution of a linear least-squares problem. It is shownthat the steepest-descent direction can be obtained by solvingthe same least-squares problem with simple bounds on the variables.This direction is used to prevent cycling at degenerate deadpoints. Numerical experiments illustrate the feasibility ofthe new method.     

概率约束线性规划最优解的存在性

本文给出了概率约束规划ｍｉｎ{cx|P(A₁x≥ξ)≥p,A₂x≥b}的最优值有限的充要条件；对一类离散型随机向量ξ，并给出了这一概率约束规划存在最优解的充要条件．实际中常用的离散型随机向量属于这类离散型随机向量．     

Solution of Special Linear Programming Problems with Additional Constraints

This paper gives a method of solution for linear programming problems whose constraints can be split into two sets, the first having a special structure, such as that of the transportation problem for example, while the second set is quite general. A problem with only the first set of constraints is referred to as a favoured problem, while a problem with both sets is called a complete problem.The proposed method is basically the simplex procedure specialized for a problem with a particular structure, and the feasibility and optimality criteria and the rules for basis change are the same as those used in the simplex procedure. However, the method takes advantage of the simple algorithms developed for the favoured problem and uses them to solve the complete problem in an efficient manner.Such problems could also be solved by the Decomposition Principle and, vice versa, Decomposition problems can be solved by the present method. The two methods are, however, essentially different in their approach to the problem.     

A Chance Constrained Approach to Fractional Programming with Random Numerator

This paper presents a chance constrained programming approach to the problem of maximizing the ratio of two linear functions of decision variables which are subject to linear inequality constraints. The coefficient parameters of the numerator of the objective function are assumed to be random variables with a known multivariate normal probability distribution. A deterministic equivalent of the stochastic linear fractional programming formulation has been obtained and a subsidiary convex program is given to solve the deterministic problem.     

一类线性规划问题的快速解法

研究了在组合投资和多属性决策指标权重确定中有着重要应用的一类线性规划问题,得到了该类线性规划问题有可行解的充要条件,以及在有可行解的情况下寻求最优解的快速解法.     

关于线性二层规划分枝定界方法的探讨

对求解线性二层规划的分枝定界方法进行了探讨.给出的一个例子表明,目前的分枝定界方法不能很好地解决上层带有任意线性形式约束的线性二层规划问题,进而在线性二层规划新定义的基础上提出了求解线性二层规划的扩展分枝定界方法.算例表明扩展分枝定界方法可以有效解决原分枝定界方法的不足.     

A Preconditioned Conjugate Gradient Approach to Linear Equality Constrained Minimization

We propose a new framework for the application of preconditioned conjugate gradients in the solution of large-scale linear equality constrained minimization problems. This framework allows for the exploitation of structure and sparsity in the context of solving the reduced Newton system (despite the fact that the reduced system may be dense). Numerical experiments performed on a variety of test problems from the Netlib LP collection indicate computational promise.     

Constructive Solution of Inverse Parametric Linear/Quadratic Programming Problems

Parametric convex programming has received a lot of attention, since it has many applications in chemical engineering, control engineering, signal processing, etc. Further, inverse optimality plays an important role in many contexts, e.g., image processing, motion planning. This paper introduces a constructive solution of the inverse optimality problem for the class of continuous piecewise affine functions. The main idea is based on the convex lifting concept. Accordingly, an algorithm to construct convex liftings of a given convexly liftable partition will be put forward. Following this idea, an important result will be presented in this article: Any continuous piecewise affine function defined over a polytopic partition is the solution of a parametric linear/quadratic programming problem. Regarding linear optimal control, it will be shown that any continuous piecewise affine control law can be obtained via a linear optimal control problem with the control horizon at most equal to 2 prediction steps.     

A Unified Monotonic Approach to Generalized Linear Fractional Programming

We present an efficient unified method for solving a wide class of generalized linear fractional programming problems. This class includes such problems as: optimizing (minimizing or maximizing) a pointwise maximum or pointwise minimum of a finite number of ratios of linear functions, optimizing a sum or product of such ratios, etc. – over a polytope. Our approach is based on the recently developed theory of monotonic optimization.     

基于多目标规划法的模糊线性回归分析

讨论输入、输出均为模糊数,回归系数为实数时的模糊线性回归分析。由于模糊最小二乘线性回归容易受异常值的影响,而最小一乘法能有效地降低回归模型的误差。为此,基于最小一乘法,建立多目标规划模型并将其转化为非线性规划问题进行求解,从而实现模糊线性回归模型的参数估计。最后,结合一个数值实例,验证和比较该方法的合理性和优越性。     

线性规划的基解算法

提出了求解线性规划问题的一种新方法-基解算法,它是一个不需引入人工变量,不必预先求出一个可行基的直接求解算法。     

An Optimum Solution for One-Dimensional Slitting Problems: A Dynamic Programming Approach

One-dimensional slitting problems are often encountered in textile, paper or sheet-metal industries where a roll of this product needs to be divided into various narrower-width rolls. The rolls are slit into pieces such that the total value of the sale is maximized depending on the width and the number of defects in the sheet. As the width of a piece increases, the value of the piece increases also, but on the other hand, the number of defects in the piece increases as well, causing reduction in its value. Based on these constraints, a dynamic programming formulation is framed so as to maximize the total value of the sale. Computational complexity with a numerical example is discussed to demonstrate how the procedure works.     

A SSLE-Type Algorithm of Quasi-Strongly Sub-Feasible Directions for Inequality Constrained Minimax Problems

In this paper, we discuss the nonlinear minimax problems with inequality constraints. Based on the stationary conditions of the discussed problems, we propose a sequential systems of linear equations (SSLE)-type algorithm of quasi-strongly sub-feasible directions with an arbitrary initial iteration point. By means of the new working set, we develop a new technique for constructing the sub-matrix in the lower right corner of the coefficient matrix of the system of linear equations (SLE). At each iteration, two systems of linear equations (SLEs) with the same uniformly nonsingular coefficient matrix are solved. Under mild conditions, the proposed algorithm possesses global and strong convergence. Finally, some preliminary numerical experiments are reported.     

A Unified Gradient Flow Approach to Constrained Nonlinear Optimization Problems

This paper presents a unified gradient flow approach to nonlinear constrained optimization problems. This method is based on a continuous gradient flow reformulation of constrained optimization problems and on a two level time discretization of the gradient flow equation with a splitting parameter . The convergence of the scheme is analyzed and it is shown that the scheme becomes first order when [0, 1] and second order when = 1 and the time discretization step length is sufficiently large. Numerical experiments for continuous, discrete and mixed discrete optimization problems were performed, and the numerical results show that the approach is effective for solving these problems.     

A Linear Programming Approach to Designing an Optimum Tax Package

This paper describes the application of linear programming to the problem of designing an optimum tax package to make the 1967 British devaluation work. The objective was to show how to release sufficient domestic resources so as to meet the extra exports demanded as a result of devaluation. It is important to realize that what matters is not the total amount of resources taken from the consumers, but the matching of these resources with the exportable goods demanded overseas. If this matching is not obtained, the tax policy may only cut down domestic production and employment without solving the balance-of-payments problem. The linear programming technique proved useful in tackling this problem of matching of demand and supply in particular directions. The particular tax package derived is heavy on those goods which have good export potential and/or high import content, and it avoids imposing taxes which will reduce domestic consumption without helping the balance of payments.     

An Adaptation of PASEB for the Solution of Multi-Objective Linear Fractional Programming Problems

In this note, an adaptation of PASEB is proposed which can solve multi-objective linear fractional programming problems. PASEB was originally proposed by the author for the solution of multi-objective linear programming problems. The proposed adaptation involves changes to certain computational aspects of PASEB to cope with the presence of fractional objectives in the problem. The changes can be expected to increase the computational requirements of the method and to slow down its speed of convergence, but they do not seriously affect its overall effectiveness.