Best interpolation in a strip II: Reduction to unconstrained convex optimization

In this paper, we study the problem of finding a real-valued function f on the interval [0, 1] with minimal L ² norm of the second derivative that interpolates the points (t _i, y _i) and satisfies e(t) f(t) d(t) for t [0, 1]. The functions e and d are continuous in each interval (t _i, t _i+1) and at t ₁ and t _nbut may be discontinuous at t _i. Based on an earlier paper by the first author [7] we characterize the solution in the case when e and d are linear in each interval (t _i, t _i+1). We present a method for the reduction of the problem to a convex finite-dimensional unconstrained minimization problem. When e and d are arbitrary continuous functions we approximate the problem by a sequence of finite-dimensional minimization problems and prove that the sequence of solutions to the approximating problems converges in the norm of W ^2,2 to the solution of the original problem. Numerical examples are reported.The first author was supported by National Science Foundation Grant Number DMS 9404431. The second author was supported by a François-Xavier Bagnoud doctoral fellowship and by National Science Foundation Grant Number MSS 9114630.     

Lagrange interpolation with constraints

Uniform convergence of Lagrange interpolation at the zeros of Jacobi polynomials in the presence of constraints is investigated. We show that by a simple procedure it is always possible to transform the matrices of these zeros into matrices such that the corresponding Lagrange interpolating polynomial respecting the given constraints well approximates a given function and its derivatives.     

On convex optimization with linear constraints

In this paper, we propose an interior-point method for minimizing a convex function subject to linear constraints. Our method employs ideas from a previously studied method due to Fan and Nekooie in a different context. Under certain assumptions, we show that the proposed method has a fast rate of convergence. A numerical example is included to illustrate the method.     

C 1 surface interpolation with constraints

Givenn pairwise distinct and arbitrarily spaced pointsP _i in a domainD of thex–y plane andn real numbersf _i, consider the problem of computing a bivariate functionf(x, y) of classC ¹ inD whose values inP _i are exactlyf _i,i=1,,n, and whose first or second order partial derivatives satisfy appropriate equality and inequality constraints on a given set ofp pointsQ _l inD.In this paper we present a method for solving the above problem, which is designed for extremely large data sets. A step of this method requires the solution of a large scale quadratic programming (QP) problem.The main purpose of this work is to analyse an iterative method for determining the solution of this QP problem: such a method is very efficient and well suited for parallel implementation on a multiprocessor system.Work supported by MURST Project of Computational Mathematics, Italy.     

Multiobjective DC programs with infinite convex constraints

New results are established for multiobjective DC programs with infinite convex constraints (MOPIC) that are defined on Banach spaces (finite or infinite dimensional) with objectives given as the difference of convex functions. This class of problems can also be called multiobjective DC semi-infinite and infinite programs, where decision variables run over finite-dimensional and infinite-dimensional spaces, respectively. Such problems have not been studied as yet. Necessary and sufficient optimality conditions for the weak Pareto efficiency are introduced. Further, we seek a connection between multiobjective linear infinite programs and MOPIC. Both Wolfe and Mond-Weir dual problems are presented, and corresponding weak, strong, and strict converse duality theorems are derived for these two problems respectively. We also extend above results to multiobjective fractional DC programs with infinite convex constraints. The results obtained are new in both semi-infinite and infinite frameworks.     

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.     

Packing under convex quadratic constraints

Mathematical Programming - We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are $$mathsf {APX}$$ -hard to...     

Admissible slopes for monotone and convex interpolation

Summary In many applications, interpolation of experimental data exhibiting some geometric property such as nonnegativity, monotonicity or convexity is unacceptable unless the interpolant reflects these characteristics. This paper identifies admissible slopes at data points of variousC ¹ interpolants which ensure a desirable shape. We discuss this question, in turn for the following function classes commonly used for shape preserving interpolations: monotone polynomials,C ¹ monotone piecewise polynomials, convex polynomials, parametric cubic curves and rational functions.     

A numerical method of nondifferentiable convex optimization with constraints

An iterative process is examined for minimizing a convex nondifferentiable functional on a convex closed set in a real Hilbert space. Convergence of the proposed process is proved. A two-sided bound on the optimal functional value is given.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 57, pp. 124–131, 1985.     

An interior-point method for fractional programs with convex constraints

