共查询到20条相似文献,搜索用时 31 毫秒
1.
Alfred Auslender 《Journal of Optimization Theory and Applications》2013,156(2):183-212
This paper is concerned with nonlinear, semidefinite, and second-order cone programs. A general algorithm, which includes sequential quadratic programming and sequential quadratically constrained quadratic programming methods, is presented for solving these problems. In the particular case of standard nonlinear programs, the algorithm can be interpreted as a prox-regularization of the Solodov sequential quadratically constrained quadratic programming method presented in Mathematics of Operations Research (2004). For such type of methods, the main cost of computation amounts to solve a linear cone program for which efficient solvers are available. Usually, “global convergence results” for these methods require, as for the Solodov method, the boundedness of the primal sequence generated by the algorithm. The other purpose of this paper is to establish global convergence results without boundedness assumptions on any of the iterative sequences built by the algorithm. 相似文献
2.
S. Lucidi 《Journal of Optimization Theory and Applications》1990,67(2):227-245
An algorithm for nonlinear programming problems with equality constraints is presented which is globally and superlinearly convergent. The algorithm employs a recursive quadratic programming scheme to obtain a search direction and uses a differentiable exact augmented Lagrangian as line search function to determine the steplength along this direction. It incorporates an automatic adjustment rule for the selection of the penalty parameter and avoids the need to evaluate second-order derivatives of the problem functions. Some numerical results are reported. 相似文献
3.
A new deterministic algorithm for solving convex mixed-integer nonlinear programming (MINLP) problems is presented in this paper: The extended supporting hyperplane (ESH) algorithm uses supporting hyperplanes to generate a tight overestimated polyhedral set of the feasible set defined by linear and nonlinear constraints. A sequence of linear or quadratic integer-relaxed subproblems are first solved to rapidly generate a tight linear relaxation of the original MINLP problem. After an initial overestimated set has been obtained the algorithm solves a sequence of mixed-integer linear programming or mixed-integer quadratic programming subproblems and refines the overestimated set by generating more supporting hyperplanes in each iteration. Compared to the extended cutting plane algorithm ESH generates a tighter overestimated set and unlike outer approximation the generation point for the supporting hyperplanes is found by a simple line search procedure. In this paper it is proven that the ESH algorithm converges to a global optimum for convex MINLP problems. The ESH algorithm is implemented as the supporting hyperplane optimization toolkit (SHOT) solver, and an extensive numerical comparison of its performance against other state-of-the-art MINLP solvers is presented. 相似文献
4.
Luís M. Fernandes Joaquim J. Júdice Hanif D. Sherali Maria A. Forjaz 《Computational Optimization and Applications》2014,59(1-2):113-134
In this paper, we discuss the solution of linear and quadratic eigenvalue complementarity problems (EiCPs) using an enumerative algorithm of the type introduced by Júdice et al. (Optim. Methods Softw. 24:549–586, 2009). Procedures for computing the interval that contains all the eigenvalues of the linear EiCP are first presented. A nonlinear programming (NLP) model for the quadratic EiCP is formulated next, and a necessary and sufficient condition for a stationary point of the NLP to be a solution of the quadratic EiCP is established. An extension of the enumerative algorithm for the quadratic EiCP is also developed, which solves this problem by computing a global minimum for the NLP formulation. Some computational experience is presented to highlight the efficiency and efficacy of the proposed enumerative algorithm for solving linear and quadratic EiCPs. 相似文献
5.
Xin-wei Liu 《计算数学(英文版)》2001,(3)
1. Introductioncrust region methods are iterative. As a strategy of globalization, the trust region approach was introduced into solving unconstrained optimization and proved to be efficient androbust. An excellent survey was given by Mor6(1983). The associated research with trustregion methods for unconstrained optimization can be found in Fletcher(1980), Powell(1975),Sorensen(1981), Shultz, Schnabel and Byrd(1985), Yuan(1985). The solution of the trust region subproblem is still an activ… 相似文献
6.
A new algorithm, the dual active set algorithm, is presented for solving a minimization problem with equality constraints and bounds on the variables. The algorithm identifies the active bound constraints by maximizing an unconstrained dual function in a finite number of iterations. Convergence of the method is established, and it is applied to convex quadratic programming. In its implementable form, the algorithm is combined with the proximal point method. A computational study of large-scale quadratic network problems compares the algorithm to a coordinate ascent method and to conjugate gradient methods for the dual problem. This study shows that combining the new algorithm with the nonlinear conjugate gradient method is particularly effective on difficult network problems from the literature. 相似文献
7.
In this paper, a new SQP algorithm is presented to solve the general nonlinear programs with mixed equality and inequality constraints. Quoted from P. Spellucci (see [9]), this method maybe be named sequential equality constrained quadratic programming (SECQP) algorithm. Per single iteration, based on an active set strategy ( see [9]), this SECQP algorithm requires only to solve equality constrained quadratic programming subproblems or system of linear equations. The theoretical analysis shows that global and superlinear convergence can be induced under some suitable conditions. 相似文献
8.
Q. Ni 《计算数学(英文版)》1997,15(1):36-54
1.IntroductionInthispaperweconsiderthefollowingnonlinearprogrammingproblemminimizef(x)subjecttogj(x)2o,jEJ={1,...,m}.(1'1)Extensionstoproblemincludingalsoequalityconstraintswillbepossible.Thefunctionf:W-Rlandgj:Rn-R',jEJaretwicecontinuouslydifferentiable.Inpaxticular,weapplyQP-free(withoutquadraticprogrammingsubproblems),truncatedhybridmethodsforsolvingthelarge-scaJenonlinearprogrammingproblems,inwhichthenumberofvariablesandthenumberofconstraiotsin(1.1)aregreat.Wediscussthecase,wheresecon… 相似文献
9.
S. MashayekhiY. Ordokhani M. Razzaghi 《Communications in Nonlinear Science & Numerical Simulation》2012,17(4):1831-1843
In this paper, a new numerical method for solving the nonlinear constrained optimal control with quadratic performance index is presented. The method is based upon hybrid functions approximation. The properties of hybrid functions consisting of block-pulse functions and Bernoulli polynomials are presented. The operational matrix of integration is introduced. This matrix is then utilized to reduce the solution of the nonlinear constrained optimal control to a nonlinear programming one to which existing well-developed algorithms may be applied. Illustrative examples are included to demonstrate the validity and applicability of the technique. 相似文献
10.
In this paper, an algorithm is developed for solving a nonlinear programming problem with linear contraints. The algorithm performs two major computations. First, the search vector is determined by projecting the negative gradient of the objective function on a polyhedral set defined in terms of the gradients of the equality constraints and the near binding inequality constraints. This least-distance program is solved by Lemke's complementary pivoting algorithm after eliminating the equality constraints using Cholesky's factorization. The second major calculation determines a stepsize by first computing an estimate based on quadratic approximation of the function and then finalizing the stepsize using Armijo's inexact line search. It is shown that any accumulation point of the algorithm is a Kuhn-Tucker point. Furthermore, it is shown that, if an accumulation point satisfies the second-order sufficiency optimality conditions, then the whole sequence of iterates converges to that point. Computational testing of the algorithm is presented. 相似文献
11.
In this paper,a new globally convergent algorithm for nonlinear optimization prablems with equality and inequality constraints is presented. The new algorithm is of SQP type which determines a search direction by solving a quadratic programming subproblem per itera-tion. Some revisions on the quadratic programming subproblem have been made in such a way that the associated constraint region is nonempty for each point x generated by the algorithm, i. e. , the subproblems always have optimal solutions. The new algorithm has two important properties. The computation of revision parameter for guaranteeing the consistency of quadratic sub-problem and the computation of the second order correction step for superlinear convergence use the same inverse of a matrix per iteration, so the computation amount of the new algorithm will not be increased much more than other SQP type algorithms; Another is that the new algorithm can give automatically a feasible point as a starting point for the quadratic subproblems pe 相似文献
12.
13.
Meiling Liu Xueqian Li Dingguo Pu 《Journal of Applied Mathematics and Computing》2012,40(1-2):261-275
A feasible sequential quadratic programming (SQP) filter algorithm is proposed for general nonlinear programming. It is based on the modified quadratic programming (QP) subproblem in which each iteration proceeds in two phases. The first phase solves a general convex QP problem which does not require any feasibility restoration phase whose computation may be expensive. And, under some mild conditions, the global convergence is proved. The second phase can make the presented SQP method derive quadratic convergence by employing exact Hessian information. 相似文献
14.
In this paper, we study recourse-based stochastic nonlinear programs and make two sets of contributions. The first set assumes
general probability spaces and provides a deeper understanding of feasibility and recourse in stochastic nonlinear programs.
A sufficient condition, for equality between the sets of feasible first-stage decisions arising from two different interpretations
of almost sure feasibility, is provided. This condition is an extension to nonlinear settings of the “W-condition,” first
suggested by Walkup and Wets (SIAM J. Appl. Math. 15:1299–1314, 1967). Notions of complete and relatively-complete recourse for nonlinear stochastic programs are defined and simple sufficient
conditions for these to hold are given. Implications of these results on the L-shaped method are discussed. Our second set
of contributions lies in the construction of a scalable, superlinearly convergent method for solving this class of problems,
under the setting of a finite sample-space. We present a novel hybrid algorithm that combines sequential quadratic programming
(SQP) and Benders decomposition. In this framework, the resulting quadratic programming approximations while arbitrarily large,
are observed to be two-period stochastic quadratic programs (QPs) and are solved through two variants of Benders decomposition.
The first is based on an inexact-cut L-shaped method for stochastic quadratic programming while the second is a quadratic
extension to a trust-region method suggested by Linderoth and Wright (Comput. Optim. Appl. 24:207–250, 2003). Obtaining Lagrange multiplier estimates in this framework poses a unique challenge and are shown to be cheaply obtainable
through the solution of a single low-dimensional QP. Globalization of the method is achieved through a parallelizable linesearch
procedure. Finally, the efficiency and scalability of the algorithm are demonstrated on a set of stochastic nonlinear programming
test problems. 相似文献
15.
D. H. Jacobson 《Journal of Optimization Theory and Applications》1968,2(6):411-440
In this paper, the notion of differential dynamic programming is used to develop new second-order and first-order successive-approximation methods for determining optimal control. The unconstrained, nonlinear control problem is first considered, and a second-order algorithm is developed which has wider application then existing second-variation and second-order algorithms. A new first-order algorithm emerges as a special case of the second-order one. Control inequality constraints are introduced into the problem and a second-order algorithm is devised which is able to solve this constrained problem. It is believed that control constraints have not been handled previously in this way. Again, a first-order algorithm emerges as a special case. The usefulness of the second-order algorithms is illustrated by the computer solution of three control problems. The methods presented in this paper have been extended by the author to solve problems with terminal constraints and implicitly given final time. Details of these procedures are not given in this paper, but the relevant references are cited. 相似文献
16.
A new smoothing function for the second-order cone programming is given by smoothing the symmetric perturbed Fischer–Burmeister function. Based on this new function, a one-step smoothing Newton method is presented for solving the second-order cone programming. The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. This algorithm does not have restrictions regarding its starting point and is Q-quadratically convergent. Numerical results suggest the effectiveness of our algorithm. 相似文献
17.
An algorithm of sequential systems of linear equations for nonlinear optimization problems with arbitrary initial point 总被引:6,自引:0,他引:6
For current sequential quadratic programming (SQP) type algorithms, there exist two problems: (i) in order to obtain a search
direction, one must solve one or more quadratic programming subproblems per iteration, and the computation amount of this
algorithm is very large. So they are not suitable for the large-scale problems; (ii) the SQP algorithms require that the related
quadratic programming subproblems be solvable per iteration, but it is difficult to be satisfied. By using ε-active set procedure
with a special penalty function as the merit function, a new algorithm of sequential systems of linear equations for general
nonlinear optimization problems with arbitrary initial point is presented. This new algorithm only needs to solve three systems
of linear equations having the same coefficient matrix per iteration, and has global convergence and local superlinear convergence.
To some extent, the new algorithm can overcome the shortcomings of the SQP algorithms mentioned above.
Project partly supported by the National Natural Science Foundation of China and Tianyuan Foundation of China. 相似文献
18.
We propose an SQP-type algorithm for solving nonlinear second-order cone programming (NSOCP) problems. At every iteration,
the algorithm solves a convex SOCP subproblem in which the constraints involve linear approximations of the constraint functions
in the original problem and the objective function is a convex quadratic function. Those subproblems can be transformed into
linear SOCP problems, for which efficient interior point solvers are available. We establish global convergence and local
quadratic convergence of the algorithm under appropriate assumptions. We report numerical results to examine the effectiveness
of the algorithm.
This work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science. 相似文献
19.
A successive quadratic programming algorithm with global and superlinear convergence properties 总被引:6,自引:0,他引:6
Masao Fukushima 《Mathematical Programming》1986,35(3):253-264
This paper presents a successive quadratic programming algorithm for solving general nonlinear programming problems. In order to avoid the Maratos effect, direction-finding subproblems are derived by modifying the second-order approximations to both objective and constraint functions of the problem. We prove that the algorithm possesses global and superlinear convergence properties.This work was supported in part by a Scientific Research Grant-in-Aid from the Ministry of Education, Science and Culture, Japan. 相似文献
20.
This paper describes a new algorithm for nonlinear programming with inequality constraints. The proposed approach solves a sequence of quadratic programming subproblems via the line search technique and uses a new globalization strategy. An increased flexibility in the step acceptance procedure is designed to promote long productive steps for fast convergence. Global convergence is proved under some reasonable assumptions and preliminary numerical results are presented. 相似文献