Convex Optimization · Problem 2.20

Convex functions — Boyd & Vandenberghe

Mathematics — Optimization · strictly-positive-solution-of-linear-equations

Problem

Strictly positive solution of linear equations. Suppose

A \in \mathbf{R}^{m \times n}

b \in \mathbf{R}^m

, with

b \in \mathcal{R}(A)

. Show that there exists an

x

satisfying

x \succ 0, \qquad Ax = b

if and only if there exists no

\lambda

with

A^T \lambda \succeq 0, \qquad A^T \lambda \neq 0, \qquad b^T \lambda \leq 0.

Hint. First prove the following fact from linear algebra:

c^T x = d

for all

x

satisfying

Ax = b

if and only if there is a vector

\lambda

such that

c = A^T \lambda

d = b^T \lambda