Search

In the literature, besides the assumption of strict complementarity, superlinear convergence of implementable polynomial-time interior point algorithms using known search directions, namely, the HKM direction, its dual or the NT direction, to solve semi-definite programs (SDPs) is shown by (i) assuming that the given SDP is nondegenerate and making modifications to these algorithms [Kojima et al. Local convergence of predictor–corrector infeasible-interior-point algorithms for SDPs and SDLCPs, Math. Program. Ser. A 80 (1998), pp. 129–160], or (ii) considering special classes of SDPs, such as the class of linear semi-definite feasibility problems (LSDFPs) and requiring the initial iterate to the algorithm to satisfy certain conditions [Sim, Superlinear convergence of an infeasible predictor–corrector path-following interior point algorithm for a semidefinite linear complementarity problem using the Helmberg–Kojima–Monteiro direction, SIAM J. Optim. 21 (2011), pp. 102–126], [Sim, Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: Polynomial complexity and local convergence, Comput. Optim. Appl. 74 (2019), pp. 583–621]. Otherwise, these algorithms are not easy to implement even though they are shown to have polynomial iteration complexities and superlinear convergence [Luo et al. Superlinear convergence of a symmetric primal–dual path following algorithm for semidefinite programming, SIAM J. Optim. 8 (1998), pp. 59–81]. The conditions in [Sim, Superlinear convergence of an infeasible predictor–corrector path-following interior point algorithm for a semidefinite linear complementarity problem using the Helmberg–Kojima–Monteiro direction, SIAM J. Optim. 21 (2011), pp. 102–126], [Sim, Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: Polynomial complexity and local convergence, Comput. Optim. Appl. 74 (2019), pp. 583–621] that the initial iterate to the algorithm is required to satisfy to have superlinear convergence when solving LSDFPs however are not practical. In this paper, we propose a practical initial iterate to an implementable infeasible interior point algorithm that guarantees superlinear convergence when the algorithm is used to solve the homogeneous feasibility model of an LSDFP. [ABSTRACT FROM AUTHOR]

A continuous location problem in which a firm wants to set up a single new facility in a competitive environment is considered. Other facilities offering the same product or service already exist in the area. Both the location and the quality of the new facility are to be found so as to maximize the profit obtained by the firm. This is a hard-to-solve global optimization problem. An evolutionary algorithm called Universal Evolutionary Global Optimizer (UEGO) seems to be the best procedure to cope with it, but the algorithm needs several hours of CPU time for solving large instances. In this paper, four parallelizations of UEGO are presented. They all are coarse-grain methods which differ in their migratory policies. A computational study is carried out to compare the performance of the parallel algorithms. The results show that one of the parallelizations always gives the best objective function value and has an almost linear speed-up for up to 16 processing elements for large instances. [ABSTRACT FROM AUTHOR]

This paper presents a new heuristic algorithm for solving the single-container loading problem. The algorithm is to formalize human experience formed in the last 1000 years by modern mathematical tools, and to refine it by a new observation. Its key issue is the cavity degree of an action that packs an item into a layer of the container, such that the item is packed as compactly as possible to other items already packed in the same layer. For the 1500 well-known benchmark problems from Bischoff, Ratcliff, and Davies, the new algorithm achieves an average container volume utilization of 89.59% with a reasonable average computing time of 27.78 min. This improves the current best utilization record reported in the literature considerably by 0.62%. Of those 1500, for the 800 strongly heterogeneous problems especially, where other algorithms usually achieved lower utilizations, it achieves an average volume utilization of 89.77%, which breaks the current best record markedly by 2.08%. [ABSTRACT FROM AUTHOR]

Direct search optimization algorithms are becoming an important alternative to well-established gradient based methods. Due to the fact that a single cost function evaluation may take a substantial amount of time, optimization can be a lengthy process. In order to shorten the run time one often resorts to parallel algorithms. Asynchronous algorithms are particularly efficient since they have no synchronization points. This paper is an attempt to establish a convergence theory for a class of such parallel direct search algorithms. The notion of a search direction generator (SDG) is introduced. An algorithmic framework for parallel distributed optimization methods based on SDGs is presented along with the corresponding convergence theory. The theory almost completely decouples the stepsize control from the sufficient descent requirement, which is necessary for the finite termination of the algorithm's inner loop. The proposed framework has several attributes considered very favourable in loosely coupled parallel systems (e.g. clusters of workstations), such as fault tolerance and scalability. The framework is illustrated by optimizing a set of test problems on a cluster of workstations. In all tested cases, a speedup was obtained that increased with the increasing number of workstations. Fault tolerance and scalability of the framework were also demonstrated by removing and adding workstations to the cluster while an optimization run was in progress. [ABSTRACT FROM AUTHOR]

