Minimum norm solution to the positive semidefinite linear complementarity problem

In this article, we present an algorithm to compute the minimum norm solution of the positive semidefinite linear complementarity problem. We show that its solution can be obtained using the alternative theorems and a convenient characterization of the solution set of a convex quadratic programming problem. This problem reduces to an unconstrained minimization problem with once differentiable convex objective function. We propose an extension of Newton's method for solving the unconstrained optimization problem. Computational results show that convergence to high accuracy often occurs in just a few iterations.     

Least-norm linear programming solution as an unconstrained minimization problem

It is shown that the dual of the problem of minimizing the 2-norm of the primal and dual optimal variables and slacks of a linear program can be transformed into an unconstrained minimization of a convex parameter-free globally differentiable piecewise quadratic function with a Lipschitz continuous gradient. If the slacks are not included in the norm minimization, one obtains a minimization problem with a convex parameter-free quadratic objective function subject to nonnegativity constraints only.     

Minimum Norm Solution to the Absolute Value Equation in the Convex Case

In this paper, we give an algorithm to compute the minimum norm solution to the absolute value equation (AVE) in a special case. We show that this solution can be obtained from theorems of the alternative and a useful characterization of solution sets of convex quadratic programs. By using an exterior penalty method, this problem can be reduced to an unconstrained minimization problem with once differentiable convex objective function. Also, we propose a quasi-Newton method for solving unconstrained optimization problem. Computational results show that convergence to high accuracy often occurs in just a few iterations.     

On optimal zero-preserving corrections for inconsistent linear systems

This paper addresses the problem of finding an optimal correction of an inconsistent linear system, where only the nonzero coefficients of the constraint matrix are allowed to be perturbed for reconstructing a consistent system. Using the Frobenius norm as a measure of the distance to feasibility, a nonconvex minimization problem is formulated, whose objective function is a sum of fractional functions. A branch-and-bound algorithm for solving this nonconvex program is proposed, based on suitably overestimating the denominator function for computing lower bounds. Computational experience is presented to demonstrate the efficacy of this approach.     

Technical Note: Some Structural Properties of a Newton-Type Method for Semidefinite Programs

Using the minimum function or the Fischer-Burmeister function, we obtain two reformulations of a semidefinite program as a nonlinear system of equations. Applying a Newton-type method to such a reformulation leads to a linear system of equations which has to be solved at each iteration. We discuss some properties of this linear system and show that the corresponding coefficient matrix is symmetric positive definite for the minimum function approach and positive definite but unsymmetric for the Fischer-Burmeister formulation.     

On an inverse linear programming problem

A method for solving the following inverse linear programming (LP) problem is proposed. For a given LP problem and one of its feasible vectors, it is required to adjust the objective function vector as little as possible so that the given vector becomes optimal. The closeness of vectors is estimated by means of the Euclidean vector norm. The inverse LP problem is reduced to a problem of unconstrained minimization for a convex piecewise quadratic function. This minimization problem is solved by means of the generalized Newton method.     

Controlled perturbations for quadratically constrained quadratic programs

Consider a minimization problem of a convex quadratic function of several variables over a set of inequality constraints of the same type of function. The duel program is a maximization problem with a concave objective function and a set of constrains that are essentially linear. However, the objective function is not differentiable over the constraint region. In this paper, we study a general theory of dual perturbations and derive a fundamental relationship between a perturbed dual program and the original problem. Based on this relationship, we establish a perturbation theory to display that a well-controlled perturbation on the dual program can overcome the nondifferentiability issue and generate an ε-optimal dual solution for an arbitrarily small number ε. A simple linear program is then constructed to make an easy conversion from the dual solution to a corresponding ε-optimal primal solution. Moreover, a numerical example is included to illustrate the potential of this controlled perturbation scheme.     

An approximation theory of matrix rank minimization and its application to quadratic equations

Matrix rank minimization problems are gaining plenty of recent attention in both mathematical and engineering fields. This class of problems, arising in various and across-discipline applications, is known to be NP-hard in general. In this paper, we aim at providing an approximation theory for the rank minimization problem, and prove that a rank minimization problem can be approximated to any level of accuracy via continuous optimization (especially, linear and nonlinear semidefinite programming) problems. One of the main results in this paper shows that if the feasible set of the problem has a minimum rank element with the least Frobenius norm, then any accumulation point of solutions to the approximation problem, as the approximation parameter tends to zero, is a minimum rank solution of the original problem. The tractability under certain conditions and convex relaxation of the approximation problem are also discussed. An immediate application of this theory to the system of quadratic equations is presented in this paper. It turns out that the condition for such a system without a nonzero solution can be characterized by a rank minimization problem, and thus the proposed approximation theory can be used to establish some sufficient conditions for the system to possess only zero solution.     

