一个新的求解线性规划最小二乘算法

§1Introduction Currently,therearetwopopularapproachesinlinearprogramming:pivotalgorithm andinterior-pointalgorithm.Manyoftheirvariantsdevelopedbothintheoryand applicationsarestillinprogress.Thepivotmethodobtainstheoptimalsolutionviamoving consecutivelytoabettercorner-pointinthefeasibleregion,anditsmodificationstryto improvethespeedofattainingtheoptimality.Incontrast,theinterior-pointalgorithmis claimedasaninterior-pointapproach,whichgoesfromafeasiblepointtoafeasiblepoint throughtheinterioroft…     

一个在置换图中寻找DFS树的最优算法

本是通过在连通置换图中构造辅助树的方法,给出了一个在具有n个顶点的置换图G中寻找深度优先支撑树（简称,DFS树）的最优算法,并证明了该算法的时间复杂性为O(n)。     

解非线性最小二乘问题的锥模型算法

在自然科学研究、经济、统计等领域,非线性最小二乘有着广泛的应用,因而寻找快捷有效的算法有着十分重要的意义。它首先是一个最优化问题,同时又有自身的结构特点,充分利用其结构特点,是寻找更有效算法的关键。     

求解log—最优组合投资问题的一个自适应算法及其理论分析

本文给出了一个求解log－最优组合投资问题的自适应算法,它是一个变型的随机逼近方法。该问题是一个约束优化问题,因此,采用基于约束流形的梯度上升方向替代常规梯度上升方向,在一些合理的假设下证明了算法的收敛性并进行了渐近稳定性分析。最后,本文将该算法应用于上海证券交易所提供的实际数据的log-最优组合投资问题求解,获得了理想的数值模拟结果。     

求全局最优解的新算法

利用局部极大值点与动力系统的稳定奇点的对应性，计算代数方程的根、无约束极大值点、有约束极大值点、非线性规划解、及最小二乘解．我们采用了常微分方程数值解的Euler算法及网格初始点的循序迭代算法，并以具体的例子和程序说明创立的方法具有通用性，同时考虑了一些存在的问题以便在理论和算法上作进一步的改进。     

基于最优保存和自适应性的混合遗传算法

1 引 言遗传算法（Genetic Algorithm,GA）是由Michigan大学Holland等创立的.常用的遗传算法一般有以下三种:简单遗传算法（Simple Genetic Algorithm,SGA）或称标准遗传算法（Canonical Genetic Algorithm,CGA）、最优保存简单遗传算法（Optimum MaintainingSimple Genetric Algorithm,OMSGA）和自适应遗传算法（Adaptive Genetic Algorithm,AGA）.     

最优投资决策的一个统计渐近算法

设■=(X_1,…,X_m)为市场收益随机向量,具有联合概率分布F(■)=F(x_1,…,x_m),又设■=(b_1,…,b_m)为一个资本投资决策,其中b_i≥0,∑_ib_i=1。称■(■,■)=∫log(∑_ib_i·x_i)dF(x_i,…,x_n)为(■,■)的倍率.一个决策■~*被称为是最优的,如■(■,■~*)=max W(■,■)。资本投资的一个核心问题就是寻找最优的■~*。许多论文都是在F(■)已知条件下讨论这个问题。本文首次给出关于■~*在m=2时的统计算法,并证明了这个估计量是一个一致统计量。     

求解Nash均衡子问题的一个算法

n人有限博弈的混合策略组合（p1^*,…,pn^*)为Nash均衡,如果其中每一策略pi^*都是参与人i(i=1,2,…,n),对其它n-1个参与人策略组合（p1^*,…,pi 1^*,pi-1^*,…,pn^*)的最优反应,即存在n个概率向量p1^*,…,pn^*使得对i=1,2,…,n及任意k1维概率向量pi恒有vi(p1^*,…,pn^*…)小于vi(pi^*,…,pi-1^*,pi 1^*,…pn^*),其中vi为参与人i的支付函数,pi=(pil,…,piki)）为ki维概率向量,即满足条件,pij大于等于0,∑kij=1pij=1,ki是参与人i的策略空间中策略个数,i=1,2,…,n,由此,Nash均衡的求解可化为下列优化问题：求n个概率向量pi^*,…,pn^8,使得对i=1,2,…,n及任意ki维的概率向量pi满足maxxvi(P1^*,…,pi-1^*,pi,Pi 1^*,…,pn^*)=vi(P1^*,,…,Pn^*)。     

关于矩阵乘法的一个算法的时间复杂度

两个n阶非负整数方阵相乘,常规算法的时间复杂度为O(n³),文献[1]提出一个“运算次数”为O(n²)的“最佳”算法,本文根据算法分析理论得出此算法的时间复杂度不低于O(n³log₂ⁿ),因而比常规算法的运算量还大.     

一个改进的线性规划预校正算法

本文我们提出了一个改进型线性规划预校正算法，我们的预步和校正步方向与Mizuno－Todd-Ye[4]的方向是不同的．我们的算法的迭代复杂度为，然而在校正步，我们降低对偶间隙一个常数因子．     

An algorithm for solving a multiple criteria optimal control problem

An algorithm for finding agood solution for a multiple criteria optimal control problem is given. The criteria are assumed to be ordered according to their importance to the decision-maker. The algorithm consists of successive solutions of single criterion optimal control problems. Other criteria are taken into account by adding constraints to the problem in a systematic manner.     

An optimal algorithm for the minimum-width cubic shell problem

