An approximation algorithm for convex multi-objective programming problems

In multi-objective convex optimization it is necessary to compute an infinite set of nondominated points. We propose a method for approximating the nondominated set of a multi-objective nonlinear programming problem, where the objective functions and the feasible set are convex. This method is an extension of Benson’s outer approximation algorithm for multi-objective linear programming problems. We prove that this method provides a set of weakly ε-nondominated points. For the case that the objectives and constraints are differentiable, we describe an efficient way to carry out the main step of the algorithm, the construction of a hyperplane separating an exterior point from the feasible set in objective space. We provide examples that show that this cannot always be done in the same way in the case of non-differentiable objectives or constraints.     

A statistical generalized programming algorithm for stochastic optimization problems

In this paper, we are concerned with an algorithm which combines the generalized linear programming technique proposed by Dantzig and Wolfe with the stochastic quasigradient method in order to solve stochastic programs with recourse. In this way, we overcome the difficulties arising in finding the exact values of the objective function of recourse problems by replacing them with the statistical estimates of the function. We present the basic steps of the proposed algorithm focusing our attention on its implementation alternatives aimed at improving both the convergence and computational performances. The main application areas are mentioned and some computational experience in the validation of our approach is reported. Finally, we discuss the possibilities of parallelization of the proposed algorithmic schemes.This paper has been partially supported by the Italian MURST 40% project on Flexible Manufacturing Systems.     

Primal-dual proximal point algorithm for linearly constrained convex programming problems

A primal-dual version of the proximal point algorithm is developed for linearly constrained convex programming problems. The algorithm is an iterative method to find a saddle point of the Lagrangian of the problem. At each iteration of the algorithm, we compute an approximate saddle point of the Lagrangian function augmented by quadratic proximal terms of both primal and dual variables. Specifically, we first minimize the function with respect to the primal variables and then approximately maximize the resulting function of the dual variables. The merit of this approach exists in the fact that the latter function is differentiable and the maximization of this function is subject to no constraints. We discuss convergence properties of the algorithm and report some numerical results for network flow problems with separable quadratic costs.     

A path following algorithm for a class of convex programming problems

We present a primal-dual path following interior algorithm for a class of linearly constrained convex programming problems with non-negative decision variables. We introduce the definition of a Scaled Lipschitz Condition and show that if the objective function satisfies the Scaled Lipschitz Condition then, at each iteration, our algorithm reduces the duality gap by at least a factor of (1–/n), where is positive and depends on the curvature of the objective function, by means of solving a system of linear equations which requires no more than O(n³) arithmetic operations. The class of functions having the Scaled Lipschitz Condition includes linear, convex quadratic and entropy functions.     

An SQP algorithm for extended linear-quadratic problems in stochastic programming

Extended Linear-Quadratic Programming (ELQP) problems were introduced by Rockafellar and Wets for various models in stochastic programming and multistage optimization. Several numerical methods with linear convergence rates have been developed for solving fully quadratic ELQP problems, where the primal and dual coefficient matrices are positive definite. We present a two-stage sequential quadratic programming (SQP) method for solving ELQP problems arising in stochastic programming. The first stage algorithm realizes global convergence and the second stage algorithm realizes superlinear local convergence under a condition calledB-regularity.B-regularity is milder than the fully quadratic condition; the primal coefficient matrix need not be positive definite. Numerical tests are given to demonstrate the efficiency of the algorithm. Solution properties of the ELQP problem underB-regularity are also discussed.Supported by the Australian Research Council.     

Fractional programming approach to two stochastic inventory problems

This paper considers two popular inventory models: the continuous review and periodic review reorder-point, order-quantity, control systems. Specifically we present two procedures which determine optimal values for the two control parameters (i.e., reorder-point and order-quantity) when the holding-and-shortage costs are non-quasi-convex. This cost structure may arise when non-linear cost rate is considered, for instance when the shortage cost is the shadow cost of a service-level constraint. The algorithms based on a fractional programming method are intuitive and efficient, and as the holding-and-shortage cost functions become quasi-convex, they are compatible to existing algorithms.     

Convergence property of the Iri-Imai algorithm for some smooth convex programming problems

In this paper, the Iri-Imai algorithm for solving linear and convex quadratic programming is extended to solve some other smooth convex programming problems. The globally linear convergence rate of this extended algorithm is proved, under the condition that the objective and constraint functions satisfy a certain type of convexity, called the harmonic convexity in this paper. A characterization of this convexity condition is given. The same convexity condition was used by Mehrotra and Sun to prove the convergence of a path-following algorithm.The Iri-Imai algorithm is a natural generalization of the original Newton algorithm to constrained convex programming. Other known convergent interior-point algorithms for smooth convex programming are mainly based on the path-following approach.     

Solving convex quadratic bilevel programming problems using an enumeration sequential quadratic programming algorithm

In this paper, we present an original method to solve convex bilevel programming problems in an optimistic approach. Both upper and lower level objective functions are convex and the feasible region is a polyhedron. The enumeration sequential linear programming algorithm uses primal and dual monotonicity properties of the primal and dual lower level objective functions and constraints within an enumeration frame work. New optimality conditions are given, expressed in terms of tightness of the constraints of lower level problem. These optimality conditions are used at each step of our algorithm to compute an improving rational solution within some indexes of lower level primal-dual variables and monotonicity networks as well. Some preliminary computational results are reported.     

