On convex quadratic programs with linear complementarity constraints

The paper shows that the global resolution of a general convex quadratic program with complementarity constraints (QPCC), possibly infeasible or unbounded, can be accomplished in finite time. The method constructs a minmax mixed integer formulation by introducing finitely many binary variables, one for each complementarity constraint. Based on the primal-dual relationship of a pair of convex quadratic programs and on a logical Benders scheme, an extreme ray/point generation procedure is developed, which relies on valid satisfiability constraints for the integer program. To improve this scheme, we propose a two-stage approach wherein the first stage solves the mixed integer quadratic program with pre-set upper bounds on the complementarity variables, and the second stage solves the program outside this bounded region by the Benders scheme. We report computational results with our method. We also investigate the addition of a penalty term y ^T Dw to the objective function, where y and w are the complementary variables and D is a nonnegative diagonal matrix. The matrix D can be chosen effectively by solving a semidefinite program, ensuring that the objective function remains convex. The addition of the penalty term can often reduce the overall runtime by at least 50 %. We report preliminary computational testing on a QP relaxation method which can be used to obtain better lower bounds from infeasible points; this method could be incorporated into a branching scheme. By combining the penalty method and the QP relaxation method, more than 90 % of the gap can be closed for some QPCC problems.     

Detecting Changes in Slope With an L0 Penalty

While there are many approaches to detecting changes in mean for a univariate time series, the problem of detecting multiple changes in slope has comparatively been ignored. Part of the reason for this is that detecting changes in slope is much more challenging: simple binary segmentation procedures do not work for this problem, while existing dynamic programming methods that work for the change in mean problem cannot be used for detecting changes in slope. We present a novel dynamic programming approach, CPOP, for finding the “best” continuous piecewise linear fit to data under a criterion that measures fit to data using the residual sum of squares, but penalizes complexity based on an L₀ penalty on changes in slope. We prove that detecting changes in this manner can lead to consistent estimation of the number of changepoints, and show empirically that using an L₀ penalty is more reliable at estimating changepoint locations than using an L₁ penalty. Empirically CPOP has good computational properties, and can analyze a time series with 10,000 observations and 100 changes in a few minutes. Our method is used to analyze data on the motion of bacteria, and provides better and more parsimonious fits than two competing approaches. Supplementary material for this article is available online.     

Scheduling for Known but Irregular Batch-Wise Demand

The paper deals with the batch size problem, given that demand is batch-wise and the times and quantities of the first n demands are known. This is found to be a problem in dynamic programming.A treatment is devised which may often enable that part of the demand to be scheduled optimally which must be procured before further information becomes available; which solves the problem in such cases. In other cases the final decision between the surviving possibilities may have to be based on possibly non-optimal criteria. Where it is known that the nth demand is the last, the problem can be solved completely.Details of computational methods are given, including worked examples. The methods appear suitable for computer programming, but are in any case (relatively) fast by hand; a solution may normally be obtained in, say, 5n minutes or less, except where the individual demands are much smaller than the optimum batch size (in which case other—approximate—methods may be preferred and would be unlikely to incur much penalty).     

Global well-posedness for the KP-II equation on the background of a non-localized solution

Motivated by transverse stability issues, we address the time evolution under the KP-II flow of perturbations of a solution which does not decay in all directions, for instance the KdV-line soliton. We study two different types of perturbations: perturbations that are square integrable in R×T and perturbations that are square integrable in R². In both cases we prove the global well-posedness of the Cauchy problem associated with such initial data.     

An interior-point piecewise linear penalty method for nonlinear programming

We present an interior-point penalty method for nonlinear programming (NLP), where the merit function consists of a piecewise linear penalty function and an ? ₂-penalty function. The piecewise linear penalty function is defined by a set of break points that correspond to pairs of values of the barrier function and the infeasibility measure at a subset of previous iterates and this set is updated at every iteration. The ? ₂-penalty function is a traditional penalty function defined by a single penalty parameter. At every iteration the step direction is computed from a regularized Newton system of the first-order equations of the barrier problem proposed in Chen and Goldfarb (Math Program 108:1?C36, 2006). Iterates are updated using a line search. In particular, a trial point is accepted if it provides a sufficient reduction in either of the penalty functions. We show that the proposed method has the same strong global convergence properties as those established in Chen and Goldfarb (Math Program 108:1?C36, 2006). Moreover, our method enjoys fast local convergence. Specifically, for each fixed small barrier parameter???, iterates in a small neighborhood (roughly within o(??)) of the minimizer of the barrier problem converge Q-quadratically to the minimizer. The overall convergence rate of the iterates to the solution of the nonlinear program is Q-superlinear.     

