Search

In this paper, we are concerned with nonlinear minimization problems with second-order cone constraints. A primal-dual interior point method that uses a commutative class of search directions is considered. We propose a new primal-dual merit function by combining the barrier penalty function and the potential function within the framework of the line search strategy, and show the global convergence property of our method. [ABSTRACT FROM AUTHOR]

The classical Remez algorithm was developed for constructing the best polynomial approximations for continuous and discrete functions in an interval [a, b]. In this paper, the classical Remez algorithm is generalized to the problem of linear spline approximation with certain conditions on the spline parameters. Namely, the spline parameters have to be nonnegative and the values of the splines at one of the borders (or both borders) of the approximation intervals may be fixed. This type of constraint occurs in some practical applications, e.g. the problem of taxation tables restoration. The results of the numerical experiments with a Remez-like algorithm developed for this class of conditional optimization problems, are presented. [ABSTRACT FROM AUTHOR]

This paper studies certain Lipschitz properties of the optimal value function of a linear semi-infinite programming problem and its dual problem in the sense of Haar. In this setting, it is already known that the optimal value function of the so-called primal problem was Lipschitz continuous around a given stable solvable problem, when perturbations of all the coefficients are allowed. Recently, a Lipschitz constant, depending only on the nominal problem data, has been computed and, the no duality gap under certain stability conditions ensures moreover that the obtained constant still holds for the dual optimal value function. Our approach here is focused on obtaining Lipschitz constants for both primal and dual optimal value functions under weaker hypothesis of stability, which do not preclude, in all the cases, the existence of duality gap. Now, the allowed perturbations are restricted to the coefficients of the objective function of the corresponding problems. [ABSTRACT FROM AUTHOR]

Primal-dual interior-point methods (IPMs) have shown their power in solving large classes of optimization problems. However, there is still a discrepancy between the practical behavior of these algorithms and their theoretical worst-case complexity results with respect to the update strategies of the dua-lity gap parameter in the algorithm. Recently, this discrepancy was significantly reduced by Peng, J., Roos, C. and Terlaky, T., 2002, Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms (Princeton, NJ: Princeton University Press) who introduced a new family of self-regular (SR)-proximity functions based IPMs. In this paper, based on a class of SR proximities, we propose an adaptive single-step large-update SR-IPM that is very close to what is used in the McIPM software package. At each step, our algorithm always chooses a large-update of the target value adaptively depending on the position of the current iterate. This adaptive choice of the target value is different from the one what is presented in Peng, J., Roos, C. and Terlaky, T., 2002, Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms (Princeton, NJ: Princeton University Press), where the target μ value is reduced by a fix factor when the iterate is sufficiently well centered. An 𝒪( qn ( q +1)/2 q log( n /ℇ)) worst-case iteration bound of the algorithm is established, where q is the barrier degree of the SR-proximity. For q = log n , our algorithm achieves the so far best complexity for large-update IPMs. Email: salahim@math.mcmaster.ca [ABSTRACT FROM AUTHOR]

This paper presents the FOM MATLAB toolbox for solving convex optimization problems using first-order methods. The diverse features of the eight solvers included in the package are illustrated through a collection of examples of different nature. [ABSTRACT FROM AUTHOR]

This paper presents a new optimal window design method with a general window design specification for the passband and stopband. The design problem is formulated as a semi-infinite linear programming problem. With suitable discretizations, an exchange algorithm is employed. The convergence of the proposed algorithm is established. In the formulation, since the stopband is minimized, the method can be employed for the design of very highly optimized windows. [ABSTRACT FROM PUBLISHER]

This paper first proposes a trust region algorithm to obtain a stationary point of unconstrained multiobjective optimisation problem. Under suitable assumptions, the global convergence of the new algorithm is established. We then extend the trust region method to solve the non-smooth multiobjective optimisation problem. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a damped semismooth Newton iterative method for mixed linear complementarity problems. Under appropriate conditions, we prove that the method exhibits monotone and superlinear convergence properties. [ABSTRACT FROM AUTHOR]

