On the Complexity of Semidefinite Programs

We show that the feasibility of a system of m linear inequalities over the cone of symmetric positive semidefinite matrices of order n can be tested in mn arithmetic operations with -bit numbers, where l is the maximum binary size of the input coefficients. We also show that any feasible system of dimension (m,n) has a solution X such that log||X|| .     

Equivalence of Two Nondegeneracy Conditions for Semidefinite Programs

Nondegeneracy assumptions are often needed in order to prove the local fast convergence of suitable algorithms as well as in the sensitivity analysis for semidefinite programs. One of the more standard nondegeneracy conditions is the geometric condition used by Alizadeh et al. (Math. Program. 77:111–128, 1997). On the other hand, Kanzow and Nagel (SIAM J. Optim. 15:654–672, 2005) recently introduced an algebraic condition that was used in order to prove, for the first time, the local quadratic convergence of a suitable algorithm for the solution of semidefinite programs without using the strict complementarity assumption. The aim of this paper is to show that these two nondegeneracy conditions are equivalent.     

含有模糊决策的线性分布式多目标规划

针对实际问题中决策变量通常是模糊的情况,讨论具有块角结构的含有模糊决策的线性分式多目标规划模型。使用α－水平集,建立了对应的α－多目标规划模型。为解决这类问题,设计了基于模糊模拟的遗传算法。数值例子表明,遗传算法很好地解决了这个问题。     

Solving Sum of Ratios Fractional Programs via Concave Minimization

This article presents an algorithm for globally solving a sum of ratios fractional programming problem. To solve this problem, the algorithm globally solves an equivalent concave minimization problem via a branch-and-bound search. The main work of the algorithm involves solving a sequence of convex programming problems that differ only in their objective function coefficients. Therefore, to solve efficiently these convex programming problems, an optimal solution to one problem can potentially be used to good advantage as a starting solution to the next problem.     

Technical Note: Some Structural Properties of a Newton-Type Method for Semidefinite Programs

Using the minimum function or the Fischer-Burmeister function, we obtain two reformulations of a semidefinite program as a nonlinear system of equations. Applying a Newton-type method to such a reformulation leads to a linear system of equations which has to be solved at each iteration. We discuss some properties of this linear system and show that the corresponding coefficient matrix is symmetric positive definite for the minimum function approach and positive definite but unsymmetric for the Fischer-Burmeister formulation.     

On the Pseudoconvexity of a Quadratic Fractional Function

In this paper we give a necessary and sufficient condition for the pseudoconvexity of a function f which is the ratio of a quadratic function over an affine function. The obtained results allow to suggest a simple algorithm to test the pseudoconvexity of f and also to characterize the pseudoconvexity of the sum of a linear and a linear fractional function.     

Global Optimization of 0-1 Hyperbolic Programs

We develop eight different mixed-integer convex programming reformulations of 0-1 hyperbolic programs. We obtain analytical results on the relative tightness of these formulations and propose a branch and bound algorithm for 0-1 hyperbolic programs. The main feature of the algorithm is that it reformulates the problem at every node of the search tree. We demonstrate that this algorithm has a superior convergence behavior than directly solving the relaxation derived at the root node. The algorithm is used to solve a discrete p-choice facility location problem for locating ten restaurants in the city of Edmonton.The research was supported in part by NSF awards DMII 95-02722 and BES 98-73586 to NVS.     

A Duality Theory for a Class of Generalized Fractional Programs

In generalized fractional programming, one seeks to minimize the maximum of a finite number of ratios. Such programs are, in general, nonconvex and consequently are difficult to solve. Here, we consider a particular case in which the ratio is the quotient of a quadratic form and a positive concave function. The dual of such a problem is constructed and a numerical example is given.     

Semidefinite bounds for the stability number of a graph via sums of squares of polynomials

Lovász and Schrijver (SIAM J. Optim. 1:166–190, 1991) have constructed semidefinite relaxations for the stable set polytope of a graph G = (V,E) by a sequence of lift-and-project operations; their procedure finds the stable set polytope in at most α(G) steps, where α(G) is the stability number of G. Two other hierarchies of semidefinite bounds for the stability number have been proposed by Lasserre (SIAM J. Optim. 11:796–817, 2001; Lecture Notes in Computer Science, Springer, Berlin Heidelberg New York, pp 293–303, 2001) and by de Klerk and Pasechnik (SIAM J. Optim. 12:875–892), which are based on relaxing nonnegativity of a polynomial by requiring the existence of a sum of squares decomposition. The hierarchy of Lasserre is known to converge in α(G) steps as it refines the hierarchy of Lovász and Schrijver, and de Klerk and Pasechnik conjecture that their hierarchy also finds the stability number after α(G) steps. We prove this conjecture for graphs with stability number at most 8 and we show that the hierarchy of Lasserre refines the hierarchy of de Klerk and Pasechnik.      

Small Ball Probabilities of Fractional Brownian Sheets via Fractional Integration Operators

