A parametric successive underestimation method for convex multiplicative programming problems

This paper addresses itself to the algorithm for minimizing the product of two nonnegative convex functions over a convex set. It is shown that the global minimum of this nonconvex problem can be obtained by solving a sequence of convex programming problems. The basic idea of this algorithm is to embed the original problem into a problem in a higher dimensional space and to apply a branch-and-bound algorithm using an underestimating function. Computational results indicate that our algorithm is efficient when the objective function is the product of a linear and a quadratic functions and the constraints are linear. An extension of our algorithm for minimizing the sum of a convex function and a product of two convex functions is also discussed.     

Global minimization of a generalized convex multiplicative function

This paper discusses an algorithm for generalized convex multiplicative programming problems, a special class of nonconvex minimization problems in which the objective function is expressed as a sum ofp products of two convex functions. It is shown that this problem can be reduced to a concave minimization problem with only 2p variables. An outer approximation algorithm is proposed for solving the resulting problem.     

Parametric simplex algorithms for solving a special class of nonconvex minimization problems

It is shown that parametric linear programming algorithms work efficiently for a class of nonconvex quadratic programming problems called generalized linear multiplicative programming problems, whose objective function is the sum of a linear function and a product of two linear functions. Also, it is shown that the global minimum of the sum of the two linear fractional functions over a polytope can be obtained by a similar algorithm. Our numerical experiments reveal that these problems can be solved in much the same computational time as that of solving associated linear programs. Furthermore, we will show that the same approach can be extended to a more general class of nonconvex quadratic programming problems.     

交替最小化算法求解强凸函数与弱凸函数和的极小值问题

交替最小化算法(简称AMA)最早由[SIAM J.Control Optim.,1991,29(1):119-138]提出,并能用于求解强凸函数与凸函数和的极小值问题.本文直接利用AMA算法来求解强凸函数与弱凸函数和的极小值问题.在强凸函数的模大于弱凸函数的模的假设下,我们证明了AMA生成的点列全局收敛到优化问题的解,并且若该优化问题中的某个函数是光滑函数时,AMA所生成的点列的收敛率是线性的.     

Solving Sum of Ratios Fractional Programs via Concave Minimization

This article presents an algorithm for globally solving a sum of ratios fractional programming problem. To solve this problem, the algorithm globally solves an equivalent concave minimization problem via a branch-and-bound search. The main work of the algorithm involves solving a sequence of convex programming problems that differ only in their objective function coefficients. Therefore, to solve efficiently these convex programming problems, an optimal solution to one problem can potentially be used to good advantage as a starting solution to the next problem.     

Constructive Solution of Inverse Parametric Linear/Quadratic Programming Problems

Parametric convex programming has received a lot of attention, since it has many applications in chemical engineering, control engineering, signal processing, etc. Further, inverse optimality plays an important role in many contexts, e.g., image processing, motion planning. This paper introduces a constructive solution of the inverse optimality problem for the class of continuous piecewise affine functions. The main idea is based on the convex lifting concept. Accordingly, an algorithm to construct convex liftings of a given convexly liftable partition will be put forward. Following this idea, an important result will be presented in this article: Any continuous piecewise affine function defined over a polytopic partition is the solution of a parametric linear/quadratic programming problem. Regarding linear optimal control, it will be shown that any continuous piecewise affine control law can be obtained via a linear optimal control problem with the control horizon at most equal to 2 prediction steps.     

Generalized proximal point algorithm for convex optimization

Ha (Ref. 1) recently introduced a generalized proximal point algorithm for solving a generalized equation. In this note, we present a generalized proximal point algorithm for convex optimization problems based on Ha's work. The idea behind this algorithm is that, instead of adding a quadratic term to all the variables, we add a quadratic term to a subset of the variables. We extend the criteria for approximate solutions given by Rockafellar (Ref. 2) and Auslender (Ref. 3) and present convergence results. Finally, we show how this algorithm can be applied to solve block-angular linear and quadratic programming problems.     

On the Minimum Norm Solution of Linear Programs

This paper describes a new technique to find the minimum norm solution of a linear program. The main idea is to reformulate this problem as an unconstrained minimization problem with a convex and smooth objective function. The minimization of this objective function can be carried out by a Newton-type method which is shown to be globally convergent. Furthermore, under certain assumptions, this Newton-type method converges in a finite number of iterations to the minimum norm solution of the underlying linear program.     

线性比式和规划问题的输出空间分支定界算法

本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的.     

Global optimization method for maximizing the sum of difference of convex functions ratios over nonconvex region

A global optimization algorithm is presented for maximizing the sum of difference of convex functions ratios problem over nonconvex feasible region. This algorithm is based on branch and bound framework. To obtain a difference of convex programming, the considered problem is first reformulated by introducing new variables as few as possible. By using subgradient and convex envelope, the fundamental problem of estimating lower bound in the branch and bound algorithm is transformed into a relaxed linear programming problem which can be solved efficiently. Furthermore, the size of the relaxed linear programming problem does not change during the algorithm search. Lastly, the convergence of the algorithm is analyzed and the numerical results are reported.     

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.     

