Loading [MathJax]/extensions/MathZoom.js
A recently introduced dualization technique for binary linear programs with equality constraints, essentially due to Poljak et al. [13], and further developed in Lemaréchal and Oustry [9], leads to simple alternative derivations of well-known, important relaxations to two well-known problems of discrete optimization: the maximum stable set problem and the maximum vertex cover problem. The resulting relaxation is easily transformed to the well-known Lovász number.
A recently introduced
dualization technique for binary linear programs with equality
constraints, essentially due to Poljak et al. [13],
and further developed in Lemaréchal and Oustry [9], leads
to simple alternative derivations of well-known, important
relaxations to
two well-known problems of discrete optimization: the
maximum stable set problem and the maximum vertex cover problem.
The resulting relaxation is easily transformed
to the well-known Lovász θ number.
This paper presents a logarithmic barrier method for solving a semi-definite linear program. The descent direction is the classical Newton direction. We propose alternative ways to determine the step-size along the direction which are more efficient than classical line-searches.
We introduce a new barrier function to solve a class of
Semidefinite Optimization Problems (SOP) with bounded variables.
That class is motivated by some (SOP) as the minimization of the
sum of the first few eigenvalues of symmetric matrices and graph
partitioning problems. We study the primal-dual central path
defined by the new barrier and we show that this path is analytic,
bounded and that all cluster points are optimal solutions of the
primal-dual pair of problems. Then, using some ideas from
semi-analytic...
This paper presents a feasible primal algorithm for linear semidefinite programming. The algorithm starts with a strictly feasible solution, but in case where no such a solution is known, an application of the algorithm to an associate problem allows to obtain one. Finally, we present some numerical experiments which show that the algorithm works properly.
In this paper we propose a primal-dual interior-point algorithm for
convex quadratic semidefinite optimization problem. The search
direction of algorithm is defined in terms of a matrix function and
the iteration is generated by full-Newton step. Furthermore, we
derive the iteration bound for the algorithm with small-update
method, namely, O( log ), which is
best-known bound so far.
In this paper, we present a sensitivity result for quadratic second-order cone programming under the weak form of second-order sufficient condition. Based on this result, we analyze the local convergence of an SQP-type method for nonlinear second-order cone programming. The subproblems of this method at each iteration are quadratic second-order cone programming problems. Compared with the local convergence analysis done before, we do not need the assumption that the Hessian matrix of the Lagrangian...
We propose a feasible primal-dual path-following interior-point algorithm for semidefinite least squares problems (SDLS). At each iteration, the algorithm uses only full Nesterov-Todd steps with the advantage that no line search is required. Under new appropriate choices of the parameter which defines the size of the neighborhood of the central-path and of the parameter which determines the rate of decrease of the barrier parameter, we show that the proposed algorithm is well defined and converges...
The ground-state energy and properties of any many-electron atom or
molecule may be rigorously computed by variationally computing the
two-electron reduced density matrix rather than the many-electron
wavefunction. While early attempts fifty years ago to compute the
ground-state 2-RDM directly were stymied because the 2-RDM must be
constrained to represent an N-electron wavefunction, recent
advances in theory and optimization have made direct computation of
the 2-RDM possible. The constraints in...
In this paper we propose a primal-dual path-following interior-point algorithm for semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main step of the algorithm consists of a feasibility step and several centering steps. At each iteration, we use only full-Newton step. Moreover, we use a more natural feasibility step, which targets at the -center. The iteration bound of the algorithm coincides...
Recently, Y.Q. Bai, M. El Ghami and C. Roos [3]
introduced a new class of
so-called eligible kernel functions which are defined by some
simple conditions.
The authors designed primal-dual interior-point methods for linear optimization (LO)
based on eligible kernel functions
and simplified the analysis of these methods considerably.
In this paper we consider the semidefinite optimization (SDO) problem
and we generalize the aforementioned results for LO to SDO.
The iteration bounds obtained are...
In this paper, we show that the direct semidefinite programming (SDP) bound for the nonconvex quadratic optimization problem over ℓ1 unit ball (QPL1) is equivalent to the optimal d.c. (difference between convex) bound for the standard quadratic programming reformulation of QPL1. Then we disprove a conjecture about the tightness of the direct SDP bound. Finally, as an extension of QPL1, we study the relaxation problem of the sparse principal component analysis, denoted by QPL2L1. We show that the...
We consider the non-convex quadratic maximization problem subject
to the l1 unit ball constraint. The nature of the l1 norm
structure makes this problem extremely hard to analyze, and as a
consequence, the same difficulties are encountered when trying to
build suitable approximations for this problem by some tractable
convex counterpart formulations. We explore some properties of
this problem, derive SDP-like relaxations and raise open
questions.
In this work, we study the properties of central paths, defined with respect to a large class of penalty and barrier functions, for convex semidefinite programs. The type of programs studied here is characterized by the minimization of a smooth and convex objective function subject to a linear matrix inequality constraint. So, it is a particular case of convex programming with conic constraints. The studied class of functions consists of spectrally defined functions induced by penalty or barrier...
In this paper, we have studied the problem of minimizing the ratio of two indefinite quadratic functions subject to a strictly convex quadratic constraint. First utilizing the relationship between fractional and parametric programming problems due to Dinkelbach, we reformulate the fractional problem as a univariate equation. To find the root of the univariate equation, the generalized Newton method is utilized that requires solving a nonconvex quadratic optimization problem at each iteration. A...
Many applications of wireless sensor networks (WSN) require information about the geographical location of each sensor node. Self-organization and localization capabilities are one of the most important requirements in sensor networks. This paper provides an overview of centralized distance-based algorithms for estimating the positions of nodes in a sensor network. We discuss and compare three approaches: semidefinite programming, simulated annealing and two-phase stochastic optimization-a hybrid...
Currently displaying 1 –
20 of
34