On the convergence of the entropy-exponential penalty trajectories and generalized proximal point methods in semidefinite optimization

The convergence of primal and dual central paths associated to entropy and exponential functions, respectively, for semidefinite programming problem are studied in this paper. It is proved that the primal path converges to the analytic center of the primal optimal set with respect to the entropy function, the dual path converges to a point in the dual optimal set and the primal-dual path associated to this paths converges to a point in the primal-dual optimal set. As an application, the generalized proximal point method with the Kullback-Leibler distance applied to semidefinite programming problems is considered. The convergence of the primal proximal sequence to the analytic center of the primal optimal set with respect to the entropy function is established and the convergence of a particular weighted dual proximal sequence to a point in the dual optimal set is obtained.     

ON SOME PROPERTIES OF SOLUTIONS TO SEMIDEFINITE PROGRAMMING

It is well known that for symmetric linear programming there exists a strictly complementary solution if the primal and the dual problems are both feasible. However, this is not necessary true for symmetric or general semide finite programming even if both the primal problem and its dual problem are strictly feasible. Some other properties are also concerned.     

Robust least square semidefinite programming with applications

In this paper, we consider a least square semidefinite programming problem under ellipsoidal data uncertainty. We show that the robustification of this uncertain problem can be reformulated as a semidefinite linear programming problem with an additional second-order cone constraint. We then provide an explicit quantitative sensitivity analysis on how the solution under the robustification depends on the size/shape of the ellipsoidal data uncertainty set. Next, we prove that, under suitable constraint qualifications, the reformulation has zero duality gap with its dual problem, even when the primal problem itself is infeasible. The dual problem is equivalent to minimizing a smooth objective function over the Cartesian product of second-order cones and the Euclidean space, which is easy to project onto. Thus, we propose a simple variant of the spectral projected gradient method (Birgin et al. in SIAM J. Optim. 10:1196–1211, 2000) to solve the dual problem. While it is well-known that any accumulation point of the sequence generated from the algorithm is a dual optimal solution, we show in addition that the dual objective value along the sequence generated converges to a finite value if and only if the primal problem is feasible, again under suitable constraint qualifications. This latter fact leads to a simple certificate for primal infeasibility in situations when the primal feasible set lies in a known compact set. As an application, we consider robust correlation stress testing where data uncertainty arises due to untimely recording of portfolio holdings. In our computational experiments on this particular application, our algorithm performs reasonably well on medium-sized problems for real data when finding the optimal solution (if exists) or identifying primal infeasibility, and usually outperforms the standard interior-point solver SDPT3 in terms of CPU time.     

Generalized Lagrangian duality for nonconvex polynomial programs with polynomial multipliers

In this paper, under the existence of a certificate of nonnegativity of the objective function over the given constraint set, we present saddle-point global optimality conditions and a generalized Lagrangian duality theorem for (not necessarily convex) polynomial optimization problems, where the Lagrange multipliers are polynomials. We show that the nonnegativity certificate together with the archimedean condition guarantees that the values of the Lasserre hierarchy of semidefinite programming (SDP) relaxations of the primal polynomial problem converge asymptotically to the common primal–dual value. We then show that the known regularity conditions that guarantee finite convergence of the Lasserre hierarchy also ensure that the nonnegativity certificate holds and the values of the SDP relaxations converge finitely to the common primal–dual value. Finally, we provide classes of nonconvex polynomial optimization problems for which the Slater condition guarantees the required nonnegativity certificate and the common primal–dual value with constant multipliers and the dual problems can be reformulated as semidefinite programs. These classes include some separable polynomial programs and quadratic optimization problems with quadratic constraints that admit certain hidden convexity. We also give several numerical examples that illustrate our results.     

On the global optimality of generalized trust region subproblems

Quadratically constrained quadratic programming is an important class of optimization problems. We consider the case with one quadratic constraint. Since both the objective function and its constraint can be neither convex nor concave, it is also known as the ‘generalized trust region subproblem.’ The theory and algorithms for this problem have been well studied under the Slater condition. In this article, we analyse the duality property between the primal problem and its Lagrangian dual problem, and discuss the attainability of the optimal primal solution without the Slater condition. The relations between the Lagrangian dual and semidefinite programming dual is also given.     

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.     

A primal–dual interior point method for nonlinear semidefinite programming

This paper is concerned with a primal–dual interior point method for solving nonlinear semidefinite programming problems. The method consists of the outer iteration (SDPIP) that finds a KKT point and the inner iteration (SDPLS) that calculates an approximate barrier KKT point. Algorithm SDPLS uses a commutative class of Newton-like directions for the generation of line search directions. By combining the primal barrier penalty function and the primal–dual barrier function, a new primal–dual merit function is proposed. We prove the global convergence property of our method. Finally some numerical experiments are given.     

An exact duality theory for semidefinite programming and its complexity implications