We first catalogue several classes of secant updates including the Dennis class, the Davidon class, and the class of all symmetric rank-2 updates. Reflection on the parametric form of this class leads to a maximality property of the Davidon class and to a natural derivation of the Broyden–Fletcher–Goldfarb–Shanno update, analogous to that presented by Fletcher for the Davidon–Fletcher–Powell inverse update. Next, we propose a symmetric rank-1 extension process for classes of updates that allows us to introduce a degree of commonness to the material presented. An application of the symmetric rank-1 extension process to the class of rank-1 secant updates produces the Dennis class, an application to the Dennis class produces the Davidon class, and an application to the Davidon class leaves the Davidon class fixed implying that it is a maximal class. The maximality of the Davidon class, the definition of the symmetric rank-1 extension process, and the demonstration that this extension process can be used to unify an important part of the literature on update classes are the contributions of the paper. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a new adaptive trust region method for unconstrained optimization problems. In the new method, we use the previous and the current iterative information and a new update rule to define the trust region radius at each iterate. The global and superlinear convergence properties of the method are established under reasonable assumptions. Preliminary numerical results show that the new method is efficient and attractive for unconstrained optimization problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider the convex quadratic optimization problem with simultaneous perturbation in the right-hand side of the constraints and the linear term of the objective function with different parameters. The regions with invariant optimal partitions as well as the behaviour of the optimal value function on the regions are investigated. We show that identifying these regions can be done in polynomial time in the output size. An algorithm for identifying all invariancy regions is presented. Some implementation details as well as a numerical example are discussed. [ABSTRACT FROM AUTHOR]

In this paper we present our experience with the optimization of atomic clusters under the binary Lennard-Jones potential. This is a generalization of the single atom type Lennard-Jones model to the case in which atoms of two different types (and 'sizes') interact within the same cluster. This problem has a combinatorial structure which increases complexity and requires strategies to be revised in order to take into account such new aspects. Our approach has been a very effective one: we have been able not only to confirm most putative optima listed in the Cambridge Cluster Database, but also to find 95 improved solutions. [ABSTRACT FROM AUTHOR]

Different types of underestimation strategies are used in deterministic global optimization. In this paper, convexification and underestimation techniques applicable to problems containing signomial functions are studied. Especially, power transformation and exponential transformation (ET) will be considered in greater detail and some new theoretical results regarding the relation between the negative power transformation and the ET are given. The techniques are, furthermore, illustrated through examples and compared with other underestimating methods used in global optimization solvers such as αBB and BARON. [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]

In this paper we propose a filter-trust-region algorithm for solving nonlinear optimization problems with simple bounds. It extends the technique of Gould et al. [Gould, N.I.M. Sainvitu, C. and Toint, Ph.L., 2005, A filter-trust-region method for unconstrained optimization. SIAM Journal on Optimization, 16(2), 341-357.] designed for unconstrained optimization problems. The two main ingredients of the method are a filter-trust-region algorithm and a gradient-projection method. The algorithm is shown to be globally convergent to at least one first-order critical point. Numerical experiments on a large set of problems are also reported. [ABSTRACT FROM AUTHOR]

In this paper, we suggest a new version of the Gauss-Newton method for solving a system of non-linear equations which combines the idea of sharp merit function with the idea of quadratic regularization. For this scheme, we prove general convergence results and, under a natural non-degeneracy assumption, local quadratic convergence. We analyze the behavior of this scheme on a natural problem class for which we get global and local worst-case complexity bounds. The implementation of each step of the scheme can be done by standard convex optimization technique. [ABSTRACT FROM AUTHOR]

In this paper we develop an optimization approach for the study of adverse drug reaction (ADR) problems. This approach is based on drug–reaction relationships represented in the form of a vector of weights, which can be defined as a solution to some global optimization problem. Although it can be used for solving many ADR problems, we concentrate on two of them here: the accurate identification of drugs that are responsible for reactions that have occurred, and drug–drug interactions. Based on drug–reaction relationships, we formulate these problems as an optimization problem. The approach is applied to cardiovascularn-type reactions from the Australian Adverse Drug Reaction Advisory Committee (ADRAC) database. Software based on this approach has been developed and could have beneficial use in prescribing. [ABSTRACT FROM AUTHOR]

