The Strong Convergence of Subgradients of Convex Functions Along Directions: Perspectives and Open Problems

In this note, some questions concerning the strong convergence of subgradients of convex functions along a given direction are recalled and posed. It is shown that some open problems in literature are linked to that of the existence of limits of subgradients from subdifferentials along a given segment.     

A geometrical interpretation of the Hungarian method

In this paper a geometrical interpretation of the Hungarian method will be given. This special algorithm to solve the dual transportation problem is not restricted to the edges of the convex polyhedron of feasible solutions. Each covering-step can be considered as a determination of a direction of steepest descent, each reduction-step as movement along that direction to a boundary point of the polyhedron. The dimension of the face that will be crossed depends on the covering that is chosen.     

Directional End of a Convex Set: Theory and Applications

A point of a convex set belongs to its end in a given direction when this direction is not feasible at that point. This paper analyzes the properties of the directional end of general convex sets and closed convex sets (for which the directional ends are connected by arcs) as well as the relationship between the directional end and certain concepts on the illumination of convex bodies. The paper includes applications of the directional end to the theory of linear systems.     

Convex mean curvature flow with a forcing term in direction of the position vector

A smooth, compact and strictly convex hypersurface evolving in ℝ ⁿ⁺¹ along its mean curvature vector plus a forcing term in the direction of its position vector is studied in this paper. We show that the convexity is preserving as the case of mean curvature flow, and the evolving convex hypersurfaces may shrink to a point in finite time if the forcing term is small, or exist for all time and expand to infinity if it is large enough. The flow can converge to a round sphere if the forcing term satisfies suitable conditions which will be given in the paper. Long-time existence and convergence of normalization of the flow are also investigated.     

Shadow systems of convex sets

Ans-system of convex sets is the system of shadows of a given convex set cast on to a subspace by a beam of light whose direction varies. Here the convexity properties ofs-systems are investigated, and, in the final section, a relationship with the projection functions of convex sets is established.     

A generalized subgradient method with relaxation step

We study conditions for convergence of a generalized subgradient algorithm in which a relaxation step is taken in a direction, which is a convex combination of possibly all previously generated subgradients. A simple condition for convergence is given and conditions that guarantee a linear convergence rate are also presented. We show that choosing the steplength parameter and convex combination of subgradients in a certain sense optimally is equivalent to solving a minimum norm quadratic programming problem. It is also shown that if the direction is restricted to be a convex combination of the current subgradient and the previous direction, then an optimal choice of stepsize and direction is equivalent to the Camerini—Fratta—Maffioli modification of the subgradient method.Research supported by the Swedish Research Council for Engineering Sciences (TFR).     

Example of a displacement convex functional of first order

We present a family of first-order functionals which are displacement convex, that is convex along the geodesics induced by the quadratic transportation distance on the circle. The displacement convexity implies the existence and uniqueness of gradient flows of the given functionals. More precisely, we show the existence and uniqueness of gradient-flow solutions of a class of fourth-order degenerate parabolic equations with periodic boundary data. Moreover, positivity of the absolutely continuous part of the solutions is preserved along the flow.     

An algorithm for solving the problem of convex programming with several objective functions

This work aims to establish an algorithm for solving the problem of convex programming with several objective-functions, with linear constraints. Starting from the idea of Rosen’s algorithm for solving the problem of convex programming with linear constraints, and taking into account the solution concept from multidimensional programming, represented by a program which reaches ”the best compromise”, we are extending this method in the case of multidimensional programming. The concept of direction of minimization is introduced, and a necessary and sufficient condition is given for as ∈R ⁿ direction to be a direction of minimization, according to the values of a criteria ensemble in a given point. The algorithm is interactive, and the intervention of the decident is minimal. The two numerical examples presented at the end validate the algorithm.     

Representing orders on the plane by translating convex figures

Given a finite collection of disjoint, convex figures on the plane, is it possible to assign to each a single direction of motion so that this collection of figures may be separated, through an arbitrary large distance, by translating each figure one at a time, along its assigned direction? We present a computational model for this separability problem based on the theory of ordered sets.     

A new LQP alternating direction method for solving variational inequality problems with separable structure

We presented a new logarithmic-quadratic proximal alternating direction scheme for the separable constrained convex programming problem. The predictor is obtained by solving series of related systems of non-linear equations in a parallel wise. The new iterate is obtained by searching the optimal step size along a new descent direction. The new direction is obtained by the linear combination of two descent directions. Global convergence of the proposed method is proved under certain assumptions. We show the O(1 / t) convergence rate for the parallel LQP alternating direction method.     

