Lange Kenneth, Zhou Hua
Departments of Biomathematics, Human Genetics, and Statistics, University of California, Los Angeles, CA 90095-1766, USA.
Department of Statistics, North Carolina State University, 2311 Stinson Drive, Campus Box 8203, Raleigh, NC 27695-8203, USA.
Math Program. 2014 Feb 1;143(1-2):339-356. doi: 10.1007/s10107-012-0612-1.
This paper derives new algorithms for signomial programming, a generalization of geometric programming. The algorithms are based on a generic principle for optimization called the MM algorithm. In this setting, one can apply the geometric-arithmetic mean inequality and a supporting hyperplane inequality to create a surrogate function with parameters separated. Thus, unconstrained signomial programming reduces to a sequence of one-dimensional minimization problems. Simple examples demonstrate that the MM algorithm derived can converge to a boundary point or to one point of a continuum of minimum points. Conditions under which the minimum point is unique or occurs in the interior of parameter space are proved for geometric programming. Convergence to an interior point occurs at a linear rate. Finally, the MM framework easily accommodates equality and inequality constraints of signomial type. For the most important special case, constrained quadratic programming, the MM algorithm involves very simple updates.
本文推导了符号式规划的新算法，符号式规划是几何规划的一种推广。这些算法基于一种名为MM算法的通用优化原理。在此框架下，可以应用几何-算术平均不等式和支撑超平面不等式来创建一个参数分离的替代函数。因此，无约束符号式规划可简化为一系列一维最小化问题。简单示例表明，所推导的MM算法可以收敛到边界点或连续最小点集合中的某一点。针对几何规划，证明了最小点唯一或出现在参数空间内部的条件。收敛到内部点的速度是线性的。最后，MM框架能够轻松处理符号式类型的等式和不等式约束。对于最重要的特殊情况，即约束二次规划，MM算法涉及非常简单的更新。
