An algorithm for the estimation of a regression function by continuous piecewise linear functions

The problem of the estimation of a regression function by continuous piecewise linear functions is formulated as a nonconvex, nonsmooth optimization problem. Estimates are defined by minimization of the empirical L ₂ risk over a class of functions, which are defined as maxima of minima of linear functions. An algorithm for finding continuous piecewise linear functions is presented. We observe that the objective function in the optimization problem is semismooth, quasidifferentiable and piecewise partially separable. The use of these properties allow us to design an efficient algorithm for approximation of subgradients of the objective function and to apply the discrete gradient method for its minimization. We present computational results with some simulated data and compare the new estimator with a number of existing ones.     

On properties of discrete (r, q) and (s, T) inventory systems

We consider single-item (r, q) and (s, T) inventory systems with integer-valued demand processes. While most of the inventory literature studies continuous approximations of these models and establishes joint convexity properties of the policy parameters in the continuous space, we show that these properties no longer hold in the discrete space, in the sense of linear interpolation extension and L^?-convexity. This nonconvexity can lead to failure of optimization techniques based on local optimality to obtain the optimal inventory policies. It can also make certain comparative properties established previously using continuous variables invalid. We revise these properties in the discrete space.     

Application of the linear principle for the strongly-correlated variables: Calculations of differences between spectra

In this paper the authors suggest a new method of detection of possible differences between similar near infrared (NIR) spectra based on the self-similar (fractal) property. This property is a general characteristic that belongs to a wide class of the strongly-correlated systems. As an example we take a set of NIR spectra measured for three systems: (1) glassy carbon (GC) electrodes, (2) GC electrodes affected by azobenzene (AB) substance and finally (3) films (AB-FILM). Besides the physical model that should describe the intrinsic properties of these substances we found the fitting function that follow from the linear principle for the strongly-correlated variables. This function expressed in the form of linear combination of 4 power-law functions describes with the high accuracy the integrated curves that were obtained from the averaged values of the initially measured spectra. The nine fitting parameters can be considered as the quantitative “finger prints” for detection of the differences between similar spectra. Besides this result we established the self-similar behavior of the remnant functions. In other words, the difference between the initially integrated function and its fitting function can be expressed in the form of linear combinations of periodical functions having a set of frequencies following to relationship ω(k) = ω₀ξ^k, where the initial frequency ω₀ and scaling factor ξ are determined by the eigen-coordinates method. This behavior in the NIR spectra was discovered in the first time and physical reasons of such behavior merit an additional research.     

A Geometric Programming Framework for Univariate Cubic L 1 Smoothing Splines

Univariate cubic L ₁ smoothing splines are capable of providing shape-preserving C ¹-smooth approximation of multi-scale data. The minimization principle for univariate cubic L ₁ smoothing splines results in a nondifferentiable convex optimization problem that, for theoretical treatment and algorithm design, can be formulated as a generalized geometric program. In this framework, a geometric dual with a linear objective function over a convex feasible domain is derived, and a linear system for dual to primal conversion is established. Numerical examples are given to illustrate this approach. Sensitivity analysis for data with uncertainty is presented. This work is supported by research grant #DAAG55-98-D-0003 of the Army Research Office, USA.     

Updating incomplete factorization preconditioners for shifted linear systems arising in a wind model

The efficiency of a finite element mass consistent model for wind field adjustment depends on the stability parameter α which allows adjustment from a strictly horizontal wind to a pure vertical one. Each simulation with the wind model leads to the resolution of a linear system of equations, the matrix of which depends on a function ε(α), i.e., (M+εN)x_ε=b_ε, where M and N are constant, symmetric and positive definite matrices with the same sparsity pattern for a given level of discretization. The estimation of this parameter may be carried out by using genetic algorithms. This procedure requires the evaluation of a fitness function for each individual of the population defined in the searching space of α, that is, the resolution of one linear system of equations for each value of α. Preconditioned Conjugate Gradient algorithm (PCG) is usually applied for the resolution of these types of linear systems due to its good convergence results. In order to solve this set of linear systems, we could either construct a different preconditioner for each of them or use a single preconditioner constructed from the first value of ε to solve all the systems. In this paper, an intermediate approach is proposed. An incomplete Cholesky factorization of matrix A_ε is constructed for the first linear system and it is updated for each ε at a low computational cost. Numerical experiments related to realistic wind field are presented in order to show the performance of the proposed preconditioning strategy.     

