Search

In deep learning, asynchronous parallel stochastic gradient descent (APSGD) is a broadly used algorithm to speed up the training process. In asynchronous system, the time delay of stale gradients in asynchronous algorithms is generally proportional to the total number of workers. When the number of workers is too large, the time delay will bring additional deviation from the accurate gradient due to delayed gradients and may cause a negative influence on the convergence speed of the algorithm. One may ask: How many workers can be used at most to achieve both the convergence and the speedup? In this paper, we consider the asynchronous training problem with the non-convex case. We theoretically study this problem to find an approximating second-order stationary point using asynchronous algorithms in non-convex optimization and investigate the behaviors of APSGD near-saddle points. This work gives the first theoretical guarantee to find an approximating second-order stationary point in asynchronous algorithms and a provable upper bound for the time delay. The techniques we provide can be generalized to analyze other types of asynchronous algorithms to understand the behaviors of asynchronous algorithms in distributed asynchronous parallel training. [ABSTRACT FROM AUTHOR]

Nowadays, large part of the technical knowledge associated with collapses of slabs is based on past failures of bridges, floors, flat roofs and balconies. Collapse mechanisms tend to often differ from each other due to unique features which make it difficult to derive a generalised technique that can predict the right mechanism. This paper proposes a novel algorithm for tackling the problem of detection of collapse mechanisms, which is part of a pseudo-lower bound method for assessing concrete slabs in bridges and buildings. The problem is generalised to a combinatorial one, and the solution is based on a set of well-known combinatorial optimization algorithms. The proposed approach enables an identification of the domain of existence of yield-lines potentially leading to collapse. The output provides an estimation of a hampered domain of feasible yield-lines through which engineers can quickly identify zones of the slab and directions in which yield-lines leading to collapse are more likely to occur. Numerical applications of the algorithm are presented herein. [ABSTRACT FROM AUTHOR]

During the past few decades, multi-agent optimization problems have drawn increased attention from the research community. When multiple objective functions are present among agents, many works optimize the sum of these objective functions. However, this formulation implies a decision regarding the relative importance of each objective: optimizing the sum is a special case of a multi-objective problem in which all objectives are prioritized equally. To enable more general prioritizations, we present a distributed optimization algorithm that explores Pareto optimal solutions for non-homogeneously weighted sums of objective functions. This exploration is performed through a new rule based on agents' priorities that generates edge weights in agents' communication graph. These weights determine how agents update their decision variables with information received from other agents in the network. Agents initially disagree on the priorities of objective functions, though they are driven to agree upon them as they optimize. As a result, agents still reach a common solution. The network-level weight matrix is (non-doubly) stochastic, contrasting with many works on the subject in which the network-level weight matrix is doubly-stochastic. New theoretical analyses are therefore developed to ensure convergence of the proposed algorithm. This paper provides a gradient-based optimization algorithm, proof of convergence to solutions, and convergence rates of the proposed algorithm. It is shown that agents' initial priorities influence the convergence rate of the proposed algorithm and that these initial choices affect its long-run behavior. Numerical results performed with different numbers of agents illustrate the performance and effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Decentralized algorithms solve multi-agent problems over a connected network, where the information can only be exchanged with the accessible neighbors. Though there exist several decentralized optimization algorithms, there are still gaps in convergence conditions and rates between decentralized and centralized algorithms. In this paper, we fill some gaps by considering two decentralized algorithms: EXTRA and NIDS. They both converge linearly with strongly convex objective functions. We will answer two questions regarding them. What are the optimal upper bounds for their stepsizes? Do decentralized algorithms require more properties on the functions for linear convergence than centralized ones? More specifically, we relax the required conditions for linear convergence of both algorithms. For EXTRA, we show that the stepsize is comparable to that of centralized algorithms. For NIDS, the upper bound of the stepsize is shown to be exactly the same as the centralized ones. In addition, we relax the requirement for the objective functions and the mixing matrices. We provide the linear convergence results for both algorithms under the weakest conditions. [ABSTRACT FROM AUTHOR]

In this paper, we provide an algorithm for solving constrained composite primal-dual monotone inclusions, i.e., monotone inclusions in which a priori information on primal-dual solutions is represented via closed and convex sets. The proposed algorithm incorporates a projection step onto the a priori information sets and generalizes methods proposed in the literature for solving monotone inclusions. Moreover, under the presence of strong monotonicity, we derive an accelerated scheme inspired on the primal-dual algorithm applied to the more general context of constrained monotone inclusions. In the particular case of convex optimization, our algorithm generalizes several primal-dual optimization methods by allowing a priori information on solutions. In addition, we provide an accelerated scheme under strong convexity. An application of our approach with a priori information is constrained convex optimization problems, in which available primal-dual methods impose constraints via Lagrange multiplier updates, usually leading to slow algorithms with unfeasible primal iterates. The proposed modification forces primal iterates to satisfy a selection of constraints onto which we can project, obtaining a faster method as numerical examples exhibit. The obtained results extend and improve several results in the literature. [ABSTRACT FROM AUTHOR]