Computer difference scheme for a singularly perturbed elliptic convection–diffusion equation in the presence of perturbations

A grid approximation of a boundary value problem for a singularly perturbed elliptic convection–diffusion equation with a perturbation parameter ε, ε ∈ (0,1], multiplying the highest order derivatives is considered on a rectangle. The stability of a standard difference scheme based on monotone approximations of the problem on a uniform grid is analyzed, and the behavior of discrete solutions in the presence of perturbations is examined. With an increase in the number of grid nodes, this scheme does not converge -uniformly in the maximum norm, but only conditional convergence takes place. When the solution of the difference scheme converges, which occurs if N ₁ ^-1 N ₂ ^-1 ? ε, where N ₁ and N ₂ are the numbers of grid intervals in x and y, respectively, the scheme is not -uniformly well-conditioned or ε-uniformly stable to data perturbations in the grid problem and to computer perturbations. For the standard difference scheme in the presence of data perturbations in the grid problem and/or computer perturbations, conditions imposed on the “parameters” of the difference scheme and of the computer (namely, on ε, N ₁,N ₂, admissible data perturbations in the grid problem, and admissible computer perturbations) are obtained that ensure the convergence of the perturbed solutions as N ₁,N ₂ → ∞, ε ∈ (0,1]. The difference schemes constructed in the presence of the indicated perturbations that converges as N ₁,N ₂ → ∞ for fixed ε, ε ∈ (0,1, is called a computer difference scheme. Schemes converging ε-uniformly and conditionally converging computer schemes are referred to as reliable schemes. Conditions on the data perturbations in the standard difference scheme and on computer perturbations are also obtained under which the convergence rate of the solution to the computer difference scheme has the same order as the solution of the standard difference scheme in the absence of perturbations. Due to this property of its solutions, the computer difference scheme can be effectively used in practical computations.     

Strong formulations for quadratic optimization with M-matrices and indicator variables

We propose a DC (Difference of two Convex functions) formulation approach for sparse optimization problems having a cardinality or rank constraint. With the largest-k norm, an exact DC representation of the cardinality constraint is provided. We then transform the cardinality-constrained problem into a penalty function form and derive exact penalty parameter values for some optimization problems, especially for quadratic minimization problems which often appear in practice. A DC Algorithm (DCA) is presented, where the dual step at each iteration can be efficiently carried out due to the accessible subgradient of the largest-k norm. Furthermore, we can solve each DCA subproblem in linear time via a soft thresholding operation if there are no additional constraints. The framework is extended to the rank-constrained problem as well as the cardinality- and the rank-minimization problems. Numerical experiments demonstrate the efficiency of the proposed DCA in comparison with existing methods which have other penalty terms.     

Vector scheduling with rejection on a single machine

In this paper, we study a vector scheduling problem with rejection on a single machine, in which each job is characterized by a d-dimension vector and a penalty, in the sense that, jobs can be either rejected by paying a certain penalty or assigned to the machine. The objective is to minimize the sum of the maximum load over all dimensions of the total vector of all accepted jobs, and the total penalty of rejected jobs. We prove that the problem is NP-hard and design two approximation algorithms running in polynomial time. When d is a fixed constant, we present a fully polynomial time approximation scheme.     

Constructive algebraic topology

The classical “computation” methods in Algebraic Topology most often work by means of highly infinite objects and in fact are not constructive. Typical examples are shown to describe the nature of the problem. The Rubio-Sergeraert solution for Constructive Algebraic Topology is recalled. This is not only a theoretical solution: the concrete computer program Kenzo has been written down which precisely follows this method. This program has been used in various cases, opening new research subjects and producing in several cases significant results unreachable by hand. In particular the Kenzo program can compute the first homotopy groups of a simply connected arbitrary simplicial set.     

Approximate values for mathematical programs with variational inequality constraints

In general the infimal value of a mathematical program with variational inequality constraints (MPVI) is not stable under perturbations in the sense that the sequence of infimal values for the perturbed programs may not converge to the infimal value of the original problem even in presence of nice data. Thus, for these programs we consider different types of values which approximate the exact value from below or/and from above under or without perturbations.     

Arbitrary-norm separating plane

A plane separating two point sets in n-dimensional real space is constructed such that it minimizes the sum of arbitrary-norm distances of misclassified points to the plane. In contrast to previous approaches that used surrogates for distance-minimization, the present work is based on a precise norm-dependent explicit closed form for the projection of a point on a plane. This projection is used to formulate the separating-plane problem as a minimization of a convex function on a unit sphere in a norm dual to that of the arbitrary norm used. For the 1-norm, the problem can be solved in polynomial time by solving 2n linear programs or by solving a bilinear program. For a general p-norm, the minimization problem can be transformed via an exact penalty formulation to minimizing the sum ofa convex function and a bilinear function on a convex set. For the one and infinity norms, a finite successive linearization algorithm can be used for solving the exact penalty formulation.     

Variational Analysis on Local Sharp Minima via Exact Penalization

In this paper we study local sharp minima of the nonlinear programming problem via exact penalization. Utilizing generalized differentiation tools in variational analysis such as subderivatives and regular subdifferentials, we obtain some primal and dual characterizations for a penalty function associated with the nonlinear programming problem to have a local sharp minimum. These general results are then applied to the ? _p penalty function with 0 ≤ p ≤ 1. In particular, we present primal and dual equivalent conditions in terms of the original data of the nonlinear programming problem, which guarantee that the ? _p penalty function has a local sharp minimum with a finite penalty parameter in the case of \(p\in (\frac {1}{2}, 1]\) and \(p=\frac {1}{2}\) respectively. By assuming the Guignard constraint qualification (resp. the generalized Guignard constraint qualification), we also show that a local sharp minimum of the nonlinear programming problem can be an exact local sharp minimum of the ? _p penalty function with p ∈ [0, 1] (resp. \(p\in [0, \frac {1}{2}]\)). Finally, we give some formulas for calculating the smallest penalty parameter for a penalty function to have a local sharp minimum.     

Determination of common due window location in a single machine scheduling problem

We consider the static deterministic single machine scheduling problem in which all jobs have a common due window. Jobs that are completed within the window incur no penalty. The objective is to find the optimal sequence and the optimal common due window location given that the due window size is a problem parameter such that the weighted sum of earliness, tardiness, and due window location penalties is minimized. We propose an O(n log n) algorithm to solve the problem. We also consider two special cases for which simple solutions can be obtained.     

Effects of Centralization on Expected Costs in a Multi-location Newsboy Problem

This is a single-period, single-product inventory model with several individual sources of demand. It is a multi-location problem with an opportunity for centralization. The holding and penalty cost functions at each location are assumed to be identical. Two types of inventory system are considered in this paper: the decentralized system and the centralized system. The decentralized system is a system in which a separate inventory is kept to satisfy the demand at each source of demand. The centralized system is a system in which all demands are satisfied from one central warehouse. This paper demonstrates that, for any probability distribution of a location's demands, the following properties are always true: given that the holding and penalty cost functions are identical at all locations, (1) if the holding and penalty cost functions are concave functions, then the expected holding and penalty costs in a decentralized system exceed those in a centralized system, except that (2) if the holding and penalty cost functions are linear functions, and for any i≠j, P_ij, the coefficient of correlation between the ith location's demand and the jth location's demand is equal to 1, then the expected holding and penalty costs in a decentralized system are equal to those in a centralized system.     

Computer difference scheme for a singularly perturbed convection-diffusion equation

The Dirichlet problem for a singularly perturbed ordinary differential convection-diffusion equation with a perturbation parameter ? (that takes arbitrary values from the half-open interval (0, 1]) is considered. For this problem, an approach to the construction of a numerical method based on a standard difference scheme on uniform meshes is developed in the case when the data of the grid problem include perturbations and additional perturbations are introduced in the course of the computations on a computer. In the absence of perturbations, the standard difference scheme converges at an \(\mathcal{O}\) (δ _st ) rate, where δ _st = (? + N ^?1)^?1 N ^?1 and N + 1 is the number of grid nodes; the scheme is not ?-uniformly well conditioned or stable to perturbations of the data. Even if the convergence of the standard scheme is theoretically proved, the actual accuracy of the computed solution in the presence of perturbations degrades with decreasing ? down to its complete loss for small ? (namely, for ? = \(\mathcal{O}\) (δ^?2max _i,j |δa _i ^j | + δ^?1 max _{i, j} |δb _i ^j |), where δ = δ _st and δa _i ^j , δb _i ^j are the perturbations in the coefficients multiplying the second and first derivatives). For the boundary value problem, we construct a computer difference scheme, i.e., a computing system that consists of a standard scheme on a uniform mesh in the presence of controlled perturbations in the grid problem data and a hypothetical computer with controlled computer perturbations. The conditions on admissible perturbations in the grid problem data and on admissible computer perturbations are obtained under which the computer difference scheme converges in the maximum norm for ? ∈ (0, 1] at the same rate as the standard scheme in the absence of perturbations.     

A new exact exponential penalty function method and nonconvex mathematical programming

A new exact penalty function method, called the l₁ exact exponential penalty function method, is introduced. In this approach, the so-called the exponential penalized optimization problem with the l₁ exact exponential penalty function is associated with the original optimization problem with both inequality and equality constraints. The l₁ exact exponential penalty function method is used to solve nonconvex mathematical programming problems with r-invex functions (with respect to the same function η). The equivalence between sets of optimal solutions of the original mathematical programming problem and of its associated exponential penalized optimization problem is established under suitable r-invexity assumption. Also lower bounds on the penalty parameter are given, for which above these values, this result is true.     

Neuere numerische methoden in der himmelsmechanik

The main problem of celestial mechanics is to compute the movement of a point mass in space. The force entering the relevant differential equations can often be split into two parts, one of which can be considered as a small perturbation. This paper reviews some methods useful for the solution of such equations. Gröbner's non-linear method is briefly mentioned. Further, a regularization technique, appropriate for the perturbed Kepler problem, is discussed and compared with other methods. Finally, the treatment in the case of forced perturbations which are of interest for satellites, is briefly outlined.

---

---

This paper was presented at the NordSAM conference in Stockholm, Aug. 1964.     

A Newton Method for Linear Programming

A fast Newton method is proposed for solving linear programs with a very large (10⁶) number of constraints and a moderate (10²) number of variables. Such linear programs occur in data mining and machine learning. The proposed method is based on the apparently overlooked fact that the dual of an asymptotic exterior penalty formulation of a linear program provides an exact least 2-norm solution to the dual of the linear program for finite values of the penalty parameter but not for the primal linear program. Solving the dual problem for a finite value of the penalty parameter yields an exact least 2-norm solution to the dual, but not a primal solution unless the parameter approaches zero. However, the exact least 2-norm solution to the dual problem can be used to generate an accurate primal solution if mn and the primal solution is unique. Utilizing these facts, a fast globally convergent finitely terminating Newton method is proposed. A simple prototype of the method is given in eleven lines of MATLAB code. Encouraging computational results are presented such as the solution of a linear program with two million constraints that could not be solved by CPLEX 6.5 on the same machine.     

Optimal Ordering Policies for Inventory Systems with Emergency Ordering

This paper considers dynamic single- and multi-product inventory problems in which the demands in each period are independent and identically distributed random variables. The problems considered have the following common characteristics. At the beginning of each period two order quantities are determined for each product. A “normal order” quantity with a constant positive lead time of λ _n periods and an “emergency order” quantity with a lead time of λ _e periods, where λ _e = λ _n - 1. The ordering decisions are based on linear procurement costs for both methods of ordering and convex holding and penalty costs. The emergency ordering costs are assumed to be higher than the normal ordering costs. In addition, future costs are discounted.For the single-product problem the optimal ordering policy is shown to be the same for all periods with the exception of the last period in the N-period problem. For the multi-product problem the one- and N-period optimal ordering policy is characterized where it is assumed that there are resource constraints on the total amount that can be ordered or produced in each period.     

Conventional penalty optimization methods

In a recent study, the effects of large penalty constants on Ritz penalty methods based on finite-element approximations used in the solution of the control of a system governed by the diffusion equation were established. The problem involves the selection of the inputu(x, t) so as to minimize the cost $$J(u) = \int_0^1 {\int_0^1 {\left\{ {u^2 (x,t) + z^2 (x,t)} \right\}dx dt,} } $$ subject to the constraint $$\partial z/\partial t = \partial ^2 z/\partial x^2 + u(x,t), 0 \leqslant x,t \leqslant 1,$$ with boundary conditions $$z(0,t) = z(1,t) = 0, 0 \leqslant t \leqslant 1,$$ and the initial state $$z(x,0) = z_0 (x), 0 \leqslant x \leqslant 1.$$ Our results verify that the Ritz penalty method exhibits good convergence properties, although the estimates for the convergence rate are cumbersome. In this paper, a conceptually simple procedure based on the conventional penalty method is presented. Some significant advantages of the method is presented. Some significant advantages of the method are the following. It allows easy estimation of its convergence rate. Furthermore, the multiplier method can be used to accelerate the rate of convergence of the method without essentially allowing the penalty constants to tend to infinity; thus, in this way, it is possible to retain the good convergence properties, an important feature which is often glossed over. The paper provides a clear mathematical analysis of how these advantages can be exploited and illustrated with numerical examples.