Hessian measures of semi-convex functions and applications to support measures of convex bodies

This paper originates from the investigation of support measures of convex bodies (sets of positive reach), which form a central subject in convex geometry and also represent an important tool in related fields. We show that these measures are absolutely continuous with respect to Hausdorff measures of appropriate dimensions, and we determine the Radon-Nikodym derivatives explicitly on sets of σ-finite Hausdorff measure. The results which we obtain in the setting of the theory of convex bodies (sets of positive reach) are achieved as applications of various new results on Hessian measures of convex (semi-convex) functions. Among these are a Crofton formula, results on the absolute continuity of Hessian measures, and a duality theorem which relates the Hessian measures of a convex function to those of the conjugate function. In particular, it turns out that curvature and surface area measures of a convex body K are the Hessian measures of special functions, namely the distance function and the support function of K. Received: 15 July 1999     

Dual Semidefinite Programs Without Duality Gaps for a Class of Convex Minimax Programs

In this paper, we introduce a new dual program, which is representable as a semidefinite linear programming problem, for a primal convex minimax programming problem, and we show that there is no duality gap between the primal and the dual whenever the functions involved are sum-of-squares convex polynomials. Under a suitable constraint qualification, we derive strong duality results for this class of minimax problems. Consequently, we present applications of our results to robust sum-of-squares convex programming problems under data uncertainty and to minimax fractional programming problems with sum-of-squares convex polynomials. We obtain these results by first establishing sum-of-squares polynomial representations of non-negativity of a convex max function over a system of sum-of-squares convex constraints. The new class of sum-of-squares convex polynomials is an important subclass of convex polynomials and it includes convex quadratic functions and separable convex polynomials. The sum-of-squares convexity of polynomials can numerically be checked by solving semidefinite programming problems whereas numerically verifying convexity of polynomials is generally very hard.     

Some geometrical aspects of semidefinite linear complementarity problems

This article studies some geometrical aspects of the semidefinite linear complementarity problem (SDLCP), which can be viewed as a generalization of the well-known linear complementarity problem (LCP). SDLCP is a special case of a complementarity problem over a closed convex cone, where the cone considered is the closed convex cone of positive semidefinite matrices. It arises naturally in the unified formulation of a pair of primal-dual semidefinite programming problems. In this article, we introduce the notion of complementary cones in the semidefinite setting using the faces of the cone of positive semidefinite matrices and show that unlike complementary cones induced by an LCP, semidefinite complementary cones need not be closed. However, under R ₀-property of the linear transformation, closedness of all the semidefinite complementary cones induced by L is ensured. We also introduce the notion of a principal subtransformation with respect to a face of the cone of positive semidefinite matrices and show that for a self-adjoint linear transformation, strict copositivity is equivalent to strict semimonotonicity of each principal subtransformation. Besides the above, various other solution properties of SDLCP will be interpreted and studied geometrically.     

Approximation of rank function and its application to the nearest low-rank correlation matrix

The rank function rank(.) is neither continuous nor convex which brings much difficulty to the solution of rank minimization problems. In this paper, we provide a unified framework to construct the approximation functions of rank(.), and study their favorable properties. Particularly, with two families of approximation functions, we propose a convex relaxation method for the rank minimization problems with positive semidefinite cone constraints, and illustrate its application by computing the nearest low-rank correlation matrix. Numerical results indicate that this convex relaxation method is comparable with the sequential semismooth Newton method (Li and Qi in SIAM J Optim 21:1641–1666, 2011) and the majorized penalty approach (Gao and Sun, 2010) in terms of the quality of solutions.     

ω-非常凸空间与ω-非常光滑空间

本文研究了ω-非常凸空间和ω-非常光滑空间的问题.利用局部自反原理和切片证明了ω-非常凸空间和ω-非常光滑空间的对偶关系,讨论了ω-非常凸空间和ω-非常光滑空间与其它凸性和光滑性的关系,给出了ω-非常凸空间与ω-非常光滑空间的若干特征刻画,所得结果完善了关于Banach空间凸性与光滑性理论的研究.     

On Extensions of the Frank-Wolfe Theorems

In this paper we consider optimization problems defined by a quadratic objective function and a finite number of quadratic inequality constraints. Given that the objective function is bounded over the feasible set, we present a comprehensive study of the conditions under which the optimal solution set is nonempty, thus extending the so-called Frank-Wolfe theorem. In particular, we first prove a general continuity result for the solution set defined by a system of convex quadratic inequalities. This result implies immediately that the optimal solution set of the aforementioned problem is nonempty when all the quadratic functions involved are convex. In the absence of the convexity of the objective function, we give examples showing that the optimal solution set may be empty either when there are two or more convex quadratic constraints, or when the Hessian of the objective function has two or more negative eigenvalues. In the case when there exists only one convex quadratic inequality constraint (together with other linear constraints), or when the constraint functions are all convex quadratic and the objective function is quasi-convex (thus allowing one negative eigenvalue in its Hessian matrix), we prove that the optimal solution set is nonempty.     