Adaptive regularized framework using cubics has emerged as an alternative to line-search and trust-region algorithms for smooth nonconvex optimization, with an optimal complexity among second-order methods. In this paper, we propose and analyze the use of an iteration dependent scaled norm in the adaptive regularized framework using cubics. Within such a scaled norm, the obtained method behaves as a line-search algorithm along the quasi-Newton direction with a special backtracking strategy. Under appropriate assumptions, the new algorithm enjoys the same convergence and complexity properties as adaptive regularized algorithm using cubics. The complexity for finding an approximate first-order stationary point can be improved to be optimal whenever a second-order version of the proposed algorithm is regarded. In a similar way, using the same scaled norm to define the trust-region neighborhood, we show that the trust-region algorithm behaves as a line-search algorithm. The good potential of the obtained algorithms is shown on a set of large-scale optimization problems. [ABSTRACT FROM AUTHOR]

Forward-backward and Douglas-Rachford splitting are methods for structured nonsmooth optimization. With the aim to use smooth optimization techniques for nonsmooth problems, the forward-backward and Douglas-Rachford envelopes where recently proposed. Under specific problem assumptions, these envelope functions have favorable smoothness and convexity properties and their stationary points coincide with the fixed-points of the underlying algorithm operators. This allows for solving such nonsmooth optimization problems by minimizing the corresponding smooth convex envelope function. In this paper, we present a general envelope function that unifies and generalizes existing ones. We provide properties of the general envelope function that sharpen corresponding known results for the special cases. We also present a new interpretation of the underlying methods as being majorization-minimization algorithms applied to their respective envelope functions. [ABSTRACT FROM AUTHOR]

First-order methods with momentum, such as Nesterov’s fast gradient method, are very useful for convex optimization problems, but can exhibit undesirable oscillations yielding slow convergence rates for some applications. An adaptive restarting scheme can improve the convergence rate of the fast gradient method, when the parameter of a strongly convex cost function is unknown or when the iterates of the algorithm enter a locally strongly convex region. Recently, we introduced the optimized gradient method, a first-order algorithm that has an inexpensive per-iteration computational cost similar to that of the fast gradient method, yet has a worst-case cost function rate that is twice faster than that of the fast gradient method and that is optimal for large-dimensional smooth convex problems. Building upon the success of accelerating the fast gradient method using adaptive restart, this paper investigates similar heuristic acceleration of the optimized gradient method. We first derive a new first-order method that resembles the optimized gradient method for strongly convex quadratic problems with known function parameters, yielding a linear convergence rate that is faster than that of the analogous version of the fast gradient method. We then provide a heuristic analysis and numerical experiments that illustrate that adaptive restart can accelerate the convergence of the optimized gradient method. Numerical results also illustrate that adaptive restart is helpful for a proximal version of the optimized gradient method for nonsmooth composite convex functions. [ABSTRACT FROM AUTHOR]

In this paper, the first two terms on the right-hand side of the Broyden-Fletcher-Goldfarb-Shanno update are scaled with a positive parameter, while the third one is also scaled with another positive parameter. These scaling parameters are determined by minimizing the measure function introduced by Byrd and Nocedal (SIAM J Numer Anal 26:727-739, 1989). The obtained algorithm is close to the algorithm based on clustering the eigenvalues of the Broyden-Fletcher-Goldfarb-Shanno approximation of the Hessian and on shifting its large eigenvalues to the left, but it is not superior to it. Under classical assumptions, the convergence is proved by using the trace and the determinant of the iteration matrix. By using a set of 80 unconstrained optimization test problems, it is proved that the algorithm minimizing the measure function of Byrd and Nocedal is more efficient and more robust than some other scaling Broyden-Fletcher-Goldfarb-Shanno algorithms, including the variants of Biggs (J Inst Math Appl 12:337-338, 1973), Yuan (IMA J Numer Anal 11:325-332, 1991), Oren and Luenberger (Manag Sci 20:845-862, 1974) and of Nocedal and Yuan (Math Program 61:19-37, 1993). However, it is less efficient than the algorithms based on clustering the eigenvalues of the iteration matrix and on shifting its large eigenvalues to the left, as shown by Andrei (J Comput Appl Math 332:26-44, 2018, Numer Algorithms 77:413-432, 2018). [ABSTRACT FROM AUTHOR]

