An alternating iterative method and its application in statistical inference

This paper studies non-convex programming problems. It is known that, in statistical inference, many constrained estimation problems may be expressed as convex programming problems. However, in many practical problems, the objective functions are not convex. In this paper, we give a definition of a semi-convex objective function and discuss the corresponding non-convex programming problems. A two-step iterative algorithm called the alternating iterative method is proposed for finding solutions for such problems. The method is illustrated by three examples in constrained estimation problems given in Sasabuchi et al. （Biometrika, 72, 465472 （1983））, Shi N. Z. （J. Multivariate Anal., 50, 282-293 （1994）） and El Barmi H. and Dykstra R. （Ann. Statist., 26, 1878 1893 （1998））.     

SOLVING A CLASS OF INVERSE QP PROBLEMS BY A SMOOTHING NEWTON METHOD

We consider an inverse quadratic programming （IQP） problem in which the parameters in the objective function of a given quadratic programming （QP） problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. This problem can be formulated as a minimization problem with a positive semidefinite cone constraint and its dual （denoted IQD（A, b）） is a semismoothly differentiable （SC^1） convex programming problem with fewer variables than the original one. In this paper a smoothing Newton method is used for getting a Karush-Kuhn-Tucker point of IQD（A, b）. The proposed method needs to solve only one linear system per iteration and achieves quadratic convergence. Numerical experiments are reported to show that the smoothing Newton method is effective for solving this class of inverse quadratic programming problems.     

求解非线性规划的原始对偶内点法(英文)

In this paper, we propose a primal-dual interior point method for solving general constrained nonlinear programming problems. To avoid the situation that the algorithm we use may converge to a saddle point or a local maximum, we utilize a merit function to guide the iterates toward a local minimum. Especially, we add the parameter ε to the Newton system when calculating the decrease directions. The global convergence is achieved by the decrease of a merit function. Furthermore, the numerical results confirm that the algorithm can solve this kind of problems in an efficient way.     

Solving a Class of Brouwer Fixed-point Problems via a Modified Aggregate Constraint Homotopy Method

In this paper, we provide an aggregate function homotopy interior point method to solve a class of Brouwer fixed-point problems. Compared with the homotopy method （proposed by Yu and Lin, Appl. Math. Comput., 74（1996）, 65）, the main adavantages of this method are as foUows： on the one hand, it can solve the Brouwer fixed-point problems in a broader class of nonconvex subsets Ω in R^n （in this paper, we let Ω={x∈ R^n ： gi（x） ≤0, i= 1,... , m}）; on the other hand, it can also deal with the subsets Ω with larger amount of constraints more effectively.     

无记忆非拟 Newton 算法的导出和全局收敛性

In this paper, a new class of memoryless non-quasi-Newton method for solving unconstrained optimization problems is proposed, and the global convergence of this method with inexact line search is proved. Furthermore, we propose a hybrid method that mixes both the memoryless non-quasi-Newton method and the memoryless Perry-Shanno quasi-Newton method. The global convergence of this hybrid memoryless method is proved under mild assumptions. The initial results show that these new methods are efficient for the given test problems. Especially the memoryless non-quasi-Newton method requires little storage and computation, so it is able to efficiently solve large scale optimization problems.     

A feasible decomposition method for constrained equations and its application to complementarity problems

In this paper, by analyzing the propositions of solution of the convex quadratic programming with nonnegative constraints, we propose a feasible decomposition method for constrained equations. Under mild conditions, the global convergence can be obtained. The method is applied to the complementary problems. Numerical results are also given to show the efficiency of the proposed method.     

A Branch and Bound Algorithm for Separable Concave Programming

In this paper, we propose a new branch and bound algorithm for the solution of large scale separable concave programming problems. The largest distance bisection (LDB) technique is proposed to divide rectangle into sub-rectangles when one problem is branched into two subproblems. It is proved that the LDB method is a normal rectangle subdivision(NRS). Numerical tests on problems with dimensions from 100 to 10000 show that the proposed branch and bound algorithm is efficient for solving large scale separable concave programming problems, and convergence rate is faster than ω-subdivision method.     

SEQUENTIAL CONVEX PROGRAMMING METHODS FOR SOLVING LARGE TOPOLOGY OPTIMIZATION PROBLEMS： IMPLEMENTATION AND COMPUTATIONAL RESULTS