We consider optimization problems with equality, inequality, and abstract set constraints. We investigate the relations between various characteristics of the constraint set related to the existence of Lagrange multipliers. For problems with no abstract set constraint, the classical condition of quasiregularity provides the connecting link between the most common constraint qualifications and existence of Lagrange multipliers. In earlier work, we introduced a new and general condition, pseudonormality, that is central within the theory of constraint qualifications, exact penalty functions, and existence of Lagrange multipliers. In this paper, we explore the relations between pseudonormality, quasiregularity, and existence of Lagrange multipliers, and show that, unlike pseudonormality, quasiregularity cannot play the role of a general constraint qualification in the presence of an abstract set constraint. In particular, under a regularity assumption on the abstract constraint set, we show that pseudonormality implies quasiregularity. However, contrary to pseudonormality, quasiregularity does not imply the existence of Lagrange multipliers, except under additional assumptions. [ABSTRACT FROM AUTHOR]

This paper studies some possible combinations of the best features of the quasi-Newton symmetric rank-one (SR1), BFGS and extra updating BFGS algorithms for solving nonlinear unconstrained optimization problems. These combinations depend on switching between the BFGS and SR1 updates so that certain desirable properties are imposed. The presented numerical results show that the proposed switching algorithm outperforms the robust BFGS method. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new incremental constraint projection algorithm for solving variational inequalities, where the underlying function is monotone plus and Lipschitz continuous. The algorithm consists two steps. In the first step, we compute a predictor point. This procedure requires a single random projection onto some setand employs an Armijo-type linesearch along a feasible direction. Then in the second step an iterate is obtained as the random projection of some point onto the setwhich we have used in the first step. The incremental constraint projection algorithm is considered for random selection and for cyclic selection of the samples. Accordingly, this algorithm is named random projection algorithm and cyclic projection algorithm. The method is shown to be globally convergent to a solution of the variational inequality problem in almost sure sense both random projection method and cyclic projection method. We provide some computational experiments and compare the efficiency of random projection method and cyclic projection method with some known algorithms. [ABSTRACT FROM AUTHOR]

In this paper, a modified Polak–Ribi‘ere–Polyak (MPRP) conjugate gradient method for smooth unconstrained optimization is proposed. This method produces at each iteration a descent direction, and this property is independent of the line search adopted. Under standard assumptions, we prove that the MPRP method using strong Wolfe conditions is globally convergent. The results of computational experiments are reported and show the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we study primal–dual first-order methods for a class of cone programming problems. In particular, we first present four natural primal–dual smooth convex minimization reformulations for them and then discuss a first-order method, that is, a variant of Nesterov's smooth (VNS) method [A. Auslender and M. Teboulle,Interior gradient and proximal methods for convex and conic optimization, SIAM J. Optim. 16(3) (2006), pp. 697–725], for solving these reformulations. The associated worst-case major arithmetic operation costs of the VNS method are estimated and compared. We conclude that the VNS method based on the last reformulation generally outperforms the others. Finally, we justify our theoretical prediction on the behaviour of the VNS method by conducting numerical experiments on Dantzig selector, basis pursuit de-noising, MAXCUT SDP relaxation and Lovász capacity problems. [ABSTRACT FROM AUTHOR]

Significant savings can be gained from terminating the optimization of a computationally expensive function well before traditional criteria, such as a maximum budget of evaluations, are satisfied. Early termination is desirable especially for noisy functions, where a solver could potentially proceed indefinitely while seeing changes insignificant relative to the noise. In this paper, we consider general termination tests that can be used in conjunction with any solver's built-in termination criteria. We propose parameterized families of termination tests, analyse their properties, and illustrate how they can employ an estimate of the function's noise level. Using a set of benchmark problems with both stochastic and deterministic noise and a set of derivative-free solvers, we compare the tests and their sensitivities to parameters in terms of both accuracy and efficiency. Recommendations are made for using the proposed tests in practice. [ABSTRACT FROM AUTHOR]

The paper proposes goal-oriented error estimation and mesh refinement for smooth convex optimal control problems with elliptic PDE constraints using the value of the reduced cost functional as quantity of interest. Error representation, hierarchical error estimators, and greedy-style error indicators are derived and compared with their counterparts when using the all-at-once cost functional as quantity of interest. The efficiency of the error estimator and generated meshes is demonstrated on numerical examples. [ABSTRACT FROM AUTHOR]