In this paper, we study the variational inequalities involving monotone and Lipschitz continuous mapping in Banach spaces. A new and simple iterative method, which combines Halpern’s technique and the subgradient extragradient idea, is given. Under mild and standard assumptions, we establish the strong convergence of our algorithm in a uniformly smooth and convex Banach spaces. We also present a modification of our method using a line-search approach, this enable to obtain strong convergence in real and reflexive Banach spaces, without the prior knowledge of the Lipschitz constant. Numerical experiments illustrate the performances of our new algorithm and provide a comparison with related algorithms. Our results generalize and extend some of the existing works in Hilbert spaces to Banach spaces as well as provide an extension from weak to strong convergence. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to introduce and study the general split equality equilibrium problem and the general split equilibrium problem in Hilbert spaces. In order to solve these problems, a new simultaneous iterative algorithm is proposed and several strong convergence theorems for the sequences generated by the algorithm are proved. As applications, we utilize our results to study the general split equality optimization problem and the general split optimization problem. The results presented in the paper extend and improve some recent results. [ABSTRACT FROM AUTHOR]

In 1937, the 16-years-old Hungarian mathematician Endre Weiszfeld, in a seminal paper, devised a method for solving the Fermat-Weber location problem-a problem whose origins can be traced back to the seventeenth century. Weiszfeld's method stirred up an enormous amount of research in the optimization and location communities, and is also being discussed and used till these days. In this paper, we review both the past and the ongoing research on Weiszfed's method. The existing results are presented in a self-contained and concise manner-some are derived by new and simplified techniques. We also establish two new results using modern tools of optimization. First, we establish a non-asymptotic sublinear rate of convergence of Weiszfeld's method, and second, using an exact smoothing technique, we present a modification of the method with a proven better rate of convergence. [ABSTRACT FROM AUTHOR]

This paper presents a primal method for finding the minimum L-infinity solution to under-determined linear systems of equations. The method is a two-phase method. Line search is performed at both phases. We establish a condition for a direction to be descent. The convergence proof of the method is shown. Expedient numerical schemes can be used whenever appropriate. Results are presented, which show the superiority of the method over some well-known methods. [ABSTRACT FROM AUTHOR]

A symmetric tensor is called copositive if it generates a multivariate form taking nonnegative values over the nonnegative orthant. Copositive tensors have found important applications in polynomial optimization, tensor complementarity problems and vacuum stability of a general scalar potential. In this paper, we consider copositivity detection of tensors from both theoretical and computational points of view. After giving several necessary conditions for copositive tensors, we propose several new criteria for copositive tensors based on the representation of the multivariate form in barycentric coordinates with respect to the standard simplex and simplicial partitions. It is verified that, as the partition gets finer and finer, the concerned conditions eventually capture all strictly copositive tensors. Based on the obtained theoretical results with the help of simplicial partitions, we propose a numerical method to judge whether a tensor is copositive or not. The preliminary numerical results confirm our theoretical findings. [ABSTRACT FROM AUTHOR]

A lot of researchers try to use the conditional convexity to develop their solution procedure to locate the optimal solution. However, this paper indicates that the solution procedure to locate the optimal solution based on the conditional convexity has logical shortcomings from a mathematics point of view. So, the main purpose of this paper will provide the alternative approach to develop a recursive algorithm for determining the optimal solution without using the conditional convexity. Finally, this paper improves many existing articles. [ABSTRACT FROM AUTHOR]

We examine computational solutions to all of the geometric programming problems published in a recent paper in the Journal of Optimization Theory and Applications. We employed three implementations of published algorithms interchangeably to obtain 'perfect duality' for all of these problems. Perfect duality is taken to mean that a computed solution of an optimization problem achieves two properties: (1) primal and dual feasibility and (2) equality of primal and dual objective function values, all within the accuracy of the machine employed. Perfect duality was introduced by Duffin (Math Program 4:125-143,1973). When primal and dual objective values differ, we say there is a duality gap. [ABSTRACT FROM AUTHOR]

Finding complete subgraphs in a graph, that is, cliques, is a key problem and has many real-world applications, e.g., finding communities in social networks, clustering gene expression data, modeling ecological niches in food webs, and describing chemicals in a substance. The problem of finding the largest clique in a graph is a well-known difficult combinatorial optimization problem and is called the maximum clique problem. In this paper, we formulate a very convenient continuous characterization of the maximum clique problem based on the symmetric rank-one non-negative approximation of a given matrix and build a one-to-one correspondence between stationary points of our formulation and cliques of a given graph. In particular, we show that the local (resp. global) minima of the continuous problem corresponds to the maximal (resp. maximum) cliques of the given graph. We also propose a new and efficient clique finding algorithm based on our continuous formulation and test it on the DIMACS data sets to show that the new algorithm outperforms other existing algorithms based on the Motzkin-Straus formulation and can compete with a sophisticated combinatorial heuristic. [ABSTRACT FROM AUTHOR]

