Conjugate gradient methods based on secant conditions that generate descent search directions for unconstrained optimization

Categories Unconstrained Optimization Tags , , , ,

Conjugate gradient methods have been paid attention to, because they can be directly applied to large-scale unconstrained optimization problems. In order to incorporate second order information of the objective function into conjugate gradient methods, Dai and Liao (2001) proposed a conjugate gradient method based on the secant condition. However, their method does not necessarily generate … Read more

Subspace accelerated matrix splitting algorithms for bound-constrained quadratic programming and linear complementarity problems

Categories Bound-constrained Optimization, Finance and Economics Tags , , , , , , ,

This paper studies the solution of two problems—bound-constrained quadratic programs and linear complementarity problems—by two-phase methods that consist of an active set prediction phase and a subspace phase. The algorithms enjoy favorable convergence properties under weaker assumptions than those assumed for other methods in the literature. The active set prediction phase employs matrix splitting iterations … Read more

Branch-and-cut Approaches for Chance-constrained Formulations of Reliable Network Design Problems

Categories Branch and Cut Algorithms, Stochastic Programming Tags , ,

We study solution approaches for the design of reliably connected networks. Speci fically, given a network with arcs that may fail at random, the goal is to select a minimum cost subset of arcs such the probability that a connectivity requirement is satis ed is at least 1-\epsilon, where \epsilon is a risk tolerance. We consider two … Read more

Orbital shrinking

Categories (Mixed) Integer Nonlinear Programming Tags , , , , , ,

Symmetry plays an important role in optimization. The usual approach to cope with symmetry in discrete optimization is to try to eliminate it by introducing artificial symmetry-breaking conditions into the problem, and/or by using an ad-hoc search strategy. In this paper we argue that symmetry is instead a beneficial feature that we should preserve and … Read more

A short note on the global convergence of the unmodified PRP method

Categories Unconstrained Optimization Tags , ,

It is well-known that the search direction generated by the standard (unmodified) PRP nonlinear conjugate gradient method is not necessarily a descent direction of the objective function, which brings difficulty for its global convergence for general functions. However, to our surprise, it is easily proved in this short note that the unmodified PRP method still … Read more

COIN-OR METSlib: a Metaheuristics Framework in Modern C++.

Categories Meta Heuristics, Nonlinear Optimization, Problem Solving Environments Tags , , , , ,

The document describes COIN-OR METSlib, a C++ framework for local search based metaheuristics. METSlib has been used to implement a massively parallel VRP algorithm, a state of the art Vertex Coloring Problem solver, a Timetabling software, and in many other projects. ArticleDownload View PDF

An LP-Newton Method: Nonsmooth Equations, KKT Systems, and Nonisolated Solutions

Categories Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , , ,

We define a new Newton-type method for the solution of constrained systems of equations and analyze in detail its properties. Under suitable conditions, that do not include differentiability or local uniqueness of solutions, the method converges locally quadratically to a solution of the system of equations, thus filling an important gap in the existing theory. … Read more

PuLP: A Linear Programming Toolkit for Python

Categories (Mixed) Integer Linear Programming, Linear Programming, Modeling Languages and Systems

This paper introduces the PuLP library, an open source package that allows mathematical programs to be described in the Python computer programming language. PuLP is a high-level modelling library that leverages the power of the Python language and allows the user to create programs using expressions that are natural to the Python language, avoiding special … Read more

A First Order Method for Finding Minimal Norm-Like Solutions of Convex Optimization Problems

Categories Convex Optimization Tags , ,

We consider a general class of convex optimization problems in which one seeks to minimize a strongly convex function over a closed and convex set which is by itself an optimal set of another convex problem. We introduce a gradient-based method, called the minimal norm gradient method, for solving this class of problems, and establish … Read more