Solving Lift-and-Project Relaxations of Binary Integer Programs

We propose a method for optimizing the lift-and-project relaxations of binary integer programs introduced by Lov\’asz and Schrijver. In particular, we study both linear and semidefinite relaxations. The key idea is a restructuring of the relaxations, which isolates the complicating constraints and allows for a Lagrangian approach. We detail an enhanced subgradient method and discuss … Read more

Necessary and Sufficient Optimality Conditions for Mathematical Programs with Equilibrium Constraints

In this paper we consider a mathematical program with equilibrium constraints (MPEC) formulated as a mathematical program with complementarity constraints. Various stationary conditions for MPECs exist in literature due to different reformulations. We give a simple proof to the M-stationary condition and show that it is sufficient or locally sufficient for optimality under some MPEC … Read more

Primal-Dual Interior-Point Algorithms for Semidefinite Optimization Based on a Simple Kernel Function

Interior-point methods (IPMs) for semidefinite optimization (SDO) have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, J.Peng et al. introduced so-called self-regular kernel (and barrier) functions and designed primal-dual interior-point algorithms based on self-regular proximity for linear optimization (LO) problems. They have also extended the approach for LO to SDO. In … Read more

On the Relationship Between Convergence Rates of Discrete and Continuous Dynamical Systems

Considering iterative sequences that arise when the approximate solution $x_k$ to a numerical problem is updated by $x_{k+1} = x_k+v(x_k)$, where $v$ is a vector field, we derive necessary and sufficient conditions for such discrete methods to converge to a stationary point of $v$ at different Q-rates in terms of the differential properties of $v$ … Read more

A modified nearly exact method for solving low-rank trust region subproblem

In this paper we present a modified nearly exact (MNE) method for solving low-rank trust region (LRTR) subproblem. The LRTR subproblem is to minimize a quadratic function, whose Hessian is a positive diagonal matrix plus explicit low-rank update, subject to a Dikin-type ellipsoidal constraint, whose scaling matrix is positive definite and has the similar structure … Read more

Construction project scheduling problem with uncertain resource constraints

This paper discusses that major problem is the construction project scheduling mathematical model and a simple algorithm in the uncertain resource environments. The project scheduling problem with uncertain resource constraints comprised mainly three parties: one of which its maximal limited capacity is fixed throughout the project duration; second maximal limited resource capacity is random variable; … Read more

Inherent smoothness of intensity patterns for intensity modulated radiation therapy generated by simultaneous projection algorithms

The efficient delivery of intensity modulated radiation therapy (IMRT) depends on finding optimized beam intensity patterns that produce dose distributions, which meet given constraints for the tumor as well as any critical organs to be spared. Many optimization algorithms that are used for beamlet-based inverse planning are susceptible to large variations of neighboring intensities. Accurately … Read more

Universal Duality in Conic Convex Optimization

Given a primal-dual pair of linear programs, it is well known that if their optimal values are viewed as lying on the extended real line, then the duality gap is zero, unless both problems are infeasible, in which case the optimal values are +infinity and -infinity. In contrast, for optimization problems over nonpolyhedral convex cones, … Read more

On the Globally Concavized Filled Function Method

In this paper we present a new definition on the globally concavized filled function for the continuous global minimization problem, which was modified from that by Ge [3]. A new class of globally concavized filled functions are constructed. These functions contain two easily determinable parameters, which are not dependent on the radius of the basin … Read more

Pointillism via Linear Programming

Pointillism is a painting technique in which the painter places dots of paint on the canvas in such a way that they blend together into desired forms when viewed from a distance. In this brief note, we describe how to use linear programming to construct a pointillist portrait. CitationDept. of Mathematics, Oberlin College, Oberlin, OH … Read more