In this paper, we describe a two-stage method for solving optimization problems with bound constraints. It combines the active-set estimate described in Facchinei and Lucidi (J Optim Theory Appl 85(2):265-289, 1995) with a modification of the non-monotone line search framework recently proposed in De Santis et al. (Comput Optim Appl 53(2):395-423, 2012). In the first stage, the algorithm exploits a property of the active-set estimate that ensures a significant reduction in the objective function when setting to the bounds all those variables estimated active. In the second stage, a truncated-Newton strategy is used in the subspace of the variables estimated non-active. In order to properly combine the two phases, a proximity check is included in the scheme. This new tool, together with the other theoretical features of the two stages, enables us to prove global convergence. Furthermore, under additional standard assumptions, we can show that the algorithm converges at a superlinear rate. Promising experimental results demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

We deal with chance constrained problems with differentiable nonlinear random functions and discrete distribution. We allow nonconvex functions both in the constraints and in the objective. We reformulate the problem as a mixed-integer nonlinear program and relax the integer variables into continuous ones. We approach the relaxed problem as a mathematical problem with complementarity constraints and regularize it by enlarging the set of feasible solutions. For all considered problems, we derive necessary optimality conditions based on Fréchet objects corresponding to strong stationarity. We discuss relations between stationary points and minima. We propose two iterative algorithms for finding a stationary point of the original problem. The first is based on the relaxed reformulation, while the second one employs its regularized version. Under validity of a constraint qualification, we show that the stationary points of the regularized problem converge to a stationary point of the relaxed reformulation and under additional condition it is even a stationary point of the original problem. We conclude the paper by a numerical example. [ABSTRACT FROM AUTHOR]

This paper investigates scaling a modified limited-memory algorithm to solve unconstrained optimization problems. The basic idea was to combine the damped techniques for the limited-memory update and the technique of equilibrating the inverse Hessian matrix. Enhanced curvature information about the objective function is stored in the form of a diagonal matrix and plays the dual roles of providing an initial matrix and equilibrating for damped limited-memory iterations. Numerical experiments indicated that the new algorithm is very effective. [ABSTRACT FROM AUTHOR]

Ariyawansa and Zhu have proposed a new class of optimization problems termed stochastic semidefinite programs to handle data uncertainty in applications leading to (deterministic) semidefinite programs. For stochastic semidefinite programs with finite event space, they have also derived a class of volumetric barrier decomposition algorithms, and proved polynomial complexity of certain members of the class. In this paper, we consider homogeneous self-dual algorithms for stochastic semidefinite programs with finite event space. We show how the structure in such problems may be exploited so that the algorithms developed in this paper have complexity similar to those of the decomposition algorithms mentioned above. [ABSTRACT FROM AUTHOR]

In the first part of this paper series, a new solver, called HDDP, was presented for solving constrained, nonlinear optimal control problems. In the present paper, the algorithm is extended to include practical safeguards to enhance robustness, and four illustrative examples are used to evaluate the main algorithm and some variants. The experiments involve both academic and applied problems to show that HDDP is capable of solving a wide class of constrained, nonlinear optimization problems. First, the algorithm is verified to converge in a single iteration on a simple multi-phase quadratic problem with trivial dynamics. Successively, more complicated constrained optimal control problems are then solved demonstrating robust solutions to problems with as many as 7 states, 25 phases, 258 stages, 458 constraints, and 924 total control variables. The competitiveness of HDDP, with respect to general-purpose, state-of-the-art NLP solvers, is also demonstrated. [ABSTRACT FROM AUTHOR]

In this paper we develop new applications of variational analysis and generalized differentiation to the following optimization problem and its specifications: given n closed subsets of a Banach space, find such a point for which the sum of its distances to these sets is minimal. This problem can be viewed as an extension of the celebrated Fermat-Torricelli problem: given three points on the plane, find another point that minimizes the sum of its distances to the designated points. The generalized Fermat-Torricelli problem formulated and studied in this paper is of undoubted mathematical interest and is promising for various applications including those frequently arising in location science, optimal networks, etc. Based on advanced tools and recent results of variational analysis and generalized differentiation, we derive necessary as well as necessary and sufficient optimality conditions for the extended version of the Fermat-Torricelli problem under consideration, which allow us to completely solve it in some important settings. Furthermore, we develop and justify a numerical algorithm of the subgradient type to find optimal solutions in convex settings and provide its numerical implementations. [ABSTRACT FROM AUTHOR]