In this paper, we describe a method to solve large-scale structural optimization problems by sequential convex programming （SCP）. A predictor-corrector interior point method is applied to solve the strictly convex subproblems. The SCP algorithm and the topology optimization approach are introduced. Especially, different strategies to solve certain linear systems of equations are analyzed. Numerical results are presented to show the efficiency of the proposed method for solving topology optimization problems and to compare different variants.     

METHOD OF CENTERS ALGORITHM FOR MULTI-OBJECTIVE PROGRAMMING PROBLEMS

In this paper, we consider a method of centers for solving multi-objective programming problems, where the objective functions involved are concave functions and the set of feasible points is convex. The algorithm is defined so that the sub-problems that must be solved during its execution may be solved by finite-step procedures. Conditions are given under which the algorithm generates sequences of feasible points and constraint multiplier vectors that have accumulation points satisfying the KKT conditions. Finally, we establish convergence of the proposed method of centers algorithm for solving multiobjective programming problems.     

FINITE ELEMENTS WITH LOCAL PROJECTION STABILIZATION FOR INCOMPRESSIBLE FLOW PROBLEMS

In this paper we review recent developments in the analysis of finite element methods for incompressible flow problems with local projection stabilization （LPS）. These methods preserve the favourable stability and approximation properties of classical residual-based stabilization （RBS） techniques but avoid the strong coupling of velocity and pressure in the stabilization terms. LPS-methods belong to the class of symmetric stabilization techniques and may be characterized as variational multiscale methods. In this work we summarize the most important a priori estimates of this class of stabilization schemes developed in the past 6 years. We consider the Stokes equations, the Oseen linearization and the NavierStokes equations. Furthermore, we apply it to optimal control problems with linear（ized） flow problems, since the symmetry of the stabilization leads to the nice feature that the operations ＂discretize＂ and ＂optimize＂ commute.     

Lagrange multiplier necessary conditions for global optimality for non-convex minimization over a quadratic constraint via S-lemma

In this paper, we present Lagrange multiplier necessary conditions for global optimality that apply to non-convex optimization problems beyond quadratic optimization problems subject to a single quadratic constraint. In particular, we show that our optimality conditions apply to problems where the objective function is the difference of quadratic and convex functions over a quadratic constraint, and to certain class of fractional programming problems. Our necessary conditions become necessary and sufficient conditions for global optimality for quadratic minimization subject to quadratic constraint. As an application, we also obtain global optimality conditions for a class of trust-region problems. Our approach makes use of outer-estimators, and the powerful S-lemma which has played key role in control theory and semidefinite optimization. We discuss numerical examples to illustrate the significance of our optimality conditions. The authors are grateful to the referees for their useful comments which have contributed to the final preparation of the paper.     

Robust duality for generalized convex programming problems under data uncertainty

In this paper we present a robust duality theory for generalized convex programming problems in the face of data uncertainty within the framework of robust optimization. We establish robust strong duality for an uncertain nonlinear programming primal problem and its uncertain Lagrangian dual by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. A robust strong duality theorem is given whenever the Lagrangian function is convex. We provide classes of uncertain non-convex programming problems for which robust strong duality holds under a constraint qualification. In particular, we show that robust strong duality is guaranteed for non-convex quadratic programming problems with a single quadratic constraint with the spectral norm uncertainty under a generalized Slater condition. Numerical examples are given to illustrate the nature of robust duality for uncertain nonlinear programming problems. We further show that robust duality continues to hold under a weakened convexity condition.     

无界区域上非凸规划的同伦方法

In the past few years, much and much attention has been paid to the method for solving non-convex programming. Many convergence results are obtained for bounded sets. In this paper, we get global convergence results for non-convex programming in unbounded sets under suitable conditions.     

Bandwidth packing problem with queueing delays: modelling and exact solution approach

In this paper we develop a general but smooth global optimization strategy for nonlinear multilevel programming problems with polyhedral constraints. At each decision level successive convex relaxations are applied over the non-convex terms in combination with a multi-parametric programming approach. The proposed algorithm reaches the approximate global optimum in a finite number of steps through the successive subdivision of the optimization variables that contribute to the non-convexity of the problem and partitioning of the parameter space. The method is implemented and tested for a variety of bilevel, trilevel and fifth level problems which have non-convexity formulation at their inner levels.     

