Let n greater than or equal to 1 and f : R-n --> R a convex function. Given distinct points z(1), z(2).... z(N) in R-n we consider the problem of finding a quadratic function g : Rn --> R such that parallel to[f...
详细信息
Let n greater than or equal to 1 and f : R-n --> R a convex function. Given distinct points z(1), z(2).... z(N) in R-n we consider the problem of finding a quadratic function g : Rn --> R such that parallel to[f (z(1)) - g(z(1))..... f(z(N)) - g(z(N))]parallel to is minimal for a given norm parallel to (.) parallel to. For the Euclidean norm this is the well-known quadratic least squares problem. (If the norm is not specified we will simply refer to g as the quadratic approximation.) In this paper we prove the result that the quadratic approximation is not necessarily convex for n greater than or equal to 2, even though it is convex if n = 1. This result has many consequences both for the field of statistics and optimization. We show that the best convex quadratic approximation can be obtained in the multivariate case by using semidefinite programming techniques.
We consider the general nonlinear optimization problem in 0-1 variables and provide an explicit equivalent positive semidefinite program in 2(n)-1 variables. The optimal values of both problems are identical. From eve...
详细信息
We consider the general nonlinear optimization problem in 0-1 variables and provide an explicit equivalent positive semidefinite program in 2(n)-1 variables. The optimal values of both problems are identical. From every optimal solution of the former, one easily finds an optimal solution of the latter, and conversely, from every solution of the latter, one may construct an optimal solution of the former. For illustration, the equivalent positive semidefinite program is explicated for quadratic 0-1 programs and MAX-CUT in R-3. For unconstrained 0-1 programs, a special representation in terms of a weighted sum of squares is provided.
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 tha...
详细信息
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.
Many signal processing applications reduce to solving combinatorial optimization problems. Recently, semidefinite programming (SDP) has been shown to be a very promising approach to combinatorial optimization, where S...
详细信息
Many signal processing applications reduce to solving combinatorial optimization problems. Recently, semidefinite programming (SDP) has been shown to be a very promising approach to combinatorial optimization, where SDP serves as a tractable convex relaxation of NT-hard problems. In this paper, we present a nonlinear programming algorithm for solving SDP, based on a change of variables that replaces the symmetrical, positive semidefinite variable X in SDP with a rectangular variable R according to X = RRT. Very encouraging results are obtained to solve even large-scale combinatorial optimization programs, as the one arising in multiuser detection for code division multiple access (CDMA) systems.
We characterize the real-valued polynomials on R(n) that are nonnegative (not necessarily strictly positive) on a grid K of points of R(n), in terms of a weighted sum of squares whose degree is bounded and known in ad...
详细信息
We characterize the real-valued polynomials on R(n) that are nonnegative (not necessarily strictly positive) on a grid K of points of R(n), in terms of a weighted sum of squares whose degree is bounded and known in advance. We also show that the minimization of an arbitrary polynomial on K (a discrete optimization problem) reduces to a convex continuous optimization problem of fixed size. The case of concave polynomials is also investigated. The proof is based on a recent result of Curto and Fialkow on the K-moment problem.
We study an infeasible primal-dual interior-poin trust-region method for constrained minimization. This method uses a log-barrier function for the slack variables and updates the slack variables using second-order cor...
详细信息
We study an infeasible primal-dual interior-poin trust-region method for constrained minimization. This method uses a log-barrier function for the slack variables and updates the slack variables using second-order correction. We show that if a certain set containing the initial iterate is bounded and the origin is not in the convex hull of the nearly active constrain gradients everywhere on this set, then the iterates remain in this set, and any cluster point of the iterates is a first-order stationary point. Moreover, any subsequence of iterates converging to the cluster point has an asymptotic second-order stationarity property, which, when the constrain functions are a ne or when the active constrain gradients are linearly independent, implies that the cluster point is a second-order stationary point. Preliminary numerical experience with the method is reported. A primal method and its extension to semidefinite nonlinear programming is also discussed.
We develop a method for generating valid convex quadratic inequalities for mixed 0-1 convex programs. We also show how these inequalities can be generated in the linear case by defining cut generation problems using a...
详细信息
We develop a method for generating valid convex quadratic inequalities for mixed 0-1 convex programs. We also show how these inequalities can be generated in the linear case by defining cut generation problems using a projection cone. The basic results for quadratic inequalities are extended to generate convex polynomial inequalities.
General successive convex relaxation methods (SRCMs) can be used to compute the convex hull of any compact set, in an Euclidean space, described by a system of quadratic inequalities and a compact convex set. Linear c...
详细信息
General successive convex relaxation methods (SRCMs) can be used to compute the convex hull of any compact set, in an Euclidean space, described by a system of quadratic inequalities and a compact convex set. Linear complementarity problems (LCPs) make an interesting and rich class of structured nonconvex optimization problems. In this paper, we study a few of the specialized lift-and-project methods and some of the possible ways of applying the general SCRMs to LCPs and related problems.
Starting from a general Hoffman-type estimate for inequalities defined via convex functions, we derive estimates of the same type for inequality constraints expressed in terms of eigenvalue functions (as in eigenvalue...
详细信息
Starting from a general Hoffman-type estimate for inequalities defined via convex functions, we derive estimates of the same type for inequality constraints expressed in terms of eigenvalue functions (as in eigenvalue optimization) or positive semidefiniteness (as in semidefinite programming).
For any given number of factors, Minimum Rank Factor Analysis yields optimal communalities for an observed covariance matrix in the sense that the unexplained common variance with that number of factors is minimized, ...
详细信息
For any given number of factors, Minimum Rank Factor Analysis yields optimal communalities for an observed covariance matrix in the sense that the unexplained common variance with that number of factors is minimized, subject to the constraint that both the diagonal matrix of unique variances and the observed covariance matrix minus that diagonal matrix are positive semidefinite. As a result, it becomes possible to distinguish the explained common variance from the total common variance. The percentage of explained common variance is similar in meaning to the percentage of explained observed variance in Principal Component Analysis, but typically the former is much closer to 100 than the latter. So far, no statistical theory of MRFA has been developed. The present paper is a first start. It yields closed-form expressions for the asymptotic bias of the explained common variance, or, more precisely, of the unexplained common variance, under the assumption of multivariate normality. Also, the asymptotic variance of this bias is derived, and also the asymptotic covariance matrix of the unique variances that define a MRFA solution. The presented asymptotic statistical inference is based on a recently developed perturbation theory of semidefinite programming. A numerical example is also offered to demonstrate the accuracy of the expressions.
暂无评论