共查询到20条相似文献,搜索用时 31 毫秒
1.
In this paper, an improved feasible QP-free method is proposed to solve nonlinear inequality constrained optimization problems. Here, a new modified method is presented to obtain the revised feasible descent direction. In view of the computational cost, the most attractive feature of the new algorithm is that only one system of linear equations is required to obtain the revised feasible descent direction. Thereby, per single iteration, it is only necessary to solve three systems of linear equations with the same coefficient matrix. In particular, without the positive definiteness assumption on the Hessian estimate, the proposed algorithm is still global convergence. Under some suitable conditions, the superlinear convergence rate is obtained. 相似文献
2.
In this paper, a simple feasible SQP method for nonlinear inequality constrained optimization is presented. At each iteration, we need to solve one QP subproblem only. After solving a system of linear equations, a new feasible descent direction is designed. The Maratos effect is avoided by using a high-order corrected direction. Under some suitable conditions the global and superlinear convergence can be induced. In the end, numerical experiments show that the method in this paper is effective. 相似文献
3.
In this paper, the feasible type SQP method is improved. A new SQP algorithm is presented to solve the nonlinear inequality constrained optimization. As compared with the existing SQP methods, per single iteration, in order to obtain the search direction, it is only necessary to solve equality constrained quadratic programming subproblems and systems of linear equations. Under some suitable conditions, the global and superlinear convergence can be induced. 相似文献
4.
Christian Kanzow 《Numerische Mathematik》2001,89(1):135-160
Summary. We introduce a new algorithm for the solution of the mixed complementarity problem (MCP) which has stronger properties than
most existing methods. In fact, typical solution methods for the MCP either generate feasible iterates but have to solve relatively
complicated subproblems (like quadratic programs or linear complementarity problems), or they have relatively simple subproblems
(like linear systems of equations) but generate not necessarily feasible iterates. The method to be presented here combines
the nice features of these two classes of methods: It has to solve only one linear system of equations (of reduced dimension)
at each iteration, and it generates feasible (more precisely: strictly feasible) iterates. The new method has some nice global
and local convergence properties. Some preliminary numerical results will also be given.
Received August 26, 1999 / Revised version recived April 11, 2000 / Published online February 5, 2001 相似文献
5.
《Journal of Computational and Applied Mathematics》2005,175(2):447-464
In this paper, a new feasible sequential quadratic programming (FSQP) algorithm is proposed to solve the nonlinear programming, where a feasible descent direction is obtained by solving only one QP subproblem. In order to avoid Maratos effect, a high-order revised direction is computed by solving a linear system with involving some “active” constraints. The theoretical analysis shows that global and superlinear convergence can be deduced. 相似文献
6.
The main objective of this study is to discuss the optimum correction of linear inequality systems and absolute value equations (AVE). In this work, a simple and efficient feasible direction method will be provided for solving two fractional nonconvex minimization problems that result from the optimal correction of a linear system. We will show that, in some special-but frequently encountered-cases, we can solve convex optimization problems instead of not-necessarily-convex fractional problems. And, by using the method of feasible directions, we solve the optimal correction problem. Some examples are provided to illustrate the efficiency and validity of the proposed method. 相似文献
7.
离散填充函数是一种用于求解多极值优化问题最优解的一种行之有效的方法.已被证明对于求解大规模离散优化问题是有效的.本文基于改进的离散填充函数定义,构造了一个新的无参数填充函数,并在理论上给出了证明,提出了一个新的填充函数算法.该填充函数无需调节参数,而且只需极小化一次目标函数.数值结果表明,该算法是高效的、可行的. 相似文献
8.
9.
I. V. Konnov 《Russian Mathematics (Iz VUZ)》2014,58(8):49-55
We solve a general optimization problem, where only approximation sequences are known instead of exact values of the goal function and feasible set. Under these conditions we suggest to utilize a penalty function method. We show that its convergence is attained for rather arbitrary means of approximation via suitable coercivity type conditions. 相似文献
10.
DerenHan 《计算数学(英文版)》2004,22(3):347-360
Typical solution methods for solving mixed complementarity problems either generatefeasible iterates but have to solve relatively complicated subproblems such as quadraticprograms or linear complementarity problems,or(those methods)have relatively simplesubproblems such as system of linear equations but possibly generate infeasible iterates.In this paper,we propose a new Newton-type method for solving monotone mixed com-plementarity problems,which ensures to generate feasible iterates,and only has to solve asystem of well-conditioned linear equations with reduced dimension per iteration.Withoutany regularity assumption,we prove that the whole sequence of iterates converges to a so-lution of the problem(truly globally convergent).Furthermore,under suitable conditions,the local superlinear rate of convergence is also established. 相似文献
11.
Ke Su 《Journal of Global Optimization》2008,41(2):203-217
In this paper, we presented a modified SQP-filter method based on the modified quadratic subproblem proposed by Zhou (J. Global
Optim. 11, 193–2005, 1997). In contrast with the SQP methods, each iteration this algorithm only needs to solve one quadratic
programming subproblems and it is always feasible. Moreover, it has no demand on the initial point. With the filter technique,
the algorithm shows good numerical results. Under some conditions, the globally and superlinearly convergent properties are
given. 相似文献
12.
In this paper, the feasible type SQP method is improved. A new algorithm is proposed to solve nonlinear inequality constrained problem, in which a new modified method is presented to decrease the computational complexity. It is required to solve only one QP subproblem with only a subset of the constraints estimated as active per single iteration. Moreover, a direction is generated to avoid the Maratos effect by solving a system of linear equations. The theoretical analysis shows that the algorithm has global and superlinear convergence under some suitable conditions. In the end, numerical experiments are given to show that the method in this paper is effective.This work is supported by the National Natural Science Foundation (No. 10261001) and Guangxi Science Foundation (No. 0236001 and 0249003) of China.
Acknowledgement.We would like to thank one anonymous referee for his valuable comments and suggestions, which greatly improved the quality of this paper. 相似文献
13.
《European Journal of Operational Research》1999,114(1):198-214
In this paper the finite criss-cross method is generalized to solve hyperbolic (fractional linear) programming problems. Just as in the case of linear or quadratic programming the criss-cross method can be initialized with any, not necessarily feasible basic solution. It is known that if the feasible region of the problem is unbounded then some of the known algorithms fail to solve the problem. Our criss-cross algorithm does not have such drawback. Finiteness of the procedure is proved under the usual mild assumptions. Some small numerical examples illustrate the main features of the algorithm and show that our method generates different iterates than other earlier published methods. 相似文献
14.
《Applied mathematics and computation》1986,18(4):285-311
The method of lines is investigated for the numerical solution of the stream-function-and-vorticity form of the Navier-Stokes equations on nonuniform grids. Stiffness characteristics of a linear one-dimensional model equation are examined to establish the feasibility of applying the method to the vorticity equation in two dimensions. The governing equations are transformed from the physical domain with a highly variable grid to a computational domain with a uniform grid. The method of lines is used to solve only the vorticity equation, and the successive-over relaxation technique is used to solve the stream-function equation. It is observed that the transformed governing equations become stiffer with increased concentration of grid points and also as the number of grid points increases. It is also observed that the differencing technique affects the stiffness characteristics. The use of forward differencing is not feasible, and backward differencing is preferable to central differencing for high Reynolds numbers. The results of specific applications for the solution of flow in curved-wall diffusers and a driven cavity demonstrate that the method of lines under certain circumstances is feasible for the numerical solution of physical problems on domains covered with variable grids. 相似文献
15.
In practice, solving realistically sized combinatorial optimization problems to optimality is often too time-consuming to be affordable; therefore, heuristics are typically implemented within most applications software. A specific category of heuristics has attracted considerable attention, namely local search methods. Most local search methods are primal in nature; that is, they start the search with a feasible solution and explore the feasible space for better feasible solutions. In this research, we propose a dual local search method and customize it to solve the traveling salesman problem (TSP); that is, a search method that starts with an infeasible solution, explores the dual space—each time reducing infeasibility, and lands in the primal space to deliver a feasible solution. The proposed design aims to replicate the designs of optimal solution methodologies in a heuristic way. To be more specific, we solve a combinatorial relaxation of a TSP formulation, design a neighborhood structure to repair such an infeasible starting solution, and improve components of intermediate dual solutions locally. Sample-based evidence along with statistically significant t-tests support the superiority of this dual design compared to its primal design counterpart. 相似文献
16.
一类非光滑全局优化问题的区间展开方法 总被引:3,自引:0,他引:3
本文利用区间展开的特点,对一类全局优化问题提出一新的区间求解方法,该方 法能处理多元函数的全局优化问题.数值试验表明提出的方法是可行和有效的. 相似文献
17.
It is known that there are feasible algorithms for minimizing convex functions, and that for general functions, global minimization
is a difficult (NP-hard) problem. It is reasonable to ask whether there exists a class of functions that is larger than the
class of all convex functions for which we can still solve the corresponding minimization problems feasibly. In this paper,
we prove, in essence, that no such more general class exists. In other words, we prove that global optimization is always
feasible only for convex objective functions. 相似文献
18.
Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model 总被引:1,自引:0,他引:1
In this paper, we address a variant of the vehicle routing problem called the vehicle routing problem with time windows and multiple routes. It considers that a given vehicle can be assigned to more than one route per planning period. We propose a new exact algorithm for this problem. Our algorithm is iterative and it relies on a pseudo-polynomial network flow model whose nodes represent time instants, and whose arcs represent feasible vehicle routes. This algorithm was tested on a set of benchmark instances from the literature. The computational results show that our method is able to solve more instances than the only other exact method described so far in the literature, and it clearly outperforms this method in terms of computing time. 相似文献
19.
In this paper, two-step method (TSM), alternative solution method (SOM-2) and best-worst case (BWC) method are introduced to solve a type of interval linear programming (ILP) problem. To compare the performance of the methods, Monte Carlo simulation is also used to solve the same ILP problem, whose solutions are assumed to be real solutions. In the comparison, two scenarios corresponding with two assumptions of distribution functions are considered: (i) all the input parameters obey normal distribution; (ii) all the input parameters obey uniform distribution. Based on the simulation results, coverage rate (CR) and validity rate (VR) are proposed as new indicators to measure the quality of the numerical solutions obtained from the methods. Results from a numerical case study indicate that the TSM and SOM-2 solutions can cover the majority of valid values (CR > 50%, VR > 50%), compared to the conventional BWC method. In addition, from the point of CR, TSM is more applicable since the solutions of TSM can identify more feasible solutions. However, from the point of VR, SOM-2 is preferred since it can exclude more baseless solutions (this means more feasible solutions are contained in the SOM-2 solutions). In general, TSM would be preferred when only the range of the system objective needs to be determined, while SOM-2 would be much useful in identifying the effective values of the objective. 相似文献
20.
We solve a general variational inequality problem in a finite-dimensional setting, where only approximation sequences are known instead of exact values of the cost mapping and feasible set. We suggest to utilize a sequence of solutions of auxiliary problems based on a penalty method. Its convergence is attained without concordance of penalty and approximation parameters under mild coercivity type conditions. We also show that the regularized version of the penalty method enables us to further weaken the coercivity condition. 相似文献