Hidden conic quadratic representation of some nonconvex quadratic optimization problems

The problem of minimizing a quadratic objective function subject to one or two quadratic constraints is known to have a hidden convexity property, even when the quadratic forms are indefinite. The equivalent convex problem is a semidefinite one, and the equivalence is based on the celebrated S-lemma. In this paper, we show that when the quadratic forms are simultaneously diagonalizable (SD), it is possible to derive an equivalent convex problem, which is a conic quadratic (CQ) one, and as such is significantly more tractable than a semidefinite problem. The SD condition holds for free for many problems arising in applications, in particular, when deriving robust counterparts of quadratic, or conic quadratic, constraints affected by implementation error. The proof of the hidden CQ property is constructive and does not rely on the S-lemma. This fact may be significant in discovering hidden convexity in some nonquadratic problems.     

Constructing a sequence of discrete Hessian matrices of an SC 1 function uniformly convergent to the generalized Hessian matrix

We construct a uniform approximation for generalized Hessian matrix of an SC ¹ function. Using the discrete gradient and the extended second order derivative, we define the discrete Hessian matrix. We construct a sequence of sets, where each set is composed of discrete Hessian matrices. We first show some new properties of SC ¹ functions. Then, we prove that for SC ¹ functions the sequence of the set of discrete Hessian matrices is uniformly convergent to the generalized Hessian matrix.      

<Emphasis Type="Italic">ε</Emphasis>-Optimality and <Emphasis Type="Italic">ε</Emphasis>-Lagrangian Duality for a Nonconvex Programming Problem with an Infinite Number of Constraints

In this paper, ε-optimality conditions are given for a nonconvex programming problem which has an infinite number of constraints. The objective function and the constraint functions are supposed to be locally Lipschitz on a Banach space. In a first part, we introduce the concept of regular ε-solution and propose a generalization of the Karush-Kuhn-Tucker conditions. These conditions are up to ε and are obtained by weakening the classical complementarity conditions. Furthermore, they are satisfied without assuming any constraint qualification. Then, we prove that these conditions are also sufficient for ε-optimality when the constraints are convex and the objective function is ε-semiconvex. In a second part, we define quasisaddlepoints associated with an ε-Lagrangian functional and we investigate their relationships with the generalized KKT conditions. In particular, we formulate a Wolfe-type dual problem which allows us to present ε-duality theorems and relationships between the KKT conditions and regular ε-solutions for the dual. Finally, we apply these results to two important infinite programming problems: the cone-constrained convex problem and the semidefinite programming problem.     

Dogleg路径信赖域方法

本文提出一类新的解无约束最优化问题的信整域方法。这类方法是通过对一般对称矩阵的Bunch-Parlett分解来产生搜索路径。它们既可以解目标函数是二次可微的也可以解目标函数是非二次可微的最优化问题，并且在由算法得到点列的任意聚点上，二次连续可微的目标函数的Hesse阵都是正定或半正定的。我们证明在一些较弱的条件下，算法是整体收敛的；对一致凸函数，是二次收敛的。一些数值结果表明这种新的方法是非常有效的。     

Convex Underestimation of Twice Continuously Differentiable Functions by Piecewise Quadratic Perturbation: Spline αBB Underestimators

This paper describes the construction of convex underestimators for twice continuously differentiable functions over box domains through piecewise quadratic perturbation functions. A refinement of the classical α BB convex underestimator, the underestimators derived through this approach may be significantly tighter than the classical αBB underestimator. The convex underestimator is the difference of the nonconvex function f and a smooth, piecewise quadratic, perturbation function, q. The convexity of the underestimator is guaranteed through an analysis of the eigenvalues of the Hessian of f over all subdomains of a partition of the original box domain. Smoothness properties of the piecewise quadratic perturbation function are derived in a manner analogous to that of spline construction.     

Convexity of Images of Convex Sets under Smooth Maps

The article presents sufficient conditions for convexity of images of convex sets under smooth mappings of finite-dimensional spaces of the same dimensions. Applications of the results to nonlinear programming are discussed. Efficient convexity tests are derived for images of Lebesgue sets of convex functions under C ^{1, 1} maps.     

Convergence Properties of Dikin’s Affine Scaling Algorithm for Nonconvex Quadratic Minimization