In this paper, we study the link between a Chance-Constrained optimization Problem (CCP) and its sample counterpart (SP). SP has a finite number, say N, of sampled constraints. Further, some of these sampled constraints, say k, are discarded, and the final solution is indicated by $x^{\ast}_{N,k}$. Extending previous results on the feasibility of sample convex optimization programs, we establish the feasibility of $x^{\ast}_{N,k}$ for the initial CCP problem. Constraints removal allows one to improve the cost function at the price of a decreased feasibility. The cost improvement can be inspected directly from the optimization result, while the theory here developed permits to keep control on the other side of the coin, the feasibility of the obtained solution. In this way, trading feasibility for performance is put on solid mathematical grounds in this paper. The feasibility result here obtained applies to a vast class of chance-constrained optimization problems, and has the distinctive feature that it holds true irrespective of the algorithm used to discard k constraints in the SP problem. For constraints discarding, one can thus, e.g., resort to one of the many methods introduced in the literature to solve chance-constrained problems with discrete distribution, or even use a greedy algorithm, which is computationally very low-demanding, and the feasibility result remains intact. We further prove that, if constraints in the SP problem are optimally removed-i.e., one deletes those constraints leading to the largest possible cost improvement-, then a precise optimality link to the original chance-constrained problem CCP in addition holds. [ABSTRACT FROM AUTHOR]

This paper presents a three-stage optimization algorithm for solving two-stage deviation robust decision making problems under uncertainty. The structure of the first-stage problem is a mixed integer linear program and the structure of the second-stage problem is a linear program. Each uncertain model parameter can independently take its value from a real compact interval with unknown probability distribution. The algorithm coordinates three mathematical programming formulations to iteratively solve the overall problem. This paper provides the application of the algorithm on the robust facility location problem and a counterexample illustrating the insufficiency of the solution obtained by considering only a finite number of scenarios generated by the endpoints of all intervals. [ABSTRACT FROM AUTHOR]

This paper deals with optimal control problems described by higher index DAEs. We introduce a class of these problems which can be transformed to index one control problems. For this class of higher index DAEs, we derive first-order approximations and adjoint equations for the functionals defining the problem. These adjoint equations are then used to state, in the accompanying paper, the necessary optimality conditions in the form of a weak maximum principle. The constructive way used to prove these optimality conditions leads to globally convergent algorithms for control problems with state constraints and defined by higher index DAEs. [ABSTRACT FROM AUTHOR]

This paper focuses on a class of discrete-time interconnected pendulumlike systems. Sufficient conditions for the global convergence of systems with both structured and unstructured uncertainties in its linear part are established in terms of linear matrix inequalities (LMIs). In the traditional decentralized control of large scale systems, the effects of interconnections were seldom studied. In this paper, a square matrix specifying the interconnecting structure is introduced in order to discuss the effects of nonlinear interconnections. It is shown that the global convergence of the whole interconnected system can be achieved by designing an appropriate interconnection matrix. In order to solve the nonlinear matrix inequalities (NMIs) arising in the synthesis problem, a global optimization algorithm is presented which can be used to handle a class of NMI problems. An illustrative example is given to demonstrate the applicability and validity of the main results and the presented algorithm. [ABSTRACT FROM AUTHOR]

The paper discusses several versions of the method of shortest residuals, a specific variant of the conjugate gradient algorithm, first introduced by Lemaréchal and Wolfe and discussed by Hestenes in a quadratic case. In the paper we analyze the global convergence of the versions considered. Numerical comparison of these versions of the method of shortest residuals and an implementation of a standard Polak–Ribière conjugate gradient algorithm is also provided. It supports the claim that the method of shortest residuals is a viable technique, competitive to other conjugate gradient algorithms. [ABSTRACT FROM AUTHOR]

This paper proposes several globally convergent geometric optimization algorithms on Riemannian manifolds, which extend some existing geometric optimization techniques. Since any set of smooth constraints in the Euclidean space Rn (corresponding to constrained optimization) and the Rn space itself (corresponding to unconstrained optimization) are both special Riemannian manifolds, and since these algorithms are developed on general Riemannian manifolds, the techniques discussed in this paper provide a uniform framework for constrained and unconstrained optimization problems. Unlike some earlier works, the new algorithms have less restrictions in both convergence results and in practice. For example, global minimization in the one-dimensional search is not required. All the algorithms addressed in this paper are globally convergent. For some special Riemannian manifold other than Rn, the newalgorithms are very efficient. Convergence rates are obtained. Applications are discussed. [ABSTRACT FROM AUTHOR]

In this paper, a new sequential penalty algorithm, based on the L[sub ∞] exact penalty function, is proposed for a general nonlinear constrained optimization problem. The algorithm has the following characteristics: it can start from an arbitrary initial point; the feasibility of the subproblem is guaranteed; the penalty parameter is adjusted automatically; global convergence without any regularity assumption is proved. The update formula of the penalty parameter is new. It is proved that the algorithm proposed in this paper behaves equivalently to the standard SQP method after sufficiently many iterations. Hence, the local convergence results of the standard SQP method can be applied to this algorithm. Preliminary numerical experiments show the efficiency and stability of the algorithm. [ABSTRACT FROM AUTHOR]

