带等式约束非线性规划的一个几何特征

在R~n上,求解二次函数的无约束优化问题已形成了一大类算法。尤其当函数是具有对称正定Hesse矩阵的二次函数时,其极小点h的求出更为简单。它可以通过直线而达到,且h=x(1)。其中H和g分别是f的阵和梯度向量。很显然,将二次函数极小化的这些优点引入到一般的非线性规划将是有价值的工作。 Mcdowell[1],[2]已就无约束优化问题做了一定的工作。本文进一步讨论约束非线性规划的情况。我们在约束流形中极小点h的邻域内,诱导了一类特殊的仿射联     

圆锥函数的共轭方向法

本文是以正定圆锥函数为基础来建立共轭方向法。由于正定二次函数是正定圆锥函数的特殊情况,正定圆锥函数是正定二次函数的扩充,因此本文建立的正定圆锥函数的共轭方向法就是以正定二次函数为基础建立起来的共轭方向法的推广,它在理论上,将后者向前推进了一大步,在应用上,扩大了后者的应用范围。     

一类亚半正定矩阵的左右逆特征值问题

1．引言在工程技术中常常遇到这样一类逆特征值问题：要求在一个矩阵集合S中，找具有给定的部分右特征对（特征值及相应的特征向量）和给定的部分左特征对（特征值及相应的特征向量）的矩阵．文［2］，［3］讨论了S为。x。实矩阵集合的情形．文［4］－［7］对S为nxn实对称矩阵．对称正定矩阵，对称半正定矩阵集合的情形进行了讨论．文【川讨论了S为亚正定阵集合的情形．并提到了对于亚半正定矩阵的情形目下无人涉及，有待进一步研究．本文将对S为nxn亚半正定矩阵集合的情形进行讨论．给出了亚半正定矩阵的左右逆特征值问题有解的充要条件…     

拟正定算子值函数与拟完全单调算子值函数

§1.引言·预备知识 作为正定函数的推广,引进具有有限个负二次式的正定连续函数(本文称为拟正定连续函数),并得到这类函数的积分表达式。夏道行讨论了具有有限个负二次式的条件正定广义函数,统一了的条件正定广义函数和的理论,拓广了[1,3]中的结果。Sakai讨论了群上拟正定连续函数在空间中的酉表示。对     

数形结合求解一类二次问题

二次函数在区间上的最值以及零点问题是高考对二次函数考察的核心内容．关于这两方面的问题,通法是对参数分类讨论,观察对称轴与所给区间之间的关系,再借助二次函数图像进行求解．此法计算复杂,需讨论情况繁多,对解题带来很大不便．下面借助函数方程的思想,数形结合求解“已知最值,求解参数取值范同“及”已知函数在区间上的零点情况,求解...     

关于矩阵奇异值p-范数的讨论的注记

指出近期矩阵奇异值p-范数的讨论中一些值得商榷的问题．应用已有的半正定Hermitian矩阵特征值和迹的性质，我们研究了相关问题．     

泛正定矩阵的进一步研究

给出了泛正定矩阵的重要性质与充要条件.进而提出了新的泛正定与泛非负定矩阵子集类的定义.在其基础上给出泛正定子集类的一系列性质,尤其是推广了Minkowski不等式.最后讨论了泛非负定子集类上的一种新的矩阵偏序的性质与充要条件.     

降维梯度法

§1.引言 本文研究降维梯度法,它具有共轭梯度法的一切性质.对于正定二次函数,用不着精确的一维搜索,只要在每步加入两个校正项,即可将高阶问题转化为低阶问题,保证了二     

关于半正定性与偏序关系的两个问题

在讨论参数估计的容许性问题时，我们常常要考虑矩阵的偏序关系．即设A，B均为n阶对称矩阵．著A-B是非负定阵，则称A大于等于B，记作A≥B，记号A≥0表示A为半正定阵．由矩阵不等式可导出根多数值不等式，如文[1]中有如下众所周知的结论：     

常系数线性微分方程组的ляпунов函数的公式

<正> §1.引言 我们考虑实常系数线性微分方程组(?)Ляпунов早已证明:如果(1)的特征方程(?)所有的根皆具负实部,那末对于任意给定的负定(正定)m 次齐次多项式 U(x_1,…,x_n),恒存在唯一正定(负定)m 次齐次多项式 V(x_1,…,x_n)满足方程     

Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations

We show that SDP (semidefinite programming) and SOCP (second order cone programming) relaxations provide exact optimal solutions for a class of nonconvex quadratic optimization problems. It is a generalization of the results by S. Zhang for a subclass of quadratic maximization problems that have nonnegative off-diagonal coefficient matrices of quadratic objective functions and diagonal coefficient matrices of quadratic constraint functions. A new SOCP relaxation is proposed for the class of nonconvex quadratic optimization problems by extracting valid quadratic inequalities for positive semidefinite cones. Its effectiveness to obtain optimal values is shown to be the same as the SDP relaxation theoretically. Numerical results are presented to demonstrate that the SOCP relaxation is much more efficient than the SDP relaxation.     

Simple solution methods for separable mixed linear and quadratic knapsack problem

