Primal-dual row-action method for convex programming

We present a primal-dual row-action method for the minimization of a convex function subject to general convex constraints. Constraints are used one at a time, no changes are made in the constraint functions and their Jacobian matrix (thus, the row-action nature of the algorithm), and at each iteration a subproblem is solved consisting of minimization of the objective function subject to one or two linear equations. The algorithm generates two sequences: one of them, called primal, converges to the solution of the problem; the other one, called dual, approximates a vector of optimal KKT multipliers for the problem. We prove convergence of the primal sequence for general convex constraints. In the case of linear constraints, we prove that the primal sequence converges at least linearly and obtain as a consequence the convergence of the dual sequence.The research of the first author was partially supported by CNPq Grant No. 301280/86.     

A proximal-based decomposition method for convex minimization problems

This paper presents a decomposition method for solving convex minimization problems. At each iteration, the algorithm computes two proximal steps in the dual variables and one proximal step in the primal variables. We derive this algorithm from Rockafellar's proximal method of multipliers, which involves an augmented Lagrangian with an additional quadratic proximal term. The algorithm preserves the good features of the proximal method of multipliers, with the additional advantage that it leads to a decoupling of the constraints, and is thus suitable for parallel implementation. We allow for computing approximately the proximal minimization steps and we prove that under mild assumptions on the problem's data, the method is globally convergent and at a linear rate. The method is compared with alternating direction type methods and applied to the particular case of minimizing a convex function over a finite intersection of closed convex sets.Corresponding author. Partially supported by Air Force Office of Scientific Research Grant 91-0008 and National Science Foundation Grant DMS-9201297.     

Fixed point optimization algorithm and its application to network bandwidth allocation

A convex optimization problem for a strictly convex objective function over the fixed point set of a nonexpansive mapping includes a network bandwidth allocation problem, which is one of the central issues in modern communication networks. We devised an iterative algorithm, called a fixed point optimization algorithm, for solving the convex optimization problem and conducted a convergence analysis on the algorithm. The analysis guarantees that the algorithm, with slowly diminishing step-size sequences, weakly converges to a unique solution to the problem. Moreover, we apply the proposed algorithm to a network bandwidth allocation problem and show its effectiveness.     

On necessary conditions for a class of nondifferentiable minimax fractional programming

The Kuhn–Tucker-type necessary optimality conditions are given for the problem of minimizing a max fractional function, where the numerator of the function involved is the sum of a differentiable function and a convex function while the denominator is the difference of a differentiable function and a convex function, subject to a set of differentiable nonlinear inequalities on a convex subset C$C$ of Rⁿ${\mathbb{R}}^n$, under the conditions similar to the Kuhn–Tucker constraint qualification or the Arrow–Hurwicz–Uzawa constraint qualification or the Abadie constraint qualification. Relations with the calmness constraint qualification are given.     

Robust network design in telecommunications under polytope demand uncertainty

We consider a model for robust network design in telecommunications, in which we minimize the cost of the maximum mismatch between supply and demand. In the present study, the demand is uncertain and takes its values in a polytope defined by constraints. This problem is hardly tractable, so we limit ourselves to computing lower bounds (by a column-generation mechanism) and upper bounds (using an algorithm due to Falk and Soland for maximizing a separable convex function over a polytope). The experimental gap obtained turns out to be large, and this seems to be mainly due to poor upper bounds. Two possible solutions are suggested for further research aimed at improving them: dc optimization (to minimize the difference of two convex functions) and AARC modeling (affinely adjustable robust counterpart).     

An iterative row-action method for interval convex programming

The iterative primal-dual method of Bregman for solving linearly constrained convex programming problems, which utilizes nonorthogonal projections onto hyperplanes, is represented in a compact form, and a complete proof of convergence is given for an almost cyclic control of the method. Based on this, a new algorithm for solving interval convex programming problems, i.e., problems of the form minf(x), subject to γ≤Ax≤δ, is proposed. For a certain family of functionsf(x), which includes the norm ∥x∥ and thex logx entropy function, convergence is proved. The present row-action method is particularly suitable for handling problems in which the matrixA is large (or huge) and sparse.     

The ellipsoid method and its consequences in combinatorial optimization

