精确罚函数和极小极大问题

在这篇文章中我们研究了对于不等式约束的非线性规划问题如何根据极小极大问题的鞍点来找精确罚问题的解。对于一个具有不等式约束的非线性规划问题,通过罚函数,我们构造出一个极小极大问题,应用交换“极小”或“极大”次序的策略,证明了罚问题的鞍点定理。研究结果显示极小极大问题的鞍点是精确罚问题的解。     

Approximate Solution of Singular Optimization Problems

We study the optimal control problem for systems described by nonlinear elliptic equations. We have no information about the existence and uniqueness of the solution for some particular control. The extremum problem may be unsolvable. We regularize the problem by using a combination of the penalty method and the Tikhonov method. For the regularized problem, we prove the existence of the solution and find necessary conditions for optimality in the form of variational inequalities. We show that the regularization method used in this paper allows one to find an approximate (in some sense) solution of the original problem.     

Rate of Convergence Analysis of Discretization and Smoothing Algorithms for Semiinfinite Minimax Problems

Discretization algorithms for semiinfinite minimax problems replace the original problem, containing an infinite number of functions, by an approximation involving a finite number, and then solve the resulting approximate problem. The approximation gives rise to a discretization error, and suboptimal solution of the approximate problem gives rise to an optimization error. Accounting for both discretization and optimization errors, we determine the rate of convergence of discretization algorithms, as a computing budget tends to infinity. We find that the rate of convergence depends on the class of optimization algorithms used to solve the approximate problem as well as the policy for selecting discretization level and number of optimization iterations. We construct optimal policies that achieve the best possible rate of convergence and find that, under certain circumstances, the better rate is obtained by inexpensive gradient methods.     

Preconditioned Kaczmarz-Extended algorithm with relaxation parameters

We analyse in this paper the possibility of using preconditioning techniques as for square non-singular systems, also in the case of inconsistent least-squares problems. We find conditions in which the minimal norm solution of the preconditioned least-squares problem equals that of the original problem. We also find conditions such that the Kaczmarz-Extended algorithm with relaxation parameters (analysed by the author in [4]), can be adapted to the preconditioned least-squares problem. In the last section of the paper we present numerical experiments, with two variants of preconditioning, applied to an inconsistent linear least-squares model problem.     

Approximation of 3-Edge-Coloring of Cubic Graphs

The problem to find a 4-edge-coloring of a 3-regular graph is solvable in polynomial time but an analogous problem for 3-edge-coloring is NP-hard. We study complexity of approximation algorithms for invariants measuring how far is a 3-regular graph from having a 3-edge-coloring. We prove that it is an NP-hard problem to approximate such invariants by a power function with exponent smaller than 1.     

Relaxation,New Combinatorial and Polynomial Algorithms for the Linear Feasibility Problem

We consider the homogenized linear feasibility problem, to find an x on the unit sphere satisfying n linear inequalities a_i ^Tx \ge 0. To solve this problem we consider the centers of the inspheres of spherical simplices, whose facets are determined by a subset of the constraints. As a result we find a new combinatorial algorithm for the linear feasibility problem. If we allow rescaling, this algorithm becomes polynomial. We point out that the algorithm also solves the more general convex feasibility problem. Moreover, numerical experiments show that the algorithm could be of practical interest.     

Method of solving the Cauchy problem for one-dimensional polywave equation with singular Bessel operator

We study the Cauchy problem for an equation with singular Bessel operator. Unlike traditional methods to solve this problem, we apply Erde´ lyi–Kober fractional operator and find an explicit formula for the desired solution. We prove that the resulting formula is a unique classical solution to the problem.     

A theoretical and empirical investigation on the Lagrangian capacities of the 0-1 multidimensional knapsack problem

We present a novel Lagrangian method to find good feasible solutions in theoretical and empirical aspects. After investigating the concept of Lagrangian capacity, which is the value of the capacity constraint that Lagrangian relaxation can find an optimal solution, we formally reintroduce Lagrangian capacity suitable to the 0-1 multidimensional knapsack problem and present its new geometric equivalent condition including a new associated property. Based on the property, we propose a new Lagrangian heuristic that finds high-quality feasible solutions of the 0-1 multidimensional knapsack problem. We verify the advantage of the proposed heuristic by experiments. We make comparisons with existing Lagrangian approaches on benchmark data and show that the proposed method performs well on large-scale data.     

The Optimal Control of a Train

We consider the problem of determining an optimal driving strategy in a train control problem with a generalised equation of motion. We assume that the journey must be completed within a given time and seek a strategy that minimises fuel consumption. On the one hand we consider the case where continuous control can be used and on the other hand we consider the case where only discrete control is available. We pay particular attention to a unified development of the two cases. For the continuous control problem we use the Pontryagin principle to find necessary conditions on an optimal strategy and show that these conditions yield key equations that determine the optimal switching points. In the discrete control problem, which is the typical situation with diesel-electric locomotives, we show that for each fixed control sequence the cost of fuel can be minimised by finding the optimal switching times. The corresponding strategies are called strategies of optimal type and in this case we use the Kuhn–Tucker equations to find key equations that determine the optimal switching times. We note that the strategies of optimal type can be used to approximate as closely as we please the optimal strategy obtained using continuous control and we present two new derivations of the key equations. We illustrate our general remarks by reference to a typical train control problem.     

