Worst-case distribution analysis of stochastic programs

We show that for even quasi-concave objective functions the worst-case distribution, with respect to a family of unimodal distributions, of a stochastic programming problem is a uniform distribution. This extends the so-called “Uniformity Principle” of Barmish and Lagoa (1997) where the objective function is the indicator function of a convex symmetric set. Article Download View … Read more

A Branch-Reduce-Cut Algorithm for the Global Optimization of Probabilistically Constrained Linear Programs

We consider probabilistic constrained linear programs with general distributions for the uncertain parameters. These problems generally involve non-convex feasible sets. We develop a branch and bound algorithm that searches for a global solution to this problem by successively partitioning the non-convex feasible region and by using bounds on the objective function to fathom inferior partitions. … Read more

Linear inequalities among graph invariants: using GraPHedron to uncover optimal relationships

Optimality of a linear inequality in finitely many graph invariants is defined through a geometric approach. For a fixed number of graph nodes, consider all the tuples of values taken by the invariants on a selected class of graphs. Then form the polytope which is the convex hull of all these tuples. By definition, the … Read more

Newton-KKT Interior-Point Methods for Indefinite Quadratic Programming

Two interior-point algorithms are proposed and analyzed, for the (local) solution of (possibly) indefinite quadratic programming problems. They are of the Newton-KKT variety in that (much like in the case of primal-dual algorithms for linear programming) search directions for the `primal´ variables and the Karush-Kuhn-Tucker (KKT) multiplier estimates are components of the Newton (or quasi-Newton) … Read more

Nonlinear-Programming Reformulation of the Order-Value Optimization problem

Order-value optimization (OVO) is a generalization of the minimax problem motivated by decision-making problems under uncertainty and by robust estimation. New optimality conditions for this nonsmooth optimization problem are derived. An equivalent mathematical programming problem with equilibrium constraints is deduced. The relation between OVO and this nonlinear-programming reformulation is studied. Particular attention is given to … Read more

A shifted Steihaug-Toint method for computing a trust-region step.

Trust-region methods are very convenient in connection with the Newton method for unconstrained optimization. The More-Sorensen direct method and the Steihaug-Toint iterative method are most commonly used for solving trust-region subproblems. We propose a method which combines both of these approaches. Using the small-size Lanczos matrix, we apply the More-Sorensen method to a small-size trust-region … Read more

Semi-Lagrangian relaxation

Lagrangian relaxation is commonly used in combinatorial optimization to generate lower bounds for a minimization problem. We propose a modified Lagrangian relaxation which used in (linear) combinatorial optimization with equality constraints generates an optimal integer solution. We call this new concept semi-Lagrangian relaxation and illustrate its practical value by solving large-scale instances of the p-median … Read more

Constrained Global Optimization with Radial Basis Functions

Response surface methods show promising results for global optimization of costly non convex objective functions, i.e. the problem of finding the global minimum when there are several local minima and each function value takes considerable CPU time to compute. Such problems often arise in industrial and financial applications, where a function value could be a … Read more

Augmented Lagrangian methods under the Constant Positive Linear Dependence constraint qualification

Two Augmented Lagrangian algorithms for solving KKT systems are introduced. The algorithms differ in the way in which penalty parameters are updated. Possibly infeasible accumulation points are characterized. It is proved that feasible limit points that satisfy the Constant Positive Linear Dependence constraint qualification are KKT solutions. Boundedness of the penalty parameters is proved under … Read more