Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [decision-problems]

A decision problem is a question (in some formal system) whose answer is either "yes" or "no".

0
votes
1answer
43 views

Nonempty interior is equivalent to the feasibility of set of strict quadratic inequalities. Why?

From Convex Optimization: Let $E_i = \{x \mid f_i(x) \le 0\}$ where $f_i(x) = x^TA_ix + 2b_i^Tx + c_i$ for $ i = 1, 2, \dots, m$ and $A_i \in S^n_{++}$ where $S^n_{++}$ is the set of all ...
3
votes
0answers
41 views

How to quickly determine if a linear program is feasible?

I have a series of linear programs in canonical form $$\begin{array}{ll} \text{maximize} & c^T \mathrm x\\ \text{subject to} & A x \leq b\\ & x \geq 0\end{array}$$ and I need to ...
2
votes
0answers
483 views

Determine if a polyhedron is a polytope

Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron. Let $M$ be an $m \times n$ matrix of integers. Let $P$ be the (possibly ...
1
vote
0answers
28 views

What is the meaning of Motzkin's theorem?

Theorem: Let $A$ and $C$ be two matrices. The system of linear inequalities $Ax<0$ and $Cx \leq 0$ has a solution iff the following equation in $\lambda$ and $\mu$ does not have a solution$$A^T \...
1
vote
0answers
36 views

How to determine whether a given point lies inside or outside of a triangle in 3D?

For example if i have triangle defined by following points [A=(15.0, 14, 15.0), B=(15.0, -45, 15.0), C=(-15.0, 14, 15.0)], and consider the point need to be project p=(15,78,0). I want to determine, ...
0
votes
0answers
19 views

How to calculate pi sub D, upper opt

I¡m learning Bayesian Networks and now I'm studying Decision Making. I have the following probability table (sorry about the format, I don't know how to do it better): ________| $\psi(y,t,d)$ $+y,+t,...
0
votes
0answers
41 views

A person often finds that she is up to 1 hour late for work. A decision problem

A person often finds that she is up to 1 hour late for work. If she is from $1$ to $30$ minutes late, $\$4 $ is deducted from her paycheck; if she is from $31$ to $60$ minutes late for work, $\$8$ is ...
0
votes
0answers
46 views

Computational complexity of a feasibility LP with $m$ inequalities, in $d$ dimension?

How would you quantify the computational complexity of feasibility LPs? Say, for example, an LP with $m$ inequalities: $$ \begin{cases} \mathbf{a_i} \cdot \mathbf{x} \leq b_i, \quad i \in [m] \\ \...