The Chinese postman problem is a famous and classical problem in graph theory. This paper introduces a new variant of this problem, namely, the time-dependent rural postman problem, which is motivated by applications, involving scheduling with time-dependent processing time. We present an arc-path formulation for the problem with a constraint set that is divided into two parts. The first part is linear and has a strong combinatorial structure, which defines the polytope of the arc-path alternation sequence (APAS), while the second part is nonlinear and is closely related to time-dependent travel time. First, we investigate the facial structure of the APAS polytope and present several facet inequalities. Second, considering the travel and service time functions as piecewise functions, we linearize the nonlinear inequalities and propose several strong, valid inequalities. Finally, we propose a cutting plane algorithm and report numerical results on several randomly generated instances. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a new numerical method to compute approximate and the so-called relaxed pessimistic solutions to mathematical programs with equilibrium constraints (MPECs), where the solution map arising in the equilibrium constraints is not single-valued. This method combines two types of existing codes, a code for derivative-free optimization under box constraints, BFO or BOBYQA, and a method for solving special parametric MPECs from the interactive system UFO. We report on numerical performance in several small-dimensional test problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider an extension of ordinary linear programming (LP) that adds weighted logarithmic barrier terms for some variables. The resulting problem generalizes both LP and the problem of finding the weighted analytic centre of a polytope. We show that the problem has a dual of the same form and give complexity results for several different interior-point algorithms. We obtain an improved complexity result for certain cases by utilizing a combination of the volumetric and logarithmic barriers. As an application, we consider the complexity of solving the Eisenberg–Gale formulation of a Fisher equilibrium problem with linear utility functions. [ABSTRACT FROM PUBLISHER]

The solution of multidimensional Lipschitz optimization problem requires a lot of computing time and memory resources. Parallel OpenMP and MPI versions of branch and bound algorithm with simplicial partitions and Lipschitz bounds were created, investigated and compared in this paper. The efficiency of the developed parallel algorithms is investigated by solving multidimensional test problems for global optimization. [ABSTRACT FROM AUTHOR]

Detection of copositivity plays an important role in combinatorial and quadratic optimization. Recently, an algorithm for copositivity detection by simplicial partition has been proposed. In this paper, we develop an improved depth-first simplicial partition algorithm which reduces memory requirements significantly and therefore enables copositivity checks of much larger matrices - of size up to a few thousands instead of a few hundreds. The algorithm has been investigated experimentally on a number of MaxClique problems as well as on generated random problems. We present numerical results showing that the algorithm is much faster than a recently published linear algebraic algorithm for copositivity detection based on traditional ideas - checking properties of principal sub-matrices. We also show that the algorithm works very well for solving MaxClique problems through copositivity checks. [ABSTRACT FROM AUTHOR]

This paper investigates the linear fractional shortest path problem with time windows. For the specific problem, an elementary path with a minimum cost/time ratio is sought in a directed graph, where two parameters (i.e. cost and time) are associated with each arc and a time window is associated with each node. Indeed, a valid path must satisfy the time window constraints, which are assumed to be of the hard type. Multi-dimensional labelling algorithms are proposed to solve this variant of the classical shortest path problem. Extensive computational tests are carried out on a meaningful number of test problems, with the goal of assessing the behaviour of the proposed approaches. The computational study shows that the introduction of dominance rules and the adoption of a bi-directional search strategy allow the definition of solution approaches that turn out to be very effective in solving the problem under consideration. [ABSTRACT FROM AUTHOR]