Quadratic knapsack problem has a central role in integer and nonlinear optimization, which has been intensively studied due to its immediate applications in many fields and theoretical reasons. Although quadratic knapsack problem can be solved using traditional nonlinear optimization methods, specialized algorithms are much faster and more reliable than the nonlinear programming solvers. In this paper, we study a mixed linear and quadratic knapsack with a convex separable objective function subject to a single linear constraint and box constraints. We investigate the structural properties of the studied problem, and develop a simple method for solving the continuous version of the problem based on bi-section search, and then we present heuristics for solving the integer version of the problem. Numerical experiments are conducted to show the effectiveness of the proposed solution methods by comparing our methods with some state of the art linear and quadratic convex solvers.     

Stochastic second-order cone programming: Applications models

Second-order cone programs are a class of convex optimization problems. We refer to them as deterministic second-order cone programs (DSCOPs) since data defining them are deterministic. In DSOCPs we minimize a linear objective function over the intersection of an affine set and a product of second-order (Lorentz) cones. Stochastic programs have been studied since 1950s as a tool for handling uncertainty in data defining classes of optimization problems such as linear and quadratic programs. Stochastic second-order cone programs (SSOCPs) with recourse is a class of optimization problems that defined to handle uncertainty in data defining DSOCPs. In this paper we describe four application models leading to SSOCPs.     

Stabilized Sequential Quadratic Programming

Recently, Wright proposed a stabilized sequential quadratic programming algorithm for inequality constrained optimization. Assuming the Mangasarian-Fromovitz constraint qualification and the existence of a strictly positive multiplier (but possibly dependent constraint gradients), he proved a local quadratic convergence result. In this paper, we establish quadratic convergence in cases where both strict complementarity and the Mangasarian-Fromovitz constraint qualification do not hold. The constraints on the stabilization parameter are relaxed, and linear convergence is demonstrated when the parameter is kept fixed. We show that the analysis of this method can be carried out using recent results for the stability of variational problems.     

A Conic Trust-Region Method for Nonlinearly Constrained Optimization

Trust-region methods are powerful optimization methods. The conic model method is a new type of method with more information available at each iteration than standard quadratic-based methods. Can we combine their advantages to form a more powerful method for constrained optimization? In this paper we give a positive answer and present a conic trust-region algorithm for non-linearly constrained optimization problems. The trust-region subproblem of our method is to minimize a conic function subject to the linearized constraints and the trust region bound. The use of conic functions allows the model to interpolate function values and gradient values of the Lagrange function at both the current point and previous iterate point. Since conic functions are the extension of quadratic functions, they approximate general nonlinear functions better than quadratic functions. At the same time, the new algorithm possesses robust global properties. In this paper we establish the global convergence of the new algorithm under standard conditions.     

An SQP algorithm for extended linear-quadratic problems in stochastic programming

Extended Linear-Quadratic Programming (ELQP) problems were introduced by Rockafellar and Wets for various models in stochastic programming and multistage optimization. Several numerical methods with linear convergence rates have been developed for solving fully quadratic ELQP problems, where the primal and dual coefficient matrices are positive definite. We present a two-stage sequential quadratic programming (SQP) method for solving ELQP problems arising in stochastic programming. The first stage algorithm realizes global convergence and the second stage algorithm realizes superlinear local convergence under a condition calledB-regularity.B-regularity is milder than the fully quadratic condition; the primal coefficient matrix need not be positive definite. Numerical tests are given to demonstrate the efficiency of the algorithm. Solution properties of the ELQP problem underB-regularity are also discussed.Supported by the Australian Research Council.     

A copositive Farkas lemma and minimally exact conic relaxations for robust quadratic optimization with binary and quadratic constraints

We present a new copositive Farkas lemma for a general conic quadratic system with binary constraints under a convexifiability requirement. By employing this Farkas lemma, we establish that a minimally exact conic programming relaxation holds for a convexifiable robust quadratic optimization problem with binary and quadratic constraints under a commonly used ellipsoidal uncertainty set of robust optimization. We then derive a minimally exact copositive relaxation for a robust binary quadratic program with conic linear constraints where the convexifiability easily holds.     

A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO

Kernel functions play an important role in the design and analysis of primal-dual interior-point algorithms. They are not only used for determining the search directions but also for measuring the distance between the given iterate and the μ-center for the algorithms. In this paper we present a unified kernel function approach to primal-dual interior-point algorithms for convex quadratic semidefinite optimization based on the Nesterov and Todd symmetrization scheme. The iteration bounds for large- and small-update methods obtained are analogous to the linear optimization case. Moreover, this unifies the analysis for linear, convex quadratic and semidefinite optimizations.     

Convergence of the Lasserre hierarchy of SDP relaxations for convex polynomial programs without compactness

We show that the Lasserre hierarchy of semidefinite programming (SDP) relaxations with a slightly extended quadratic module for convex polynomial optimization problems always converges asymptotically even in the case of non-compact semi-algebraic feasible sets. We then prove that the positive definiteness of the Hessian of the associated Lagrangian at a saddle-point guarantees the finite convergence of the hierarchy. We do this by establishing a new sum-of-squares polynomial representation of convex polynomials over convex semi-algebraic sets.     

Full Nesterov-Todd step infeasible interior-point method for symmetric optimization

Euclidean Jordan algebras were proved more than a decade ago to be an indispensable tool in the unified study of interior-point methods. By using it, we generalize the full-Newton step infeasible interior-point method for linear optimization of Roos [Roos, C., 2006. A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM Journal on Optimization. 16 (4), 1110-1136 (electronic)] to symmetric optimization. This unifies the analysis for linear, second-order cone and semidefinite optimizations.