In this paper, by using a so-called fixed steplength strategy, we propose a BFGS method without use of line searches for unconstrained optimization. Under mild conditions, we show the global and superlinear convergence of the proposed method even when the objective function is nonconvex. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new proximity measure function based on the min-max principle, and use its optimality condition as the centering equation in a primal-dual path following algorithm. The basic idea is to create a self-adjusting mechanism in the perturbed equations themselves so as to adaptively tune current search directions according to information gained from the last iterate. Through computing the Netlib test problems and making numerical comparison with Lipsol software package, the efficiency of the proposed algorithm is justified. [ABSTRACT FROM AUTHOR]

It is often important to know more about the characteristics of a mathematical program than the simple information that is returned by a solver. For example, to choose an appropriate solution algorithm, one may need to know something about the convexity of the functions in a nonlinear program, or about which constraints are redundant. For the complex model forms, particularly nonlinear programs and mixed-integer programs, random sampling can discover a great deal of information. This paper describes how to discover interesting characteristics of mathematical programs via sampling, and describes solutions to several difficulties that arise in practice. Several new techniques for discovering characteristics and for improving the accuracy of the characterizations are described. [ABSTRACT FROM AUTHOR]

A nonlinear conjugate gradient algorithm which is a modification of the Dai and Yuan [A nonlinear conjugate gradient method with a strong global convergence property, SIAM J. Optim. 10 (1999), pp. 177-182] conjugate gradient algorithm satisfying a parameterized sufficient descent condition with a parameter δk is proposed. The parameter δk is computed by means of the conjugacy condition, thus an algorithm which is a positive multiplicative modification of the Hestenes and Stiefel [Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards Sec. B 48 (1952), pp. 409-436] algorithm is obtained. The algorithm can be viewed as an adaptive version of the Dai and Liao [New conjugacy conditions and related nonlinear conjugate gradient methods, Appl. Math. Optim. 43 (2001), pp. 87-101] conjugate gradient algorithm. Close to our computational scheme is the conjugate gradient algorithm recently proposed by Hager and Zhang [A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM J. Optim. 16 (2005), pp. 170-192]. Computational results, for a set consisting of 750 unconstrained optimization test problems, show that this new conjugate gradient algorithm substantially outperforms the known conjugate gradient algorithms. [ABSTRACT FROM AUTHOR]

Discrete optimal control problems with variable endpoints and with equality type constraints on the control are considered. We derive first- and second-order necessary optimality conditions, which are meaningful under the assumptions weaker than those previously used in the literature. [ABSTRACT FROM AUTHOR]

We propose a new algorithm for linearly constrained strictly convex problems. This algorithm follows the characterization of saddle points introduced earlier in ref. [Ouorou, A., 2000, A primal-dual algorithm for monotropic programming and its application to network optimization. Computational Optimization and Applications, 15(2), 125-143.], using two different augmented Lagrangian functions defined for the primal problem and its dual. The saddle points may be computed in a variety of ways. We propose a scheme that results in a special implementation of Martinet's proximal algorithm ref. [Martinet, B. 1970, Régularisation d'inéquations variationnelles par approximations successives. Revue Franç'Informatique et de Recherche Opérationnelle, 3, 154-179.]. In the primal space, the resulting algorithm appears as a nonsmooth version of the projection algorithm by Rosen ref. [Rosen, J.B., 1960, The gradient projected method for nonlinear programming, part I: Linear Constraints. Journal of the Society for Industrial and Applied Mathematics, 8, 181-217.]. The dual iterates are generated through an unconstrained subproblem which can be solved efficiently by L-BFGS refs. [Byrd, R., Lu, P., Nocedal, J. and Zhu, C. 1995, A limited memory algorithm for bound constrained optimization. SIAM Journal on Scientific Computation, 16(5), 1190-1208.; Liu, D. and Nocedal, J., 1989, On the limited memory BFGS method for large scale optimization. Mathematical Programming B 45, 503-528.]. We establish convergence with no use of the concept of resolvent of maximal monotone operators. To assess the numerical behaviour of the algorithm, we use some randomly generated quadratic network flow problems and compare it with PPRN, a specialized code for linear and nonlinear cost network flow problems. [ABSTRACT FROM AUTHOR]

