1,721,166 research outputs found
On the Role of Continuously Differentiable Exact Penalty Functions in Constrained Global Optimization.
No full textThe aim of this paper is to show that the new continuously differentiable exact penalty functions recently proposed in literature can play an important role in the field of constrained global optimization. In fact they allow us to transfer ideas and results proposed in unconstrained global optimization to the constrained case.
First, by drawing our inspiration from the unconstrained case and by using the strong exactness properties of a particular continuously differentiable penalty function, we propose a sufficient condition for a local constrained minimum point to be global.
Then we show that every constrained local minimum point satisfying the second order sufficient conditions is an ldquoattraction pointrdquo for a particular implementable minimization algorithm based on the considered penalty function. This result can be used to define new classes of global algorithms for the solution of general constrained global minimization problems. As an example, in this paper we describe a simulated annealing algorithm which produces a sequence of points converging in probability to a global minimum of the original constrained problem
NEW RESULTS ON A CLASS OF EXACT AUGMENTED LAGRANGIANS
No full textIn this paper, a new continuously differentiable exact augmented Lagrangian is introduced for the solution of nonlinear programming problems with compact feasible set. The distinguishing features of this augmented Lagrangian are that it is radially unbounded with respect to the multiplier and that it goes to infinity on the boundary of a compact set containing the feasible region. This allows one to establish a complete equivalence between the unconstrained minimization of the augmented Lagrangian on the product space of problem variables and multipliers and the solution of the constrained problem. © 1988 Plenum Publishing Corporation
New Results on a Continuously Differentiable Exact Penalty Function
No full textThe main motivation of this paper is to weaken the conditions that imply the correspondence between the solution of a constrained problem and the unconstrained minimization of a continuously differentiable function. In particular, a new continuously differentiable exact penalty function is proposed for the solution of nonlinear programming problems. Under mild assumptions, a complete equivalence can be established between the solution of the original constrained problem and the unconstrained minimization of this penalty function on a perturbation of the feasible set. This new penalty function and its exactness properties allow us to define globally and superlinearly convergent algorithms to solve nonlinear programming problems. As an example, a Newton-type algorithm is described which converges locally in one iteration in case of quadratic programming problems
Recursive Quadratic Programming Algorithm that Uses an Exact Augmented Lagrangian Function
No full textAn 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
A New Result in the Theory and Computation of the Least Norm Solution of a Linear Programm
No full textBy perturbing properly a linear program to a separable quadratic program, it is possible to solve the latter in its dual variable space by iterative techniques such as sparsity-preserving SOR (successive overrelaxation) algorithms. The main result of this paper gives an effective computational criterion to check whether the solutions of the perturbed quadratic programs provide the least-norm solution of the original linear program
Nonlinear Methods for Large Scale Linear Programming Problems
No full textIstituto di Analisi dei Sistemi e Informatica, Consiglio Nazionale delle Ricerch
A Nonmonotone Bundle-Type Scheme for Convex Nonsmooth Minimization
No full textIn this paper, we present a general scheme for bundle-type algorithms which includes a nonmonotone line search procedure and for which global convergence can be proved. Some numerical examples are reported, showing that the nonmonotonicity can be beneficial from a computational point of view
A derivative-free algorithm for systems of nonlinear inequalities
No full textRecently a new derivative-free algorithm has been proposed for the solution of linearly constrained finite minimax problems. This derivative-free algorithm is based on a smoothing technique that allows one to take into account the non-smoothness of the max function. In this paper, we investigate, both from a theoretical and computational point of view, the behavior of the minmax algorithm when used to solve systems of nonlinear inequalities when derivatives are unavailable. In particular, we show an interesting property of the algorithm, namely, under some mild conditions regarding the regularity of the functions defining the system, it is possible to prove that the algorithm locates a solution of the problem after a finite number of iterations. Furthermore, under a weaker regularity condition, it is possible to show that an accumulation point of the sequence generated by the algorithm exists which is a solution of the system. Moreover, we carried out numerical experimentation and comparison of the method against a standard pattern search minimization method. The obtained results confirm that the good theoretical properties of the method correspond to interesting numerical performance. Moreover, the algorithm compares favorably with a standard derivative-free method, and this seems to indicate that extending the smoothing technique to pattern search algorithms can be beneficial
A Differentiable Exact Penalty Function for Bound Constrained Quadratic Programming Problems
No full textA DERIVATIVE-FREE ALGORITHM FOR INEQUALITY CONSTRAINED NONLINEAR PROGRAMMING VIA SMOOTHING OF AN l(infinity) PENALTY FUNCTION
No full textIn this paper we consider inequality constrained nonlinear optimization problems where the first order derivatives of the objective function and the constraints cannot be used. Our starting point is the possibility to transform the original constrained problem into an unconstrained or linearly constrained minimization of a nonsmooth exact penalty function. This approach shows two main difficulties: the first one is the nonsmoothness of this class of exact penalty functions which may cause derivative-free codes to converge to nonstationary points of the problem; the second one is the fact that the equivalence between stationary points of the constrained problem and those of the exact penalty function can only be stated when the penalty parameter is smaller than a threshold value which is not known a priori. In this paper we propose a derivative-free algorithm which overcomes the preceding difficulties and produces a sequence of points that admits a subsequence converging to a Karush-Kuhn-Tucker point of the constrained problem. In particular the proposed algorithm is based on a smoothing of the nondifferentiable exact penalty function and includes an updating rule which, after at most a finite number of updates, is able to determine a "right value" for the penalty parameter. Furthermore we present the results obtained on a real world problem concerning the estimation of parameters in an insulin-glucose model of the human body
- …