This paper focuses on solving a class of multi-criteria optimization with the difference of convex objective functions. Proximal point algorithms, extensively studied for scalar optimization, are extended to our setting. We show that the proposed algorithms are well posed and globally convergent to a critical point. For an application, the new methods are used to a multi-criteria model arising in portfolio optimization. The numerical results show the efficiency of our methods. [ABSTRACT FROM AUTHOR]

In this paper, sizing of the thickness of a cylindrical shell subject to a stochastic force is considered. The variational principle of stochastic partial differential equations (PDEs) is applied to derive the necessary optimality conditions. The goal is to determine the optimal thickness of a cylindrical shell such that subject to a stochastic force it does not deform, although, because of the elasticity of a cylindrical shell, occasionally small deformations that do not destroy the structure are allowable. The sizing problem under a stochastic force is considered via a one-dimensional stochastic PDE-constrained optimization problem. Test examples are solved using a self-adjoint gradient algorithm. [ABSTRACT FROM AUTHOR]

In the present paper, we study the finite termination of sequences generated by inexact proximal point algorithms for finding zeroes of a maximal monotone (set-valued) operator $$T$$ on a Hilbert space. Under some mild conditions, we get that a sequence generated by inexact proximal point algorithm stops after a finite number of iterations. Our results extend the corresponding results in Rockafellar (SIAM J Control Optim 14:877-898, ). In particular, for optimization problems, our results improve corresponding results in Ferris (Math Progr 50:359-366, ). As applications, we obtain finite termination of projected gradient method. [ABSTRACT FROM AUTHOR]

In this paper, we introduce two primal-dual active-set methods for solving large-scale constrained optimization problems. The first method minimizes a sequence of primal-dual augmented Lagrangian functions subject to bounds on the primal variables and artificial bounds on the dual variables. The basic structure is similar to the well-known optimization package Lancelot (Conn, et al. in SIAM J Numer Anal 28:545-572, ), which uses the traditional primal augmented Lagrangian function. Like Lancelot, our algorithm may use gradient projection-based methods enhanced by subspace acceleration techniques to solve each subproblem and therefore may be implemented matrix-free. The artificial bounds on the dual variables are a unique feature of our method and serve as a form of dual regularization. Our second algorithm is a two-phase method. The first phase computes iterates using our primal-dual augmented Lagrangian algorithm, which benefits from using cheap gradient projections and matrix-free linear CG calculations. The final iterate produced during this phase is then used as input for phase two, which is a stabilized sequential quadratic programming method (Gill and Robinson in SIAM J Opt 1-45, ). Obtaining superlinear local convergence under weak assumptions is an important benefit of the transition to a stabilized sequential quadratic programming algorithm. Interestingly, the bound-constrained subproblem used in phase one is equivalent to the stabilized subproblem used in phase two under certain assumptions. This fact makes our choice of algorithms a natural one. [ABSTRACT FROM AUTHOR]

Rollout algorithms have demonstrated excellent performance on a variety of dynamic and discrete optimization problems. Interpreted as an approximate dynamic programming algorithm, a rollout algorithm estimates the value-to-go at each decision stage by simulating future events while following a heuristic policy, referred to as the base policy. While in many cases rollout algorithms are guaranteed to perform as well as their base policies, there have been few theoretical results showing additional improvement in performance. In this paper, we perform a probabilistic analysis of the subset sum problem and 0-1 knapsack problem, giving theoretical evidence that rollout algorithms perform strictly better than their base policies. Using a stochastic model from the existing literature, we analyze two rollout methods that we refer to as the exhaustive rollout and consecutive rollout, both of which employ a simple greedy base policy. We prove that both methods yield a significant improvement in expected performance after a single iteration of the rollout algorithm, relative to the base policy. [ABSTRACT FROM AUTHOR]

Constrained global optimization problems can be tackled by using exact penalty approaches. In a preceding paper, we proposed an exact penalty algorithm for constrained problems which combines an unconstrained global minimization technique for minimizing a non-differentiable exact penalty function for given values of the penalty parameter, and an automatic updating of the penalty parameter that occurs only a finite number of times. However, in the updating of the penalty parameter, the method requires the evaluation of the derivatives of the problem functions. In this work, we show that an efficient updating can be implemented also without using the problem derivatives, in this way making the approach suitable for globally solving constrained problems where the derivatives are not available. In the algorithm, any efficient derivative-free unconstrained global minimization technique can be used. In particular, we adopt an improved version of the DIRECT algorithm. In addition, to improve the performances, the approach is enriched by resorting to derivative-free local searches, in a multistart framework. In this context, we prove that, under suitable assumptions, for every global minimum point there exists a neighborhood of attraction for the local search. An extensive numerical experience is reported. [ABSTRACT FROM AUTHOR]

