0-1多项式规划问题的SDP松弛方法(英)

本文提出了一类新的构造0-1多项式规划的半定规划(SDP)松弛方法. 我们首先利用矩阵分解和分片线性逼近给出一种新的SDP松弛, 该 松弛产生的界比标准线性松弛产生的界更紧. 我们还利用 拉格朗日松弛和平方和(SOS)松弛方法给出了一种构造Lasserre的SDP 松弛的新方法.     

Indefinite stochastic LQ control with cross term via semidefinite programming

An indefinite stochastic linear-quadratic (LQ) optimal control problem with cross term over an infinite time horizon is studied, allowing the weighting matrices to be indefinite. A systematic approach to the problem based on semidefinite programming (SDP) and related duality analysis is developed. Several implication relations among the SDP complementary duality, the existence of the solution to the generalized Riccati equation and the optimality of LQ problem are discussed. Based on these relations, a numerical procedure that provides a thorough treatment of the LQ problem via primal-dual SDP is given: it identifies a stabilizing optimal feedback control or determines the problem has no optimal solution. An example is provided to illustrate the results obtained.     

半定规划的PRP~+共轭梯度法(英文)

本文对半定规划(SDP)的最优性条件提出一价值函数并研究其性质.基此,提出半定规划的PRP+共轭梯度法.为得到PRP+共轭梯度法的收敛性,提出一Armijo-型线搜索.无需水平集有界及迭代点列聚点的存在,算法全局收敛.     

非凸半定规划的增广Lagrangian的微分的计算

迄今为止，还未见出版过有关求解非凸半定规划的算法，但在最近，Chen，et.al(2000)和Sun＆Sun(1999)关于非凸半定规划(SDP)的增广Lagrangian的研究是非常有用的，在本文中，我们证明非凸半定规划的增广Lagrangian是可微的，并且给出它的可微表达式．     

Minimum energy configurations on a toric lattice as a quadratic assignment problem

We consider three known bounds for the quadratic assignment problem (QAP): an eigenvalue, a convex quadratic programming (CQP), and a semidefinite programming (SDP) bound. Since the last two bounds were not compared directly before, we prove that the SDP bound is stronger than the CQP bound. We then apply these to improve known bounds on a discrete energy minimization problem, reformulated as a QAP, which aims to minimize the potential energy between repulsive particles on a toric grid. Thus we are able to prove optimality for several configurations of particles and grid sizes, complementing earlier results by Bouman et al. (2013). The semidefinite programs in question are too large to solve without pre-processing, and we use a symmetry reduction method by Permenter and Parrilo (2020) to make computation of the SDP bounds possible.     

Quadratic convergence of a smoothing Newton method for symmetric cone programming without strict complementarity

This paper deals with symmetric cone programming (SCP), which includes the linear programming (LP), the second-order cone programming (SOCP), the semidefinite programming (SDP) as special cases. Based on the Chen?CMangasarian smoothing function of the projection operator onto symmetric cones, we establish a smoothing Newton method for SCP. Global and quadratic convergence of the proposed algorithm is established under the primal and dual constraint nondegeneracies, but without the strict complementarity. Moreover, we show the equivalence at a Karush?CKuhn?CTucker (KKT) point among the primal and dual constraint nondegeneracies, the nonsingularity of the B-subdifferential of the smoothing counterpart of the KKT system, and the nonsingularity of the corresponding Clarke??s generalized Jacobian.     

A comment on “Measuring super-efficiency in DEA in the presence of infeasibility”

In a recent paper by Chen [Chen, Y., 2005. Measuring super-efficiency in DEA in the presence of infeasibility. European Journal of Operational Research 161 (1), 447–468], he deals with the infeasibility of super-efficiency DEA models in variable returns to scale (VRS) technology. He provides a necessary and sufficient condition for simultaneous infeasibility of input- and output-oriented super-efficiency DEA models in VRS case, then he claims that both of these models are infeasible only for a rare situation. In this paper, we present some counterexamples and comments to the contention by Chen.     

A Semidefinite Programming approach for solving Multiobjective Linear Programming

Several algorithms are available in the literature for finding the entire set of Pareto-optimal solutions of Multiobjective Linear Programmes (MOLPs). However, all of them are based on active-set methods (simplex-like approaches). We present a different method, based on a transformation of any MOLP into a unique lifted Semidefinite Program (SDP), the solutions of which encode the entire set of Pareto-optimal extreme point solutions of any MOLP. This SDP problem can be solved, among other algorithms, by interior point methods; thus unlike an active set-method, our method provides a new approach to find the set of Pareto-optimal solutions of MOLP.     

A model to estimate the size of aggregates formed in a Dissolved Air Flotation unit

