共查询到20条相似文献,搜索用时 31 毫秒
1.
A linear programming-based optimization algorithm for solving nonlinear programming problems 总被引:1,自引:0,他引:1
In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems. 相似文献
2.
J. R. WillemsA. V. Cabot 《Mathematical and Computer Modelling》1995,21(12):75-84
In this paper, we present a branch and bound algorithm for solving the constrained entropy mathematical programming problem. Unlike other methods for solving this problem, our method solves more general problems with inequality constraints. The advantage of the proposed technique is that the relaxed problem solved at each node is a singly constrained network problem. The disadvantage is that the relaxed problem has twice as many variables as the original problem. An application to regional planning is given, and an example problem is solved. 相似文献
3.
Efficient Sequential Quadratic Programming Implementations for Equality-Constrained Discrete-Time Optimal Control 总被引:1,自引:0,他引:1
Efficient sequential quadratic programming (SQP) implementations are presented for equality-constrained, discrete-time, optimal control problems. The algorithm developed calculates the search direction for the equality-based variant of SQP and is applicable to problems with either fixed or free final time. Problem solutions are obtained by solving iteratively a series of constrained quadratic programs. The number of mathematical operations required for each iteration is proportional to the number of discrete times N. This is contrasted by conventional methods in which this number is proportional to N
3. The algorithm results in quadratic convergence of the iterates under the same conditions as those for SQP and simplifies to an existing dynamic programming approach when there are no constraints and the final time is fixed. A simple test problem and two application problems are presented. The application examples include a satellite dynamics problem and a set of brachistochrone problems involving viscous friction. 相似文献
4.
An outer-approximation algorithm is presented for solving mixed-integer nonlinear programming problems of a particular class.
Linearity of the integer (or discrete) variables, and convexity of the nonlinear functions involving continuous variables
are the main features in the underlying mathematical structure. Based on principles of decomposition, outer-approximation
and relaxation, the proposed algorithm effectively exploits the structure of the problems, and consists of solving an alternating
finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program. Convergence
and optimality properties of the algorithm are presented, as well as a general discussion on its implementation. Numerical
results are reported for several example problems to illustrate the potential of the proposed algorithm for programs in the
class addressed in this paper. Finally, a theoretical comparison with generalized Benders decomposition is presented on the
lower bounds predicted by the relaxed master programs. 相似文献
5.
Ulrich Raber 《Journal of Global Optimization》1998,13(4):417-432
In this paper we present an algorithm for solving nonconvex quadratically constrained quadratic programs (all-quadratic programs). The method is based on a simplicial branch-and-bound scheme involving mainly linear programming subproblems. Under the assumption that a feasible point of the all-quadratic program is known, the algorithm guarantees an -approximate optimal solution in a finite number of iterations. Computational experiments with an implementation of the procedure are reported on randomly generated test problems. The presented algorithm often outperforms a comparable rectangular branch-and-bound method. 相似文献
6.
Krzysztof C. Kiwiel 《Applied Mathematics and Optimization》1988,18(1):163-180
A descent method is given for minimizing a nondifferentiable function which can be locally approximated by pointwise minima of convex functions. At each iterate the algorithm finds several directions by solving several linear or quadratic programming subproblems. These directions are then used in an Armijo-like search for the next iterate. A feasible direction extension to inequality constrained minimization problems is also presented. The algorithms converge to points satisfying necessary optimality conditions which are sharper than the ones involved in convergence results for algorithms based on the Clarke subdifferential.This research was sponsored by Project 02.15. 相似文献
7.
In this article, an affine scaling interior trust-region algorithm which employs backtracking line search with filter technique is presented for solving nonlinear equality constrained programming with nonnegative constraints on variables. At current iteration, the general full affine scaling trust-region subproblem is decomposed into a pair of trust-region subproblems in vertical and horizontal subspaces, respectively. The trial step is given by the solutions of the pair of trust-region subproblems. Then, the step size is decided by backtracking line search together with filter technique. This is different from traditional trust-region methods and has the advantage of decreasing the number of times that a trust-region subproblem must be resolved in order to determine a new iteration point. Meanwhile, using filter technique instead of merit function to determine a new iteration point can avoid the difficult decisions regarding the choice of penalty parameters. Under some reasonable assumptions, the new method possesses the property of global convergence to the first-order critical point. Preliminary numerical results show the effectiveness of the proposed algorithm. 相似文献
8.
《Journal of Computational and Applied Mathematics》2005,180(1):201-211
Sequential quadratic programming (SQP) has been one of the most important methods for solving nonlinearly constrained optimization problems. In this paper, we present and study an active set SQP algorithm for inequality constrained optimization. The active set technique is introduced which results in the size reduction of quadratic programming (QP) subproblems. The algorithm is proved to be globally convergent. Thus, the results show that the global convergence of SQP is still guaranteed by deleting some “redundant” constraints. 相似文献
9.
Faiz A. Al-Khayyal Christian Larsen Timothy Van Voorhis 《Journal of Global Optimization》1995,6(3):215-230
We present an algorithm for finding approximate global solutions to quadratically constrained quadratic programming problems. The method is based on outer approximation (linearization) and branch and bound with linear programming subproblems. When the feasible set is non-convex, the infinite process can be terminated with an approximate (possibly infeasible) optimal solution. We provide error bounds that can be used to ensure stopping within a prespecified feasibility tolerance. A numerical example illustrates the procedure. Computational experiments with an implementation of the procedure are reported on bilinearly constrained test problems with up to sixteen decision variables and eight constraints.This research was supported in part by National Science Foundation Grant DDM-91-14489. 相似文献
10.
11.
Audet C. Hansen P. Jaumard B. Savard G. 《Journal of Optimization Theory and Applications》1997,93(2):273-300
We study links between the linear bilevel and linear mixed 0–1 programming problems. A new reformulation of the linear mixed 0–1 programming problem into a linear bilevel programming one, which does not require the introduction of a large finite constant, is presented. We show that solving a linear mixed 0–1 problem by a classical branch-and-bound algorithm is equivalent in a strong sense to solving its bilevel reformulation by a bilevel branch-and-bound algorithm. The mixed 0–1 algorithm is embedded in the bilevel algorithm through the aforementioned reformulation; i.e., when applied to any mixed 0–1 instance and its bilevel reformulation, they generate sequences of subproblems which are identical via the reformulation. 相似文献
12.
Surrogate Gradient Algorithm for Lagrangian Relaxation 总被引:6,自引:0,他引:6
The subgradient method is used frequently to optimize dual functions in Lagrangian relaxation for separable integer programming problems. In the method, all subproblems must be solved optimally to obtain a subgradient direction. In this paper, the surrogate subgradient method is developed, where a proper direction can be obtained without solving optimally all the subproblems. In fact, only an approximate optimization of one subproblem is needed to get a proper surrogate subgradient direction, and the directions are smooth for problems of large size. The convergence of the algorithm is proved. Compared with methods that take effort to find better directions, this method can obtain good directions with much less effort and provides a new approach that is especially powerful for problems of very large size. 相似文献
13.
Hong-gangXue Cheng-xianXu Feng-minXu 《计算数学(英文版)》2004,22(6):895-904
In this paper, we propose a new branch and bound algorithm for the solution of large scale separable concave programming problems. The largest distance bisection (LDB) technique is proposed to divide rectangle into sub-rectangles when one problem is branched into two subproblems. It is proved that the LDB method is a normal rectangle subdivision(NRS). Numerical tests on problems with dimensions from 100 to 10000 show that the proposed branch and bound algorithm is efficient for solving large scale separable concave programming problems, and convergence rate is faster than ω-subdivision method. 相似文献
14.
In this paper, we describe a method to solve large-scale structural optimization problems by sequential convex programming (SCP). A predictor-corrector interior point method is applied to solve the strictly convex subproblems. The SCP algorithm and the topology optimization approach are introduced. Especially, different strategies to solve certain linear systems of equations are analyzed. Numerical results are presented to show the efficiency of the proposed method for solving topology optimization problems and to compare different variants. 相似文献
15.
16.
胡国雷 《高等学校计算数学学报》2000,22(2):117-122
1 引 言我们知道,描述常义线性规划问题的数学模型为:mincTxs.tAx=bx≥0 在经济问题中,线性规划中的向量c往往表示为价格,而在许多实际规划问题中价格向量c往往会在一定范围内扰动.这时,我们可以考虑这样一类广义线性规划问题:minx{maxy∈YyTx}s.tAx=b x∈X(1)其中,A∈Rm×n,b∈Rm,X={x∈Rn|x≥0},Y是Rn中的一个凸闭子集.有关广义线性规划问题的求解,何在文献[1]中作过一些讨论.我们通过对线性约束Ax=b引入乘子可得到广义线性规划问题(1)定义在X×Y×Rm上的Lagrange函数为:L(x,y,η)=yTx-ηT(Ax-b)(2) 如果x*是(1)式的… 相似文献
17.
18.
19.
Nuno P. Faísca Konstantinos I. Kouramas Pedro M. Saraiva Berç Rustem Efstratios N. Pistikopoulos 《Optimization Letters》2008,2(2):267-280
In this work, we present a new algorithm for solving complex multi-stage optimization problems involving hard constraints
and uncertainties, based on dynamic and multi-parametric programming techniques. Each echelon of the dynamic programming procedure,
typically employed in the context of multi-stage optimization models, is interpreted as a multi-parametric optimization problem,
with the present states and future decision variables being the parameters, while the present decisions the corresponding
optimization variables. This reformulation significantly reduces the dimension of the original problem, essentially to a set
of lower dimensional multi-parametric programs, which are sequentially solved. Furthermore, the use of sensitivity analysis
circumvents non-convexities that naturally arise in constrained dynamic programming problems. The potential application of
the proposed novel framework to robust constrained optimal control is highlighted. 相似文献
20.
Hong-Xuan Huang Panos M. Pardalos Oleg A. Prokopyev 《Computational Optimization and Applications》2006,33(2-3):187-208
In this paper several equivalent formulations for the quadratic binary programming problem are presented. Based on these formulations
we describe four different kinds of strategies for estimating lower bounds of the objective function, which can be integrated
into a branch and bound algorithm for solving the quadratic binary programming problem. We also give a theoretical explanation
for forcing rules used to branch the variables efficiently, and explore several properties related to obtained subproblems.
From the viewpoint of the number of subproblems solved, new strategies for estimating lower bounds are better than those used
before. A variant of a depth-first branch and bound algorithm is described and its numerical performance is presented. 相似文献