L. G. Khachiyan recently published a polynomial algorithm to check feasibility of a system of linear inequalities. The method is an adaptation of an algorithm proposed by Shor for non-linear optimization problems. In this paper we show that the method also yields interesting results in combinatorial optimization. Thus it yields polynomial algorithms for vertex packing in perfect graphs; for the matching and matroid intersection problems; for optimum covering of directed cuts of a digraph; for the minimum value of a submodular set function; and for other important combinatorial problems. On the negative side, it yields a proof that weighted fractional chromatic number is NP-hard. Research by the third author was supported by the Netherlands Organisation for the Advancement of Pure Research (Z.W.O.).     

Reformulation in mathematical programming: An application to quantum chemistry

This paper concerns the application of reformulation techniques in mathematical programming to a specific problem arising in quantum chemistry, namely the solution of Hartree-Fock systems of equations, which describe atomic and molecular electronic wave functions based on the minimization of a functional of the energy. Their traditional solution method does not provide a guarantee of global optimality and its output depends on a provided initial starting point. We formulate this problem as a multi-extremal nonconvex polynomial programming problem, and solve it with a spatial Branch-and-Bound algorithm for global optimization. The lower bounds at each node are provided by reformulating the problem in such a way that its convex relaxation is tight. The validity of the proposed approach was established by successfully computing the ground-state of the helium and beryllium atoms.     

Extensions of Dinkelbach's algorithm for solving non-linear fractional programming problems

Dinkelbach's algorithm was developed to solve convex fractinal programming. This method achieves the optimal solution of the optimisation problem by means of solving a sequence of non-linear convex programming subproblems defined by a parameter. In this paper it is shown that Dinkelbach's algorithm can be used to solve general fractional programming. The applicability of the algorithm will depend on the possibility of solving the subproblems. Dinkelbach's extended algorithm is a framework to describe several algorithms which have been proposed to solve linear fractional programming, integer linear fractional programming, convex fractional programming and to generate new algorithms. The applicability of new cases as nondifferentiable fractional programming and quadratic fractional programming has been studied. We have proposed two modifications to improve the speed-up of Dinkelbachs algorithm. One is to use interpolation formulae to update the parameter which defined the subproblem and another truncates the solution of the suproblem. We give sufficient conditions for the convergence of these modifications. Computational experiments in linear fractional programming, integer linear fractional programming and non-linear fractional programming to evaluate the efficiency of these methods have been carried out.     

Partially finite convex programming,Part I: Quasi relative interiors and duality theory

We study convex programs that involve the minimization of a convex function over a convex subset of a topological vector space, subject to a finite number of linear inequalities. We develop the notion of the quasi relative interior of a convex set, an extension of the relative interior in finite dimensions. We use this idea in a constraint qualification for a fundamental Fenchel duality result, and then deduce duality results for these problems despite the almost invariable failure of the standard Slater condition. Part II of this work studies applications to more concrete models, whose dual problems are often finite-dimensional and computationally tractable.     

Solving cone-constrained convex programs by differential inclusions

A differential inclusion is designed for solving cone-constrained convex programs. The method is of subgradient-projection type. It involves projection, penalties and Lagrangian relaxation. Nonsmooth data can be accommodated. A novelty is that multipliers converge monotonically upwards to equilibrium levels. An application to stochastic programming is considered.Corresponding author.     

A saddle-point characterization of Pareto optima

This paper provides an answer to the following basic problem of convex multi-objective optimization: Find a saddle-point condition that is both necessary and sufficient that a given point be Pareto optimal. No regularity condition is assumed for the constraints or the objectives.Research partly supported by the Natural Sciences and Engineering Research Council of Canada.Corresponding author.Contribution of this author is a part of her M.Sc. Thesis in Applied Mathematics.     

An efficient algorithm for large scale global optimization of continuous functions

A fast descent algorithm, resorting to a “stretching” function technique and built on one hybrid method (GRSA) which combines simulated annealing (SA) algorithm and gradient based methods for large scale global optimizations, is proposed. Unlike the previously proposed method in which the original objective functions remain unchanged during the whole course of optimization, the new method firstly constructs an auxiliary function on one local minimizer obtained by gradient based methods and then SA is executed on this constructed auxiliary function instead of on the original objective function in order that we can improve the jumping ability of SA algorithm to escape from the currently discovered local minimum to a better one from which the gradient based methods restart a new local search. The above procedure is repeated until a global minimum is detected. In addition, corresponding to the adopted “stretching” technique, a new next trial point generating scheme is designed. It is verified by simulation especially on large scale problems that the convergence speed is greatly accelerated, which is its main difference from many other reported methods that mostly cope with functions with less than 50 variables and does not apply to large scale optimization problems. Furthermore, the new algorithm functions as a global optimization procedure with a high success probability and high solution precision.     