In this paper, an exact dual is derived for Semidefinite Programming (SDP), for which strong duality properties hold without any regularity assumptions. Its main features are: (i) The new dual is an explicit semidefinite program with polynomially many variables and polynomial size coefficient bitlengths. (ii) If the primal is feasible, then it is bounded if and only if the dual is feasible. (iii) When the primal is feasible and bounded, then its optimum value equals that of the dual, or in other words, there is no duality gap. Further, the dual attains this common optimum value. (iv) It yields a precise theorem of the alternative for semidefinite inequality systems, i.e. a characterization of theinfeasibility of a semidefinite inequality in terms of thefeasibility of another polynomial size semidefinite inequality. The standard duality for linear programming satisfies all of the above features, but no such explicit gap-free dual program of polynomial size was previously known for SDP, without Slater-like conditions being assumed. The dual is then applied to derive certain complexity results for SDP. The decision problem of Semidefinite Feasibility (SDFP), which asks to determine if a given semidefinite inequality system is feasible, is the central problem of interest, he complexity of SDFP is unknown, but we show the following: (i) In the Turing machine model, the membership or nonmembership of SDFP in NP and Co-NP is simultaneous; hence SDFP is not NP-Complete unless NP=Co-NP. (ii) In the real number model of Blum, Shub and Smale, SDFP is in NP∩CoNP.     

Duality theories in nonlinear semidefinite programming

We consider the duality theories in nonlinear semidefinite programming. Some duality theorems are established to show the important relations among the optimal solutions and optimal values of the primal, the dual and the saddle point problems of nonlinear semidefinite programming.     

On the Central Paths in Symmetric Cone Programming

This paper is devoted to the study of optimal solutions of symmetric cone programs by means of the asymptotic behavior of central paths with respect to a broad class of barrier functions. This class is, for instance, larger than that typically found in the literature for semidefinite positive programming. In this general framework, we prove the existence and the convergence of primal, dual and primal–dual central paths. We are then able to establish concrete characterizations of the limit points of these central paths for specific subclasses. Indeed, for the class of barrier functions defined at the origin, we prove that the limit point of a primal central path minimizes the corresponding barrier function over the solution set of the studied symmetric cone program. In addition, we show that the limit points of the primal and dual central paths lie in the relative interior of the primal and dual solution sets for the case of the logarithm and modified logarithm barriers.     

Chordal decomposition in operator-splitting methods for sparse semidefinite programs

Mathematical Programming - We employ chordal decomposition to reformulate a large and sparse semidefinite program (SDP), either in primal or dual standard form, into an equivalent SDP with smaller...     

Semidefinite programming for the educational testing problem

Methods for solving the educational testing problem which arises from statistics are considered. The problem is to find lower bounds for the reliability of the total score on a test (or subtests) whose items are not parallel using data from a single test administration. We formulate the problem as an optimization problem with a linear objective function and semidefinite constraints. We maintain exact primal and dual feasibility during the course of the algorithm. The search direction is found using an inexact Gauss–Newton method rather than a Newton method on a symmetrized system. Computational results illustrating the robustness of the algorithm are successfully exploited. Research supported by King Fahd University of Petroleum and Minerals under Project FT/2005–2007.     

The minimal cone for conic linear programming

It is known that the minimal cone for the constraint system of a conic linear programming problem is a key component in obtaining strong duality without any constraint qualification. For problems in either primal or dual form, the minimal cone can be written down explicitly in terms of the problem data. However, due to possible lack of closure, explicit expressions for the dual cone of the minimal cone cannot be obtained in general. In the particular case of semidefinite programming, an explicit expression for the dual cone of the minimal cone allows for a dual program of polynomial size that satisfies strong duality. In this paper we develop a recursive procedure to obtain the minimal cone and its dual cone. In particular, for conic problems with so-called nice cones, we obtain explicit expressions for the cones involved in the dual recursive procedure. As an example of this approach, the well-known duals that satisfy strong duality for semidefinite programming problems are obtained. The relation between this approach and a facial reduction algorithm is also discussed.     

Goal-oriented r-adaptivity based on the evaluation of the physical and material residual

This contribution is concerned with goal–oriented r-adaptivity based on energy minimization principles for the primal and the dual problem. We obtain a material residual of the primal and of the dual problem, which are indicators for non–optimal finite element meshes. For goal–oriented r-adaptivity we have to optimize the mesh with respect to the dual solution, because the error of a local quantity of interest depends on the error in the corresponding dual solution. We use the material residual of the primal and dual problem in order to obtain a procedure for mesh optimization with respect to a local quantity of interest. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Convergent Lagrangian heuristics for nonlinear minimum cost network flows

