A POLYNOMIAL PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one corrector step after each predictor step, where Step 2 is a predictor step and Step 4 is a corrector step in the algorithm. In the algorithm, the predictor step decreases the dual gap as much as possible in a wider neighborhood of the central path and the corrector step draws iteration points back to a narrower neighborhood and make a reduction for the dual gap. It is shown that the algorithm has O（√nL） iteration complexity which is the best result for convex quadratic programming so far.

A Combined Homotopy Infeasible Interior-Point Method for Convex Nonlinear Programming

In this paper, on the basis of the logarithmic barrier function and KKT conditions, we propose a combined homotopy infeasible interior-point method （CHIIP） for convex nonlinear programming problems. For any convex nonlinear programming, without strict convexity for the logarithmic barrier function, we get different solutions of the convex programming in different cases by CHIIP method.

Predictor-corrector interior-point algorithm for linearly constrained convex programming

Active set method and gradient projection method are curre nt ly the main approaches for linearly constrained convex programming. Interior-po int method is one of the most effective choices for linear programming. In the p aper a predictor-corrector interior-point algorithm for linearly constrained c onvex programming under the predictor-corrector motivation was proposed. In eac h iteration, the algorithm first performs a predictor-step to reduce the dualit y gap and then a corrector-step to keep the points close to the central traject ory. Computations in the algorithm only require that the initial iterate be nonn egative while feasibility or strict feasibility is not required. It is proved th at the algorithm is equivalent to a level-1 perturbed composite Newton method. Numerical experiments on twenty-six standard test problems are made. The result s show that the proposed algorithm is stable and robust.

Stochastic level-value approximation for quadratic integer convex programming

We propose a stochastic level value approximation method for a quadratic integer convex minimizing problem in this paper. This method applies an importance sampling technique, and make use of the cross-entropy method to update the sample density functions. We also prove the asymptotic convergence of this algorithm, and report some numerical results to illuminate its effectiveness.

A POTENTIAL REDUCTION ALGORITHM FOR LINEARLY CONSTRAINED CONVEX PROGRAMMING

A potential reduction algorithm is proposed for optimization of a convex function subject to linear constraints.At each step of the algorithm,a system of linear equations is solved to get a search direction and the Armijo's rule is used to determine a stepsize.It is proved that the algorithm is globally convergent.Computational results are reported.

Fast First-Order Methods for Minimizing Convex Composite Functions

Two new versions of accelerated first-order methods for minimizing convex composite functions are proposed. In this paper, we first present an accelerated first-order method which chooses the step size 1/ Lk to be 1/ L0 at the beginning of each iteration and preserves the computational simplicity of the fast iterative shrinkage-thresholding algorithm. The first proposed algorithm is a non-monotone algorithm. To avoid this behavior, we present another accelerated monotone first-order method. The proposed two accelerated first-order methods are proved to have a better convergence rate for minimizing convex composite functions. Numerical results demonstrate the efficiency of the proposed two accelerated first-order methods.

NEWTON METHOD FOR SOLVING A CLASS OF SMOOTH CONVEX PROGRAMMING

An algorithm for solving a class of smooth convex programming is given. Using smooth exact multiplier penalty function, a smooth convex programming is minimized to a minimizing strongly convex function on the compact set was reduced. Then the strongly convex function with a Newton method on the given compact set was minimized.

Checking weak and strong optimality of the solution to interval convex quadratic program

In this paper,we investigate three canonical forms of interval convex quadratic pro-gramming problems.Necessary and suficient conditions for checking weak and strong optimality of given vector corresponding to various forms of feasible region,are established respectively.By using the concept of feasible direction,these conditions are formulated in the form of linear systems with both equations and inequalities.In addition,we provide two specific examples to illustrate the efficiency of the conditions.

PARALLEL MULTIPLICATIVE ITERATIVE METHODS FOR CONVEX PROGRAMMING

