An extension of the standard polynomial-time primal-dual path-following algorithm to the weighted determinant maximization problem with semidefinite constraints

The problem of maximizing the sum of linear functional and several weighted logarithmic determinant (logdet) functions under semidefinite constraints is a generalization of the semidefinite programming (SDP) and has a number of applications in statistics and datamining, and other areas of informatics and mathematical sciences. In this paper, we extend the framework of standard primal-dual … Read more

Generating and Measuring Instances of Hard Semidefinite Programs, SDP

Linear Programming, LP, problems with finite optimal value have a zero duality gap and a primal-dual strictly complementary optimal solution pair. On the other hand, there exists Semidefinite Programming, SDP, problems which have a nonzero duality gap (different primal and dual optimal values; not both infinite). The duality gap is assured to be zero if … Read more

A primal-dual interior point method for nonlinear optimization over second order cones

In this paper, we are concerned with nonlinear minimization problems with second order cone constraints. A primal-dual interior point method is proposed for solving the problems. We also propose a new primal-dual merit function by combining the barrier penalty function and the potential function within the framework of the line search strategy, and show the … Read more

Interior-Point l_2 Penalty Methods for Nonlinear Programming with Strong Global Convergence Properties

We propose two line search primal-dual interior-point methods that approximately solve a equence of equality constrained barrier subproblems. To solve each subproblem, our methods apply a modified Newton method and use an $\ell_2$-exact penalty function to attain feasibility. Our methods have strong global convergence properties under standard assumptions. Specifically, if the penalty parameter remains bounded, … Read more

Constraint Reduction for Linear Programs with Many Inequality Constraints

Consider solving a linear program in standard form, where the constraint matrix $A$ is $m \times n$, with $n \gg m \gg 1$. Such problems arise, for example, as the result of finely discretizing a semi-infinite program. The cost per iteration of typical primal-dual interior-point methods on such problems is $O(m^2n)$. We propose to reduce … Read more

Parallel Primal-Dual Interior-Point Methods for SemiDefinite Programs

The Semidefinite Program (SDP) is a fundamental problem in mathematical programming. It covers a wide range of applications, such as combinatorial optimization, control theory, polynomial optimization, and quantum chemistry. Solving extremely large-scale SDPs which could not be solved before is a significant work to open up a new vista of future applications of SDPs. Our … Read more

An (\sqrt{n}\log \frac{(x^0)^Ts^0}{\epsilon})$ iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone linear complementarity problems

In this paper we propose a new class of primal-dual path-following interior point algorithms for solving monotone linear complementarity problems. At each iteration, the method would select a target on the central path with a large update from the current iterate, and then the Newton method is used to get the search directions, followed by … Read more

An Adaptive Self-Regular Proximity Based Large-Update IPM for LO

Primal-Dual Interior-Point Methods (IPMs) have shown their power in solving large classes of optimization problems. However, there is still a gap between the practical behavior of these algorithms and their theoretical worst-case complexity results with respect to the update strategies of the duality gap parameter in the algorithm. The so-called small-update IPMs enjoy the best … Read more

An interior-point L1-penalty method for nonlinear optimization

A mixed interior/exterior-point method for nonlinear programming is described, that handles constraints by an L1-penalty function. A suitable decomposition of the penalty terms and embedding of the problem into a higher-dimensional setting leads to an equivalent, surprisingly regular, reformulation as a smooth penalty problem only involving inequality constraints. The resulting problem may then be tackled … Read more

A Parallel Primal-Dual Interior-Point Method for Semidefinite Programs Using Positive Definite Matrix Completion

A parallel computational method SDPARA-C is presented for SDPs (semidefinite programs). It combines two methods SDPARA and SDPA-C proposed by the authors who developed a software package SDPA. SDPARA is a parallel implementation of SDPA and it features parallel computation of the elements of the Schur complement equation system and a parallel Cholesky factorization of … Read more