Tag Info

Hot answers tagged

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) ...


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

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 ...


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 ...


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 ...


2

We can determine the domain of $f^*$ without having to determine $f^*$ fully, but that's not difficult, either. Suppose we have a value of $Y$ satisfying $\langle Y, X \rangle \geq 0$ for some $X\succ 0$. Define $$\alpha\triangleq \langle Y, X \rangle\geq 0, \quad \beta\triangleq\log\det X > 0.$$ Now consider $\bar{X}=t X$ for $t>0$. Then ...


2

A affine map $g$ on $\mathbb P(X)$ corresponds to a (right) stochastic matrix $T$, i.e. a matrix with real nonnegative entries, each row summing to $1$, acting on $\mathbb P(X)$ (represented by row vectors) by $\pi \mapsto \pi T$. The matrix $T$ is doubly stochastic iff the uniform distribution is invariant under $g$. If in addition $T$ is aperiodic and ...


2

Thanks to Michael for catching my previous errors. You need to be careful with terminology here. In the following, I am assuming that $A$ is symmetric. The function $\phi(A) = \max_{\|x\|\le 1} \langle x, Ax \rangle$ is always convex because it is the $\sup$ of a collection of convex (in fact, linear) functions $A \mapsto \langle x, Ax \rangle$. However, ...


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 ...


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

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

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, ...


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 ...


1

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 ...


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 ...


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 ...



Only top voted, non community-wiki answers of a minimum length are eligible