We investigate the small ball problem for d-dimensional fractional Brownian sheets by functional analytic methods. For this reason we show that integration operators of Riemann–Liouville and Weyl type are very close in the sense of their approximation properties, i.e., the Kolmogorov and entropy numbers of their difference tend to zero exponentially. This allows us to carry over properties of the Weyl operator to the Riemann–Liouville one, leading to sharp small ball estimates for some fractional Brownian sheets. In particular, we extend Talagrand's estimate for the 2-dimensional Brownian sheet to the fractional case. When passing from dimension 1 to dimension d2, we use a quite general estimate for the Kolmogorov numbers of the tensor products of linear operators.     

Regularity via duality in calculus of variations and degenerate elliptic PDEs

A technique based on duality to obtain $H^1$ or other Sobolev regularity results for solutions of convex variational problems is presented. This technique, first developed in order to study the regularity of the pressure in the variational formulation of the Incompressible Euler equation, has been recently re-employed in Mean Field Games. Here, it is shown how to apply it to classical problems in relation with degenerate elliptic PDEs of p-Laplace type. This allows to recover many classical results via a different point of view, and to have inspiration for new ones. The applications include, among others, variational models for traffic congestion and more general minimization problems under divergence constraints, but the most interesting results are obtained in dynamical problems such as Mean Field Games with density constraints or density penalizations.     

Semidefinite representation of convex sets

Let be a semialgebraic set defined by multivariate polynomials g _i (x). Assume S is convex, compact and has nonempty interior. Let , and ∂ S (resp. ∂ S _i ) be the boundary of S (resp. S _i ). This paper, as does the subject of semidefinite programming (SDP), concerns linear matrix inequalities (LMIs). The set S is said to have an LMI representation if it equals the set of solutions to some LMI and it is known that some convex S may not be LMI representable (Helton and Vinnikov in Commun Pure Appl Math 60(5):654–674, 2007). A question arising from Nesterov and Nemirovski (SIAM studies in applied mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 1994), see Helton and Vinnikov in Commun Pure Appl Math 60(5):654–674, 2007 and Nemirovski in Plenary lecture, International Congress of Mathematicians (ICM), Madrid, Spain, 2006, is: given a subset S of , does there exist an LMI representable set Ŝ in some higher dimensional space whose projection down onto equals S. Such S is called semidefinite representable or SDP representable. This paper addresses the SDP representability problem. The following are the main contributions of this paper: (i) assume g _i (x) are all concave on S. If the positive definite Lagrange Hessian condition holds, i.e., the Hessian of the Lagrange function for optimization problem of minimizing any nonzero linear function ℓ ^T x on S is positive definite at the minimizer, then S is SDP representable. (ii) If each g _i (x) is either sos-concave ( − ∇² g _i (x) = W(x) ^T W(x) for some possibly nonsquare matrix polynomial W(x)) or strictly quasi-concave on S, then S is SDP representable. (iii) If each S _i is either sos-convex or poscurv-convex (S _i is compact convex, whose boundary has positive curvature and is nonsingular, i.e., ∇g _i (x) ≠ 0 on ∂ S _i ∩ S), then S is SDP representable. This also holds for S _i for which ∂ S _i ∩ S extends smoothly to the boundary of a poscurv-convex set containing S. (iv) We give the complexity of Schmüdgen and Putinar’s matrix Positivstellensatz, which are critical to the proofs of (i)–(iii).      

Fractional Weyl-Riesz Integrodifferentiation of Periodic Functions of Two Variables via the Periodization of the Riesz Kernel

We consider the periodization of the Riesz fractional integrals (Riesz potentials) of two variables and show that already in this case we come across different effects, depending on whether we use the repeated periodization, first in one variable, and afterwards in another one, or the so called double periodization. We show that the naturally introduced doubly-periodic Weyl-Riesz kernel of order 0< f <2 in general coincides with the periodization of the Riesz kernel, the repeated periodization being possible for all 0< f <2 , while the double one is applicable only for 0< f <1 . This is obtained as a realization of a certain general scheme of periodization, both repeated and double versions. We prove statements on coincidence of the corresponding periodic and nonperiodic convolutions and give an application to the case of the Riesz kernel.     

与分数阶热半群相关的平方函数刻画Hardy空间

令L=-△+V是一个Schr(o)dinger算子,V是一个满足逆H(o)lder不等式的非负位势.在本文中,首先引入由分数阶热半群{e-tLα)t＞0生成的Lusin面积函数,其次通过从属性公式和半群的正则性,我们用平方函数刻画与L相关的Hardy空间HnL/(n+γ)(Rn).     

Minimizing Polynomials via Sum of Squares over the Gradient Ideal

A method is proposed for finding the global minimum of a multivariate polynomial via sum of squares (SOS) relaxation over its gradient variety. That variety consists of all points where the gradient is zero and it need not be finite. A polynomial which is nonnegative on its gradient variety is shown to be SOS modulo its gradient ideal, provided the gradient ideal is radical or the polynomial is strictly positive on the real gradient variety. This opens up the possibility of solving previously intractable polynomial optimization problems. The related problem of constrained minimization is also considered, and numerical examples are discussed. Experiments show that our method using the gradient variety outperforms prior SOS methods.