A simple randomised algorithm for convex optimisation

We consider maximising a concave function over a convex set by a simple randomised algorithm. The strength of the algorithm is that it requires only approximate function evaluations for the concave function and a weak membership oracle for the convex set. Under smoothness conditions on the function and the feasible set, we show that our algorithm computes a near-optimal point in a number of operations which is bounded by a polynomial function of all relevant input parameters and the reciprocal of the desired precision, with high probability. As an application to which the features of our algorithm are particularly useful we study two-stage stochastic programming problems. These problems have the property that evaluation of the objective function is #P-hard under appropriate assumptions on the models. Therefore, as a tool within our randomised algorithm, we devise a fully polynomial randomised approximation scheme for these function evaluations, under appropriate assumptions on the models. Moreover, we deal with smoothing the feasible set, which in two-stage stochastic programming is a polyhedron.     

An algorithm for maximizing a convex function over a simple set

The problem of maximizing a convex function on a so-called simple set is considered. Based on the optimality conditions [19], an algorithm for solving the problem is proposed. This numerical algorithm is shown to be convergent. The proposed algorithm has been implemented and tested on a variety of test problems.     

A simple algorithm for building the 3-D convex hull

A new algorithm is given for finding the convex hull of a finite set of distinct points in three-dimensional space. The algorithm finds the faces of the hull one by one, thus gradually building the polyhedron that constitutes the hull. The algorithm is described as developed through stepwise refinement.     

An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints

In this paper we investigate two approaches to minimizing a quadratic form subject to the intersection of finitely many ellipsoids. The first approach is the d.c. (difference of convex functions) optimization algorithm (abbr. DCA) whose main tools are the proximal point algorithm and/or the projection subgradient method in convex minimization. The second is a branch-and-bound scheme using Lagrangian duality for bounding and ellipsoidal bisection in branching. The DCA was first introduced by Pham Dinh in 1986 for a general d.c. program and later developed by our various work is a local method but, from a good starting point, it provides often a global solution. This motivates us to combine the DCA and our branch and bound algorithm in order to obtain a good initial point for the DCA and to prove the globality of the DCA. In both approaches we attempt to use the ellipsoidal constrained quadratic programs as the main subproblems. The idea is based upon the fact that these programs can be efficiently solved by some available (polynomial and nonpolynomial time) algorithms, among them the DCA with restarting procedure recently proposed by Pham Dinh and Le Thi has been shown to be the most robust and fast for large-scale problems. Several numerical experiments with dimension up to 200 are given which show the effectiveness and the robustness of the DCA and the combined DCA-branch-and-bound algorithm. Received: April 22, 1999 / Accepted: November 30, 1999?Published online February 23, 2000     

A new penalty function algorithm for convex quadratic programming

In this paper, we develop an exterior point algorithm for convex quadratic programming using a penalty function approach. Each iteration in the algorithm consists of a single Newton step followed by a reduction in the value of the penalty parameter. The points generated by the algorithm follow an exterior path that we define. Convergence of the algorithm is established. The proposed algorithm was motivated by the work of Al-Sultan and Murty on nearest point problems, a special quadratic program. A preliminary implementation of the algorithm produced encouraging results. In particular, the algorithm requires a small and almost constant number of iterations to solve the small to medium size problems tested.     

Analysis to Neyman-Pearson classification with convex loss function

Neyman-Pearson classification has been studied in several articles before.But they all proceeded in the classes of indicator functions with indicator function as the loss function,which make the calculation to be difficult.This paper investigates NeymanPearson classification with convex loss function in the arbitrary class of real measurable functions.A general condition is given under which Neyman-Pearson classification with convex loss function has the same classifier as that with indicator loss function.We give analysis to NP-ERM with convex loss function and prove it's performance guarantees.An example of complexity penalty pair about convex loss function risk in terms of Rademacher averages is studied,which produces a tight PAC bound of the NP-ERM with convex loss function.     

Optimization of the quantile criterion for the convex loss function by a stochastic quasigradient algorithm

A stochastic quasigradient algorithm is suggested for solving the quantile optimization problem with a convex loss function. The algorithm is based on stochastic finite-difference approximations of gradients of the quantile function by using the order statistics. The algorithm convergence almost surely is proved.     

最小化三个凸函数之和的一个简单原始-对偶算法

提出一个简单的原始-对偶算法求解三个凸函数之和的最小化问题, 其中目标函数包含有梯度李普希兹连续的光滑函数, 非光滑函数和含有复合算子的非光滑函数. 在新方法中, 对偶变量迭代使用预估-矫正的方案. 分析了算法的收敛性和收敛速率. 最后, 数值实验说明了算法的有效性.     

A team decision problem for a convex loss function over aBernoulli random variable

Summary Suppose each member of a team observes aBernoulli random variable,x, and the team outcome is the inner product, a,x, of the observation vectorx and the decision vectora. This paper considers the case when the loss function is convex. Two numerical examples are given.

---

Zusammenfassung Angenommen, jedes Mitglied eines Teams beobachtet eineBernoulli-verteilte Zufallsvariablex und das Team-Ergebnis besteht aus dem skalaren Produkt a,x des Beobachtungsvektorsx und des Entscheidungsvektorsa. Die vorliegende Arbeit behandelt den Fall, bei dem die Nutzenfunktion konvex ist. Zwei numerische Beispiele werden vorgeführt.

---

---

A Marketing Team

---

Research supported in part by Deutsche Forschungsgemeinschaft while the first author was a guest professor at the Institut für Angewandte Mathematik, Universität Heidelberg. Additional support came from Studiengruppe für Systemforschung, Heidelberg.     

A new algorithm for minimizing convex functions over convex sets