Inequalities in completely convex stochastic programming

A two-stage stochastic programming problem in which the random variable enters in a convex manner is called completely convex. For such problems we give a sequence of inequalities and equalities showing the equivalence of optimality over plans and optimality of a two-stage procedure related to dynamic programming and giving upper bounds on the expected value of perfect information. Our assumptions are the weakest possible to guarantee the results in the completely convex case and supersede previous related results which have received erroneous proofs or have been established under highly restrictive conditions. In the course of our argument we exhibit a new measurable selection theorem and a rather general form of Jensen's inequality. We also present a multistage generalization of our central theorem.     

A regularized smoothing method for fully parameterized convex problems with applications to convex and nonconvex two-stage stochastic programming

Mathematical Programming - We present an approach to regularize and approximate solution mappings of parametric convex optimization problems that combines interior penalty (log-barrier) solutions...     

A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems

This paper presents a primal-dual conjugate subgradient algorithm for solving convex programming problems. The motivation, however, is to employ it for solving specially structured or decomposable linear programming problems. The algorithm coordinates a primal penalty function and a Lagrangian dual function, in order to generate a (geometrically) convergent sequence of primal and dual iterates. Several refinements are discussed to improve the performance of the algorithm. These are tested on some network problems, with side constraints and variables, faced by the Freight Equipment Management Program of the Association of American Railroads, and suggestions are made for implementation.This research was supported by the Association of American Railroads.     

An unconstrained convex programming approach to solving convex quadratic programming problems

In this paper, we derive an unconstrained convex programming approach to solving convex quadratic programming problems in standard form. Related duality theory is established by using two simple inequalities. An ?-optimal solution is obtained by solving an unconstrained dual convex program. A dual-to-primal conversion formula is also provided. Some preliminary computational results of using a curved search method is included     

An entropy based central cutting plane algorithm for convex min-max semi-infinite programming problems

In this paper,we present a central cutting plane algorithm for solving convex min-max semi-infinite programming problems.Because the objective function here is non-differentiable,we apply a smoothing technique to the considered problem and develop an algorithm based on the entropy function.It is shown that the global convergence of the proposed algorithm can be obtained under weaker conditions.Some numerical results are presented to show the potential of the proposed algorithm.     

Stability results for stochastic programming problems

The paper deals with a statistical approach to stability analysis in nonlinear stochastic programming. Firstly the distribution function of the underlying random variable is estimated by the empirical distribution function, and secondly the problem of estimated parameters is considered. In both the cases the probability that the solution set of the approximate problem, is not contained in an l-neighbourhood of the solution set to the original problem is estimated, and under differentiability properties an asymptotic expansion for the density of the (unique) solution to the approximate problem is derived.     

A parallel descent algorithm for convex programming

In this paper, we propose a parallel decomposition algorithm for solving a class of convex optimization problems, which is broad enough to contain ordinary convex programming problems with a strongly convex objective function. The algorithm is a variant of the trust region method applied to the Fenchel dual of the given problem. We prove global convergence of the algorithm and report some computational experience with the proposed algorithm on the Connection Machine Model CM-5.     

A redundancy detection algorithm for fuzzy stochastic multi-objective linear fractional programming problems

The computational complexity of linear and nonlinear programming problems depends on the number of objective functions and constraints involved and solving a large problem often becomes a difficult task. Redundancy detection and elimination provides a suitable tool for reducing this complexity and simplifying a linear or nonlinear programming problem while maintaining the essential properties of the original system. Although a large number of redundancy detection methods have been proposed to simplify linear and nonlinear stochastic programming problems, very little research has been developed for fuzzy stochastic (FS) fractional programming problems. We propose an algorithm that allows to simultaneously detect both redundant objective function(s) and redundant constraint(s) in FS multi-objective linear fractional programming problems. More precisely, our algorithm reduces the number of linear fuzzy fractional objective functions by transforming them in probabilistic–possibilistic constraints characterized by predetermined confidence levels. We present two numerical examples to demonstrate the applicability of the proposed algorithm and exhibit its efficacy.     

CVaR-constrained stochastic programming reformulation for stochastic nonlinear complementarity problems

We reformulate a stochastic nonlinear complementarity problem as a stochastic programming problem which minimizes an expected residual defined by a restricted NCP function with nonnegative constraints and CVaR constraints which guarantee the stochastic nonlinear function being nonnegative with a high probability. By applying smoothing technique and penalty method, we propose a penalized smoothing sample average approximation algorithm to solve the CVaR-constrained stochastic programming. We show that the optimal solution of the penalized smoothing sample average approximation problem converges to the solution of the corresponding nonsmooth CVaR-constrained stochastic programming problem almost surely. Finally, we report some preliminary numerical test results.     

Characterizing strict efficiency for convex multiobjective programming problems

The article pertains to characterize strict local efficient solution (s.l.e.s.) of higher order for the multiobjective programming problem (MOP) with inequality constraints. To create the necessary framework, we partition the index set of objectives of MOP to give rise to subproblems. The s.l.e.s. of order m for MOP is related to the local efficient solution of a subproblem. This relationship inspires us to adopt the D.C. optimization approach, the convex subdifferential sum rule, and the notion of ε-subdifferential to derive the necessary and sufficient optimality conditions for s.l.e.s. of order m \geqq 1{m \geqq 1} for the convex MOP. Further, the saddle point criteria of higher order are also presented.