A method for generating a well-distributed Pareto set in nonlinear multiobjective optimization

A method is presented for generating a well-distributed Pareto set in nonlinear multiobjective optimization. The approach shares conceptual similarity with the Physical Programming-based method, the Normal-Boundary Intersection and the Normal Constraint methods, in its systematic approach investigating the objective space in order to obtain a well-distributed Pareto set. The proposed approach is based on the generalization of the class functions which allows the orientation of the search domain to be conducted in the objective space. It is shown that the proposed modification allows the method to generate an even representation of the entire Pareto surface. The generation is performed for both convex and nonconvex Pareto frontiers. A simple algorithm has been proposed to remove local Pareto solutions. The suggested approach has been verified by several test cases, including the generation of both convex and concave Pareto frontiers.     

Lower subdifferentiability of quadratic functions

In this paper we characterize those quadratic functions whose restrictions to a convex set are boundedly lower subdifferentiable and, for the case of closed hyperbolic convex sets, those which are lower subdifferentiable but not boundedly lower subdifferentiable.Once characterized, we will study the applicability of the cutting plane algorithm of Plastria to problems where the objective function is quadratic and boundedly lower subdifferentiable.Financial support from the Dirección General de Investigación Científica y Técnica (DGICYT), under project PS89-0058, is gratefully acknowledged.     

Some Randomized Algorithms for Convex Quadratic Programming

We adapt some randomized algorithms of Clarkson [3] for linear programming to the framework of so-called LP-type problems, which was introduced by Sharir and Welzl [10]. This framework is quite general and allows a unified and elegant presentation and analysis. We also show that LP-type problems include minimization of a convex quadratic function subject to convex quadratic constraints as a special case, for which the algorithms can be implemented efficiently, if only linear constraints are present. We show that the expected running times depend only linearly on the number of constraints, and illustrate this by some numerical results. Even though the framework of LP-type problems may appear rather abstract at first, application of the methods considered in this paper to a given problem of that type is easy and efficient. Moreover, our proofs are in fact rather simple, since many technical details of more explicit problem representations are handled in a uniform manner by our approach. In particular, we do not assume boundedness of the feasible set as required in related methods. Accepted 7 May 1997     

An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities

In this paper, an entropy-like proximal method for the minimization of a convex function subject to positivity constraints is extended to an interior algorithm in two directions. First, to general linearly constrained convex minimization problems and second, to variational inequalities on polyhedra. For linear programming, numerical results are presented and quadratic convergence is established.Corresponding author. His research has been supported by C.E.E grants: CI1* CT 92-0046.     

A quasi-linear algorithm for calculating the infimal convolution of convex quadratic functions

In this paper we present an algorithm of quasi-linear complexity to exactly calculate the infimal convolution of convex quadratic functions. The algorithm exactly and simultaneously solves a separable uniparametric family of quadratic programming problems resulting from varying the equality constraint.     

Robust conjugate duality for convex optimization under uncertainty with application to data classification

In this paper we present a robust conjugate duality theory for convex programming problems in the face of data uncertainty within the framework of robust optimization, extending the powerful conjugate duality technique. We first establish robust strong duality between an uncertain primal parameterized convex programming model problem and its uncertain conjugate dual by proving strong duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem under a regularity condition. This regularity condition is not only sufficient for robust duality but also necessary for it whenever robust duality holds for every linear perturbation of the objective function of the primal model problem. More importantly, we show that robust strong duality always holds for partially finite convex programming problems under scenario data uncertainty and that the optimistic counterpart of the dual is a tractable finite dimensional problem. As an application, we also derive a robust conjugate duality theorem for support vector machines which are a class of important convex optimization models for classifying two labelled data sets. The support vector machine has emerged as a powerful modelling tool for machine learning problems of data classification that arise in many areas of application in information and computer sciences.     

A method of linearizations for linearly constrained nonconvex nonsmooth minimization

A readily implementable algorithm is given for minimizing a (possibly nondifferentiable and nonconvex) locally Lipschitz continuous functionf subject to linear constraints. At each iteration a polyhedral approximation tof is constructed from a few previously computed subgradients and an aggregate subgradient, which accumulates the past subgradient information. This aproximation and the linear constraints generate constraints in the search direction finding subproblem that is a quadratic programming problem. Then a stepsize is found by an approximate line search. All the algorithm's accumulation points are stationary. Moreover, the algorithm converges whenf happens to be convex.