In Dissolved Air Flotation (DAF) a solid phase is separated from a liquid phase with the aid of air bubbles. The solid phase is usually coagulated into larger particles termed flocs. The air bubbles and flocs form aggregates, which rise to the surface of the flotation unit where they are removed. In this paper we propose a model that estimates the size of the formed aggregates. The estimation is based on the local balance of forces describing the approach and attachment of flocs to air bubbles. The interaction of flocs and bubbles is described by surface forces, hydrodynamic forces and the buoyancy force. The model is validated with available experimental results and the obtained aggregate sizes agree reasonable with those obtained by the experiments. The approach proposed here is intended for water treatment applications, but can be modified for other flotation processes.     

Optimal design of a sewer line using Linear Programming

Wastewater collection systems greatly contribute to the cost of the overall municipal sewerage system; a cost-effective design of the collection system will provide significant savings towards the cost of wastewater services. It is impossible to evaluate the full impact that each pipe size and slope would have on the overall cost of the collection system with intuitive designs. However, these solutions generally satisfy the design objectives within the given constraints. A survey of the literature indicates that various optimisation techniques are being applied for least-cost solutions. In general these approaches provide continuous pipe sizes, which are converted to closest commercial sizes for adoption, which would heavily dilute the optimal outcome. Search methods are also adopted to obtain cost-effective design solutions using directly commercial pipe sizes, which are computationally expensive. In the design of a sewerage system, a sewer line is a basic unit occurring repeatedly in the design-process and finally the combinations of these basic units formulate the complete sewer system. However, the branch sewer lines, main sewers, trunk sewers, pumping stations, treatment plant and outfall sewers are in general the main components of an urban wastewater collection, treatment and disposal systems. A method has been developed to optimise this basic unit using Linear Programming technique without transforming nonlinear objective function or constraint equations into linear functions and incorporating commercially available pipe sizes directly in the problem formulation. The current research area of optimal sewer system design is focusing equally on economic considerations and hydraulic feasibility and moving away from conventional design guidelines based on only self cleaning velocity concepts for node to node sewer link hydraulic design. This paper is a step forward in developing optimal design approaches of sewer systems.     

Faster,but weaker,relaxations for quadratically constrained quadratic programs

We introduce a new relaxation framework for nonconvex quadratically constrained quadratic programs (QCQPs). In contrast to existing relaxations based on semidefinite programming (SDP), our relaxations incorporate features of both SDP and second order cone programming (SOCP) and, as a result, solve more quickly than SDP. A downside is that the calculated bounds are weaker than those gotten by SDP. The framework allows one to choose a block-diagonal structure for the mixed SOCP-SDP, which in turn allows one to control the speed and bound quality. For a fixed block-diagonal structure, we also introduce a procedure to improve the bound quality without increasing computation time significantly. The effectiveness of our framework is illustrated on a large sample of QCQPs from various sources.     

A space-indexed formulation of packing boxes into a larger box

Current integer programming solvers fail to decide whether 12 unit cubes can be packed into a 1×1×11 box within an hour using the natural relaxation of Chen/Padberg. We present an alternative relaxation of the problem of packing boxes into a larger box, which makes it possible to solve much larger instances.     

Continuous sedimentation of multi-component particles

Continuous sedimentation of solid particles in a liquid takes place in a clarifier-thickener unit, which has one feed inlet and two outlets. The process is vital in a waste water treatment plant, where the particles consist of several biological components. The concentrations of these are modelled by a one-dimensional system of conservation laws with source term. It is shown how a unique solution can be obtained, and how analytical solutions are used to form a conservative numerical algorithm. © 1997 B. G. Teubner Stuttgart–John Wiley & Sons Ltd.     

A conversion of an SDP having free variables into the standard form SDP

This paper deals with a semidefinite program (SDP) having free variables, which often appears in practice. To apply the primal–dual interior-point method, we usually need to convert our SDP into the standard form having no free variables. One simple way of conversion is to represent each free variable as a difference of two nonnegative variables. But this conversion not only expands the size of the SDP to be solved but also yields some numerical difficulties which are caused by the non-existence of a primal–dual pair of interior-feasible solutions in the resulting standard form SDP and its dual. This paper proposes a new conversion method that eliminates all free variables. The resulting standard form SDP is smaller in its size, and it can be more stably solved in general because the SDP and its dual have interior-feasible solutions whenever the original primal–dual pair of SDPs have interior-feasible solutions. Effectiveness of the new conversion method applied to SDPs having free variables is reported in comparison to some other existing methods.     

Cooling system optimization for a terahertz radiation detector via parametric analysis of the fluid-solid interaction problem