We consider the separable nonlinear and strictly convex single-commodity network flow problem (SSCNFP). We develop a computational scheme for generating a primal feasible solution from any Lagrangian dual vector; this is referred to as “early primal recovery”. It is motivated by the desire to obtain a primal feasible vector before convergence of a Lagrangian scheme; such a vector is not available from a Lagrangian dual vector unless it is optimal. The scheme is constructed such that if we apply it from a sequence of Lagrangian dual vectors that converge to an optimal one, then the resulting primal (feasible) vectors converge to the unique optimal primal flow vector. It is therefore also a convergent Lagrangian heuristic, akin to those primarily devised within the field of combinatorial optimization but with the contrasting and striking advantage that it is guaranteed to yield a primal optimal solution in the limit. Thereby we also gain access to a new stopping criterion for any Lagrangian dual algorithm for the problem, which is of interest in particular if the SSCNFP arises as a subproblem in a more complex model. We construct instances of convergent Lagrangian heuristics that are based on graph searches within the residual graph, and therefore are efficiently implementable; in particular we consider two shortest path based heuristics that are based on the optimality conditions of the original problem. Numerical experiments report on the relative efficiency and accuracy of the various schemes.     

THE CENTRAL PATH IN SMOOTH CONVEX SEMIDEFINITE PROGRAMS

Abstract

In this paper we study the welldefinedness of the central path associated to a nonlinear convex semidefinite programming problem with smooth objective and constraint functions. Under standard assumptions, we prove that the existence of the central path is equivalent to the nonemptiness and boundedness of the optimal set. Other equivalent conditions are given, such as the existence of a strictly dual feasible point or the existence of a single central point. The monotonic behavior of the primal and dual logarithmic barriers and of the primal and dual objective functions along the trajectory is also discussed. The existence and optimality of cluster points is established and finally, under the additional assumption of analyticity of the data functions, the convergence of the primal-dual trajectory is proved.     

Applications of gauge duality in robust principal component analysis and semidefinite programming

Gauge duality theory was originated by Freund (1987), and was recently further investigated by Friedlander et al. (2014). When solving some matrix optimization problems via gauge dual, one is usually able to avoid full matrix decompositions such as singular value and/or eigenvalue decompositions. In such an approach, a gauge dual problem is solved in the first stage, and then an optimal solution to the primal problem can be recovered from the dual optimal solution obtained in the first stage. Recently, this theory has been applied to a class of semidefinite programming (SDP) problems with promising numerical results by Friedlander and Macêdo (2016). We establish some theoretical results on applying the gauge duality theory to robust principal component analysis (PCA) and general SDP. For each problem, we present its gauge dual problem, characterize the optimality conditions for the primal-dual gauge pair, and validate a way to recover a primal optimal solution from a dual one. These results are extensions of Friedlander and Macêdo (2016) from nuclear norm regularization to robust PCA and from a special class of SDP which requires the coefficient matrix in the linear objective to be positive definite to SDP problems without this restriction. Our results provide further understanding in the potential advantages and disadvantages of the gauge duality theory.     

Complementarity and nondegeneracy in semidefinite programming

Primal and dual nondegeneracy conditions are defined for semidefinite programming. Given the existence of primal and dual solutions, it is shown that primal nondegeneracy implies a unique dual solution and that dual nondegeneracy implies a unique primal solution. The converses hold if strict complementarity is assumed. Primal and dual nondegeneracy assumptions do not imply strict complementarity, as they do in LP. The primal and dual nondegeneracy assumptions imply a range of possible ranks for primal and dual solutionsX andZ. This is in contrast with LP where nondegeneracy assumptions exactly determine the number of variables which are zero. It is shown that primal and dual nondegeneracy and strict complementarity all hold generically. Numerical experiments suggest probability distributions for the ranks ofX andZ which are consistent with the nondegeneracy conditions. Supported in part by the U.S. National Science Foundation grant CCR-9625955. Supported in part by U.S. National Science Foundation grant CCR-9501941 and the U.S. Office of Naval Research grant N00014-96-1-0704. Supported in part by U.S. National Science Foundation grant CCR-9401119.     

A new class of polynomial primal–dual methods for linear and semidefinite optimization

We propose a new class of primal–dual methods for linear optimization (LO). By using some new analysis tools, we prove that the large-update method for LO based on the new search direction has a polynomial complexity of O(n^4/(4+ρ)log(n/ε)) iterations, where ρ∈[0,2] is a parameter used in the system defining the search direction. If ρ=0, our results reproduce the well-known complexity of the standard primal–dual Newton method for LO. At each iteration, our algorithm needs only to solve a linear equation system. An extension of the algorithms to semidefinite optimization is also presented.     

Dual interior point methods for linear semidefinite programming problems

Dual interior point methods for solving linear semidefinite programming problems are proposed. These methods are an extension of dual barrier-projection methods for linear programs. It is shown that the proposed methods converge locally at a linear rate provided that the solutions to the primal and dual problems are nondegenerate.