Аннотация
The decomposition of a mathematical programming problem $$ (1)\quad \max\sb{x\ge 0}\{f(x)\vert \quad g\sb k(x)\le 0,\quad k=1,...,m,\quad x\in R\sp n\} $$ based on the introduction of aggregated variables where f is concave and $g\sb k$ are convex functions, is presented. Let vector x be decomposed into I disjoint parts $J\sb i$, $i\in I$. Then the aggregated variables $X\sp i=\sum\sb{j}x\sp i\sb j$ and the set of weight elements $$ A=\{\alpha\sp i\sb j\vert \quad \sum\sb{j}\alpha\sp i\sb j=1,\quad \alpha\sp i\sb j\ge 0,\quad i=1,...,I,\quad j=1,...,J\sb i\} $$ are introduced and the aggregated problem is formulated: $$ (2)\quad \max\sb{X\ge 0}\{F(x)\vert \quad G\sb k(X)\le 0,\quad k=1,...,m\} $$ with $F(X)=f(\alpha\sp 1\sb 1X\sp 1,...,\alpha\sp I\sb{J\sb I}X\sp I)$, and analogously $G\sb k.$ \par Let $\Theta$ ($\alpha$) be the optimal value of (2). Then conditions are presented which allow to obtain from the optimal solution $\overset \circ \to X$ of the aggregated problem (2) an optimal solution $\overset \circ \to x = \overset \circ \to \alpha \overset \circ \to X$ of the initial problem, $\overset \circ \to \alpha$ being the local maximum of the problem (3): $$ (3)\quad \max\sb{\alpha \in A}\{\Theta (\alpha)\vert \quad p\sb r(\alpha X)\le 0,\quad r=1,...,R,\quad X\ge 0\} $$ for some convex $p\sb r(x)$ such that if $g\sb k(x)\le 0$ then $p\sb r(x)\le 0$. Under Slater regularity conditions together with uniqueness of the solution of (2) the first order necessary optimality conditions for $\overset \circ \to x = \overset \circ \to \alpha \overset \circ \to X$ are presented. For the solution of (3) the conditional gradient method is proposed where the subproblem of choosing the descent direction is solved by the first order necessary conditions. At last, a special
case with a part of variables having block-angular structure is considered.
Ключевые слова
Convex programming; Decomposition methods; Mathematical programming (numerical methods); Computational methods (optimization); aggregated variables; first order necessary optimality conditions; conditional gradient method; block-angular structure
|