'Separable' uncertainty sets have been widely used in robust portfolio selection models (e.g. see [E. Erdoğan, D. Goldfarb, and G. Iyengar, Robust portfolio management, manuscript, Department of Industrial Engineering and Operations Research, Columbia University, New York, 2004; D. Goldfarb and G. Iyengar, Robust portfolio selection problems, Math. Oper. Res. 28 (2003), pp. 1-38; R.H. Tutuncu and M. Koenig, Robust asset allocation, Ann. Oper. Res. 132 (2004), pp. 157-187]). For these uncertainty sets, each type of uncertain parameter (e.g. mean and covariance) has its own uncertainty set. As addressed in [Z. Lu, A new cone programming approach for robust portfolio selection, Tech. Rep., Department of Mathematics, Simon Fraser University, Burnaby, BC, 2006; Z. Lu, A computational study on robust portfolio selection based on a joint ellipsoidal uncertainty set, Math. Program. (2009), DOI: 10.1007/510107-009-0271-z], these 'separable' uncertainty sets typically share two common properties: (1) their actual confidence level, namely, the probability of uncertain parameters falling within the uncertainty set, is unknown, and it can be much higher than the desired one; and (2) they are fully or partially box-type. The associated consequences are that the resulting robust portfolios can be too conservative, and moreover, they are usually highly non-diversified, as observed in the computational experiments conducted in [Z. Lu, A new cone programming approach for robust portfolio selection, Tech. Rep., Department of Mathematics, Simon Fraser University, Burnaby, BC, 2006; Z. Lu, A computational study on robust portfolio selection based on a joint ellipsoidal uncertainty set, Math. Program. (2009), DOI: 10.1007/510107-009-0271-Z; R.H.Tutuncu and M. Koenig, Robust asset allocation, Ann. Oper. Res. 132 (2004), pp. 157-187]. To combat these drawbacks, we consider a factor model for random asset returns. For this model, we introduce a 'joint' ellipsoidal uncertainty set for the model parameters and show that it can be constructed as a confidence region associated with a statistical procedure applied to estimate the model parameters. We further show that the robust maximum risk-adjusted return (RMRAR) problem with this uncertainty set can be reformulated and solved as a cone programming problem. The computational results reported in [Z. Lu, A new cone programming approach for robust portfolio selection, Tech. Rep., Department of Mathematics, Simon Fraser University, Burnaby, BC, 2006; Z. Lu, A computational study on robust portfolio selection based on a joint ellipsoidal uncertainty set, Math. Program. (2009), DOI: 10.1007/510107-009-0271-Z] demonstrate that the robust portfolio determined by the RMRAR model with our 'joint' uncertainty set outperforms that with Goldfarb and Iyengar's 'separable' uncertainty set proposed in the seminal paper [D. Goldfarb and G. Iyengar, Robust portfolio selection problems, Math. Oper. Res. 28 (2003), pp. 1-38] in terms of wealth growth rate and transaction cost; moreover, our robust portfolio is fairly diversified, but Goldfarb and Iyengar's is surprisingly highly non-diversified. [ABSTRACT FROM AUTHOR]

In this paper, we study approximate optimality conditions for the Canonical DC (CDC) optimization problem and their relationships with stopping criteria for a large class of solution algorithms for the problem. In fact, global optimality conditions for CDC are very often restated in terms of a non-convex optimization problem, which has to be solved each time the optimality of a given tentative solution has to be checked. Since this is in principle a costly task, it makes sense to only solve the problem approximately, leading to an inexact stopping criteria and therefore to approximate optimality conditions. In this framework, it is important to study the relationships between the approximation in the stopping criteria and the quality of the solutions that the corresponding approximated optimality conditions may eventually accept as optimal, in order to ensure that a small tolerance in the stopping criteria does not lead to a disproportionally large approximation of the optimal value of the CDC problem. We develop conditions ensuring that this is the case; these turn out to be closely related with the well-known concept of regularity of a CDC problem, actually coinciding with the latter if the reverse-constraint set is a polyhedron. [ABSTRACT FROM AUTHOR]

In this paper, we present new convergence properties of the primal-dual methods based on Rockafellar and Wets's augmented Lagrangian function for inequality constrained global optimization problems. Four different algorithmic strategies are considered to circumvent the boundedness condition of the multipliers in the convergence analysis for basic primal-dual method. We first show that under weaker conditions, the augmented Lagrangian method using safeguarding strategy converges to a global optimal solution of the original problem. The convergence properties of the augmented Lagrangian method using conditional multiplier updating rule is then presented. We also investigate the use of penalty parameter updating criteria and normalization of the multipliers in augmented Lagrangian methods. Finally, we present some preliminary numerical results for the four modified augmented Lagrangian methods. [ABSTRACT FROM AUTHOR]