Let be a convex set for which there is an oracle with the following property. Given any pointz∈ℝ ⁿ the oracle returns a “Yes” ifz∈S; whereas ifz∉S then the oracle returns a “No” together with a hyperplane that separatesz fromS. The feasibility problem is the problem of finding a point inS; the convex optimization problem is the problem of minimizing a convex function overS. We present a new algorithm for the feasibility problem. The notion of a volumetric center of a polytope and a related ellipsoid of maximum volume inscribable in the polytope are central to the algorithm. Our algorithm has a significantly better global convergence rate and time complexity than the ellipsoid algorithm. The algorithm for the feasibility problem easily adapts to the convex optimization problem.     

A simple convex optimization problem with many applications

This paper presents an algorithm for the solution of a simpleconvex optimization problem. This problem is a generalizationof several other optimization problems which have applicationsto resource allocation, optimal capacity expansion, and vehiclescheduling. The algorithm is based on a constraint-relaxationapproach. It is easily implemented and transparent, and canbe used to solve even fairly large problems by hand calculator.     

An efficient and numerically correct algorithm for the 2D convex hull problem

An efficient and numerically correct program called FastHull for computing the convex hulls of finite point sets in the plane is presented. It is based on the Akl-Toussaint algorithm and the MergeHull algorithm. Numerical correctness of the FastHull procedure is ensured by using special routines for interval arithmetic and multiple precision arithmetic. The FastHull algorithm guaranteesO(N logN) running time in the worst case and has linear time performance for many kinds of input patterns. It appears that the FastHull algorithm runs faster than any currently known 2D convex hull algorithm for many input point patterns.     

Minimax detection of a signal for nondegenerate loss functions, and extremal convex problems

We study a wide class of minimax problems of signal detection under nonparametric alternatives and a modification of these problems for a special class of loss functions. Under rather general assumptions, we obtain the exact asymptotics (of Gaussian type) for the minimax error probabilities and the structure of asymptotically minimax tests. The methods are based on a reduction of the problems under consideration to extremal problems of minimization of a certain Hilbert norm on a convex set of sequences of probability measures on the real line. These extremal problems are investigated in a paper by I. A. Suslina for alternatives having the type of l_q-ellipsoids with l_p-balls removed. Bibliography: 16 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 228, 1996, pp. 162–188.     

A Predictor-corrector algorithm with multiple corrections for convex quadratic programming

Recently an infeasible interior-point algorithm for linear programming (LP) was presented by Liu and Sun. By using similar predictor steps, we give a (feasible) predictor-corrector algorithm for convex quadratic programming (QP). We introduce a (scaled) proximity measure and a dynamical forcing factor (centering parameter). The latter is used to force the duality gap to decrease. The algorithm can decrease the duality gap monotonically. Polynomial complexity can be proved and the result coincides with the best one for LP, namely, $O(\sqrt{n}\log n\mu^{0}/\varepsilon)$ .     

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 descent algorithm for nonsmooth convex optimization

This paper presents a new descent algorithm for minimizing a convex function which is not necessarily differentiable. The algorithm can be implemented and may be considered a modification of the ε-subgradient algorithm and Lemarechal's descent algorithm. Also our algorithm is seen to be closely related to the proximal point algorithm applied to convex minimization problems. A convergence theorem for the algorithm is established under the assumption that the objective function is bounded from below. Limited computational experience with the algorithm is also reported.     

An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space

We present an efficient algorithm for planning the motion of a convex polygonal bodyB in two-dimensional space bounded by a collection of polygonal obstacles. Our algorithm extends and combines the techniques of Leven and Sharir and of Sifrony and Sharir used for the case in whichB is a line segment (a ladder). It also makes use of the results of Kedem and Sharir on the planning of translational motion ofB amidst polygonal obstacles, and of a recent result of Leven and Sharir on the number of free critical contacts ofB with such polygonal obstacles. The algorithm runs in timeO(kn ₆(kn) logkn), wherek is the number of sides ofB, n is the number of obstacle edges, and ,(q) is an almost linear function ofq yielding the maximal number of connected portions ofq continuous functions which compose the graph of their lower envelope, where it is assumed that each pair of these functions intersect in at mosts points.Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.     

A relaxation algorithm for the minimization of a quasiconcave function on a convex polyhedron

A study was made of the global minimization of a general quasiconcave function on a convex polyhedron. This nonconvex problem arises in economies of scale environments and in alternative formulations of other well-known problems, as in the case of bilinear programming.Although not very important in our final results, a local minimum can be easily obtained. However, a major aspect is the existence of two families of lower bounds on the optimal functional value: one is provided by non-linear programming duality, the other is derived from a lexicographic ordering of basic solutions which allows the use of relaxation concepts. These results were exploited in a finite algorithm for obtaining the global minimum whose initial implementation has had encouraging performance.     

An algorithm for the construction of convex hulls in simple integer recourse programming

We consider the objective function of a simple integer recourse problem with fixed technology matrix and discretely distributed right-hand sides. Exploiting the special structure of this problem, we devise an algorithm that determines the convex hull of this function efficiently. The results are improvements over those in a previous paper. In the first place, the convex hull of many objective functions in the class is covered, instead of only one-dimensional versions. In the second place, the algorithm is faster than the one in the previous paper. Moreover, some new results on the structure of the objective function are presented.     

A customized proximal point algorithm for convex minimization with linear constraints

This paper demonstrates a customized application of the classical proximal point algorithm (PPA) to the convex minimization problem with linear constraints. We show that if the proximal parameter in metric form is chosen appropriately, the application of PPA could be effective to exploit the simplicity of the objective function. The resulting subproblems could be easier than those of the augmented Lagrangian method (ALM), a benchmark method for the model under our consideration. The efficiency of the customized application of PPA is demonstrated by some image processing problems.