Regularization of Steffensen's method with inexactly specified initial data

A minimization problem is considered for the case when the minimand function and the functions defining the set of equality and inequality constraints are known with an error. A regularized Steffensen's method for the solution of this problem is proposed. It is shown that, when the variation of the regularization and penalty parameters is compatible with the errors, the sequence generated by this method converges in norm to the minimum point with minimum norm.Translated from Metody Matematicheskogo Modelirovaniya, Avtomatizatsiya Obrabotki Nablyudenii i Ikh Primeneniya, pp. 15–23, 1986.     

Quadratic programming problems and related linear complementarity problems

This paper investigates the general quadratic programming problem, i.e., the problem of finding the minimum of a quadratic function subject to linear constraints. In the case where, over the set of feasible points, the objective function is bounded from below, this problem can be solved by the minimization of a linear function, subject to the solution set of a linear complementarity problem, representing the Kuhn-Tucker conditions of the quadratic problem.To detect in the quadratic problem the unboundedness from below of the objective function, necessary and sufficient conditions are derived. It is shown that, when these conditions are applied, the general quadratic programming problem becomes equivalent to the investigation of an appropriately formulated linear complementarity problem.This research was supported by the Hungarian Research Foundation, Grant No. OTKA/1044.     

On a class of quadratic programs

This paper considers a class of quadratic programs where the constraints ae linear and the objective is a product of two linear functions. Assuming the two linear factors to be non-negative, maximization and minimization cases are considered. Each case is analyzed with the help of a bicriteria linear program obtained by replacing the quadratic objective with the two linear functions. Global minimum (maximum) is attained at an efficient extreme point (efficient point) of the feasible set in the solution space and corresponds to an efficient extreme point (efficient point) of the feasible set in the bicriteria space. Utilizing this fact and certain other properties, two finite algorithms, including validations are given for solving the respective problems. Each of these, essentially, consists of solving a sequence of linear programs. Finally, a method is provided for relaxing the non-negativity assumption on the two linear factors of the objective function.     

一类不可微二次规划逆问题

本文求解了一类二次规划的逆问题,具体为目标函数是矩阵谱范数与向量无穷范数之和的最小化问题.首先将该问题转化为目标函数可分离变量的凸优化问题,提出用G-ADMM法求解.并结合奇异值阈值算法,Moreau-Yosida正则化算法,matlab优化工具箱的quadprog函数来精确求解相应的子问题.而对于其中一个子问题的精确...     

Inverse Problems of Submodular Functions on Digraphs

In this paper, we study the inverse problem of submodular functions on digraphs. Given a feasible solution x* for a linear program generated by a submodular function defined on digraphs, we try to modify the coefficient vector c of the objective function, optimally and within bounds, such that x* becomes an optimal solution of the linear program. It is shown that the problem can be formulated as a combinatorial linear program and can be transformed further into a minimum cost circulation problem. Hence, it can be solved in strongly polynomial time. We also give a necessary and sufficient condition for the feasibility of the problem. Finally, we extend the discussion to the version of the inverse problem with multiple feasible solutions.     

New reformulation and feasible semismooth Newton method for a class of stochastic linear complementarity problems

A class of stochastic linear complementarity problems (SLCPs) with finitely many realizations is considered. We first formulate the problem as a new constrained minimization problem. Then, we propose a feasible semismooth Newton method which yields a stationary point of the constrained minimization problem. We study the condition for the level set of the objective function to be bounded. As a result, the condition for the solution set of the constrained minimization problem is obtained. The global and quadratic convergence of the proposed method is proved under certain assumptions. Preliminary numerical results show that this method yields a reasonable solution with high safety and within a small number of iterations.     

An implementable proximal point algorithmic framework for nuclear norm minimization

