Tag Info

New answers tagged

0

$\newcommand{\Reals}{\mathbf{R}}\newcommand{\setA}{\mathcal{A}}$If the points $(x_{j})_{j=1}^{N}$ are linearly independent as vectors in $\Reals^{n}$, the set $\setA$ is the parallelipiped[1] centered at the origin, with a vertex at $-\sum_{j} x_{j}$ and edges $(2x_{j})_{j=1}^{N}$.[2] If the points are linearly dependent, $\setA$ is a projection of a ...


1

Zonotope. (I have nothing more to say, but say more to satisfy the computer.)


1

Simply specifying that a function is twice differentiable is not enough to guarantee a complexity rate. The best theoretical treatment of second-order methods---that is, methods that exploit both first- and second-derivative information---is probably by Yurii Nesterov and Arkadii Nemirovskii. Their work requires an assumption of self-concordance, which in ...


1

Let $f_i(x) = \sum_{j=1}^n x_{(j)}$. This is a concave function of $x$. To prove it, define $$S_{(i)}\triangleq \{s\in\{0,1\}^n\,|\,\textstyle\sum_j s_j = i\}$$ In other words, $S_{(i)}$ is the set of all $\{0,1\}$ vectors with exactly $i$ nonzeros. Then $$f_i(x) = \inf_{s\in S_{(i)}} s^Tx.$$ Because $f_i(x)$ is the pointwise infimum of affine functions, it ...


1

The matrix $A_k$ should be an approximation of the Jacobian of $c$ at $x_k$. For the first look, you can think of $\nabla c(x_k)^\top$. Then, the constraint is just the first-order Taylor expansion of $c$ at $x_k$.


1

1. Projection onto a halspace Proposition. If $C\subset\mathbb{R}^n$ is a subspace then $$ \langle x-P_C(x), y-P_C(x)\rangle=0 \quad \forall y\in C. $$ Proof. By the property of the metric projection, we have $$ \langle x-P_C(x), u-P_C(x)\rangle\leq 0 \quad \forall u\in C. $$ Substituting $u=y\in C$ and $u=2P_C(x)-y\in C$ into above inequality we obtain $$ ...


0

Let's suppose $a\neq 0$. Then $f''(x) \le 0 $ for all $x$ implies $4a^2x^2+4abx+b2+2a$ has a constant sign, which can happen only if $\Delta'=-8a^3\le 0\iff a\ge 0$. In such a case, this sign is the sign of $4a^2$, so $f$ can't be concave unless $a=0$ If $a=0$, similarly we must have $b=0$. Thus $f$ is concave if and only if $a=b=0$, i. e. if and only ...


0

Here we need that $f''=(2ax+b)^2e^{ax^2+b}+2ae^{ax^2+b}\le 0$, since the exponential is positive we need $$(2ax+b)^2+2a\le 0.$$


2

It's true that some of the $x_i$ will tend to $\infty$ as $P$ does, however, it's not always true that all of them will. Intuitively, because the functions are increasing, the solutions must always lie on the top right-hand face of the simplex $$\Sigma_P:=\left\{x:\sum_i x_i=P\right\}.$$ A quick argument for this goes like suppose that a solution $y$ does ...


0

Since $C$ is a subspace, we have $$ \langle x-P_C(x),P_C(x)-P_C(y)\rangle=0; $$ $$ \langle y-P_C(y),P_C(y)-P_C(x)\rangle=0. $$ Adding two equalities we obtain $$ \langle x-P_C(x)-(y-P_C(y)),P_C(x)-P_C(y)\rangle=0 $$ or equivalently, $$ \langle x-y, P_C(x)-P_C(y)\rangle=\|P_C(x)-P_C(y)\|^2. $$ We have \begin{eqnarray*} ...


0

Consider two points with $x = a > 0$ and $y > 0$. They lie on a straight line which is both convex and concave. Now consider two points on $x=y,\quad x>0$, here $f=x^2$ which is convex. Now, two points on $x+y=5$ (say) gives you a concave function, so $f$ is clearly neither convex nor concave in your region (or indeed, anywhere).


4

First convince yourself that an optimizer must intersect the graph of $e^x$ exactly twice in the interval $[0,1]$. Then a better parametrization of the linear approximation is $$\ell(x) = (x - s) \cdot \frac{e^t - e^s}{t-s} + e^s$$ which intersects $e^x$ precisely at $x = s$ and $x = t$. Then the integral being optimized is $$ \int_0^s e^x - \ell(x) ...