We present an interior-point method for a class of fractional programs with convex constraints. The proposed algorithm converges at a polynomial rate, similarly as in the case of a convex problem, even though fractional programs are only pseudo-convex. Here, the rate of convergence is measured in terms of the area of two-dimensional convex setsC _k containing the origin and certain projections of the optimal points, and the area ofC _k is reduced by a constant factorc < 1 at each iteration. The factorc depends only on the self-concordance parameter of a barrier function associated with the feasible set. We present an outline of a practical implementation of the proposed method, and we report results of some preliminary numerical experiments.Corresponding author.     

An interior-point method for multifractional programs with convex constraints

We present an interior-point method for a family of multi-fractional programs with convex constraints. The programs under consideration consist of minimizing the maximum of a finite number of linear fractions over some convex set. First, we present a simple shortstep algorithm for solving such multifractional programs, and we show that, under suitable assumptions, the convergence of the short-step algorithm is weakly polynomial in a sense specified below. Then, we describe a practical implementation of the proposed method, and we report results of numerical experiments with this algorithm. These results suggest that the proposed method is a viable alternative to the standard Dinkelbach-type algorithms for solving multifractional programs.The authors would like to thank Professor A. S. Nemirovsky for stimulating discussions via electronic mail. We are grateful to two anonymous referees for comments and suggestions that improved our paper.     

Branch-and-reduce algorithm for convex programs with additional multiplicative constraints

This article presents a branch-and-reduce algorithm for globally solving for the first time a convex minimization problem (P) with p?1$p?1$ additional multiplicative constraints. In each of these p   additional constraints, the product of two convex functions is constrained to be less than or equal to a positive number. The algorithm works by globally solving a 2p$2p$-dimensional master problem (MP) equivalent to problem (P). During a typical stage k of the algorithm, a point is found that minimizes the objective function of problem (MP) over a nonconvex set F^k$F^k$ that contains the portion of the boundary of the feasible region of the problem where a global optimal solution lies. If this point is feasible in problem (MP), the algorithm terminates. Otherwise, the algorithm continues by branching and creating a new, reduced nonconvex set F^k+1$F^{k+1}$ that is a strict subset of F^k$F^k$. To implement the algorithm, all that is required is the ability to solve standard convex programming problems and to implement simple algebraic steps. Convergence properties of the algorithm are given, and results of some computational experiments are reported.     

On a problem of integer convex interpolation

The study of a generalized projective scheme closely related to the binary projective space P ⁽²⁾ = Proj \mathbbF₀[t]{\mathbb{F}}_0[t], where t is a free binary variable, is started, In particular, the global sections of the structure sheaf on elements of a certain affine covering are computed, and the scheme points of the unary version are described. Bibliography: 4 titles.     

Conditions for boundedness in concave programming under reverse convex and convex constraints

In this paper, we are concerned with the problem of boundedness in the constrained global maximization of a convex function. In particular, we present necessary and sufficient conditions for boundedness of a feasible region defined by reverse convex constraints and we establish sufficient and necessary conditions for existence of an upper bound for a convex objective function defined over the system of concave inequality constraints. We also address the problem of boundedness in the global maximization problem when a feasible region is convex and unbounded.     

New strong duality results for convex programs with separable constraints

It is known that convex programming problems with separable inequality constraints do not have duality gaps. However, strong duality may fail for these programs because the dual programs may not attain their maximum. In this paper, we establish conditions characterizing strong duality for convex programs with separable constraints. We also obtain a sub-differential formula characterizing strong duality for convex programs with separable constraints whenever the primal problems attain their minimum. Examples are given to illustrate our results.     

A saddle-point criterion for convex problems with infinite-dimensional equality constraints

In this paper, we develop a saddle-point criterion for convex optimization problems with infinite-dimensional equality constraints. The method used in the derivation of this criterion is based on the property of openness of the equality operator. As an application, we develop necessary and sufficient conditions for an optimal control problem under a suitable controllability assumption. Constructing an optimal solution for a production planning problem is used as an illustrative example.The authors would like to thank Professor R. T. Rockafellar for his suggestions which have resulted in an improved version of the paper.     

On a nonseparable convex maximization problem with continuous knapsack constraints

We develop a polynomial-time algorithm for a class of nonseparable convex maximization problems with continuous knapsack constraints based on an analysis of the Karush-Kuhn-Tucker optimality conditions and the special problem structure. This problem class has applicability in areas such as production and logistics planning and financial engineering.     

Monotone and convex interpolation by weighted cubic splines

Algorithms for interpolating by weighted cubic splines are constructed with the aim of preserving the monotonicity and convexity of the original discrete data. The analysis performed in this paper makes it possible to develop two algorithms with the automatic choice of the shape-controlling parameters (weights). One of them preserves the monotonicity of the data, while the other preserves the convexity. Certain numerical results are presented.