On convexity properties of ψ-direct sums of Banach spaces

The ψ-direct sum of Banach spaces is strictly convex (respectively, uniformly convex, locally uniformly convex, uniformly convex in every direction) if each of the Banach spaces are strictly convex (respectively, uniformly convex, locally uniformly convex, uniformly convex in every direction) and the corresponding ψ-norm is strictly convex.     

Some convergence properties of the conjugate gradient method

It has been conjectured that the conjugate gradient method for minimizing functions of several variables has a superlinear rate of convergence, but Crowder and Wolfe show by example that the conjecture is false. Now the stronger result is given that, if the objective function is a convex quadratic and if the initial search direction is an arbitrary downhill direction, then either termination occurs or the rate of convergence is only linear, the second possibility being more usual. Relations between the starting point and the initial search direction that are necessary and sufficient for termination in the quadratic case are studied.     

Estimating Support Functions of Random Polytopes via Orlicz Norms

We study the expected value of support functions of random polytopes in a certain direction, where the random polytope is given by independent random vectors uniformly distributed in an isotropic convex body. All results are obtained using probabilistic estimates in terms of Orlicz norms that were not used in this connection before.     

Lower semicontinuous functionals with uniform sublevel sets

In this paper, lower semicontinuous functionals with uniform sublevel sets are investigated, where the sublevel sets are linear shifts of a set in a fixed direction. The extended real-valued functionals are defined on a topological vector space. Conditions are given under which they are proper, finite-valued, continuous, convex, sublinear, strictly quasi-convex, strictly quasi-concave or monotone. We apply the functionals to the separation of not necessarily convex sets.     

Boundary differentiability of solutions of elliptic equations on convex domains

The boundary differentiability is shown for solutions of elliptic differential equations in non-divergence form on convex domains. Counterexamples are given to illustrate that the result is optimal in the sense that gradients of solutions exist but may be discontinuous along boundaries.     

Optimal Smoothing for Convex Polytopes

It is proved that, given a convex polytope P in Rⁿ, togetherwith a collection of compact convex subsets in the interiorof each facet of P, there exists a smooth convex body arbitrarilyclose to P that coincides with each facet precisely along theprescribed sets, and has positive curvature elsewhere. 2000Mathematics Subject Classification 53A07, 52B11, 53C45.     

A new reduced gradient method for solving linearly constrained multiobjective optimization problems

In this paper, we consider the linearly constrained multiobjective minimization, and we propose a new reduced gradient method for solving this problem. Our approach solves iteratively a convex quadratic optimization subproblem to calculate a suitable descent direction for all the objective functions, and then use a bisection algorithm to find an optimal stepsize along this direction. We prove, under natural assumptions, that the proposed algorithm is well-defined and converges globally to Pareto critical points of the problem. Finally, this algorithm is implemented in the MATLAB environment and comparative results of numerical experiments are reported.     

Non-interactive geometric probing: Reconstructing non-convex polygons

We address the problem of characterizing polygonal shapes that can be reconstructed from a class of scanners that have asymmetric resolution. We approach this problem using the methodology of non-interactive probing.

Laser raster scanners provide very high precision along the direction of a scan, but it is not practical to place scans very close to each other. A system capable of generating an omni-directional scan pattern can make a series of directional measurements sufficient to permit the reconstruction of a scanned polygon based on the position of edge crossings and the path of the scanning beam between edge crossings. We provide a procedure to reconstruct a polygon from such a data set, as well as a characterization of the shapes that can be reconstructed given a particular scan density. Our system applies to both concave and convex polygons, as well as to polygons containing holes.     

An implementation of a reduced subgradient method via Luenberger-Mokhtar variant

We present an implementable algorithm for minimizing a convex function which is not necessarily differentiable subject to linear equality constraints and to nonnegativity bounds on the variables. The algorithm is based on extending the variant proposed by Luenberger to the nondifferentiable case and using the bundle techniques introduced by Lemaréchal to approximate the subdifferential of the objective function. In particular, at each iteration, we compute a search direction by solving a quadratic subproblem, and an inexact line search along this direction yields a decrease in the objective value. Under some assumptions, the convergence of the proposed algorithm is analysed. Finally, some numerical results are presented, which show that the algorithm performs efficiently.