A Decomposition Method for Global and Local Quadratic Minimization

We present a decomposition method for indefinite quadratic programming problems having n variables and m linear constraints. The given problem is decomposed into at most m QP subproblems each having m linear constraints and n-1 variables. All global minima, all isolated local minima and some of the non-isolated local minima for the given problem are obtained from those of the lower dimensional subproblems. One way to continue solving the given problem is to apply the decomposition method again to the subproblems and repeatedly doing so until subproblems of dimension 1 are produced and these can be solved directly. A technique to reduce the potentially large number of subproblems is formulated.     

A Cutting Plane Approach to Solving Quadratic Infinite Programs on Measure Spaces

We study infinite dimensional quadratic programming (QP) problems of integral type. The decision variable is taken in the space of bounded regular Borel measures on compact Hausdorff spaces. An implicit cutting plane algorithm is developed to obtain an optimal solution of the infinite dimensional QP problem. The major computational tasks in using the implicit cutting plane approach to solve infinite dimensional QP problems lie in finding a global optimizer of a non-linear and non-convex program. We present an explicit scheme to relax this requirement and to get rid of the unnecessary constraints in each iteration in order to reduce the size of the computatioinal programs. A general convergence proof of this approach is also given.     

解带有二次约束二次规划的一个整体优化方法

在本文中，我们提出了一种解带有二次约束二次规划问题（QP）的新算法，这种方法是基于单纯形分枝定界技术，其中包括极小极大问题和线性规划问题作为子问题，利用拉格朗日松弛和投影次梯度方法来确定问题（QP）最优值的下界，在问题（QP）的可行域是n维的条件下，如果这个算法有限步后终止，得到的点必是问题（QP）的整体最优解；否则，该算法产生的点的序列{v^k}的每一个聚点也必是问题（QP）的整体最优解。     

Application of sequential quadratic programming software program to an actual problem

We produced a nonlinear optimization software program which is based on a Sequential Quadratic Programming (SQP) method (Schittkowski, 1981a). Our program has several original characteristics: (1) automatic choice between two QP solvers, the Goldfarb—Idnani (GI) method (Goldfarb and Idnani, 1983) and the Least Squares (LS) method (Schittkowski, 1981b); (2) an augmented Lagrange function (Schittkowski, 1981a) as the objective function for line search; (3) adaptive Armijo method for line search; (4) direct definition of upper and lower bounds for variables and constraint functions; and (5) accurate numerical differentials. These characteristics ensure the reliability of our program for solving standard problems. In this paper, point (3) is described in detail. Then, the program is applied to an actual problem, the optimal placement of blocks. A model for this problem has been suggested by Sha and Dutton (1984), but it was unsuited to treatment by the SQP method. Thus we modify it to ensure program applicability.     

Standard bi-quadratic optimization problems and unconstrained polynomial reformulations

A so-called Standard Bi-Quadratic Optimization Problem (StBQP) consists in minimizing a bi-quadratic form over the Cartesian product of two simplices (so this is different from a Bi-Standard QP where a quadratic function is minimized over the same set). An application example arises in portfolio selection. In this paper we present a bi-quartic formulation of StBQP, in order to get rid of the sign constraints. We study the first- and second-order optimality conditions of the original StBQP and the reformulated bi-quartic problem over the product of two Euclidean spheres. Furthermore, we discuss the one-to-one correspondence between the global/local solutions of StBQP and the global/local solutions of the reformulation. We introduce a continuously differentiable penalty function. Based upon this, the original problem is converted into the problem of locating an unconstrained global minimizer of a (specially structured) polynomial of degree eight.     

Linear multiplicative programming

An algorithm for solving a linear multiplicative programming problem (referred to as LMP) is proposed. LMP minimizes the product of two linear functions subject to general linear constraints. The product of two linear functions is a typical non-convex function, so that it can have multiple local minima. It is shown, however, that LMP can be solved efficiently by the combination of the parametric simplex method and any standard convex minimization procedure. The computational results indicate that the amount of computation is not much different from that of solving linear programs of the same size. In addition, the method proposed for LMP can be extended to a convex multiplicative programming problem (CMP), which minimizes the product of two convex functions under convex constraints.     

A New Semidefinite Programming Bound for Indefinite Quadratic Forms Over a Simplex

