A Nonsmooth Global Optimization Technique Using Slopes: The One-Dimensional Case

In this paper we introduce a pruning technique based on slopes in the context of interval branch-and-bound methods for nonsmooth global optimization. We develop the theory for a slope pruning step which can be utilized as an accelerating device similar to the monotonicity test frequently used in interval methods for smooth problems. This pruning step offers the possibility to cut away a large part of the box currently investigated by the optimization algorithm. We underline the new technique's efficiency by comparing two variants of a global optimization model algorithm: one equipped with the monotonicity test and one equipped with the pruning step. For this reason, we compared the required CPU time, the number of function and derivative or slope evaluations, and the necessary storage space when solving several smooth global optimization problems with the two variants. The paper concludes on the test results for several nonsmooth examples.     

A quasi-discrete Newton algorithm with a nonmonotone stabilization technique

In this paper, we define an unconstrained optimization algorithm employing only first-order derivatives, in which a nonmonotone stabilization technique is used in conjunction with a quasidiscrete Newton method for the computation of the search direction. Global and superlinear convergence is proved, and numerical results are reported.     

Contingent derivatives and regularization for noncoercive inverse problems

Abstract

We study the inverse problem of parameter identification in noncoercive variational problems that commonly appear in applied models. We examine the differentiability of the set-valued parameter-to-solution map using the first-order and the second-order contingent derivatives. We explore the inverse problem using the output least-squares and the modified output least-squares objectives. By regularizing the noncoercive variational problem, we obtain a single-valued regularized parameter-to-solution map and investigate its smoothness and boundedness. We also consider optimization problems using the output least-squares and the modified output least-squares objectives for the regularized variational problem. We give a complete convergence analysis showing that for the output least-squares and the modified output least-squares, the regularized minimization problems approximate the original optimization problems suitably. We also provide the first-order and the second-order adjoint method for the computation of the first-order and the second-order derivatives of the output least-squares objective. We provide discrete formulas for the gradient and the Hessian calculation and present numerical results.     

A generalized Newton algorithm using higher-order derivatives

This paper presents a general optimization algorithm using first-order torth order derivatives to find the optimum of anr-continuously differentiable function of many variables. This algorithm collapses to the Newton-Raphson algorithm when only first- and second-order derivatives are used. The computation of the required higher-order derivatives are readily available through thetable algorithm. The generalized CES production function is used as an example.     

An inexact Newton method for nonconvex equality constrained optimization

We present a matrix-free line search algorithm for large-scale equality constrained optimization that allows for inexact step computations. For strictly convex problems, the method reduces to the inexact sequential quadratic programming approach proposed by Byrd et al. [SIAM J. Optim. 19(1) 351–369, 2008]. For nonconvex problems, the methodology developed in this paper allows for the presence of negative curvature without requiring information about the inertia of the primal–dual iteration matrix. Negative curvature may arise from second-order information of the problem functions, but in fact exact second derivatives are not required in the approach. The complete algorithm is characterized by its emphasis on sufficient reductions in a model of an exact penalty function. We analyze the global behavior of the algorithm and present numerical results on a collection of test problems.     

一类无需线性搜索的记忆梯度法

提出一类新的求解无约束优化问题的记忆梯度法,证明了算法的全局收敛性.当目标函数为一致凸函数时,对其线性收敛速率进行了分析.新算法在迭代过程中无需对步长进行线性搜索,仅需对算法中的一些参数进行预测估计,从而减少了目标函数及梯度的迭代次数,降低了算法的计算量和存储量.数值试验表明算法是有效的.     

Accelerating Branch-and-Bound through a Modeling Language Construct for Relaxation-Specific Constraints

In the tradition of modeling languages for optimization, a single model is passed to a solver for solution. In this paper, we extend BARON’s modeling language in order to facilitate the communication of problem-specific relaxation information from the modeler to the branch-and-bound solver. This effectively results into two models being passed from the modeling language to the solver. Three important application areas are identified and computational experiments are presented. In all cases, nonlinear constraints are provided only to the relaxation constructor in order to strengthen the lower bounding step of the algorithm without complicating the local search process. In the first application area, nonlinear constraints from the reformulation–linearization technique (RLT) are added to strengthen a problem formulation. This approach is illustrated for the pooling problem and computational results show that it results in a scheme that makes global optimization nearly as fast as local optimization for pooling problems from the literature. In the second application area, we communicate with the relaxation constructor the first-order optimality conditions for unconstrained global optimization problems. Computational experiments with polynomial programs demonstrate that this approach leads to a significant reduction of the size of the branch-and-bound search tree. In the third application, problem-specific nonlinear optimality conditions for the satisfiability problem are used to strengthen the lower bounding step and are found to significantly expedite the branch-and-bound algorithm when applied to a nonlinear formulation of this problem.     