Local convergence of the method of multipliers for variational and optimization problems under the noncriticality assumption

We present an efficient algorithm to find an optimal fiber orientation in composite materials. Within a two-scale setting fiber orientation is regarded as a function in space on the macrolevel. The optimization problem is formulated within a function space setting which makes the imposition of smoothness requirements straightforward and allows for rather general convex objective functionals. We show the existence of a global optimum in the Sobolev space H ¹(Ω). The algorithm we use is a one level optimization algorithm which optimizes with respect to the fiber orientation directly. The costly solve of a big number of microlevel problems is avoided using coordinate transformation formulas. We use an adjoint-based gradient type algorithm, but generalizations to higher-order schemes are straightforward. The algorithm is tested for a prototypical numerical example and its behaviour with respect to mesh independence and dependence on the regularization parameter is studied.     

Global optimization based on novel heuristics,low-discrepancy sequences and genetic algorithms

In this paper a new heuristic hybrid technique for bound-constrained global optimization is proposed. We developed iterative algorithm called GLP_τS that uses genetic algorithms, LP_τ low-discrepancy sequences of points and heuristic rules to find regions of attraction when searching a global minimum of an objective function. Subsequently Nelder–Mead Simplex local search technique is used to refine the solution. The combination of the three techniques (Genetic algorithms, LP_τO Low-discrepancy search and Simplex search) provides a powerful hybrid heuristic optimization method which is tested on a number of benchmark multimodal functions with 10–150 dimensions, and the method properties – applicability, convergence, consistency and stability are discussed in detail.     

Consensus of partitions : a constructive approach

Given a profile (family) ?? of partitions of a set of objects or items X, we try to establish a consensus partition containing a maximum number of joined or separated pairs in X that are also joined or separated in the profile. To do so, we define a score function, S _?? associated to any partition on X. Consensus partitions for ?? are those maximizing this function. Therefore, these consensus partitions have the median property for the profile and the symmetric difference distance. This optimization problem can be solved, in certain cases, by integer linear programming. We define a polynomial heuristic which can be applied to partitions on a large set of items. In cases where an optimal solution can be computed, we show that the partitions built by this algorithm are very close to the optimum which is reached in practically all the cases, except for some sets of bipartitions.     

A Lagrangian relaxation approach to the edge-weighted clique problem

The b-clique polytope CPⁿ_b is the convex hull of the node and edge incidence vectors of all subcliques of size at most b of a complete graph on n nodes. Including the Boolean quadric polytope QPⁿ=CPⁿ_n as a special case and being closely related to the quadratic knapsack polytope, it has received considerable attention in the literature. In particular, the max-cut problem is equivalent with optimizing a linear function over CPⁿ_n. The problem of optimizing linear functions over CPⁿ_b has so far been approached via heuristic combinatorial algorithms and cutting-plane methods.We study the structure of CPⁿ_b in further detail and present a new computational approach to the linear optimization problem based on the idea of integrating cutting planes into a Lagrangian relaxation of an integer programming problem that Balas and Christofides had suggested for the traveling salesman problem. In particular, we show that the separation problem for tree inequalities becomes polynomial in our Lagrangian framework. Finally, computational results are presented.     

Dichotomies and moving singularities

We consider a linear differential system ε ^σ Φ (t,ε)Y′ =A(t, ε)Y, with ε a small parameter and Φ(t, ε) a function which may vanish in the domain of definition. Under some conditions imposed on the eigenvalues of the matrixA(t, ε), there exists an invertible matrixH(t, ε) which is continuous on ([0,a] × [0, ε₀]). The transformationY=H(t, ε)Z takes then dimensional linear system into two differential systems of orderk andn?k respectively, withk. Thus the investigaton ofn dimensional systems encountered in singular perturbation as well as in stability theory is considerably simplified.     

