Limiting behavior of the approximate second-order subdifferential of a convex function

Hiriart-Urruty and the author recently introduced the notions of Dupin indicatrices for nonsmooth convex surfaces and studied them in connection with their concept of a second-order subdifferential for convex functions. They noticed that second-order subdifferentials can be viewed as limit sets of difference quotients involving approximate subdifferentials. In this paper, we elaborate this point in a more detailed way and discuss some related questions.The author is grateful to the referees for their helpful comments.     

计算多项式函数的全局下确界和全局最小值的有效算法

通过捕获所谓的严格临界点, 本文提出了一个计算实多项式函数的全局下确界和全局最小值的有效方法. 对于实数域R 上一个n 元多项式f, 该方法可用来判定f 在Rⁿ 上是否具有有限的全局下确界. 在f 具有有限的全局下确界的情况下, f 的下确界可严格地表示为码(h; a, b), 其中h 是一个实单元多项式, a 和b 是使得a < b 的两个有理数, 而(h; a, b) 代表h(z) 在开区间]a, b[ 中仅有的实根.此外, 当f 具有有限下确界时, 本文的方法可进一步判定f 的下确界能否达到. 在我们的算法设计中,著名的吴方法起着重要作用.     

Algorithms for computing the global infimum and minimum of a polynomial function

By catching the so-called strictly critical points,this paper presents an effective algorithm for computing the global infimum of a polynomial function.For a multivariate real polynomial f ,the algorithm in this paper is able to decide whether or not the global infimum of f is finite.In the case of f having a finite infimum,the global infimum of f can be accurately coded in the Interval Representation.Another usage of our algorithm to decide whether or not the infimum of f is attained when the global infimum of f is finite.In the design of our algorithm,Wu’s well-known method plays an important role.     

Constructing a polytope to approximate a convex body

We develop an algorithm to construct a convex polytopeP withn vertices, contained in an arbitrary convex bodyK inR ^d , so that the ratio of the volumes |K/P|/|K| is dominated byc ·. d/n ^2/(d–1).Supported in part by the fund for the promotion of research in the Technion     

An approximate decomposition algorithm for convex minimization

For nonsmooth convex optimization, Robert Mifflin and Claudia Sagastizábal introduce a VU-space decomposition algorithm in Mifflin and Sagastizábal (2005) [11]. An attractive property of this algorithm is that if a primal-dual track exists, this algorithm uses a bundle subroutine. With the inclusion of a simple line search, it is proved to be globally and superlinearly convergent. However, a drawback is that it needs the exact subgradients of the objective function, which is expensive to compute. In this paper an approximate decomposition algorithm based on proximal bundle-type method is introduced that is capable to deal with approximate subgradients. It is shown that the sequence of iterates generated by the resulting algorithm converges to the optimal solutions of the problem. Numerical tests emphasize the theoretical findings.     

Algorithms for optimal area triangulations of a convex polygon

Given a convex polygon with n vertices in the plane, we are interested in triangulations of its interior, i.e., maximal sets of non-intersecting diagonals that subdivide the interior of the polygon into triangles. The MaxMin area triangulation is the triangulation of the polygon that maximizes the area of the smallest triangle in the triangulation. Similarly, the MinMax area triangulation is the triangulation that minimizes the area of the largest area triangle in the triangulation. We present algorithms that construct MaxMin and MinMax area triangulations of a convex polygon in O(n²logn) time and O(n²) space. The algorithms use dynamic programming and a number of geometric properties that are established within the paper.     

An approximate method for solving the convex programming problem

We consider an iterative process for maximization of a convex nondifferentiable functional in a real Hilbert space. Two-sided bounds on the optimal functional value are derived. Stability of the approximate solutions is considered. Convergence of the proposed iterative process is proved.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 59, pp. 122–129, 1986     

Method for finding an approximate solution of the asphericity problem for a convex body

Given a convex body, the finite-dimensional problem is considered of minimizing the ratio of its circumradius to its inradius (in an arbitrary norm) by choosing a common center of the circumscribed and inscribed balls. An approach is described for obtaining an approximate solution of the problem, whose accuracy depends on the error of a preliminary polyhedral approximation of the convex body and the unit ball of the used norm. The main result consists of developing and justifying a method for finding an approximate solution with every step involving the construction of supporting hyperplanes of the convex body and the unit ball of the used norm at some marginal points and the solution of a linear programming problem.     

On the numerical recovery of a holomorphic mapping from a finite set of approximate values

Summary. The least squares approach for the recovery of a holomorphic mapping from given perturbed nodal values is considered. The mapping is assumed to be a priori bounded by a known quantity, so that the recovery problem is well-posed. The present analysis shows that for nodes that are the zeroes of Jacobi polynomials a quasioptimal algorithm results with a fairly moderate number of nodes. The analysis also takes into account the effect of the numerical linear algebra involved. Some numerical experiments are presented. Received June 10, 1999 / Revised version received July 16, 2001 / Published online September 19, 2001     

A strong duality theorem for the minimum of a family of convex programs

We produce a duality theorem for the minimum of an arbitrary family of convex programs. This duality theorem provides a single concave dual maximization and generalizes recent work in linear disjunctive programming. Homogeneous and symmetric formulations are studied in some detail, and a number of convex and nonconvex applications are given.This work was partially funded by National Research Council of Canada, Grant No. A4493. Thanks are due to Mr. B. Toulany for many conversations and to Dr. L. MacLean who suggested the chance-constrained model.     

Computing approximate solutions for convex conic systems of constraints

We propose a way to reformulate a conic system of constraints as an optimization problem. When an appropriate interior-point method (ipm) is applied to the reformulation, the ipm iterates yield backward-approximate solutions, that is, solutions for nearby conic systems. In addition, once the number of ipm iterations passes a certain threshold, the ipm iterates yield forward-approximate solutions, that is, points close to an exact solution of the original conic system. The threshold is proportional to the reciprocal of distance to ill-posedness of the original conic system.?The condition numbers of the linear equations encountered when applying an ipm influence the computational cost at each iteration. We show that for the reformulation, the condition numbers of the linear equations are uniformly bounded both when computing reasonably-accurate backward-approximate solutions to arbitrary conic systems and when computing forward-approximate solutions to well-conditioned conic systems. Received: July 11, 1997 / Accepted: August 18, 1999?Published online March 15, 2000     

Algorithms for minimum length partitions of polygons

We show that it is possible to find a diagonal partition of anyn-vertex simple polygon into smaller polygons, each of at mostm edges, minimizing the total length of the partitioning diagonals, in timeO(n ³ m ²). We derive the same asymptotic upper time-bound for minimum length diagonal partitions of simple polygons into exactlym-gons provided that the input polygon can be partitioned intom-gons. Also, in the latter case, if the input polygon is convex, we can reduce the upper time-bound toO(n ³ logm).     

On approximate solutions for robust convex semidefinite optimization problems

In this paper, we consider approximate solutions (\(\epsilon \)-solutions) for a convex semidefinite programming problem in the face of data uncertainty. Using robust optimization approach (worst-case approach), we prove an approximate optimality theorem and approximate duality theorems for \(\epsilon \)-solutions in robust convex semidefinite programming problem under the robust characteristic cone constraint qualification. Moreover, an example is given to illustrate the obtained results.     

凸可行问题的平行近似次梯度投影算法

对凸可行问题提出了包括上松弛的平行近似次梯度投影算法和加速平行近似次梯度投影算法．与序列近似次梯度投影算法相比, 平行近似次梯度投影算法(每次迭代同时运用多个凸集的近似次梯度超平面上的投影)能够保证迭代序列收敛到离各个凸集最近的点． 上松弛的迭代技术和含有外推因子的加速技术的应用, 减少了数据存储量, 提高了收 敛速度. 最后在较弱的条件下证明了算法的收敛性, 数值实验结果验证了算法的有效性和优越性.