Convex Separable Minimization Subject to Bounded Variables

A minimization problem with convex and separable objective function subject to a separable convex inequality constraint and bounded variables is considered. A necessary and sufficient condition is proved for a feasible solution to be an optimal solution to this problem. Convex minimization problems subject to linear equality/linear inequality constraint, and bounds on the variables are also considered. A necessary and sufficient condition and a sufficient condition, respectively, are proved for a feasible solution to be an optimal solution to these two problems. Algorithms of polynomial complexity for solving the three problems are suggested and their convergence is proved. Some important forms of convex functions and computational results are given in the Appendix.     

A Polynomial Cutting Surfaces Algorithm for the Convex Feasibility Problem Defined by Self-Concordant Inequalities

Consider a nonempty convex set in ^m which is defined by a finite number of smooth convex inequalities and which admits a self-concordant logarithmic barrier. We study the analytic center based column generation algorithm for the problem of finding a feasible point in this set. At each iteration the algorithm computes an approximate analytic center of the set defined by the inequalities generated in the previous iterations. If this approximate analytic center is a solution, then the algorithm terminates; otherwise either an existing inequality is shifted or a new inequality is added into the system. As the number of iterations increases, the set defined by the generated inequalities shrinks and the algorithm eventually finds a solution of the problem. The algorithm can be thought of as an extension of the classical cutting plane method. The difference is that we use analytic centers and convex cuts instead of arbitrary infeasible points and linear cuts. In contrast to the cutting plane method, the algorithm has a polynomial worst case complexity of O(Nlog 1/) on the total number of cuts to be used, where N is the number of convex inequalities in the original problem and is the maximum common slack of the original inequality system.     

Convex minimization under Lipschitz constraints

We consider the problem of minimizing a convex functionf(x) under Lipschitz constraintsf _i (x)0,i=1,...,m. By transforming a system of Lipschitz constraintsf _i (x)0,i=l,...,m, into a single constraints of the formh(x)-x²0, withh(·) being a closed convex function, we convert the problem into a convex program with an additional reverse convex constraint. Under a regularity assumption, we apply Tuy's method for convex programs with an additional reverse convex constraint to solve the converted problem. By this way, we construct an algorithm which reduces the problem to a sequence of subproblems of minimizing a concave, quadratic, separable function over a polytope. Finally, we show how the algorithm can be used for the decomposition of Lipschitz optimization problems involving relatively few nonconvex variables.     

Global Optimality Conditions in Maximizing a Convex Quadratic Function under Convex Quadratic Constraints

For the problem of maximizing a convex quadratic function under convex quadratic constraints, we derive conditions characterizing a globally optimal solution. The method consists in exploiting the global optimality conditions, expressed in terms of -subdifferentials of convex functions and -normal directions, to convex sets. By specializing the problem of maximizing a convex function over a convex set, we find explicit conditions for optimality.     

Optimizing constrained subtrees of trees

Given a treeG = (V, E) and a weight function defined on subsets of its nodes, we consider two associated problems. The first, called the rooted subtree problem, is to find a maximum weight subtree, with a specified root, from a given set of subtrees.The second problem, called the subtree packing problem, is to find a maximum weight packing of node disjoint subtrees chosen from a given set of subtrees, where the value of each subtree may depend on its root.We show that the complexity status of both problems is related, and that the subtree packing problem is polynomial if and only if each rooted subtree problem is polynomial. In addition we show that the convex hulls of the feasible solutions to both problems are related: the convex hull of solutions to the packing problem is given by pasting together the convex hulls of the rooted subtree problems.We examine in detail the case where the set of feasible subtrees rooted at nodei consists of all subtrees with at mostk nodes. For this case we derive valid inequalities, and specify the convex hull whenk 4.Research supported in part by Nato Collaborative Research Grant CRG 900281, Science Program SC1-CT91-620 of the EEC, and contract No 26 of the programme Pôle d'attraction interuniversitaire of the Belgian government.     

Convex Quadratic Approximation

For some applications it is desired to approximate a set of m data points in ⁿ with a convex quadratic function. Furthermore, it is required that the convex quadratic approximation underestimate all m of the data points. It is shown here how to formulate and solve this problem using a convex quadratic function with s = (n + 1)(n + 2)/2 parameters, s m, so as to minimize the approximation error in the L ¹ norm. The approximating function is q(p,x), where p ^s is the vector of parameters, and x n. The Hessian of q(p,x) with respect to x (for fixed p) is positive semi-definite, and its Hessian with respect to p (for fixed x) is shown to be positive semi-definite and of rank n. An algorithm is described for computing an optimal p* for any specified set of m data points, and computational results (for n = 4,6,10,15) are presented showing that the optimal q(p*,x) can be obtained efficiently. It is shown that the approximation will usually interpolate s of the m data points.     