On the navier-stokes equation with the additional conditionu 1 1 =u 3=0

We study the Navier-Stokes equation with the additional conditionu ₁ ¹ =u ³=0. In certain cases, solutions are represented in a closed form. In other cases, the investigated system reduces to simpler systems of partial differential equations. We study the symmetry properties of these systems and construct classes of their particular solutions.     

Scheduling with target start times

We address the single-machine problem of scheduling n independent jobs subject to target start times. Target start times are essentially release times that may be violated at a certain cost. The objective is to minimize a bicriteria objective function that is composed of total completion time and maximum promptness, which measures the observance of these target start times. We show that in case of a linear objective function the problem is solvable in O(n⁴) time if preemption is allowed or if total completion time outweighs maximum promptness.     

Insensitizing controls for a large-scale ocean circulation model

We consider here a linear quasi-geostrophic ocean model. We look for controls insensitizing (resp. ε-insensitizing) an observation function of the state. The existence of such controls is equivalent to a null controllability property (resp. an approximate controllability property) for a cascade Stokes-like system. Under reasonable assumptions on the spatial domains where the observation and the control are performed, we are able to prove these properties. To cite this article: E. Fernández-Cara et al., C. R. Acad. Sci. Paris, Ser. I 337 (2003).     

State-Feedback Stabilization of Well-Posed Linear Systems

A finite-dimensional linear time-invariant system is output-stabilizable if and only if it satisfies the finite cost condition, i.e., if for each initial state there exists at least one L² input that produces an L² output. It is exponentially stabilizable if and only if for each initial state there exists at least one L² input that produces an L² state trajectory. We extend these results to well-posed linear systems with infinite-dimensional input, state and output spaces. Our main contribution is the fact that the stabilizing state feedback is well posed, i.e., the map from an exogenous input (or disturbance) to the feedback, state and output signals is continuous in L_loc² in both open-loop and closed-loop settings. The state feedback can be chosen in such a way that it also stabilizes the I/O map and induces a (quasi) right coprime factorization of the original transfer function. The solution of the LQR problem has these properties.     

Kharitonov-like theorems for robust performance of interval systems

The sensitivity function of a control system is an important concept in performance analysis, classical filter design as well as modern robust H^∞ control. For an interval system, we prove that the maximal H^∞ norm of its sensitivity function is achieved at twelve (out of sixteen) Kharitonov vertices. Similar Kharitonov-like results are established for the complementary sensitivity function and strict positive realness of interval systems. These results are useful in robust performance analysis and H_∞ control design for dynamic systems under parametric perturbations.     

On a linear transcendence measure for the solutions of a universal differential equation at algebraic points

In this paper the author continues his work on arithmetic properties of the solutions of a universal differential equation at algebraic points. Every real continuous function on the real line can be uniformly approximated by C^∞-solutions of a universal differential equation. An algebraic universal differential equation of order five and degree 11 is explicitly given, such that every finite set of nonvanishing derivatives y^(k₁)(τ),…,y^(k_r)(τ) (1?k₁<?<k_r) at an algebraic point τ is linearly independent over the field of algebraic numbers. A linear transcendence measure for these values is effectively computed.     

Optimizing Lyapunov functions for systems with structured uncertainties

The robust stability problem of a nominally linear system with nonlinear, time-varying structured perturbationsp _j ,j=1,...,q, is considered. The system is of the form $$\dot x = A_N x + \sum\limits_{j = 1}^q {p_j A_j x} .$$ When the Lyapunov direct method is utilized to solve the problem, the most frequently chosen Lyapunov function is some quadratic form. The paper presents a procedure of optimization of Lyapunov functions. Under some simple conditions, the weak convergence of the procedure is ensured, making the procedure effective in solving the robust stability problem. The procedure is simple, requiring only numerical routines such as inverting positive-definite symmetric matrices and determining the eigenvalues and eigenvectors of symmetric matrices. It is expected that the optimal Lyapunov function may be used in a robust linear feedback controller design. The examples demonstrate the effectiveness of the method. As shown when considering a system of dimension 24, the method is effective for large-scale systems.     