The present study considers the optimization of a cooling system incorporated in a radiation detector working on the principle of liquid crystal thermography. Its configuration is that of a rectangular channel of small aspect ratio – inside of which cold water flows – that is directly attached to an extremely-thin detection element, made out of a thermochromic liquid crystal (TLC) layer fixed to a polyester sheet. The analysis places special attention at seeking for the optimal channel height/gap that enables a stable thermal environment for the sensing unit while minimizing its possible deformation. The optimization is carried out by way of a parametric study, based on numerical solutions of a fully-coupled non-dimensional mathematical model describing the fluid-solid mechanical interaction and conjugate heat transfer, for a set of expected operating conditions to establish the relative influence of inlet velocity, heat input and the channel height/gap on the variation in fluid temperature and the solid elastic deformation. It is shown that although quantitatively different, qualitatively the results have similar trends. By defining the corresponding two-objective function, the numerical simulations indicate that, for the set of operating conditions studied, there is a common value for the height/gap of the cooling channel which represents the optimal.     

Local and global returns to scale in performance measurement

In data envelopment analysis, the type of local returns to scale (RTS) exhibited by a technically efficient unit indicates whether an increase or reduction of the scale of operations could improve the productivity of the unit. One of the approaches to testing RTS is based on the comparison of the efficiency of the unit in specially constructed reference technologies. It has been suggested that this approach is equally suitable for convex and non-convex, including the free disposal hull, technologies. In this paper, we construct examples that show that this suggestion in the case of non-convex technologies is not correct. We show that the type of RTS obtained by this approach is not a local, but global, characteristic of the technology, as it indicates the direction to the most productive scale size of the unit. In non-convex technologies, the local and global classifications of RTS are generally different.     

Comparing SOS and SDP relaxations of sensor network localization

We investigate the relationships between various sum of squares (SOS) and semidefinite programming (SDP) relaxations for the sensor network localization problem. In particular, we show that Biswas and Ye’s SDP relaxation is equivalent to the degree one SOS relaxation of Kim et al. We also show that Nie’s sparse-SOS relaxation is stronger than the edge-based semidefinite programming (ESDP) relaxation, and that the trace test for accuracy, which is very useful for SDP and ESDP relaxations, can be extended to the sparse-SOS relaxation.     

A new second-order corrector interior-point algorithm for semidefinite programming

In this paper, we propose a second-order corrector interior-point algorithm for semidefinite programming (SDP). This algorithm is based on the wide neighborhood. The complexity bound is O(?nL){O(\sqrt{n}L)} for the Nesterov-Todd direction, which coincides with the best known complexity results for SDP. To our best knowledge, this is the first wide neighborhood second-order corrector algorithm with the same complexity as small neighborhood interior-point methods for SDP. Some numerical results are provided as well.     

Sums of squares based approximation algorithms for MAX-SAT

We investigate the Semidefinite Programming based sums of squares (SOS) decomposition method, designed for global optimization of polynomials, in the context of the (Maximum) Satisfiability problem. To be specific, we examine the potential of this theory for providing tests for unsatisfiability and providing MAX-SAT upper bounds. We compare the SOS approach with existing upper bound and rounding techniques for the MAX-2-SAT case of Goemans and Williamson [Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42(6) (1995) 1115-1145] and Feige and Goemans [Approximating the value of two prover proof systems, with applications to MAX2SAT and MAXDICUT, in: Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 182-189] and the MAX-3-SAT case of Karloff and Zwick [A 7/8-approximation algorithm for MAX 3SAT? in: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, Miami Beach, FL, USA, IEEE Press, New York, 1997], which are based on Semidefinite Programming as well. We prove that for each of these algorithms there is an SOS-based counterpart which provides upper bounds at least as tight, but observably tighter in particular cases. Also, we propose a new randomized rounding technique based on the optimal solution of the SOS Semidefinite Program (SDP) which we experimentally compare with the appropriate existing rounding techniques. Further we investigate the implications to the decision variant SAT and compare experimental results with those yielded from the higher lifting approach of Anjos [On semidefinite programming relaxations for the satisfiability problem, Math. Methods Oper. Res. 60(3) (2004) 349-367; An improved semidefinite programming relaxation for the satisfiability problem, Math. Programming 102(3) (2005) 589-608; Semidefinite optimization approaches for satisfiability and maximum-satisfiability problems, J. Satisfiability Boolean Modeling Comput. 1 (2005) 1-47].We give some impression of the fraction of the so-called unit constraints in the various SDP relaxations. From a mathematical viewpoint these constraints should be easily dealt within an algorithmic setting, but seem hard to be avoided as extra constraints in an SDP setting. Finally, we briefly indicate whether this work could have implications in finding counterexamples to uncovered cases in Hilbert's Positivstellensatz.