The paper describes a method for computing a lower bound of the global minimum of an indefinite quadratic form over a simplex. The bound is derived by computing an underestimator of the convex envelope by solving a semidefinite program (SDP). This results in a convex quadratic program (QP). It is shown that the optimal value of the QP is a lower bound of the optimal value of the original problem. Since there exist fast (polynomial time) algorithms for solving SDP's and QP's the bound can be computed in reasonable time. Numerical experiments indicate that the relative error of the bound is about 10 percent for problems up to 20 variables, which is much better than a known SDP bound.     

Application of the dual active set algorithm to quadratic network optimization

A new algorithm, the dual active set algorithm, is presented for solving a minimization problem with equality constraints and bounds on the variables. The algorithm identifies the active bound constraints by maximizing an unconstrained dual function in a finite number of iterations. Convergence of the method is established, and it is applied to convex quadratic programming. In its implementable form, the algorithm is combined with the proximal point method. A computational study of large-scale quadratic network problems compares the algorithm to a coordinate ascent method and to conjugate gradient methods for the dual problem. This study shows that combining the new algorithm with the nonlinear conjugate gradient method is particularly effective on difficult network problems from the literature.     

使用自正则度量的凸二次规划的原始对偶内点法的多项式复杂性

最近Peng等人使用新的搜索方向和自正则度量为求解线性规划问题提出了一个原始对偶内点法.本文将这个长步法延伸到凸二次规划.在线性规划情形时,原始空间和对偶空间中的尺度Newton方向是正交的,而在二次规划情形时这是不成立的.本文将处理这个问题并且证明多项式复杂性,并且得到复杂性的上界为O(n√log n log (n/ε)).     

The projection method of optimization applied to engineering plasticity problems

In engineering plasticity, the behavior of a structure (e.g., a frame or truss) under a variety of loading conditions is studied. Two primary types of analysis are generally conducted. Limit analysis determines the rigid plastic collapse load for a structure and can be formulated as a linear program (LP). Deformation analysis at plastic collapse can be formulated as a quadratic program (QP). The constraints of the two optimization problems are closely related. This paper presents a specialization of the projection method for linear programming for the limit-load analysis problem. The algorithm takes advantage of the relationship between the LP constraints and QP constraints to provide advantageous starting data for the projection method applied to the QP problem. An important feature of the method is that it avoids problems of apparent infeasibility due to roundoff errors. Experimental results are given for two medium-sized problems.This work was supported by the National Research Council of Canada under Research Grant No. A8189.     

球约束凸二次规划的一个新算法

首先利用Lagrange对偶 ,将球约束凸二次规划问题转化为无约束优化问题 ,然后运用单纯形法求解无约束优化问题 ,从而获得原问题的最优解     

A FPTAS for computing a symmetric Leontief competitive economy equilibrium

In this paper, we consider a linear complementarity problem (LCP) arisen from the Nash and Arrow–Debreu competitive economy equilibria where the LCP coefficient matrix is symmetric. We prove that the decision problem, to decide whether or not there exists a complementary solution, is NP-complete. Under certain conditions, an LCP solution is guaranteed to exist and we present a fully polynomial-time approximation scheme (FPTAS) for approximating a complementary solution, although the LCP solution set can be non-convex or non-connected. Our method is based on approximating a quadratic social utility optimization problem (QP) and showing that a certain KKT point of the QP problem is an LCP solution. Then, we further show that such a KKT point can be approximated with a new improved running time complexity ${{O}((\frac{n^4}{\epsilon})\log\log(\frac{1}{\epsilon}))}$ arithmetic operation in accuracy ${\epsilon \in (0,1)}$ . We also report preliminary computational results which show that the method is highly effective. Applications in competitive market model problems with other utility functions are also presented, including global trading and dynamic spectrum management problems.     

A note on the strong polynomiality of convex quadratic programming

We prove that a general convex quadratic program (QP) can be reduced to the problem of finding the nearest point on a simplicial cone inO(n ³ +n logL) steps, wheren andL are, respectively, the dimension and the encoding length of QP. The proof is quite simple and uses duality and repeated perturbation. The implication, however, is nontrivial since the problem of finding the nearest point on a simplicial cone has been considered a simpler problem to solve in the practical sense due to its special structure. Also we show that, theoretically, this reduction implies that (i) if an algorithm solves QP in a polynomial number of elementary arithmetic operations that is independent of the encoding length of data in the objective function then it can be used to solve QP in strongly polynomial time, and (ii) ifL is bounded by a first order exponential function ofn then (i) can be stated even in stronger terms: to solve QP in strongly polynomial time, it suffices to find an algorithm running in polynomial time that is independent of the encoding length of the quadratic term matrix or constraint matrix. Finally, based on these results, we propose a conjecture.corresponding author. The research was done when the author was at the Department of IE & OR, University of California at Berkeley, and partially supported by ONR grant N00014-91-j-1241.     

