Minimizing Piecewise-Concave Functions Over Polyhedra
提出一种迭代方法，求解目标函数为有限个凹函数逐点最大值的线性约束优化问题，利用分段凹性构建线性化模型并引入曲线搜索策略，结合变邻域搜索和坐标方向搜索启发式算法，在测试问题上验证了有效性。
We introduce an iterative method for solving linearly constrained optimization problems, whose nonsmooth nonconvex objective function is defined as the pointwise maximum of finitely many concave functions. Such problems often arise from reformulations of certain constraint structures (e.g., binary constraints, finite max-min constraints) in diverse areas of optimization. We state a local optimization strategy, which exploits piecewise-concavity of the objective function, giving rise to a linearized model corrected by a proximity term. In addition we introduce an approximate line-search strategy, based on a curvilinear model, which, similarly to bundle methods, can return either a satisfactory descent or a null-step declaration. Termination at a point satisfying an approximate stationarity condition is proved. We embed the local minimization algorithm into a Variable Neighborhood Search scheme and a Coordinate Direction Search heuristic, whose aim is to improve the current estimate of the global minimizer by exploring different parts of the feasible region. We finally provide computational results obtained on two sets of small- to large-size test problems.