This paper presents an exact penalty method for solving optimization problems with very general constraints covering, in particular, nonlinear programming (NLP), semidefinite programming (SDP), and second-order cone p...
详细信息
This paper presents an exact penalty method for solving optimization problems with very general constraints covering, in particular, nonlinear programming (NLP), semidefinite programming (SDP), and second-order cone programming (SOCP). The algorithm is called the sequential linear cone method (SLCM) because for SDP and SOCP the main cost of computation amounts to solving at each iteration a linear cone program for which efficient solvers are available. Restricted to NLP, SLCM is exactly a sequential quadratic program method. Under two basic conditions which concern only the data, it is proved that the sequence of iterates is bounded. Furthermore, in particular, when the feasible set is nonempty, under two additional constraint qualification conditions, it is proved that the cluster points are stationary points. In that case, it is established also that the sequence of penalty parameters eventually stays constant, and for a particular class of data it is proved that a unit step length can be obtained.
Bell inequalities are pillars of quantum physics in that their violations imply that certain properties of quantum physics (e.g., entanglement) cannot be represented by any classical picture of physics. In this articl...
详细信息
Bell inequalities are pillars of quantum physics in that their violations imply that certain properties of quantum physics (e.g., entanglement) cannot be represented by any classical picture of physics. In this article Bell inequalities and their violations are considered through the lens of noncommutative polynomial optimization. Optimality of these violations is certified for a large majority of a set of standard Bell inequalities, denoted A2--A89 in the literature. The main techniques used in the paper include the NPA hierarchy, i.e., the noncommutative version of the Lasserre semidefinite programming (SDP) hierarchies based on the Helton-McCullough Positivstellensatz, the Gelfand--Naimark--Segal (GNS) construction with a novel use of the Artin-Wedderburn theory for rounding and projecting, and nonlinear programming (NLP). A new ``Newton chip"-like technique for reducing sizes of SDPs arising in the constructed polynomial optimization problems is presented. This technique is based on conditional expectations. Finally, noncommutative Gro"\bner bases are exploited to certify when an optimizer (a solution yielding optimum violation) cannot be extracted from a dual SDP solution.
The constraint nondegeneracy condition is one of the most relevant and useful constraint qualifications in nonlinear semidefinite programming. It can be characterized in terms of any fixed orthonormal basis of the, le...
详细信息
The constraint nondegeneracy condition is one of the most relevant and useful constraint qualifications in nonlinear semidefinite programming. It can be characterized in terms of any fixed orthonormal basis of the, let us say, l-dimensional kernel of the constraint matrix, by the linear independence of a set of l(l + 1)/2 derivative vectors. We show that this linear independence requirement can be equivalently formulated in a smaller set, of l derivative vectors, by considering all orthonormal bases of the kernel instead. This allows us to identify that not all bases are relevant for a constraint qualification to be defined, giving rise to a strictly weaker variant of nondegeneracy related to the global convergence of an external penalty method. We use some of these ideas to revisit an approach of Forsgren (Math Program 88, 105-128, 2000) for exploiting the sparsity structure of a transformation of the constraints to define a constraint qualification, which led us to develop another relaxed notion of nondegeneracy using a simpler transformation. If the zeros of the derivatives of the constraint function at a given point are considered, instead of the zeros of the function itself in a neighborhood of that point, we obtain an even weaker constraint qualification that connects Forsgren's condition and ours.
Symmetricity of an optimal solution of Semi-Definite programming (SDP) is discussed based on the symmetry property of the central path that is traced by a primal-dual interior-point method. A symmetric SDP is defined ...
详细信息
Symmetricity of an optimal solution of Semi-Definite programming (SDP) is discussed based on the symmetry property of the central path that is traced by a primal-dual interior-point method. A symmetric SDP is defined by operators for rearranging elements of matrices and vectors, and the solution on the central path is proved to be symmetric. Therefore, it is theoretically guaranteed that a symmetric optimal solution is always obtained by using a primal-dual interior-point method even if there exist other asymmetric optimal solutions. The optimization problem of symmetric trusses under eigenvalue constraints is shown to be formulated as a symmetric SDP. Numerical experiments illustrate convergence to strictly symmetric optimal solutions.
We study stochastic linear-quadratic (LQ) optimal control problems over an infinite time horizon, allowing the cost matrices to be indefinite. We develop a systematic approach based on semidefinite programming (SDP). ...
详细信息
We study stochastic linear-quadratic (LQ) optimal control problems over an infinite time horizon, allowing the cost matrices to be indefinite. We develop a systematic approach based on semidefinite programming (SDP). A central issue is the stability of the feedback control;and we show this can be effectively examined through the complementary duality of the SDP. Furthermore, we establish several implication relations among the SDP complementary duality, the ( generalized) Riccati equation, and the optimality of the LQ control problem. Based on these relations, we propose a numerical procedure that provides a thorough treatment of the LQ control problem via primal-dual SDP: it identifies a stabilizing feedback control that is optimal or determines that the problem possesses no optimal solution. For the latter case, we develop an epsilon -approximation scheme that is asymptotically optimal.
A simple method for the design of an optimal two-channel orthogonal cyclic filterbank using semidefinite programming is presented. The criterion for optimality is to maximize the passband energy, or equivalently, to m...
详细信息
A simple method for the design of an optimal two-channel orthogonal cyclic filterbank using semidefinite programming is presented. The criterion for optimality is to maximize the passband energy, or equivalently, to minimize the stopband energy of the filter's impulse response. The objective function and orthogonality constraints are represented in terms of the cyclic autocorrelation sequence of the filter's impulse response. The convex formulation of the filter design problem is obtained by imposing the positive semidefinite property on the cyclic autocorrelation matrix. The solution of the semidefinite programming problem gives a class of optimal cyclic filters with unique discrete Fourier transform magnitude response. The design method is illustrated with an example.
semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced in Zhao et al. (J Comb Optim 2:71-109, 1998). Empirically, these bounds are often quite good in practice, but computatio...
详细信息
semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced in Zhao et al. (J Comb Optim 2:71-109, 1998). Empirically, these bounds are often quite good in practice, but computationally demanding, even for relatively small instances. For QAP instances where the data matrices have large automorphism groups, these bounds can be computed more efficiently, as was shown in Klerk and Sotirov (Math Program A, 122(2), 225-246, 2010). Continuing in the same vein, we show how one may obtain stronger bounds for QAP instances where one of the data matrices has a transitive automorphism group. To illustrate our approach, we compute improved lower bounds for several instances from the QAP library QAPLIB.
In this paper we present penalty and barrier methods for solving general convex semidefinite programming problems. More precisely, the constraint set is described by a convex operator that takes its values in the cone...
详细信息
In this paper we present penalty and barrier methods for solving general convex semidefinite programming problems. More precisely, the constraint set is described by a convex operator that takes its values in the cone of negative semidefinite symmetric matrices. This class of methods is an extension of penalty and barrier methods for convex optimization to this setting. We provide implementable stopping rules and prove the convergence of the primal and dual paths obtained by these methods under minimal assumptions. The two parameters approach for penalty methods is also extended. As for usual convex programming, we prove that after a finite number of steps all iterates will be feasible.
Graph partition is used in the telecommunication industry to subdivide a transmission network into small clusters. We consider both linear and semidefinite relaxations for the equipartition problem and present numeric...
详细信息
Graph partition is used in the telecommunication industry to subdivide a transmission network into small clusters. We consider both linear and semidefinite relaxations for the equipartition problem and present numerical results on real data from France Telecom networks with up 900 nodes, and also on randomly generated problems.
We consider a Newton-CG augmented Lagrangian method for solving semidefinite programming (SDP) problems from the perspective of approximate semismooth Newton methods. In order to analyze the rate of convergence of our...
详细信息
We consider a Newton-CG augmented Lagrangian method for solving semidefinite programming (SDP) problems from the perspective of approximate semismooth Newton methods. In order to analyze the rate of convergence of our proposed method, we characterize the Lipschitz continuity of the corresponding solution mapping at the origin. For the inner problems, we show that the positive definiteness of the generalized Hessian of the objective function in these inner problems, a key property for ensuring the efficiency of using an inexact semismooth Newton-CG method to solve the inner problems, is equivalent to the constraint nondegeneracy of the corresponding dual problems. Numerical experiments on a variety of large-scale SDP problems with the matrix dimension n up to 4, 110 and the number of equality constraints m up to 2, 156, 544 show that the proposed method is very efficient. We are also able to solve the SDP problem fap36 (with n = 4, 110 and m = 1, 154, 467) in the Seventh DIMACS Implementation Challenge much more accurately than in previous attempts.
暂无评论