The nuclear norm minimization problem is to find a matrix with the minimum nuclear norm subject to linear and second order cone constraints. Such a problem often arises from the convex relaxation of a rank minimization problem with noisy data, and arises in many fields of engineering and science. In this paper, we study inexact proximal point algorithms in the primal, dual and primal-dual forms for solving the nuclear norm minimization with linear equality and second order cone constraints. We design efficient implementations of these algorithms and present comprehensive convergence results. In particular, we investigate the performance of our proposed algorithms in which the inner sub-problems are approximately solved by the gradient projection method or the accelerated proximal gradient method. Our numerical results for solving randomly generated matrix completion problems and real matrix completion problems show that our algorithms perform favorably in comparison to several recently proposed state-of-the-art algorithms. Interestingly, our proposed algorithms are connected with other algorithms that have been studied in the literature.     

Superlinear Convergence of a Newton-Type Algorithm for Monotone Equations

We consider the problem of finding solutions of systems of monotone equations. The Newton-type algorithm proposed in Ref. 1 has a very nice global convergence property in that the whole sequence of iterates generated by this algorithm converges to a solution, if it exists. Superlinear convergence of this algorithm is obtained under a standard nonsingularity assumption. The nonsingularity condition implies that the problem has a unique solution; thus, for a problem with more than one solution, such a nonsingularity condition cannot hold. In this paper, we show that the superlinear convergence of this algorithm still holds under a local error-bound assumption that is weaker than the standard nonsingularity condition. The local error-bound condition may hold even for problems with nonunique solutions. As an application, we obtain a Newton algorithm with very nice global and superlinear convergence for the minimum norm solution of linear programs.This research was supported by the Singapore-MIT Alliance and the Australian Research Council.     

A cut-peak function method for global optimization

A new method is proposed for solving box constrained global optimization problems. The basic idea of the method is described as follows: Constructing a so-called cut-peak function and a choice function for each present minimizer, the original problem of finding a global solution is converted into an auxiliary minimization problem of finding local minimizers of the choice function, whose objective function values are smaller than the previous ones. For a local minimum solution of auxiliary problems this procedure is repeated until no new minimizer with a smaller objective function value could be found for the last minimizer. Construction of auxiliary problems and choice of parameters are relatively simple, so the algorithm is relatively easy to implement, and the results of the numerical tests are satisfactory compared to other methods.     

基于Lanczos双A-正交的一种修正的QMR算法

本文研究了基于Lanczos双正交过程的拟极小残量法(QMR).将QMR算法中的Lanczos双正交过程用Lanczos双A-正交过程代替,利用该算法得到的近似解与最后一个基向量的线性组合来作为新的近似解,使新近似解的残差范数满足一个一维极小化问题,从而得到一种基于Lanczos双A-正交的修正的QMR算法.数值试验表明,对于某些大型线性稀疏方程组,新算法比QMR算法收敛快得多.     

Heuristic Methods for Linear Multiplicative Programming

The linear multiplicative programming is the minimization of the product of affine functions over a polyhedral set. The problem with two affine functions reduces to a parametric linear program and can be solved efficiently. For the objective function with more than two affine functions multiplied, no efficient algorithms that solve the problem to optimality have been proposed, however Benson and Boger have proposed a heuristic algorithm that exploits links of the problem with concave minimization and multicriteria optimization. We will propose a heuristic method for the problem as well as its modification to enhance the accuracy of approximation. Computational experiments demonstrate that the method and its modification solve randomly generated problems within a few percent of relative error.     

非光滑约束问题的既约次梯度法

１引言 对带约束的不可微的非线性规划问题,由于不能使用梯度,求极小点就比较困难．本文给出解决此问题的一种有效的算法． ２　非光滑约束问题的既约次梯度法 １）非线性规划问题的Ｌａｅｒａｎｅ对偶理论 考虑下面非线性规划问题其中ｇ（ｘ）＝（ｇ１（ｘ）,…,ｇｒ（ｘ））Ｔ,ｈ（ｘ））＝（ｈ１（ｘ）,…,ｈｍ（ｘ））Ｔ,ｆ（ｘ）＝　　　　　　Ｒｎ中是Ｌｉｓｐｓｃｈｉｔｚ连续的ｉ＝１,２,…,ｒ,ｊ＝１,２,…,ｍ相应的Ｌａｇｒａｎｇｅ对偶问题为其中　　（ｕ,　）＝ｉｎｆＬ（ｘ;ｕ,ｖ）＝ｉｎｆ（ｆ（ｘ）＋ｕＴ…