Convex approximations for complete integer recourse models

We consider convex approximations of the expected value function of a two-stage integer recourse problem. The convex approximations are obtained by perturbing the distribution of the random right-hand side vector. It is shown that the approximation is optimal for the class of problems with totally unimodular recourse matrices. For problems not in this class, the result is a convex lower bound that is strictly better than the one obtained from the LP relaxation.This research has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences.Key words.integer recourse – convex approximationMathematics Subject Classification (1991):90C15, 90C11     

The design centering problem as a D.C. programming problem

The following problem is studied: Given a compact setS inR ⁿ and a Minkowski functionalp(x), find the largest positive numberr for which there existsx S such that the set of ally R ⁿ satisfyingp(y–x) r is contained inS. It is shown that whenS is the intersection of a closed convex set and several complementary convex sets (sets whose complements are open convex) this design centering problem can be reformulated as the minimization of some d.c. function (difference of two convex functions) overR ⁿ . In the case where, moreover,p(x) = (x ^T Ax)^1/2, withA being a symmetric positive definite matrix, a solution method is developed which is based on the reduction of the problem to the global minimization of a concave function over a compact convex set.     

Convex Hulls in Singular Spaces of Negative Curvature

The paper gives a simple example of a complete CAT(–1)-space containing a set S with the following property: the boundary at infinity CH(S)of the convex hull of S differs from S by an isolated point. In contrast to this it is shown that if S is a union of finitely many convex subsets of a complete CAT(–1)-space X, then CH(S) = S. Moreover, this identity holds without restrictions on S if CH is replaced by some notion of almost convex hull.     

Solving a Class of Multiplicative Programs with 0–1 Knapsack Constraints

We develop a branch-and-bound algorithm to solve a nonlinear class of 0–1 knapsack problems. The objective function is a product of m2 affine functions, whose variables are mutually exclusive. The branching procedure in the proposed algorithm is the usual one, but the bounding procedure exploits the special structure of the problem and is implemented through two stages: the first stage is based on linear programming relaxation; the second stage is based on Lagrangian relaxation. Computational results indicate that the algorithm is promising.     

On Convex Limit Sets and Brownian Motion

We prove limsup results for nonnegative functionals of convex sets determined by normalized Brownian paths in Banach spaces. This continues the interesting investigation of D. Khoshnevisan into this area, and relates to some classical unsolved isoperimetric problems for the convex hull of curves in ^d. Section 4 contains the solution of a problem similar to these classical problems.     

Vector Equilibrium Problems Under Asymptotic Analysis

Given a closed convex set K in Rⁿ; a vector function F:K×K R^m; a closed convex (not necessarily pointed) cone P(x) in ^m with non-empty interior, PP(x) Ø, various existence results to the problemfind xK such that F(x,y)- int P(x) y K under P(x)-convexity/lower semicontinuity of F(x,) and pseudomonotonicity on F, are established. Moreover, under a stronger pseudomonotonicity assumption on F (which reduces to the previous one in case m=1), some characterizations of the non-emptiness of the solution set are given. Also, several alternative necessary and/or sufficient conditions for the solution set to be non-empty and compact are presented. However, the solution set fails to be convex in general. A sufficient condition to the solution set to be a singleton is also stated. The classical case P(x)=^m ₊ is specially discussed by assuming semi-strict quasiconvexity. The results are then applied to vector variational inequalities and minimization problems. Our approach is based upon the computing of certain cones containing particular recession directions of K and F.     

Convex programs with an additional reverse convex constraint

A method is presented for solving a class of global optimization problems of the form (P): minimizef(x), subject toxD,g(x)0, whereD is a closed convex subset ofR ⁿ andf,g are convex finite functionsR ⁿ . Under suitable stability hypotheses, it is shown that a feasible point is optimal if and only if 0=max{g(x):xD,f(x)f( )}. On the basis of this optimality criterion, the problem is reduced to a sequence of subproblemsQ _k ,k=1, 2, ..., each of which consists in maximizing the convex functiong(x) over some polyhedronS _k . The method is similar to the outer approximation method for maximizing a convex function over a compact convex set.     

