Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) No edit summary |
||
Line 59:
\end{align}</math>
where K is a closed [[Convex cone|pointed convex cone]], L is a [[linear subspace]] of R''<sup>n</sup>'', and b is a vector in R''<sup>n</sup>''. A linear program in standard form in the special case in which K is the nonnegative orthant of R''<sup>n</sup>''.
=== Eliminating linear equality constraints ===
It is possible to convert a convex program in standard form, to a convex program with no equality constraints.<ref name=":2" />{{Rp|page=132}} Denote the equality constraints ''h<sub>i</sub>''(''x'')=0 as ''Ax''=''b'', where ''A'' has ''n'' columns. If ''Ax''=''b'' is infeasible, then of course the original problem is infeasible. Otherwise, it has some solution ''x''<sub>0</sub> , and the set of all solutions can be presented as: ''Fz''+''x''<sub>0</sub>, where ''z'' is in ''R<sup>k</sup>'', ''k''=''n''-rank(''A''), and ''F'' is an ''n''-by-''k'' matrix. Substituting ''x'' = ''Fz''+''x''<sub>0</sub> in the original problem gives: <blockquote><math>\begin{align}
&\underset{\mathbf{x}}{\operatorname{minimize}}& & f(\mathbf{F \mathbf{z} + \mathbf{x}_0}) \\
&\operatorname{subject\ to}
& &g_i(\mathbf{F \mathbf{z} + \mathbf{x}_0}) \leq 0, \quad i = 1, \dots, m \\
\end{align}</math></blockquote>where the variables are '''z'''. Note that there are rank(''A'') fewer variables.
==Special cases==
| |||