共查询到20条相似文献,搜索用时 515 毫秒
1.
《Optimization》2012,61(1-2):75-90
In this paper, a kind of subgradient projection algorithms is established for minimizing a locally Lipschitz continuous function subject to nonlinearly smooth constraints, which is based on the idea to get a feasible and strictly descent direction by combining the ?-subgradient projection direction that attempts to satisfy the Kuhn-Tucker conditions with one corrected direction produced by a linear programming subproblem. The algorithm avoids the zigzagging phenomenon and converges to Kuhn-Tucker points, due to using the c.d.f. maps of Polak and Mayne (1985), ?active constraints and ?adjusted rules 相似文献
2.
The problem under consideration is a maximization problem over a constraint set defined by a finite number of inequality and equality constraints over an arbitrary set in a reflexive Banach space. A generalization of the Kuhn-Tucker necessary conditions is developed where neither the objective function nor the constraint functions are required to be differentiable. A new constraint qualification is imposed in order to validate the optimality criteria. It is shown that this qualification is the weakest possible in the sense that it is necessary for the optimality criteria to hold at the point under investigation for all families of objective functions having a constrained local maximum at this point 相似文献
3.
AGENERALTECHNIQUEFORDEALINGWITHDEGENERACYINREDUCEDGRADIENTMETHODSFORLINEARLYCONSTRAINED NONLINEAR PROGRAMMINGHANJIYE(韩继业);HUX... 相似文献
4.
In this paper we present ε-optimality conditions of the Kuhn-Tucker type for points which are within ε of being optimal to the problem of minimizing a nondifferentiable convex objective function subject to nondifferentiable convex inequality constraints, linear equality constraints and abstract constraints. Such ε-optimality conditions are of interest for theoretical consideration as well as from the computational point of view. Some illustrative applications are made. Thus we derive an expression for the ε-subdifferential of a general convex ‘max function’. We also show how the ε-optimality conditions given in this paper can be mechanized into a bundle algorithm for solving nondifferentiable convex programming problems with linear inequality constraints. 相似文献
5.
R. Mifflin 《Journal of Optimization Theory and Applications》1976,18(2):199-228
Convergence of a method of centers algorithm for solving nonlinear programming problems is considered. The algorithm is defined so that the subproblems that must be solved during its execution may be solved by finite-step procedures. Conditions are given under which the algorithm generates sequences of feasible points and constraint multiplier vectors that have accumulation points satisfying the Fritz John or the Kuhn-Tucker optimality conditions. Under stronger assumptions, linear convergence rates are established for the sequences of objective function, constraint function, feasible point, and multiplier values.This work was supported in part by the National Aeronautics and Space Administration, Predoctoral Traineeship No. NsG(T)-117, and by the National Science Foundation, Grants No. GP-25081 and No. GK-32710.The author wishes to thank Donald M. Topkis for his valuable criticism of an earlier version of this paper and a referee for his helpful comments. 相似文献
6.
1.IntroductionTheproblemconsideredinthispaperiswhereX={xER"laTx5hi,jEI={l,.'.,m}},ajeR"(jEI)areallcolumn*ThisresearchissupportedbytheNationalNaturalSciencesFoundationofChinaandNaturalSciencesFoundationofHunanProvince.vectors,hiERI(j6I)areallscalars,andf:R"-- Risacontinuouslydifferentiablefunction.Weonlyconsiderinequalityconstraintsheresinceanyequalitycanbeexpressedastwoinequalities.Withoutassumingregularityofthelinearconstraints,thereisnotanydifficultyinextendingtheresultstothegenera… 相似文献
7.
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. 相似文献
8.
C. J. Lin S. Lucidi L. Palagi A. Risi M. Sciandrone 《Journal of Optimization Theory and Applications》2009,141(1):107-126
Many real applications can be formulated as nonlinear minimization problems with a single linear equality constraint and box
constraints. We are interested in solving problems where the number of variables is so huge that basic operations, such as
the evaluation of the objective function or the updating of its gradient, are very time consuming. Thus, for the considered
class of problems (including dense quadratic programs), traditional optimization methods cannot be applied directly. In this
paper, we define a decomposition algorithm model which employs, at each iteration, a descent search direction selected among
a suitable set of sparse feasible directions. The algorithm is characterized by an acceptance rule of the updated point which
on the one hand permits to choose the variables to be modified with a certain degree of freedom and on the other hand does
not require the exact solution of any subproblem. The global convergence of the algorithm model is proved by assuming that
the objective function is continuously differentiable and that the points of the level set have at least one component strictly
between the lower and upper bounds. Numerical results on large-scale quadratic problems arising in the training of support
vector machines show the effectiveness of an implemented decomposition scheme derived from the general algorithm model. 相似文献
9.
B. S. Goh 《Journal of Optimization Theory and Applications》2011,148(3):505-527
In an optimization problem with equality constraints the optimal value function divides the state space into two parts. At
a point where the objective function is less than the optimal value, a good iteration must increase the value of the objective function. Thus, a good iteration must be a balance between increasing or decreasing the objective
function and decreasing a constraint violation function. This implies that at a point where the constraint violation function
is large, we should construct noninferior solutions relative to points in a local search region. By definition, an accessory
function is a linear combination of the objective function and a constraint violation function. We show that a way to construct
an acceptable iteration, at a point where the constraint violation function is large, is to minimize an accessory function.
We develop a two-phases method. In Phase I some constraints may not be approximately satisfied or the current point is not
close to the solution. Iterations are generated by minimizing an accessory function. Once all the constraints are approximately
satisfied, the initial values of the Lagrange multipliers are defined. A test with a merit function is used to determine whether
or not the current point and the Lagrange multipliers are both close to the optimal solution. If not, Phase I is continued.
If otherwise, Phase II is activated and the Newton method is used to compute the optimal solution and fast convergence is
achieved. 相似文献
10.
Jin-bao Jian Xing-de Mo Li-juan Qiu Su-ming Yang Fu-sheng Wang 《Journal of Optimization Theory and Applications》2014,160(1):158-188
In this paper, the nonlinear minimax problems with inequality constraints are discussed. Based on the idea of simple sequential quadratically constrained quadratic programming algorithm for smooth constrained optimization, an alternative algorithm for solving the discussed problems is proposed. Unlike the previous work, at each iteration, a feasible direction of descent called main search direction is obtained by solving only one subprogram which is composed of a convex quadratic objective function and simple quadratic inequality constraints without the second derivatives of the constrained functions. Then a high-order correction direction used to avoid the Maratos effect is computed by updating the main search direction with a system of linear equations. The proposed algorithm possesses global convergence under weak Mangasarian–Fromovitz constraint qualification and superlinear convergence under suitable conditions with the upper-level strict complementarity. At last, some preliminary numerical results are reported. 相似文献
11.
In this paper, two successive approximation techniques are presented for a class of large-scale nonlinear programming problems with decomposable constraints and a class of high-dimensional discrete optimal control problems, respectively. It is shown that: (a) the accumulation point of the sequence produced by the first method is a Kuhn-Tucker point if the constraint functions are decomposable and if the uniqueness condition holds; (b) the sequence converges to an optimum solution if the objective function is strictly pseudoconvex and if the constraint functions are decomposable and quasiconcave; and (c) similar conclusions for the second method hold also for a class of discrete optimal control problems under some assumptions. 相似文献
12.
Using the idea of upper convexificators, we propose constraint qualifications and study existence and boundedness of the Kuhn-Tucker
multipliers for a nonsmooth multiobjective optimization problem with inequality constraints and an arbitrary set constraint.
We show that, at locally weak efficient solutions where the objective and constraint functions are locally Lipschitz, the
constraint qualifications are necessary and sufficient conditions for the Kuhn-Tucker multiplier sets to be nonempty and bounded
under certain semiregularity assumptions on the upper convexificators of the functions. 相似文献
13.
C. Singh 《Journal of Optimization Theory and Applications》1977,22(4):631-635
Sufficient optimality criteria of the Kuhn-Tucker and Fritz John type in nonlinear programming are established in the presence of equality-inequality constraints. The constraint functions are assumed to be quasiconvex, and the objective function is taken to be pseudoconvex (or convex). 相似文献
14.
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. 相似文献
15.
《Journal of Computational and Applied Mathematics》2005,173(1):115-148
In this paper, we propose a new nonmonotonic interior point backtracking strategy to modify the reduced projective affine scaling trust region algorithm for solving optimization subject to nonlinear equality and linear inequality constraints. The general full trust region subproblem for solving the nonlinear equality and linear inequality constrained optimization is decomposed to a pair of trust region subproblems in horizontal and vertical subspaces of linearize equality constraints and extended affine scaling equality constraints. The horizontal subproblem in the proposed algorithm is defined by minimizing a quadratic projective reduced Hessian function subject only to an ellipsoidal trust region constraint in a null subspace of the tangential space, while the vertical subproblem is also defined by the least squares subproblem subject only to an ellipsoidal trust region constraint. By introducing the Fletcher's penalty function as the merit function, trust region strategy with interior point backtracking technique will switch to strictly feasible interior point step generated by a component direction of the two trust region subproblems. The global convergence of the proposed algorithm while maintaining fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion should bring about speeding up the convergence progress in some high nonlinear function conditioned cases. 相似文献
16.
This paper provides a canonical dual approach for minimizing a general quadratic function over a set of linear constraints. We first perturb the feasible domain by a quadratic constraint, and then solve a “restricted” canonical dual program of the perturbed problem at each iteration to generate a sequence of feasible solutions of the original problem. The generated sequence is proven to be convergent to a Karush-Kuhn-Tucker point with a strictly decreasing objective value. Some numerical results are provided to illustrate the proposed approach. 相似文献
17.
《Optimization》2012,61(3-4):275-281
A nonlinear program with inequality and equality constraints, generated by lipschitzian functions in a real Banach space is considered. The sufficiency of the Kuhn-Tucker optimality conditions at a point is established, using the function subdifferentials which generate the program. Also. in nonsmooth frame, Hanson's converse duality theorem from the convex programming is generalized 相似文献
18.
De-Tong Zhu 《计算数学(英文版)》1995,13(1):20-31
1.IntroductionConsiderthenonlinearequalityc0nstrainedoptimizati0npr0blemminf(x),s.t.c(x)=0(l-1)wheref:R"-R1andc:R"-R",m5n.RecentlyreducedHessianmethodsarepr0p0sedt0s0lvethispr0blem.C0lemanandConn[1l,andNocedalandOvertonl6lproposedseparatelysimilarquasi-Newt0nmethodsusingapproximatereducedHessian,However,suchmethodscann0tensuregl0balconvergenceandthereforeareavailableonlywhentheinitialstartsaregooden0ugh.TwobaJsicappr0aches,namelythelinesearchandthetrustregion,havebeende-velopedinordertoen… 相似文献
19.
Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. This paper develops a genetic algorithm for the linear bilevel problem in which both objective functions are linear and the common constraint region is a polyhedron. Taking into account the existence of an extreme point of the polyhedron which solves the problem, the algorithm aims to combine classical extreme point enumeration techniques with genetic search methods by associating chromosomes with extreme points of the polyhedron. The numerical results show the efficiency of the proposed algorithm. In addition, this genetic algorithm can also be used for solving quasiconcave bilevel problems provided that the second level objective function is linear. 相似文献
20.
C.A Botsaris 《Journal of Mathematical Analysis and Applications》1981,79(1):96-112
In this paper a class of algorithms is presented for minimizing a nonlinear function subject to nonlinear equality constraints along curvilinear search paths obtained by solving a linear approximation to an initial-value system of differential equations. The system of differential equations is derived by introducing a continuously differentiable matrix whose columns span the subspace tangent to the feasible region. The new approach provides a convenient way for working with the constraint set itself, rather than with the subspace tangent to it. The algorithms obtained in this paper may be viewed as curvilinear extensions of two known and successful minimization techniques. Under certain conditions, the algorithms converge to a point satisfying the first-order Kuhn-Tucker optimality conditions at a rate that is asymptotically at least quadratic. 相似文献