In this paper, a new nonsmooth trust region algorithm is proposed for solving unconstrained minimization problems with locally Lipschitz objective functions. At first, by using an approximation of the steepest descent direction, a local model is presented for locally Lipschitz functions. More precisely, in the quadratic model of classical trust region methods, the gradient vector is replaced by an approximation of the steepest descent direction. We then apply one of the efficient approaches of classical trust region methods in order to solve the obtained model. Using the BFGS updating formula for the Hessian approximation of the model, we show that the proposed algorithm is convergent under some mild and standard conditions on the objective function. Finally, the presented algorithm is implemented in the MATLAB environment and applied on some nonsmooth test problems. [ABSTRACT FROM AUTHOR]

Clusterwise linear regression consists of finding a number of linear regression functions each approximating a subset of the data. In this paper, the clusterwise linear regression problem is formulated as a nonsmooth nonconvex optimization problem and an algorithm based on an incremental approach and on the discrete gradient method of nonsmooth optimization is designed to solve it. This algorithm incrementally divides the whole dataset into groups which can be easily approximated by one linear regression function. A special procedure is introduced to generate good starting points for solving global optimization problems at each iteration of the incremental algorithm. The algorithm is compared with the multi-start Späth and the incremental algorithms on several publicly available datasets for regression analysis. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a parameter-dependent class of Krylov-based methods, namely Conjugate Directions $$(CD)$$ , for the solution of symmetric linear systems. We give evidence that, in our proposal, we generate sequences of conjugate directions, extending some properties of the standard conjugate gradient (CG) method, in order to preserve the conjugacy. For specific values of the parameters in our framework, we obtain schemes equivalent to both the CG and the scaled-CG. We also prove the finite convergence of the algorithms in $$CD$$ , and we provide some error analysis. Finally, preconditioning is introduced for $$CD$$ , and we show that standard error bounds for the preconditioned CG also hold for the preconditioned $$CD$$ . [ABSTRACT FROM AUTHOR]

Methods which do not use any derivative information are becoming popular among researchers, since they allow to solve many real-world engineering problems. Such problems are frequently characterized by the presence of discrete variables, which can further complicate the optimization process. In this paper, we propose derivative-free algorithms for solving continuously differentiable Mixed Integer NonLinear Programming problems with general nonlinear constraints and explicit handling of bound constraints on the problem variables. We use an exterior penalty approach to handle the general nonlinear constraints and a local search approach to take into account the presence of discrete variables. We show that the proposed algorithms globally converge to points satisfying different necessary optimality conditions. We report a computational experience and a comparison with a well-known derivative-free optimization software package, i.e., NOMAD, on a set of test problems. Furthermore, we employ the proposed methods and NOMAD to solve a real problem concerning the optimal design of an industrial electric motor. This allows to show that the method converging to the better extended stationary points obtains the best solution also from an applicative point of view. [ABSTRACT FROM AUTHOR]

In this paper, we suggest another accelerated conjugate gradient algorithm for which both the descent and the conjugacy conditions are guaranteed. The search direction is selected as a linear combination of the gradient and the previous direction. The coefficients in this linear combination are selected in such a way that both the descent and the conjugacy condition are satisfied at every iteration. The algorithm introduces the modified Wolfe line search, in which the parameter in the second Wolfe condition is modified at every iteration. It is shown that both for uniformly convex functions and for general nonlinear functions, the algorithm with strong Wolfe line search generates directions bounded away from infinity. The algorithm uses an acceleration scheme modifying the step length in such a manner as to improve the reduction of the function values along the iterations. Numerical comparisons with some conjugate gradient algorithms using a set of 75 unconstrained optimization problems with different dimensions show that the computational scheme outperforms the known conjugate gradient algorithms like Hestenes and Stiefel; Polak, Ribière and Polyak; Dai and Yuan or the hybrid Dai and Yuan; CG_DESCENT with Wolfe line search, as well as the quasi-Newton L-BFGS. [ABSTRACT FROM AUTHOR]

In this paper, as an extension of a previous study, an improved approximation for the Gaussian Q-function is presented. The nonlinear least squares algorithm is employed to optimize the coefficients of the proposed approximation. The accuracy of the presented approximation is evaluated using extensive computer simulations. Results show that the proposed approximation has superior accuracy in high arguments' region when compared to the performance of other approaches introduced in the literature. [ABSTRACT FROM AUTHOR]