Corrected sequential linear programming for sparse minimax optimization

We present a new algorithm for nonlinear minimax optimization which is well suited for large and sparse problems. The method is based on trust regions and sequential linear programming. On each iteration a linear minimax problem is solved for a basic step. If necessary, this is followed by the determination of a minimum norm corrective step based on a first-order Taylor approximation. No Hessian information needs to be stored. Global convergence is proved. This new method has been extensively tested and compared with other methods, including two well known codes for nonlinear programming. The numerical tests indicate that in many cases the new method can find the solution in just as few iterations as methods based on approximate second-order information. The tests also show that for some problems the corrective steps give much faster convergence than for similar methods which do not employ such steps.Research supported partly by The Nordic Council of Ministers, The Icelandic Science Council, The University of Iceland Research Fund and The Danish Science Research Council.     

A proximal point algorithm for the monotone second-order cone complementarity problem

This paper is devoted to the study of the proximal point algorithm for solving monotone second-order cone complementarity problems. The proximal point algorithm is to generate a sequence by solving subproblems that are regularizations of the original problem. After given an appropriate criterion for approximate solutions of subproblems by adopting a merit function, the proximal point algorithm is verified to have global and superlinear convergence properties. For the purpose of solving the subproblems efficiently, we introduce a generalized Newton method and show that only one Newton step is eventually needed to obtain a desired approximate solution that approximately satisfies the appropriate criterion under mild conditions. Numerical comparisons are also made with the derivative-free descent method used by Pan and Chen (Optimization 59:1173–1197, 2010), which confirm the theoretical results and the effectiveness of the algorithm.     

Globally convergent DC trust-region methods

In this paper, we investigate the use of DC (Difference of Convex functions) models and algorithms in the application of trust-region methods to the solution of a class of nonlinear optimization problems where the constrained set is closed and convex (and, from a practical point of view, where projecting onto the feasible region is computationally affordable). We consider DC local models for the quadratic model of the objective function used to compute the trust-region step, and apply a primal-dual subgradient method to the solution of the corresponding trust-region subproblems. One is able to prove that the resulting scheme is globally convergent to first-order stationary points. The theory requires the use of exact second-order derivatives but, in turn, the computation of the trust-region step asks only for one projection onto the feasible region (in comparison to the calculation of the generalized Cauchy point which may require more). The numerical efficiency and robustness of the proposed new scheme when applied to bound-constrained problems is measured by comparing its performance against some of the current state-of-the-art nonlinear programming solvers on a vast collection of test problems.     

On the Global Convergence of a Projective Trust Region Algorithm for Nonlinear Equality Constrained Optimization

A trust-region sequential quadratic programming (SQP) method is developed and analyzed for the solution of smooth equality constrained optimization problems. The trust-region SQP algorithm is based on filter line search technique and a composite-step approach, which decomposes the overall step as sum of a vertical step and a horizontal step. The algorithm includes critical modifications of horizontal step computation. One orthogonal projective matrix of the Jacobian of constraint functions is employed in trust-region subproblems. The orthogonal projection gives the null space of the transposition of the Jacobian of the constraint function. Theoretical analysis shows that the new algorithm retains the global convergence to the first-order critical points under rather general conditions. The preliminary numerical results are reported.     

An efficient nonmonotone trust-region method for unconstrained optimization

The monotone trust-region methods are well-known techniques for solving unconstrained optimization problems. While it is known that the nonmonotone strategies not only can improve the likelihood of finding the global optimum but also can improve the numerical performance of approaches, the traditional nonmonotone strategy contains some disadvantages. In order to overcome to these drawbacks, we introduce a variant nonmonotone strategy and incorporate it into trust-region framework to construct more reliable approach. The new nonmonotone strategy is a convex combination of the maximum of function value of some prior successful iterates and the current function value. It is proved that the proposed algorithm possesses global convergence to first-order and second-order stationary points under some classical assumptions. Preliminary numerical experiments indicate that the new approach is considerably promising for solving unconstrained optimization problems.     

A Newton’s method for perturbed second-order cone programs

We develop optimality conditions for the second-order cone program. Our optimality conditions are well-defined and smooth everywhere. We then reformulate the optimality conditions into several systems of equations. Starting from a solution to the original problem, the sequence generated by Newton’s method converges Q-quadratically to a solution of the perturbed problem under some assumptions. We globalize the algorithm by (1) extending the gradient descent method for differentiable optimization to minimizing continuous functions that are almost everywhere differentiable; (2) finding a directional derivative of the equations. Numerical examples confirm that our algorithm is good for “warm starting” second-order cone programs—in some cases, the solution of a perturbed instance is hit in two iterations. In the progress of our algorithm development, we also generalize the nonlinear complementarity function approach for two variables to several variables.     

A note on the implementation of an interior-point algorithm for nonlinear optimization with inexact step computations