We study convergence properties of Dikins affine scaling algorithm applied to nonconvex quadratic minimization. First, we show that the objective function value either diverges or converges Q-linearly to a limit. Using this result, we show that, in the case of box constraints, the iterates converge to a unique point satisfying first-order and weak second-order optimality conditions, assuming the objective function Hessian Q is rank dominant with respect to the principal submatrices that are maximally positive semidefinite. Such Q include matrices that are positive semidefinite or negative semidefinite or nondegenerate or have negative diagonals. Preliminary numerical experience is reported.     

Riemannian convexity of functionals

This paper extends the Riemannian convexity concept to action functionals defined by multiple integrals associated to Lagrangian differential forms on first order jet bundles. The main results of this paper are based on the geodesic deformations theory and their impact on functionals in Riemannian setting. They include the basic properties of Riemannian convex functionals, the Riemannian convexity of functionals associated to differential m-forms or to Lagrangians of class C ¹ respectively C ², the generalization to invexity and geometric meaningful convex functionals. Riemannian convexity of functionals is the central ingredient for global optimization. We illustrate the novel features of this theory, as well as its versatility, by introducing new definitions, theorems and algorithms that bear upon the currently active subject of functionals in variational calculus and optimal control. In fact so deep rooted is the convexity notion that nonconvex problems are tackled by devising appropriate convex approximations.     

When is rounding allowed in integer nonlinear optimization?

In this paper we consider nonlinear integer optimization problems. Nonlinear integer programming has mainly been studied for special classes, such as convex and concave objective functions and polyhedral constraints. In this paper we follow an other approach which is not based on convexity or concavity. Studying geometric properties of the level sets and the feasible region, we identify cases in which an integer minimizer of a nonlinear program can be found by rounding (up or down) the coordinates of a solution to its continuous relaxation. We call this property rounding property. If it is satisfied, it enables us (for fixed dimension) to solve an integer programming problem in the same time complexity as its continuous relaxation. We also investigate the strong rounding property which allows rounding a solution to the continuous relaxation to the next integer solution and in turn yields that the integer version can be solved in the same time complexity as its continuous relaxation for arbitrary dimensions.     

Regularity Properties of Optimal Controls with Application to Discrete Approximation

This paper is directed to the analysis of regularity properties of optimal solutions for a nonlinear control problem with convex control constraints. Since the problem formulation is given typically in L -terms, we introduce first the essential limit set as a tool for the local investigation of L -functions. Under second-order conditions of the coercivity type on the solution, a structural result is obtained characterizing the local behavior of the optimal control by means of Lipschitz continuous functions. Further, the consequences for certain discrete approximations are discussed; for uniquely solvable problems, we show the Lipschitz continuity of the optimal control.     

Criteria for Unconstrained Global Optimization

We develop criteria for the existence and uniqueness of the global minima of a continuous bounded function on a noncompact set. Special attention is given to the problem of parameter estimation via minimization of the sum of squares in nonlinear regression and maximum likelihood. Definitions of local convexity and unimodality are given using the level set. A fundamental theorem of nonconvex optimization is formulated: If a function approaches the minimal limiting value at the boundary of the optimization domain from below and its Hessian matrix is positive definite at the point where the gradient vanishes, then the function has a unique minimum. It is shown that the local convexity level of the sum of squares is equal to the minimal squared radius of the regression curvature. A new multimodal function is introduced, the decomposition function, which can be represented as the composition of a convex function and a nonlinear function from the argument space to a space of larger dimension. Several general global criteria based on majorization and minorization functions are formulated.     

On cone of nonsymmetric positive semidefinite matrices

In this paper, we analyze and characterize the cone of nonsymmetric positive semidefinite matrices (NS-psd). Firstly, we study basic properties of the geometry of the NS-psd cone and show that it is a hyperbolic but not homogeneous cone. Secondly, we prove that the NS-psd cone is a maximal convex subcone of P₀-matrix cone which is not convex. But the interior of the NS-psd cone is not a maximal convex subcone of P-matrix cone. As the byproducts, some new sufficient and necessary conditions for a nonsymmetric matrix to be positive semidefinite are given. Finally, we present some properties of metric projection onto the NS-psd cone.     

Semidefinite optimization models for limit and shakedown analysis problems involving matrix spreads

Limit and shakedown analysis problems of Computational Mechanics lead to convex optimization problems, characterized by linear objective functions, linear equality constraints and constraints expressing the restrictions imposed by the material strength. It is shown that two important strength criteria, the Mohr–Coulomb and the Tresca criterion, can be represented as systems of semidefinite constraints, leading this way to semidefinite programming problems.