Minimum-support solutions of polyhedral concave programs *

Motivated by the successful application of mathematical programming techniques to difficult machine learning problems, we seek solutions of concave minimization problems over polyhedral sets with minimum number of nonzero components. We that if

such problems have a solution, they have a vertex solution with a minimal number of zeros. This includes linear programs and general linear complementarity problems. A smooth concave exponential approximation to a step function solves the minimumsupport problem exactly for a finite value of the smoothing parameter. A fast finite linear-programming-based iterative method terminates at a stationary point, which for many important real world problems provides very useful answers. Utilizing the

complementarity property of linear programs and linear complementarity problems, an upper bound on the number of nonzeros can be obtained by solving a single convex minimization problem on a polyhedral set     

An outer approximation method for minimizing the product of several convex functions on a convex set

This paper addresses the minimization of the product ofp convex functions on a convex set. It is shown that this nonconvex problem can be converted to a concave minimization problem withp variables, whose objective function value is determined by solving a convex minimization problem. An outer approximation method is proposed for obtaining a global minimum of the resulting problem. Computational experiments indicate that this algorithm is reasonable efficient whenp is less than 4.This research was partly supported by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. (C)03832018 and (C)04832010.     

基于局部self-concordant障碍函数的全牛顿步多项式时间算法

由Nesterov和Nemirovski[4]创立的self-concordant障碍函数理论为解线性和凸优化问题提供了多项式时间内点算法.根据self-concordant障碍函数的参数,就可以分析内点算法的复杂性.在这篇文章中,我们介绍了基于核函数的局部self-concordant障碍函数,它在线性优化问题的中心路径及其邻域内满足self-concordant性质.通过求解此障碍函数的局部参数值,我们得到了求解线性规划问题的基于此局部Self-concordant障碍函数的纯牛顿步内点算法的理论迭代界.此迭代界与目前已知的最好的理论迭代界是一致的.     

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.     

凸规划的新算法

对一般凸目标函数和一般凸集约束的凸规划问题新解法进行探讨,它是线性规划一种新算法的扩展和改进,此算法的基本思想是在规划问题的可行域中由所建－的一个切割面到另一个切割面的不断推进来求取最优的。文章对目标函数是二次的且约束是一般凸集和二次目标函数且约束是线性的情形,给出了更简单的算法。     

Iterative linear programming solution of convex programs

An iterative linear programming algorithm for the solution of the convex programming problem is proposed. The algorithm partially solves a sequence of linear programming subproblems whose solution is shown to converge quadratically, superlinearly, or linearly to the solution of the convex program, depending on the accuracy to which the subproblems are solved. The given algorithm is related to inexact Newton methods for the nonlinear complementarity problem. Preliminary results for an implementation of the algorithm are given.This material is based on research supported by the National Science Foundation, Grants DCR-8521228 and CCR-8723091, and by the Air Force Office of Scientific Research, Grant AFOSR-86-0172. The author would like to thank Professor O. L. Mangasarian for stimulating discussions during the preparation of this paper.     

求解非凸区域上凸函数比式和问题的全局优化方法

针对非凸区域上的凸函数比式和问题,给出一种求其全局最优解的确定性方法.该方法基于分支定界框架.首先通过引入变量,将原问题等价转化为d.c.规划问题,然后利用次梯度和凸包络构造松弛线性规划问题,从而将关键的估计下界问题转化为一系列线性规划问题,这些线性规划易于求解而且规模不变,更容易编程实现和应用到实际中;分支采用单纯形对分不但保证其穷举性,而且使得线性规划规模更小.理论分析和数值实验表明所提出的算法可行有效.     

A Branch and Bound Algorithm for Solving Low Rank Linear Multiplicative and Fractional Programming Problems

This paper is concerned with a practical algorithm for solving low rank linear multiplicative programming problems and low rank linear fractional programming problems. The former is the minimization of the sum of the product of two linear functions while the latter is the minimization of the sum of linear fractional functions over a polytope. Both of these problems are nonconvex minimization problems with a lot of practical applications. We will show that these problems can be solved in an efficient manner by adapting a branch and bound algorithm proposed by Androulakis–Maranas–Floudas for nonconvex problems containing products of two variables. Computational experiments show that this algorithm performs much better than other reported algorithms for these class of problems.     

On the convergence rate of a forward-backward type primal-dual splitting algorithm for convex optimization problems

In this paper, we analyse the convergence rate of the sequence of objective function values of a primal-dual proximal-point algorithm recently introduced in the literature for solving a primal convex optimization problem having as objective the sum of linearly composed infimal convolutions, nonsmooth and smooth convex functions and its Fenchel-type dual one. The theoretical part is illustrated by numerical experiments in image processing.