Convergence of the Gradient Projection Method for Generalized Convex Minimization

This paper develops convergence theory of the gradient projection method by Calamai and Moré (Math. Programming, vol. 39, 93–116, 1987) which, for minimizing a continuously differentiable optimization problem min{f(x) : x } where is a nonempty closed convex set, generates a sequence x_k+1 = P(x_k – _k f(x_k)) where the stepsize _k > 0 is chosen suitably. It is shown that, when f(x) is a pseudo-convex (quasi-convex) function, this method has strong convergence results: either x_k x^* and x^* is a minimizer (stationary point); or x_k arg min{f(x) : x } = , and f(x_k) inf{f(x) : x }.     

A Long-Step, Cutting Plane Algorithm for Linear and Convex Programming

A cutting plane method for linear programming is described. This method is an extension of Atkinson and Vaidya's algorithm, and uses the central trajectory. The logarithmic barrier function is used explicitly, motivated partly by the successful implementation of such algorithms. This makes it possible to maintain primal and dual iterates, thus allowing termination at will, instead of having to solve to completion. This algorithm has the same complexity (O(nL ²) iterations) as Atkinson and Vaidya's algorithm, but improves upon it in that it is a long-step version, while theirs is a short-step one in some sense. For this reason, this algorithm is computationally much more promising as well. This algorithm can be of use in solving combinatorial optimization problems with large numbers of constraints, such as the Traveling Salesman Problem.     

Some Characterization of Locally Nonconical Convex Sets

A closed convex set Q in a local convex topological Hausdorff spaces X is called locally nonconical (LNC) if for every x, y Q there exists an open neighbourhood U of x such that . A set Q is local cylindric (LC) if for x, y Q, x y, z (x, y) there exists an open neighbourhood U of z such that U Q (equivalently: bd(Q) U) is a union of open segments parallel to [x, y]. In this paper we prove that these two notions are equivalent. The properties LNC and LC were investigated in [3], where the implication LNC LC was proved in general, while the inverse implication was proved in case of Hilbert spaces.     

A chance-constrained programming algorithm

This paper describes a new algorithm solving the deterministic equivalents of chance-constrained problems where the random variables are normally distributed and independent of each other. In this method nonlinear chance-constraints are first replaced by uniformly tighter linear constraints. The resulting linear programming problem is solved by a standard simplex method. The linear programming problem is then revised using the solution data and solved again until the stopping rule of the algorithm terminates the process. It is proved that the algorithm converges and that the solution found is the -optimal solution of the chance-constrained programming problem.The computational experience of the algorithm is reported. The algorithm is efficient if the random variables are distributed independently of each other and if they number less than two hundred. The computing system is called CHAPS, i.e. Chance-ConstrainedProgrammingSystem.     

p-Harmonic Maps and Convex Functions

p-harmonic maps (p ' 2) between Riemannian manifolds are investigated. Some theorems of Liouville type are given for such maps when target manifolds have convex functions.     

Primal-Dual Nonlinear Rescaling Method for Convex Optimization

In this paper, we consider a general primal-dual nonlinear rescaling (PDNR) method for convex optimization with inequality constraints. We prove the global convergence of the PDNR method and estimate the error bounds for the primal and dual sequences. In particular, we prove that, under the standard second-order optimality conditions, the error bounds for the primal and dual sequences converge to zero with linear rate. Moreover, for any given ratio 0 > > 1, there is a fixed scaling parameter k > 0 such that each PDNR step shrinks the primal-dual error bound by at least a factor 0 > > 1, for any k k. The PDNR solver was tested on a variety of NLP problems including the constrained optimization problems (COPS) set. The results obtained show that the PDNR solver is numerically stable and produces results with high accuracy. Moreover, for most of the problems solved, the number of Newton steps is practically independent of the problem size.     

Convex Envelopes of Monomials of Odd Degree

Convex envelopes of nonconvex functions are widely used to calculate lower bounds to solutions of nonlinear programming problems (NLP), particularly within the context of spatial Branch-and-Bound methods for global optimization. This paper proposes a nonlinear continuous and differentiable convex envelope for monomial terms of odd degree, x ^2k+1, where k N and the range of x includes zero. We prove that this envelope is the tightest possible. We also derive a linear relaxation from the proposed envelope, and compare both the nonlinear and linear formulations with relaxations obtained using other approaches.