Given a set of n points in ${\mathbb{R}}^3$, the minimum-width cubic shell problem asks to find a thinnest cubic shell that encloses the input points, where a cubic shell refers to as a closed volume between two concentric axis-aligned cubes. In this paper, we improve the previous $O(n{\log }^{2}n)$-time algorithm presented in Bae (2019) [6] to $O(n\log n)$ worst-case time. This is the first optimal-time algorithm to the problem.     

多背包问题的半定松驰算法

The multiple knapsack problem denoted by MKP (B,S,rn,n) can be defined as follows. A set B of n items and a set S of rn knapsacks are given such that each item j has a profit pi and weight wj,and each knapsack i has a capacity Ci. The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks. MKP (B,S,m,n) is strongly NP-Complete and no polynomial time approximation algorithm can have an approximation ratio better than 0.5. In the last ten years,semi-definite programming has been empolyed to solve some combinatorial problems successfully. This paper firstly presents a semi-definite relaxation algorithm (MKPS) for MKP (B,S,rn,n). It is proved that MKPS have a approximation ratio better than 0. 5 for a subclass of MKP (B,S,m,n) with n≤100, m≤5 and max^nj=1{wj}/min^mi=1={Ci}≤2/3.     

An optimal regularizing algorithm for the recovery of functionals in linear inverse problems with sourcewise represented solution

A linear operator equation with a sourcewise represented exact solution is solved approximately. To this end, the method of extending compacts developed in an earlier work is applied. Based on this method, a new algorithm is proposed for recovering the value of a linear functional at the solution of the linear operator equation. This algorithm is shown to be an optimal regularizing one.     

Opticon: An algorithm for the optimal control of nonlinear stochastic models

In this paper we describe the algorithm OPTCON which has been developed for the optimal control of nonlinear stochastic models. It can be applied to obtain approximate numerical solutions of control problems where the objective function is quadratic and the dynamic system is nonlinear. In addition to the usual additive uncertainty, some or all of the parameters of the model may be stochastic variables. The optimal values of the control variables are computed in an iterative fashion: First, the time-invariant nonlinear system is linearized around a reference path and approximated by a time-varying linear system. Second, this new problem is solved by applying Bellman's principle of optimality. The resulting feedback equations are used to project expected optimal state and control variables. These projections then serve as a new reference path, and the two steps are repeated until convergence is reached. The algorithm has been implemented in the statistical programming system GAUSS. We derive some mathematical results needed for the algorithm and give an overview of the structure of OPTCON. Moreover, we report on some tentative applications of OPTCON to two small macroeconometric models for Austria.     

A recursive algorithm for the infinity-norm fixed point problem

We present the PFix algorithm for the fixed point problem f(x)=x on a nonempty domain [a,b], where d1, , and f is a Lipschitz continuous function with respect to the infinity norm, with constant q1. The computed approximation satisfies the residual criterion , where >0. In general, the algorithm requires no more than ∑_i=1^dsⁱ function component evaluations, where s≡max(1,log₂(||b−a||_∞/))+1. This upper bound has order as →0. For the domain [0,1]^d with <0.5 we prove a stronger result, i.e., an upper bound on the number of function component evaluations is , where r≡log₂(1/). This bound approaches as r→∞ (→0) and as d→∞. We show that when q<1 the algorithm can also compute an approximation satisfying the absolute criterion , where x^* is the unique fixed point of f. The complexity in this case resembles the complexity of the residual criterion problem, but with tolerance (1−q) instead of . We show that when q>1 the absolute criterion problem has infinite worst-case complexity when information consists of function evaluations. Finally, we report several numerical tests in which the actual number of evaluations is usually much smaller than the upper complexity bound.     

An inverse optimal problem in discrete-time stochastic control

In this paper, we study an inverse optimal problem in discrete-time stochastic control. We give necessary and sufficient conditions for a solution to a system of stochastic difference equations to be the solution of a certain optimal control problem. Our results extend to the stochastic case the work of Dechert. In particular, we present a stochastic version of an important principle in welfare economics.     

A time-decomposition algorithm for a stiff linear two-point boundary-value problem and its application to a nonlinear optimal control problem

An algorithm is proposed to solve a stiff linear two-point boundary-value problem (TPBVP). In a stiff problem, since some particular solutions of the system equation increase and others decrease rapidly as the independent variable changes, the integration of the system equation suffers from numerical errors. In the proposed algorithm, first, the overall interval of integration is divided into several subintervals; then, in each subinterval a sub-TPBVP with arbitrarily chosen boundary values is solved. Second, the exact boundary values which guarantee the continuity of the solution are determined algebraically. Owing to the division of the integration interval, the numerical error is effectively reduced in spite of the stiffness of the system equation. It is also shown that the algorithm is successfully imbedded into an interaction-coordination algorithm for solving a nonlinear optimal control problem.The authors would like to thank Mr. T. Sera and Mr. H. Miyake for their help with the calculations.     

An optimal minimax algorithm

Computer game-playing programs repeatedly calculate minimax elements = min _i max _j M _ij of large pay off matricesM _ij . A straightforwardrow-by-row calculation of scans rows ofM _ij one at a time, skipping to a new row whenever an element is encountered that exceeds a current minimax. Anoptimal calculation, derived here, scans the matrix more erratically but finds after testing the fewest possible matrix elements. Minimizing the number of elements tested is reasonable when elements must be computed as needed by evaluating future game positions. This paper obtains the expected number of tests required when the elements are independent, identically distributed, random variables. For matrices 50 by 50 or smaller, the expected number of tests required by the row-by-row calculation can be at most 42% greater than the number for the optimal calculation. When the numbersR, C of rows and columns are very large, both calculations require an expected number of tests nearRC/InR.