1

May I suggest the Frank-Wolfe method? Here's an example found by a quick google on "Frank Wolfe example" http://aerostudents.com/files/valueEngineeringAndOperationsOptimisation/FrankWolfeAlgorithmDemonstration.pdf


1

Very similar to your example. On $C = [0,1] \times [0,1]$, $$ f(x,y) = \cases{ 1 & if $x \ge 1/2$ and $y = 1$\cr 0 & otherwise\cr}$$ Let $g(x,y) = f(x,y) + \lambda y$. Note that the only cases where $f(t p + (1-t) q) > t f(p) + (1-t) f(q)$ have one of $p$ and $q$, say $p$, is in $[0,1/2] \times \{1\}$ and the other in $(1/2, ...


2

For $n=1$ the structure of the graph of a maximal monotone operator is known. First the domain and range of such an operator are (possibly degenerate) intervals. If the domain is just one value then the graph is a vertical line passing through that value (similarly for the range being degenerate). If the domain is a non-degenerate interval ($(a,b)$ or ...


1

You can find the source of maximal monotone mappings in the following and the references therein: Variational Analysis, Rockafellar, R. Tyrrell, Wets, Roger J.-B. http://www.springer.com/gp/book/9783540627722 Maximal Monotone Operators in Banach Spaces, Viorel Barbu http://link.springer.com/chapter/10.1007%2F978-1-4419-5542-5_2 Lectures on Maximal Monotone ...


2

Since the set over which you are minimizing is compact, there exists a minimizer. Since the set is convex and the objective function is convex, the set of minimizers is convex. The KKT conditions now tell you what the form of any minimizer must be: Either $x_i = 0$ or the numbers $a_i/b_i \exp(-x_i/b_i)$ must all equal the same value $\lambda> 0$. This ...


0

Hint: A strictly convex function has at most one (global) minimum.


1

From what I can tell, most of your question is adequately addressed in this other post, except perhaps for the last part: The reason I ask this question is that if for any $\lambda \in K^*$, we have $\lambda \ge_{K^*} 0$, why not just using $\lambda \in K^*$ instead of $\lambda \ge_{K^*} 0$ in the above statement? I can think of two good reasons to ...


2

A sum of convex functions is convex, so if the $l_i \ge 0$ it is sufficient for all $w_i$ to be convex functions of $y$. If you require $w_i > 0$ (and all the constants $a_i$ and $b_j$ are positive), taking logarithms gives you a system of linear equations in $\log(w_i)$ and $y_i$, so (if there is a solution) you get $\log(w_i)$ as affine functions of ...


3

This holds in one dimension, that a strictly convex function $f:\mathbb{R} \to \mathbb{R}$ with minimum at $x^*$ on the real line will attain its minimum on $\mathbb{Z}$ either at $\lfloor x^* \rfloor$ or $\lceil x^* \rceil$ (or both). [Note that a strictly convex real function need not attain a minimum value, either at real or integer arguments, e.g. $f(x) ...


-2

A set S in R^n is said to be convex if we consider any two distinct points from this set, then the line segment through these points must lie in the set we considered.On the other hand, By an affine set we mean a set A in R^n, in which if we consider any two distinct points from this set, then the line passing through these points must lie in the set we ...


1

EDIT: Geez, I totally forgot that Section 4.3.1 of Boyd & Vandenberghe's book Convex Optimization shows how to compute the Chebyshev center of a polyhedron described by inequalities. The Chebyshev center is the center of the largest inscribed circle of the polygon; and the model that computes it gives the radius as well. I could have skipped all of this ...


1

I highly recommend the following book: Hiriart-Urruty, Jean-Baptiste, and Claude Lemaréchal. Fundamentals of convex analysis. It is a rigorous book on the mathematical foundations on convex analysis, and is designed for learning the topic from the ground up. I can't comment on how the book compares to Bersekas' Convex Optimization Theory, since I haven't ...


2

I think you want Convex Optimization Theory by Dimitri P. Bertsekas, and Convex Analysis and Optimization by Bertsekas, Nedić, and Ozdaglar. These are a product of an theoretical, east-coast (i.e., MIT) approach to convex optimization, as opposed to the more practical, west-coast (i.e., Stanford) approach offered by Boyd & Vandenberghe. (And you ...



Top 50 recent answers are included