The focus of this paper is on the analysis and evaluation of a type of parallel strategies applied to the algorithm Advanced Multidimensional Interval analysis Global Optimization (AMIGO). We investigate two parallel versions of AMIGO, called Parallel AMIGO (PAMIGO) algorithm, Global-PAMIGO and Local-PAMIGO. The idea behind our study is that in order to exploit the potential parallelism of algorithms, researchers need to adapt them to the target computer architectures. Our PAMIGO algorithms have been designed for shared memory architectures and are based on a threaded programming model, which is suitable to be run on current personal computers with multicore processors. Our first experimental results show a promising speed-up up to four process units. We analyse the loss of efficiency when the number of process units is greater than four by obtaining a profile of the algorithm executions. Secondly we experiment with the use of a local memory allocator per thread. This increases the efficiency by reducing the number of lock conflicts given by the standard system memory allocator. Our experimental results for both PAMIGO versions, using up to 15 process units, obtain a good performance for hard to solve problems on unicore and multicore processors. It is noteworthy that both versions of PAMIGO obtain a similar performance. Our experiments may be useful for researchers who use parallel B&B algorithms. [ABSTRACT FROM AUTHOR]

Teardrop is an efficient sampling trajectory for acquiring magnetic resonance imaging Data, especially balanced steady state free precession images. In this paper, we present two models for optimizing such trajectories. These are the first models to incorporate motion-insensitivity constraints into a nonraster (also called spiral) sampling trajectory. The first model is nonlinear and very specific to Teardrop. The second model uses sequential second-order cone programming, and is generalizable to other trajectories in two and three dimensions. We present a weak convergence proof for the sequential method. [ABSTRACT FROM AUTHOR]

We describe algorithms for maximum likelihood estimation of Gaussian graphical models with conditional independence constraints. This problem is also known as covariance selection, and it can be expressed as an unconstrained convex optimization problem with a closed-form solution if the underlying graph is chordal. The focus of the paper is on iterative algorithms for covariance selection with nonchordal graphs. We first derive efficient methods for evaluating the gradient and Hessian of the log-likelihood function when the underlying graph is chordal. The algorithms are formulated as simple recursions on a clique tree associated with the graph. We also show that the gradient and Hessian mappings are easily inverted when the underlying graph is chordal. We then exploit these results to obtain efficient implementations of Newton's method and the conjugate gradient method for large nonchordal graphs, by embedding the graph in a chordal graph. [ABSTRACT FROM AUTHOR]

This paper describes a support vector machine-based (SVM) parametric optimization method for semi-supervised classification, called LIAM (for linear hyperplane classifier with a priori metric information). Our method takes advantage of similarity information to leverage the unlabelled data in training SVMs. In addition to the smoothness constraints in existing semi-supervised methods, LIAM incorporates local class similarity constraints, that we empirically show, improved the accuracies in the presence of a few labelled points. We present and discuss a general convex mathematical-programming-based formulation to solve the inductive semi-supervised problem; i.e. our proposed algorithm directly classifies test samples not present when training. This general formulation results in different variants depending on the choice of the norms that are used in the objective function. For example, when using the 1-norm the proposed formulation becomes a linear programming problem that has the advantage of generating sparse solutions depending on a minimal set of the original features (feature selection). On the other hand, one of the proposed formulations results in an unconstrained quadratic problem for which solutions can be obtained by solving a simple system of linear equations, resulting in a fast competitive alternative to state-of-the-art semi-supervised algorithms. Our experiments on public benchmarks indicate that LIAM is at least one order of magnitude faster and at least as or more accurate (in most of the cases) than other state-of-the-art semi-supervised classification methods. [ABSTRACT FROM AUTHOR]

A class of new spectral conjugate gradient methods are proposed in this paper. First, we modify the spectral Perry's conjugate gradient method, which is the best spectral conjugate gradient algorithm SCG by Birgin and Martinez [E.G. Birgin and J.M. Martinez, A spectral conjugate gradient method for unconstrained optimization, Appl. Math. Optim. 43 (2001), 117-128.], such that it possesses sufficient descent property for any (inexact) line search. It is shown that, for strongly convex functions, the method is a global convergent. Further, a global convergence result for nonconvex minimization is established when the line search fulfils the Wolfe line search conditions. Some other spectral conjugate gradient methods with guaranteed descent are presented here. Numerical comparisons are given with both SCG and CG_DESCENT methods using the unconstrained optimization problems in the CUTE library. [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]

