In linear programming we find a feasible region , is this region always convex? . if a concave region is found where objective is minimization , I think then a solution exists . Advance thanks.  someone deleted the answer of my previous post , although i wasn't sure about the answer of 1st question , and no one is replying in that post , as i am in hurry so i re-posted it to get a  answer. Thanks
122975
So I know that in general the simplex method for linear and convex quadratic programming can require exponential time. But assuming a positive semidefinite quadratic program that is solvable by the simplex method, then the problem is definitely in P, right?  The reason I ask: I am working on getting a handle on complexity theory. And I think I found a reduction from a problem to a positive semidefinite quadratic problem BUT the solution is only valid if the returned optimum is at a vertex of the feasible region. So that leaves out solving it with an interior point method since the minimum can be trivially obtained at the center of the feasible region and maybe at other points too. Since the simplex method operates on vertices, then I know that once the optimum is found, then it is at a point I actually care about.  Assuming the reduction is proper and always results in a correct answer: is reduction to the simplex method a sufficient condition for proving membership in P? OR does someone have a good reference to efficient exterior point methods for this class of problem? Is there another method for quadratic programs that I am overlooking? OR am I basically stuck with proving that the number of iterations is polynomial for this specific program? Is this question better suited to a different stack exchange site?
49714
I know what an ellipsoid is, but I do not know how to approach how to prove that one is convex. Any advice would be greatly appreciated.
101659
Prove, using Jensen's formula if $f(x) = x^\alpha, (\alpha &gt; 1)$ is convex.$$\left(\sum_{i=1}^n x_i \right)^\alpha \leq n^{\alpha-1} \left(\sum_{i=1}^n x_i^\alpha \right)$$  Any tips on how to get this done? I can't really see much of a connection between Jensen's inequality and this one. It may be silly, but I'm really stuck here.
94638
Given an arbitrary set $A\subset\mathbb R^n$, why do all extreme points of the convex hull $\operatorname{conv}(A)$ lie in $A$?  (An extreme point of a convex set is defined as one that cannot be written as a strictly convex combination of two distinct points of this set.)
123793
For $x_1, x_2 &gt; 0$, let $$f(x_1,x_2) := \frac{1}{x_1^3x_2}$$ Is function $f$ convex?  I think it is because Hessian matrix is $$\begin{pmatrix} \frac{12}{x_1^5x_2} &amp; \frac{3}{x_1^4x_2^2} \\ \frac{3}{x_1^4x_2^2} &amp; \frac{2}{x_1^3x_2^3}\end{pmatrix}$$ And I think the matrix is positive because each value is positive (is it true?) Thanks!
61671
How to prove that the intersection of any finite number of convex sets is a convex set?  I have no idea.
87424
I am minimizing a convex function $f(x,y)$ using the steepest descent method: $$\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma \nabla F(\mathbf{x}_n),\ n \ge 0$$  My function is defined over a specific domain $D = \{(x, y) \in R^2 : 2x^2+y^2 &lt; 10\}$, if my $x_{n+1}$ goes out of bound, my method diverge. I was told to choose $\gamma$ using armijo rule to stay inbound.   Can someone explain to me the method and also describe a pseudo code for implementing it?
105495
I have read about this problem:    But I want to see how it is proven that the "optimal" solution is indeed optimal. I understand how to prove that if the optimal solution is of the form "wait for $t$ candidates and then choose the next best one" then $t=n/e$ is optimal; but why is the best strategy of that form in the first place?  A complete proof is not required - a reference to a good text discussing this is good as well.
81337
I have a convex polytope described by the intersection of a hypercube and two parallel lower and upper hyperplanes cutting through the hypercube. I want to find the projection of a point onto the polytope. I read the question  and see that the general problem of finding a projection onto a convex polytope can be solved with quadratic programming. However, taken alone, projection onto a hypercube or a hyperplane is trivial. For the hypercube, each dimension is defined by a lower+upper bounds and we just pull each dimension within those bounds, which take $O(n)$ time in $n$ dimensions. For the hyperplane just find the projection onto it. So I'm wondering whether there is simpler method for finding such a projection, maybe somehow combining the two independent projections.
81159
This question is related to the  one.      Let $\Omega$ be an open connected subset of ${\bf R}^n$ and $f:\Omega\to{\bf R}^n$ be continuously differentiable such that   $$ \sup_{x\in\Omega}||Df(x)||&lt;+\infty.  $$   Show that for every compact $K\subset \Omega$, there exists $L_K$ such that for every $x,y\in K$,   $$ |f(x)-f(y)|\leq L_K|x-y|.  $$     Here are some thoughts about it. If $\Omega$ is convex, then one can apply the theorem quoted in the previous question. Suppose it is not. By the compactness of $K$, one can cover it with finitely many open balls contained in $\Omega$. Since open balls are convex, one can have a Lipschitz constant $L_i$ for each ball. For any $x,y\in K$, if they are in the same open ball, then one can bound $|f(x)-f(y)|$ using the maximum of $\{L_i\}$. But when they are not in the same ball, I don't see how to go on.
85916
I am reading Boyd &amp; Vandenberghe's Convex Optimization. The authors use curved greater than or equal to (\succcurlyeq)  $$f(x^*) \succcurlyeq \alpha$$  and curved less than or equal to (\preccurlyeq)  $$f(x^*) \preccurlyeq \alpha$$  Can someone explain what they mean?
20383
Let $A \subset \mathbb{R}^n$ be closed and $d_A(x) = \inf_{a \in A} \|x-a\|$. I need to show that $d_A$ is convex if and only if $A$ is convex.  I have no good ideas in either direction. Can somebody please give me a hint?  For the direction ($\Longleftarrow$), my attempt was:  Let $a_1 := \operatorname*{argmin}_{a \in A} \|x-a\|, a_2 := \operatorname*{argmin}_{a\in A} \|y-a\|$, then:  \begin{align*} d_A(x) &amp;= \inf_{a \in A} \|\lambda x + (1 - \lambda)y - a\| = \inf \|\lambda(x-a) + (1-\lambda) (y-a)\|\\ &amp;\leq \lambda \|x-a_1\| + (1-\lambda)\|y-a_2\| = \lambda d_A(x) + (1-\lambda)d_A(y) \end{align*}  However, I'm not sure whether the inequality in the third step is actually correct.
3255
Where can I find a good proof that CRF based models and logistic regression based models are convex? Is there a general trick to test/prove that a model or objective function is convex?
47060
My book tells me that of the solutions to the Lagrange system, the smallest is the minimum of the function given the constraint and the largest is the maximum given that one actually exists.  But what if we only have one point as a solution? How to know whether Lagrange multipliers gives maximum or minimum?
108633
I am trying to show that if $f$ is convex in $(a,b)$ it is  in $[c,d]$ where $a \lt c \lt d \lt b$.  Here's what I have so far:  Let $t_1,t_2 \in \mathbb{R}$ such that $a \lt t_2 \lt c \lt d \lt t_1 \lt b$  and let $x_1,x_2 \in [c,d]$.  Because $f$ is convex I know that $$\dfrac{f(c)-f(t_2)}{c-t_2} \lt \dfrac{f(x_2)-f(x_1)}{x_2-x_1} \lt \dfrac{f(t_1)-f(d)}{t_1-d}$$  I think I'm almost there, but what is the right $C$?
48948
I'm trying to solve the following problem:  Let $f:K\rightarrow \mathbb{R} $, $f$ convex and $K \subseteq \mathbb{R}^n$ convex. Then $f$ is continuous on $K$.   I have proved the only case $n=1$, but for an arbitrary $n$??
75994
I'm learning for an exam in calculus and have come across this question which I can't seem to prove:  Let $C \subseteq V$ be a convex set. Let there be a function &gt;$f:C\rightarrow \mathbb{R}$ a convex function. Now let there be scalars $\alpha_1,\alpha_2 \dots \alpha_k &gt;0$ such that &gt;$\sum^k_{i=1} \alpha_i = 1$, and also let there be a group of points &gt;$x_1,x_2\dots x_k \in C$. Show that the following inequality exists: $f(\sum^k_{i=1} \alpha_i x_i) \leq \sum^k_{i=1} \alpha_i f(x_i) $  I thought about using induction to show the inequality, whereby the basis k=2 is the actual definition of a convex function i.e: $f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)$ I've ran into a problem using induction, since the scalars won't sum up to 1 in the induction hypothesis. I also don't really use the fact that C is convex, which I'm probably supposed to... Either there is some algebraic trick that can be done so I can use induction, or I'm doing something wrong (and induction is not the way to go with this inequality) Any help will be appreciated, thank you!