In this paper, we present two parallel multiplicative algorithms for convex programming. If the objective function has compact level sets and has a locally Lipschitz continuous gradient, we discuss convergence of the algorithms. The proofs are essentially based on the results of sequential methods shown by Eggermontt[1].

The Second-Order Differential Equation System with the Feedback Controls for Solving Convex Programming

In this paper, we establish the second-order differential equation system with the feedback controls for solving the problem of convex programming. Using Lagrange function and projection operator, the equivalent operator equations for the convex programming problems under the certain conditions are obtained. Then a second-order differential equation system with the feedback controls is constructed on the basis of operator equation. We prove that any accumulation point of the trajectory of the second-order differential equation system with the feedback controls is a solution to the convex programming problem. In the end, two examples using this differential equation system are solved. The numerical results are reported to verify the effectiveness of the second-order differential equation system with the feedback controls for solving the convex programming problem.

Optimal deployment of swarm positions in cooperative interception of multiple UAV swarms

In order to prevent the attacker from breaking through the blockade of the interception,deploying multiple Unmanned Aerial Vehicle(UAV)swarms on the interception line is a new combat style.To solve the optimal deployment of swarm positions in the cooperative interception,an optimal deployment optimization model is presented by minimizing the penetration zones'area and the analytical expression of the optimal deployment positions is deduced.Firstly,from the view of the attackers breaking through the interception line,the situations of vertical penetration and oblique penetration are analyzed respectively,and the mathematical models of penetration zones are obtained under the condition of a single UAV swarm and multiple UAV swarms.Secondly,based on the optimization goal of minimizing the penetration area,the optimal deployment optimization model for swarm positions is proposed,and the analytical solution of the optimal deployment is solved by using the convex programming theory.Finally,the proposed optimal deployment is compared with the uniform deployment and random deployment to verify the validity of the theoretical analysis.

CONTINUUM TOPOLOGY OPTIMIZATION FOR MONOLITHIC COMPLIANT MECHANISMS OF MICRO-ACTUATORS

A multi-objective scheme for structural topology optimization of distributed compliant mechanisms of micro-actuators in MEMS condition is presented in this work, in which mechanical flexibility and structural stiffness are both considered as objective functions. The compliant micro-mechanism developed in this way can not only provide sufficient output work but also have sufficient rigidity to resist reaction forces and maintain its shape when holding the work-piece. A density filtering approach is also proposed to eliminate numerical instabilities such as checkerboards, mesh-dependency and one-node connected hinges occurring in resulting mechanisms. SIMP is used as the interpolation scheme to indicate the dependence of material modulus on element-regularized densities. The sequential convex programming method, such as the method of moving asymptotes （MMA）, is used to solve the optimization problem. The validation of the presented methodologies is demonstrated by a typical numerical example.

Projection type neural network and its convergence analysis

Projection type neural network for optimization problems has advantages over other networks for fewer parameters , low searching space dimension and simple structure. In this paper, by properly constructing a Lyapunov energy function, we have proven the global convergence of this network when being used to optimize a continuously differentiable convex function defined on a closed convex set. The result settles the extensive applicability of the network. Several numerical examples are given to verify the efficiency of the network.

Resource Planning and Allocation Problem Under Uncertain Environment

This paper generalizes the classic resource allocation problem to the resource planning and allocation problem, in which the resource itself is a decision variable and the cost of each activity is uncertain when the resource is determined. The authors formulate this problem as a two-stage stochastic programming. The authors first propose an efficient algorithm for the case with finite states. Then, a sudgradient method is proposed for the general case and it is shown that the simple algorithm for the unique state case can be used to compute the subgradient of the objective function. Numerical experiments are conducted to show the effectiveness of the model.

Energy Efficiency Optimization for D2D Communications Based on SCA and GP Method

