共查询到18条相似文献,搜索用时 296 毫秒
1.
2.
3.
4.
线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法. 相似文献
5.
曹建兵 《数学物理学报(A辑)》2018,(4)
借助于代数度量广义逆方面的扰动结论,同时利用一般的约束极值解问题和无约束极值问题的一个等价转化,该文在自反严格凸Banach空间中获得了具有等式约束的极值解问题的扰动估计.最后,作为主要结论的推论,该文分别考虑了不适定算子方程的极值解、最佳逼近解和点投影到线性流形等问题的扰动分析. 相似文献
6.
基于J.M.Peng研究一类变分不等式问题(简记为VIP)时所提出的价值函数,本文提出了求解强单调的VIP的一个新的信赖域算法。和已有的处理VIP的信赖域方法不同的是:它在每步迭代时,不必求解带信赖域界的子问题,仅解一线性方程组而求得试验步。这样,计算的复杂性一般来说可降低。在通常的假设条件下,文中还证明了算法的整体收敛性。最后,在梯度是半光滑和约束是矩形域的假设下,该算法还是超线性收敛的。 相似文献
7.
针对下层为线性规划的非线性双层规划问题,提出了一种基于下层对偶理论的遗传算法。首先利用下层对偶问题可行域的极点对上层变量的取值域进行划分,使得每一个划分区域对应一个极点。根据原一对偶问题最优解的关系,确定每个划分区域对应的下层最优解。其次利用罚函数方法处理了上层约束,设计了一个依赖于种群变化的动态罚因子。对20个测试问题的数值结果表明,所提出的算法是可行有效的。 相似文献
8.
双层线性规划的一个全局优化方法 总被引:7,自引:0,他引:7
用线性规划对偶理论分析了双层线性规划的最优解与下层问题的对偶问题可行域上极点之间的关系,通过求得下层问题的对偶问题可行域上的极点,将双层线性规划转化为有限个线性规划问题,从而用线性规划方法求得问题的全局最优解.由于下层对偶问题可行域上只有有限个极点,所以方法具有全局收敛性. 相似文献
9.
10.
本文研究非线性规划的总体极值问题,问题的目标函数和约束函数均为凹函数。给出的算法由二阶段组成,第一阶段是通过解一系列的线性规划,在非凸的可行域内找到一些靠近总体极值的点。在第二个阶段中,用第一阶段中得到的点为初始点,由解一系列的非线性方程组所得的解来逼近总体极值点。在适当的假设条件下。这样的逼近具有超线性收敛性。 相似文献
11.
As a synchronization parallel framework, the parallel variable transformation (PVT) algorithm is effective to solve unconstrained optimization problems. In this paper, based on the idea that a constrained optimization problem is equivalent to a differentiable unconstrained optimization problem by introducing the Fischer Function, we propose an asynchronous PVT algorithm for solving large-scale linearly constrained convex minimization problems. This new algorithm can terminate when some processor satisfies terminal condition without waiting for other processors. Meanwhile, it can enhances practical efficiency for large-scale optimization problem. Global convergence of the new algorithm is established under suitable assumptions. And in particular, the linear rate of convergence does not depend on the number of processors. 相似文献
12.
《Journal of Computational and Applied Mathematics》2002,145(1):133-149
The problem of finding an such that Ax⩽b and x⩾0 arises in numerous contexts. We propose a new optimization method for solving this feasibility problem. After converting Ax⩽b into a system of equations by introducing a slack variable for each of the linear inequalities, the method imposes an entropy function over both the original and the slack variables as the objective function. The resulting entropy optimization problem is convex and has an unconstrained convex dual. If the system is consistent and has an interior solution, then a closed-form formula converts the dual optimal solution to the primal optimal solution, which is a feasible solution for the original system of linear inequalities. An algorithm based on the Newton method is proposed for solving the unconstrained dual problem. The proposed algorithm enjoys the global convergence property with a quadratic rate of local convergence. However, if the system is inconsistent, the unconstrained dual is shown to be unbounded. Moreover, the same algorithm can detect possible inconsistency of the system. Our numerical examples reveal the insensitivity of the number of iterations to both the size of the problem and the distance between the initial solution and the feasible region. The performance of the proposed algorithm is compared to that of the surrogate constraint algorithm recently developed by Yang and Murty. Our comparison indicates that the proposed method is particularly suitable when the number of constraints is larger than that of the variables and the initial solution is not close to the feasible region. 相似文献
13.
14.
This paper presents the convergence proof and complexity analysis of an interior-point framework that solves linear programming problems by dynamically selecting and adding relevant inequalities. First, we formulate a new primal–dual interior-point algorithm for solving linear programmes in non-standard form with equality and inequality constraints. The algorithm uses a primal–dual path-following predictor–corrector short-step interior-point method that starts with a reduced problem without any inequalities and selectively adds a given inequality only if it becomes active on the way to optimality. Second, we prove convergence of this algorithm to an optimal solution at which all inequalities are satisfied regardless of whether they have been added by the algorithm or not. We thus provide a theoretical foundation for similar schemes already used in practice. We also establish conditions under which the complexity of such algorithm is polynomial in the problem dimension and address remaining limitations without these conditions for possible further research. 相似文献
15.
The paper provides some examples of mutually dual unconstrained optimization problems originating from regularization problems for systems of linear equations and/or inequalities. The solution of each of these mutually dual problems can be found from the solution of the other problem by means of simple formulas. Since mutually dual problems have different dimensions, it is natural to solve the unconstrained optimization problem of the smaller dimension. 相似文献
16.
时贞军 《数学物理学报(A辑)》2004,4(6):675-682
该文提出一种无约束优化非线性共轭梯度法,证明了精确线性 搜索下的全局收敛性。当目标函数为一致凸函数时,证明了算法具有线性收敛速度。数值实验表明算法对于求解实际问题是有效的。 相似文献
17.
An Improved Method for Designing Quadrature Mirror Filter Banks via Unconstrained Optimization 总被引:1,自引:0,他引:1
This paper proposes an algorithm to design a two-channel linear phase quadrature mirror filter (QMF) bank. The design problem
is presented systematically as an unconstrained optimization that minimizes the weighted sum of error of transfer function
of the filter bank at quadrature frequency, stopband energy and the passband error of a prototype filter (PF). A new method
is developed for the design of a low pass prototype filter for QMF banks. For solving given optimization problem, Quasi-Newton
optimization technique is used. Numerical examples and comparisons with several existing methods are included to show the
performances and effectiveness of this method. An application of the proposed method is considered in the area of subband
coding of the images. 相似文献