The paper extends affine conjugate Newton methods from convex to nonconvex minimization, with particular emphasis on PDE problems originating from compressible hyperelasticity. On the basis of well-known schemes from finite dimensional nonlinear optimization, three different algorithmic variants are worked out in a function space setting, which permits an adaptive multilevel finite element implementation. These algorithms are tested on two well-known 3D test problems and a real-life example from surgical operation planning. [ABSTRACT FROM AUTHOR]

In this paper, we study some well-known cases of nonlinear programming problems, presenting them as instances of inexact or semi-infinite linear programming. The class of problems considered contains, in particular, semi-definite programming, second-order cone programming and special cases of inexact semi-definite programming. Strong duality results for the nonlinear problems studied are obtained via the Lagrangian duality. Using these results, we propose some dual algorithms for the studied classes of problems. The proposed algorithms can be interpreted as cutting plane or discretization algorithms. Finally, some comments on the convergence of the proposed algorithms and on preliminary numerical tests are given. [ABSTRACT FROM AUTHOR]

In this paper, we implement Zhang's method [Zhang, S., 2004, Journal of Global Optimization , 29, 479–496], which transforms a general convex optimization problem with smooth convex constraints into a convex conic optimization problem and then apply the techniques of self-dual embedding and central path-following for solving the resulting conic optimization model. A crucial advantage of the approach is that no initial solution is required and the method is particularly suitable when the feasibility status of the problem is unknown. In our implementation, we use a merit function approach proposed by Andersen and Ye [Andersen, E.D. and Ye, Y., 1998, Computational Optimization and Applications , 10, 243–269] to determine the step-size along the search direction. We evaluate the efficiency of the proposed algorithm by observing its performance on some test problems, which include logarithmic functions, exponential functions and quadratic functions in the constraints. Furthermore, we consider in particular the geometric programming and L p -programming problems. Numerical results of our algorithm on these classes of optimization problems are reported. We conclude that the algorithm is stable, efficient and easy-to-use in general. As the method allows the user to freely select the initial solution, it is natural to take advantage of this and apply the so-called warm-start strategy, whenever the data of a new problem is not too much different from a previously solved problem. This strategy turns out to be effective, according to our numerical experience. [ABSTRACT FROM AUTHOR]

The aim of the paper is to demonstrate the efficiency of application of the Theory of Exact Penalties and Nonsmooth Optimization to solving variational problems. As an example we discuss the main (or so-called simplest ) problem of the Calculus of Variations. It is shown that this approach allows one not only to get the main known results (e.g., the Euler and Weierstrass necessary conditions) but also to gain a deeper understanding of the intristic nature of the Euler condition, to derive new extremality conditions and to construct new direct numerical methods for solving variational problems based on the notions of subgradient and hypogradient of the exact penalty function. [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]

We present software for investigations with cut-generating functions in the Gomory-Johnson model and extensions, implemented in the computer algebra system SageMath. [ABSTRACT FROM AUTHOR]

We reexamine the work of Aupyet al.on optimal algorithms for hierarchical adjoint computations, where two levels of memories are available. The previous optimal algorithm had a quadratic execution time. Here, with structural arguments, namely periodicity, on the optimal solution, we provide an optimal algorithm in constant time and space, with appropriate pre-processing. We also provide an asymptotically optimal algorithm for the online problem, when the adjoint chain size is not known before-hand. Again, these algorithms rely on the proof that the optimal solution for hierarchical adjoint computations is weakly periodic. We conjecture a closed-form formula for the period. Finally, we assess the convergence speed of the approximation ratio for the online problem through simulations. [ABSTRACT FROM AUTHOR]

Constructing a feasible solution, where the focus is on 'hard' constraints only, is an important part of solving timetabling problems. For the University Course Timetabling Problem, we propose a heuristic algorithm to schedule events to timeslots based on cliques, each representing a set of events that could be scheduled in the same timeslot, which the algorithm constructs. Our algorithm has been tested on a set of well-known instances, and the experimental results show that our algorithm is efficient and can compete with other effective algorithms. [ABSTRACT FROM AUTHOR]