Approximating a class of combinatorial problems with rational objective function

In the late seventies, Megiddo proposed a way to use an algorithm for the problem of minimizing a linear function a ₀ + a ₁ x ₁ + . . . + a _n x _n subject to certain constraints to solve the problem of minimizing a rational function of the form (a ₀ + a ₁ x ₁ + . . . + a _n x _n )/(b ₀ + b ₁ x ₁ + . . . + b _n x _n ) subject to the same set of constraints, assuming that the denominator is always positive. Using a rather strong assumption, Hashizume et al. extended Megiddo’s result to include approximation algorithms. Their assumption essentially asks for the existence of good approximation algorithms for optimization problems with possibly negative coefficients in the (linear) objective function, which is rather unusual for most combinatorial problems. In this paper, we present an alternative extension of Megiddo’s result for approximations that avoids this issue and applies to a large class of optimization problems. Specifically, we show that, if there is an α-approximation for the problem of minimizing a nonnegative linear function subject to constraints satisfying a certain increasing property then there is an α-approximation (1/α-approximation) for the problem of minimizing (maximizing) a nonnegative rational function subject to the same constraints. Our framework applies to covering problems and network design problems, among others.     

A reduced gradient method for quadratic programs with quadratic constraints and lp-constrained lp-approximation problems

A dual algorithm is developed for solving a general class of nonlinear programs that properly contains all convex quadratic programs with quadratic constraints and l_p-constrained l_p-approximation problems. The general dual program to be solved has essentially linear constraints but the objective function is nondifferentiable when certain variables equal zero. Modifications to the reduced gradient method for linearly constrained problems are presented that overcome the numerical difficulties associated with the nondifferentiable objective function. These modifications permit ‘blocks’ of variables to move to and away from zero on certain iterations even though the objective function is nondifferentiable at points having a block of variables equal to zero.     

Setting targets for surrogate-based optimization

In the context of surrogate-based optimization (SBO), most designers have still very little guidance on when to stop and how to use infill measures with target requirements (e.g., one-stage approach for goal seeking and optimization); the reason: optimum estimates independent of the surrogate and optimization strategy are seldom available. Hence, optimization cycles are typically stopped when resources run out (e.g., number of objective function evaluations/time) or convergence is perceived, and targets are empirically set which may affect the effectiveness and efficiency of the SBO approach. This work presents an approach for estimating the minimum (target) of the objective function using concepts from extreme order statistics which relies only on the training data (sample) outputs. It is assumed that the sample inputs are randomly distributed so the outputs can be considered a random variable, whose density function is bounded (a, b), with the minimum (a) as its lower bound. Specifically, an estimate of the minimum (a) is obtained by: (i) computing the bounds (using training data and the moment matching method) of a selected set of analytical density functions (catalog), and (ii) identifying the density function in the catalog with the best match to the sample outputs distribution and corresponding minimum estimate (a). The proposed approach makes no assumption about the nature of the objective functions, and can be used with any surrogate, and optimization strategy even with high dimensional problems. The effectiveness of the proposed approach was evaluated using a compact catalog of Generalized Beta density functions and well-known analytical optimization test functions, i.e., F2, Hartmann 6D, and Griewangk 10D and in the optimization of a field scale alkali-surfactant-polymer enhanced oil recovery process. The results revealed that: (a) the density function (from a catalog) with the best match to a function outputs distribution, was the same for both large and reduced samples, (b) the true optimum value was always within a 95% confidence interval of the estimated minimum distribution, and (c) the estimated minimum represents a significant improvement over the present best solution and an excellent approximation of the true optimum value.