Adaptive regularization with cubics on manifolds

Mathematical Programming - Adaptive regularization with cubics (ARC) is an algorithm for unconstrained, non-convex optimization. Akin to the trust-region method, its iterations can be thought of as...     

Reducing quadratic programming problem to regression problem: Stepwise algorithm

Quadratic programming is concerned with minimizing a convex quadratic function subject to linear inequality constraints. The variables are assumed to be nonnegative. The unique solution of quadratic programming (QP) problem (QPP) exists provided that a feasible region is non-empty (the QP has a feasible space).A method for searching for the solution to a QP is provided on the basis of statistical theory. It is shown that QPP can be reduced to an appropriately formulated least squares (LS) problem (LSP) with equality constraints and nonnegative variables. This approach allows us to obtain a simple algorithm to solve QPP. The applicability of the suggested method is illustrated with numerical examples.     

求解无约束优化问题的一个秩一适定方法

在本文中,我们给出一个求解无约束优化问题的秩一适定方法,该方法具有下述较好性质:校正矩阵是对称正定的;在适当条件下,对非凸函数拥有全局收敛性.我们还给出数值检验结果.     

基于动力系统的线性不等式组的解法

本文提出了一种新的求解线性不等式组可行解的方法-基于动力系统的方法．假设线性不等式组的可行域为非空,在可行域的相对内域上建立一个非线性关系表达式,进而得到一个结构简单的动力系统模型．同时,定义了穿越方向。文章最后的数值实验结果表明此算法是有效的．     

Investigating a hybrid simulated annealing and local search algorithm for constrained optimization

Constrained Optimization Problems (COP) often take place in many practical applications such as kinematics, chemical process optimization, power systems and so on. These problems are challenging in terms of identifying feasible solutions when constraints are non-linear and non-convex. Therefore, finding the location of the global optimum in the non-convex COP is more difficult as compared to non-convex bound-constrained global optimization problems. This paper proposes a Hybrid Simulated Annealing method (HSA), for solving the general COP. HSA has features that address both feasibility and optimality issues and here, it is supported by a local search procedure, Feasible Sequential Quadratic Programming (FSQP). We develop two versions of HSA. The first version (HSAP) incorporates penalty methods for constraint handling and the second one (HSAD) eliminates the need for imposing penalties in the objective function by tracing feasible and infeasible solution sequences independently. Numerical experiments show that the second version is more reliable in the worst case performance.     

Elimination of bounds in optimization problems by transforming variables

The problem of minimizing a nonlinear objective function ofn variables, with continuous first and second partial derivatives, subject to nonnegativity constraints or upper and lower bounds on the variables is studied. The advisability of solving such a constrained optimization problem by making a suitable transformation of its variables in order to change the problem into one of unconstrained minimization is considered. A set of conditions which guarantees that every local minimum of the new unconstrained problem also satisfies the first-order necessary (Kuhn—Tucker) conditions for a local minimum of the original constrained problem is developed. It is shown that there are certain conditions under which the transformed objective function will maintain the convexity of the original objective function in a neighborhood of the solution. A modification of the method of transformations which moves away from extraneous stationary points is introduced and conditions under which the method generates a sequence of points which converges to the solution at a superlinear rate are given.     

Active-Set Projected Trust-Region Algorithm for Box-Constrained Nonsmooth Equations

In this paper, by means of an active-set strategy, we present a trust-region method for solving box-constrained nonsmooth equations. Nice properties of the proposed method include: (a) all iterates remain feasible; (b) the search direction, as adequate combination of the projected gradient direction and the trust-region direction, is an asymptotic Newton direction under mild conditions; (c) the subproblem of the proposed method, possessing the form of an unconstrained trust-region subproblem, can be solved by existing methods; (d) the subproblem of the proposed method is of reduced dimension, which is potentially cheaper when applied to solve large-scale problems. Under appropriate conditions, we establish global and local superlinear/quadratic convergence of the method. Preliminary numerical results are given.