In this paper, a new global optimization algorithm is developed, which is named Particle Swarm Optimization combined with Particle Generator (PSO-PG). Based on a series of comparable numerical experiments, we show that the calculation accuracy of the new algorithm is greatly improved and optimization efficiency is increased as well, in comparison with those of the standard PSO. It is also found that the optimization results obtained from PSO-PG are almost independent of the coefficients adopted in the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we develop models for production planning with coordinated dynamic pricing. The application that motivated this research is manufacturing pricing, where the products are non-perishable assets and can be stored to fulfill the future demands. We assume that the firm does not change the price list very frequently. However, the developed model and its solution strategy have the capability to handle the general case of manufacturing systems with frequent time-varying price lists. We consider a multi-product capacitated setting and introduce a demand-based model, where the demand is a function of the price. The key parts of the model are that the planning horizon is discrete-time multi-period, and backorders are allowed. As a result of this, the problem becomes a nonlinear programming problem with the nonlinearities in both the objective function and some constraints. We develop an algorithm which computes the optimal production and pricing policy on a finite time horizon. We illustrate the application of the algorithm through a detailed numerical example. [ABSTRACT FROM AUTHOR]

In this paper, ellipsoidal estimations are used to track the central path of linear programming. A higher-order interior-point algorithm is devised to search the optimizers along the ellipse. The algorithm is proved to be polynomial with the best complexity bound for all polynomial algorithms and better than the best known bound for higher-order algorithms. [ABSTRACT FROM AUTHOR]

In the conic optimization problems, it is well-known that a positive duality gap may occur, and that solving such a problem is numerically difficult or unstable. For such a case, we propose a facial reduction algorithm to find a primal-dual pair of conic optimization problems having the zero duality gap and the optimal value equal to one of the original primal or dual problems. The conic expansion approach is also known as a method to find such a primal-dual pair, and in this paper we clarify the relationship between our facial reduction algorithm and the conic expansion approach. Our analysis shows that, although they can be regarded as dual to each other, our facial reduction algorithm has ability to produce a finer sequence of faces of the cone including the feasible region. A simple proof of the convergence of our facial reduction algorithm for the conic optimization is presented. We also observe that our facial reduction algorithm has a practical impact by showing numerical experiments for graph partition problems; our facial reduction algorithm in fact enhances the numerical stability in those problems. [ABSTRACT FROM AUTHOR]

In this paper, an improved spectral conjugate gradient algorithm is developed for solving nonconvex unconstrained optimization problems. Different from the existent methods, the spectral and conjugate parameters are chosen such that the obtained search direction is always sufficiently descent as well as being close to the quasi-Newton direction. With these suitable choices, the additional assumption in the method proposed by Andrei on the boundedness of the spectral parameter is removed. Under some mild conditions, global convergence is established. Numerical experiments are employed to demonstrate the efficiency of the algorithm for solving large-scale benchmark test problems, particularly in comparison with the existent state-of-the-art algorithms available in the literature. [ABSTRACT FROM AUTHOR]

Linear Discriminant Analysis (LDA) is one of the most efficient statistical approaches for feature extraction and dimension reduction. The generalized Foley-Sammon transform and the trace ratio model are very important in LDA and have received increasing interest. An efficient iterative method has been proposed for the resulting trace ratio optimization problem, which, under a mild assumption, is proved to enjoy both the local quadratic convergence and the global convergence to the global optimal solution (Zhang, L.-H., Liao, L.-Z., Ng, M.K.: SIAM J. Matrix Anal. Appl. 31:1584, ). The present paper further investigates the convergence behavior of this iterative method under no assumption. In particular, we prove that the iteration converges superlinearly when the mild assumption is removed. All possible limit points are characterized as a special subset of the global optimal solutions. An illustrative numerical example is also presented. [ABSTRACT FROM AUTHOR]

The proximal point algorithm is classical and popular in the community of optimization. In practice, inexact proximal point algorithms which solve the involved proximal subproblems approximately subject to certain inexact criteria are truly implementable. In this paper, we first propose an inexact proximal point algorithm with a new inexact criterion for solving convex minimization, and show its O(1/ k) iteration-complexity. Then we show that this inexact proximal point algorithm is eligible for being accelerated by some influential acceleration schemes proposed by Nesterov. Accordingly, an accelerated inexact proximal point algorithm with an iteration-complexity of O(1/ k) is proposed. [ABSTRACT FROM AUTHOR]

In this paper, we propose and analyze an algorithm that couples the gradient method with a general exterior penalization scheme for constrained or hierarchical minimization of convex functions in Hilbert spaces. We prove that a proper but simple choice of the step sizes and penalization parameters guarantees the convergence of the algorithm to solutions for the optimization problem. We also establish robustness and stability results that account for numerical approximation errors, discuss implementation issues and provide examples in finite and infinite dimension. [ABSTRACT FROM AUTHOR]