A Globally Convergent and Efficient Method for Unconstrained Discrete-Time Optimal Control

Shift schemes are commonly used in non-convex situations when solving unconstrained discrete-time optimal control problems by the differential dynamic programming (DDP) method. However, the existing shift schemes are inefficient when the shift becomes too large. In this paper, a new method of combining the DDP method with a shift scheme and the steepest descent method is proposed to cope with non-convex situations. Under certain assumptions, the proposed method is globally convergent and has q-quadratic local conve rgence. Extensive numerical experiments on many test problems in the literature are reported. These numerical results illustrate the robustness and efficiency of the proposed method.     

Multistage stochastic demand-side management for price-making major consumers of electricity in a co-optimized energy and reserve market

In this paper, we take an optimization-driven heuristic approach, motivated by dynamic programming, to solve a class of non-convex multistage stochastic optimization problems. We apply this to the problem of optimizing the timing of energy consumption for a large manufacturer who is a price-making major consumer of electricity. We introduce a mixed-integer program that co-optimizes consumption bids and interruptible load reserve offers, for such a major consumer over a finite time horizon. By utilizing Lagrangian methods, we decompose our model through approximately pricing the constraints that link the stages together. We construct look-up tables in the form of consumption-utility curves, and use these to determine optimal consumption levels. We also present heuristics, in order to tackle the non-convexities within our model, and improve the accuracy of our policies. In the second part of the paper, we present stochastic solution methods for our model in which, we reduce the size of the scenario tree by utilizing a tailor-made scenario clustering method. Furthermore, we report on a case study that implements our models for a major consumer in the (full) New Zealand Electricity Market and present numerical results.     

Deterministic solution approach for some classes of nonlinear multilevel programs with multiple followers

In this paper we investigate multilevel programming problems with multiple followers in each hierarchical decision level. It is known that such type of problems are highly non-convex and hard to solve. A solution algorithm have been proposed by reformulating the given multilevel program with multiple followers at each level that share common resources into its equivalent multilevel program having single follower at each decision level. Even though, the reformulated multilevel optimization problem may contain non-convex terms at the objective functions at each level of the decision hierarchy, we applied multi-parametric branch-and-bound algorithm to solve the resulting problem that has polyhedral constraints. The solution procedure is implemented and tested for a variety of illustrative examples.     

Relaxations of linear programming problems with first order stochastic dominance constraints

Linear stochastic programming problems with first order stochastic dominance (FSD) constraints are non-convex. For their mixed 0-1 linear programming formulation we present two convex relaxations based on second order stochastic dominance (SSD). We develop necessary and sufficient conditions for FSD, used to obtain a disjunctive programming formulation and to strengthen one of the SSD-based relaxations.     

Nonlinear robust optimization via sequential convex bilevel programming

In this paper, we present a novel sequential convex bilevel programming algorithm for the numerical solution of structured nonlinear min–max problems which arise in the context of semi-infinite programming. Here, our main motivation are nonlinear inequality constrained robust optimization problems. In the first part of the paper, we propose a conservative approximation strategy for such nonlinear and non-convex robust optimization problems: under the assumption that an upper bound for the curvature of the inequality constraints with respect to the uncertainty is given, we show how to formulate a lower-level concave min–max problem which approximates the robust counterpart in a conservative way. This approximation turns out to be exact in some relevant special cases and can be proven to be less conservative than existing approximation techniques that are based on linearization with respect to the uncertainties. In the second part of the paper, we review existing theory on optimality conditions for nonlinear lower-level concave min–max problems which arise in the context of semi-infinite programming. Regarding the optimality conditions for the concave lower level maximization problems as a constraint of the upper level minimization problem, we end up with a structured mathematical program with complementarity constraints (MPCC). The special hierarchical structure of this MPCC can be exploited in a novel sequential convex bilevel programming algorithm. We discuss the surprisingly strong global and locally quadratic convergence properties of this method, which can in this form neither be obtained with existing SQP methods nor with interior point relaxation techniques for general MPCCs. Finally, we discuss the application fields and implementation details of the new method and demonstrate the performance with a numerical example.