A scaled memoryless BFGS preconditioned conjugate gradient algorithm for solving unconstrained optimization problems is presented. The basic idea is to combine the scaled memoryless BFGS method and the preconditioning technique in the frame of the conjugate gradient method. The preconditioner, which is also a scaled memoryless BFGS matrix, is reset when the Beale-Powell restart criterion holds. The parameter scaling the gradient is selected as the spectral gradient. In very mild conditions, it is shown that, for strongly convex functions, the algorithm is globally convergent. Computational results for a set consisting of 750 unconstrained optimization test problems show that this new scaled conjugate gradient algorithm substantially outperforms the known conjugate gradient methods including the spectral conjugate gradient by Birgin and Martínez [Birgin, E. and Martínez, J.M., 2001, A spectral conjugate gradient method for unconstrained optimization. Applied Mathematics and Optimization, 43, 117-128], the conjugate gradient by Polak and Ribière [Polak, E. and Ribière, G., 1969, Note sur la convergence de méthodes de directions conjuguées. Revue Francaise Informat. Reserche Opérationnelle, 16, 35-43], as well as the most recent conjugate gradient method with guaranteed descent by Hager and Zhang [Hager, W.W. and Zhang, H., 2005, A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM Journal on Optimization, 16, 170-192; Hager, W.W. and Zhang, H., 2004, CG-DESCENT, A conjugate gradient method with guaranteed descent ACM Transactions on Mathematical Software, 32, 113-137]. [ABSTRACT FROM AUTHOR]

We develop an iterative method for solving the KKT system of the semi-infinite programming (SIP) problem. At each iteration, we solve the KKT system of a nonlinear programming problem with finite constraints by a semismooth Newton method. The algorithm either terminates at a KKT point of the SIP problem in finitely many iterations or generates an infinite sequence of iterates whose any accumulation point is a KKT point of the problem. We also analyse the convergence rate of the method. Preliminary numerical results are reported. [ABSTRACT FROM AUTHOR]

We consider the problem of discriminating two finite point sets in the n -dimensional space by a finite number of hyperplanes generating a piecewise linear function. If the intersection of these sets is empty, then they can be strictly separated by a max-min of linear functions. An error function is introduced. This function is nonconvex piecewise linear. We discuss an algorithm for its minimization. The results of numerical experiments using some real-world datasets are presented, which show the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

In this article, we consider a particular class of nonlinear mixed variable optimization problems where the structure and the number of variables of the problem depend on the values of some discrete variables. The peculiarity of this class is that, for fixed values of the integer variables, the corresponding continuous optimization problem contains no constraints and a large number of variables. For such a class of problems we propose two minimization algorithms and prove their global convergence properties. [ABSTRACT FROM AUTHOR]

Quadratic approximations to the objective function provide a way of estimating first and second derivatives in iterative algorithms for unconstrained minimization. Therefore, we address the construction of suitable quadratic models Q by interpolating values of the objective function F . On a typical iteration, the objective function is calculated at the point that minimizes the current quadratic model subject to a trust region bound, and we find that these values of F provide good information for the updating of Q , except that a few extra values are needed occasionally to avoid degeneracy. The number of interpolation points and their positions can be controlled adequately by deleting one of the current points to make room for each new one. An algorithm is described that works in this way. It is applied to an optimization calculation that has between 10 and 160 variables. The numerical results suggest that, if m = 2 n + 1, then the number of evaluations of F is only of magnitude n , where m and n are the number of interpolation conditions of each model and the number of variables, respectively. This success is due to the technique that updates Q . It minimizes the Frobenius norm of the change to ∇ 2 Q , subject to the interpolation conditions that have been mentioned. [ABSTRACT FROM AUTHOR]