This paper describes an implementation of an interior-point algorithm for large-scale nonlinear optimization. It is based on the algorithm proposed by Curtis et?al. (SIAM J Sci Comput 32:3447?C3475, 2010), a method that possesses global convergence guarantees to first-order stationary points with the novel feature that inexact search direction calculations are allowed in order to save computational expense. The implementation follows the proposed algorithm, but includes many practical enhancements, such as functionality to avoid the computation of a normal step during every iteration. The implementation is included in the IPOPT software package paired with an iterative linear system solver and preconditioner provided in PARDISO. Numerical results on a large nonlinear optimization test set and two PDE-constrained optimization problems with control and state constraints are presented to illustrate that the implementation is robust and efficient for large-scale applications.     

A second-order globally convergent direct-search method and its worst-case complexity

Direct-search algorithms form one of the main classes of algorithms for smooth unconstrained derivative-free optimization, due to their simplicity and their well-established convergence results. They proceed by iteratively looking for improvement along some vectors or directions. In the presence of smoothness, first-order global convergence comes from the ability of the vectors to approximate the steepest descent direction, which can be quantified by a first-order criticality (cosine) measure. The use of a set of vectors with a positive cosine measure together with the imposition of a sufficient decrease condition to accept new iterates leads to a convergence result as well as a worst-case complexity bound. In this paper, we present a second-order study of a general class of direct-search methods. We start by proving a weak second-order convergence result related to a criticality measure defined along the directions used throughout the iterations. Extensions of this result to obtain a true second-order optimality one are discussed, one possibility being a method using approximate Hessian eigenvectors as directions (which is proved to be truly second-order globally convergent). Numerically guaranteeing such a convergence can be rather expensive to ensure, as it is indicated by the worst-case complexity analysis provided in this paper, but turns out to be appropriate for some pathological examples.     

Globally and Superlinearly Convergent QP-Free Algorithm for Nonlinear Constrained Optimization

A new, infeasible QP-free algorithm for nonlinear constrained optimization problems is proposed. The algorithm is based on a continuously differentiable exact penalty function and on active-set strategy. After a finite number of iterations, the algorithm requires only the solution of two linear systems at each iteration. We prove that the algorithm is globally convergent toward the KKT points and that, if the second-order sufficiency condition and the strict complementarity condition hold, then the rate of convergence is superlinear or even quadratic. Moreover, we incorporate two automatic adjustment rules for the choice of the penalty parameter and make use of an approximated direction as derivative of the merit function so that only first-order derivatives of the objective and constraint functions are used.     

A hybrid algorithm for nonlinear minimax problems

In this paper, a hybrid algorithm for solving finite minimax problem is presented. In the algorithm, we combine the trust-region methods with the line-search methods and curve-search methods. By means of this hybrid technique, the algorithm, according to the specific situation at each iteration, can adaptively performs the trust-region step, line-search step or curve-search step, so as to avoid possibly solving the trust-region subproblems many times, and make better use of the advantages of different methods. Moreover, we use second-order correction step to circumvent the difficulties of the Maratos effect occurred in the nonsmooth optimization. Under mild conditions, we prove that the new algorithm is of global convergence and locally superlinear convergence. The preliminary experiments show that the new algorithm performs efficiently.     

First-and second-order optimality conditions for mathematical programs with vanishing constraints

We consider a special class of optimization problems that we call Mathematical Programs with Vanishing Constraints, MPVC for short, which serves as a unified framework for several applications in structural and topology optimization. Since an MPVC most often violates stronger standard constraint qualification, first-order necessary optimality conditions, weaker than the standard KKT-conditions, were recently investigated in depth. This paper enlarges the set of optimality criteria by stating first-order sufficient and second-order necessary and sufficient optimality conditions for MPVCs. Dedicated to Jiří V. Outrata on the occasion of his 60th birthday. This research was partially supported by the DFG (Deutsche Forschungsgemeinschaft) under grant KA1296/15-1.     

一个新的带线性搜索的信赖域算法

本文对于无约束最优化问题提出了一个新的信赖域方法。在该算法中采用的是线性模型，并且当试探步不成功的时候，采用线性搜索，从而减少了计算量。文中证明了在适当的条件下算法的全局收敛性。     

Globally solving nonconvex quadratic programming problems via completely positive programming

Nonconvex quadratic programming (QP) is an NP-hard problem that optimizes a general quadratic function over linear constraints. This paper introduces a new global optimization algorithm for this problem, which combines two ideas from the literature—finite branching based on the first-order KKT conditions and polyhedral-semidefinite relaxations of completely positive (or copositive) programs. Through a series of computational experiments comparing the new algorithm with existing codes on a diverse set of test instances, we demonstrate that the new algorithm is an attractive method for globally solving nonconvex QP.