Solving the optimal control problem of the parabolic PDEs in exploitation of oil

In this paper, the optimal control problem is governed by weak coupled parabolic PDEs and involves pointwise state and control constraints. We use measure theory method for solving this problem. In order to use the weak solution of problem, first problem has been transformed into measure form. This problem is reduced to a linear programming problem. Then we obtain an optimal measure which is approximated by a finite combination of atomic measures. We find piecewise-constant optimal control functions which are an approximate control for the original optimal control problem.     

A discrete dynamic convexized method for nonlinear integer programming

In this paper, we consider the box constrained nonlinear integer programming problem. We present an auxiliary function, which has the same discrete global minimizers as the problem. The minimization of the function using a discrete local search method can escape successfully from previously converged discrete local minimizers by taking increasing values of a parameter. We propose an algorithm to find a global minimizer of the box constrained nonlinear integer programming problem. The algorithm minimizes the auxiliary function from random initial points. We prove that the algorithm can converge asymptotically with probability one. Numerical experiments on a set of test problems show that the algorithm is efficient and robust.     

A Heuristic for Common Due-date Assignment and Job Scheduling on Parallel Machines

In this paper we consider the problem of scheduling a set of simultaneously available jobs on several parallel and identical machines. The problem is to find the optimal due-date, assuming this to be the same for all jobs. We also seek to sequence the jobs such that some are early and some are late so as to minimize a penalty function. For the single-machine problem, we present a simple proof of the well-known optimality result that the optimal due-date coincides with one of the job completion times. We show that the optimal job sequence for the single-machine problem can be easily determined. We prove that the same optimal due-date result can be generalized to the parallel-machine problem. However, determination of the optimal job sequence for such a problem is much more complex, and we present a simple heuristic to find an approximate solution. On the basis of a limited experiment, we observe that the heuristic is very effective in obtaining near-optimal solutions.     

Optimal stochastic control of the intensity of point processes

We consider an intensity control problem for a point process to maximize the expectation of a function of the time when the nth event occurs. We find the optimal control policy when the objective function is unimodal. Moreover, if the objective function is log-concave, so is the value function. As an application, we completely solve an intensity control problem that generalizes the problem studied by Brémaud (1976) and Defourny (2018). Also, we resolve the two conjectures made by Defourny (2018).     

Rigid Embeddings of Sasakian Hyperquadrics in $$\mathbb {C}^{n+1}$$

We give a classification of Sasakian manifolds that are CR-equivalent to hyperquadrics by describing their exact parameter space. For “ half” of the parameter space, we find an explicit representation by defining equations. This problem is related to the problem of finding pseudo-Kähler potentials with prescribed Ricci curvature.     

Determination of the possibility of rock burst in a coal seam

The article presents an algorithm for computing a quantity that serves as a criterion for the possibility of rock burst in a coal seam.We propose to seek this quantity in the two steps: At the first step, an inverse problem is solved to find the necessary quantities; while at the second step, we solve a boundary value problem for the biharmonic equation. The inverse problem can be solved by minimizing an objective functional that is shown to be strongly convex.     

Riemann problem and singular integral equations with coefficients generated by piecewise constant functions

We study a Riemann boundary value problem with a shift into the interior of the domain. The problem has piecewise constant coefficients that take two values. We find conditions for the existence and uniqueness of a solution of the inhomogeneous problem and formulas for the number of linearly independent solutions of the homogeneous problem. We consider scalar singular integral operators with a shift and matrix characteristic operators whose coefficients are generated by piecewise constant functions and which have automorphic properties. For these operators, we find invertibility conditions.     

The influence of face-to-face communication: a principal-agent experiment

The principal-agent problem is an interesting problem involved in many everyday relationships, such as the one between company owners and their delegates. Our experiment simulates such a relationship, whereby the task of participating pairs is to negotiate labor contracts. Our aim is to find the effects of face-to-face communication and negotiation on contract framing. We argue that including pre-play communication into the principal-agent problem leads to a significant improvement of agent’s effort and results in changes of the compensation scheme. We show that incentives are not the only possibility to induce high effort. We use content analysis of the video-taped negotiations to find some characteristics of the communication process.     

Approximate Penalty Method in Optimal Control Problems for Nonsmooth Singular Systems

We consider an abstract optimal control problem with additional constraints and nonsmooth terms, but without the requirement that both the state equation on the set of admissible controls and the extremum problem be solvable. We use the approximate penalty method proposed here to find an approximate (in the weak sense) solution of the problem. As an example, we consider the optimal control problem for a singular nonlinear elliptic type equation.     

Confidence regional method of stochastic spanning tree problem

We consider a P model version of stochastic spanning tree problems with random edge costs. Parameters of underling probability distribution of edge costs are unknown and so they are estimated by a confidence region from statistical data. The problem is first transformed into a deterministic equivalent problem with a minimax type objective function and a confidence region of means and variances, since we assume normal distributions with respect to random edge costs. Our model reflects the situation that the maximum possible damage due to an unknown parameter should be minimized. We show the problem can be reduced to the deterministic equivalent problem of another stochastic spanning tree problem, which is already investigated by us. Thus, we can find an optimal spanning tree of the original problem very efficiently by this reduction.