In this paper, we propose an energy-efficient power control scheme for device-to-device(D2D) communications underlaying cellular networks, where multiple D2D pairs reuse the same resource blocks allocated to one cellular user. Taking the maximum allowed transmit power and the minimum data rate requirement into consideration, we formulate the energy efficiency maximization problem as a non-concave fractional programming(FP) problem and then develop a two-loop iterative algorithm to solve it. In the outer loop, we adopt Dinkelbach method to equivalently transform the FP problem into a series of parametric subtractive-form problems, and in the inner loop we solve the parametric subtractive problems based on successive convex approximation and geometric programming method to obtain the solutions satisfying the KarushKuhn-Tucker conditions. Simulation results demonstrate the validity and efficiency of the proposed scheme, and illustrate the impact of different parameters on system performance.

Robust predictive control of uncertain intergrating linear systems with input constraints

This paper presents a two-stage robust model predictive control (RMPC) algorithm named as IRMPC for uncertain linear integrating plants described by a state-space model with input constraints. The global convergence of the resulted closed loop system is guaranteed under mild assumption. The simulation example shows its validity and better performance than conventional Min-Max RMPC strategies.

An ECN-based Optimal Flow Control Algorithm for the Internet

According to the Wide Area Network model, we formulate Internet flow control as a constrained convex programming problem, where the objective is to maximize the total utility of all sources over their transmission rates. Based on this formulation, flow control can be converted to a normal unconstrained optimization problem through the barrier function method, so that it can be solved by means of a gradient projection algorithm with properly rate iterations. We prove that the algorithm converges to the global optimal point, which is also a stable proportional fair rate allocation point, provided that the step size is properly chosen. The main difficulty facing the realization of iteration algorithm is the distributed computation of congestion measure. Fortunately, Explicit Congestion Notification (ECN) is likely to be used to improve the performance of TCP in the near future. By using ECN, it is possible to realize the iteration algorithm in IP networks. Our algorithm is divided into two parts, algorithms in the router and in the source. The router marks the ECN bit with a probability that varies as its buffer occupancy varies, so that the congestion measure of links can be communicated to the source when the marked ECN bits are reflected back from its destination. Source rates are then updated by all sessions according to the received congestion measure. The main advantage of our scheme is its fast convergence ability and robustness; it can also provide the network with zero packet loss by properly choosing the queue threshold and provide differentiated service to users by applying different utility functions.

Existence results for generalized vector equilibrium problems with applications

By a coincidence theorem, some existence theorems of solutions are proved for four types of generalized vector equilibrium problems with moving cones. Applications to the generalized semi-infinite programs with the generalized vector equilibrium constraints under the mild conditions are also given. The results of this paper unify and improve the corresponding results in the previous literature.

Approximate Customized Proximal Point Algorithms for Separable Convex Optimization

Proximal point algorithm(PPA)is a useful algorithm framework and has good convergence properties.Themain difficulty is that the subproblems usually only have iterative solutions.In this paper,we propose an inexact customized PPA framework for twoblock separable convex optimization problem with linear constraint.We design two types of inexact error criteria for the subproblems.The first one is absolutely summable error criterion,under which both subproblems can be solved inexactly.When one of the two subproblems is easily solved,we propose another novel error criterion which is easier to implement,namely relative error criterion.The relative error criterion only involves one parameter,which is more implementable.We establish the global convergence and sub-linear convergence rate in ergodic sense for the proposed algorithms.The numerical experiments on LASSO regression problems and total variation-based image denoising problem illustrate that our new algorithms outperform the corresponding exact algorithms.

Solving the Binary Linear Programming Model in Polynomial Time

The paper presents a technique for solving the binary linear programming model in polynomial time. The general binary linear programming problem is transformed into a convex quadratic programming problem. The convex quadratic programming problem is then solved by interior point algorithms. This settles one of the open problems of whether P = NP or not. The worst case complexity of interior point algorithms for the convex quadratic problem is polynomial. It can also be shown that every liner integer problem can be converted into binary linear problem.