Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

2
votes
1answer
80 views

Check if convex polygon is completely contained completely within another convex polygon.

How can I determine if a convex polygon is completely contained within another convex polygon where speed is critical? I've thought about doing this, which will only use inequalities: pcp = ...
0
votes
1answer
12 views

If a quadratic form $f$ takes the minimum on a triangle in a vertex, what can I say about min of $f$ on edges of a subdivision?

Let $f(x)=x^2+y^2$ be the Euclidean square-norm and $A,B,C\in\mathbb{R}^2$ be vertices of a triangle $\Delta$ such that $f$ takes the maximum on $\Delta$ in $C$, the minimum in $A$ and takes the ...
0
votes
0answers
37 views

Using semidefinite programming to solve the following problem

I am struggling with the following problem, and wonder is SDP can help: $$\mathrm{maximize\ } \alpha_{10}+\alpha_5+(\alpha_2+\alpha_8)/2 \mathrm{\ subjected\ to\ } \mathrm{T_1}\succeq0, ...
1
vote
1answer
14 views

Convex combination and convex set

From where does $tx + (1-t)x'$ originate from? I am selfstudying an economists book, and this is popping up all of a sudden. I get that it's a line between $x$ and $x'$, but why? And is $tx' + (1-t)x$ ...
0
votes
1answer
26 views

Solving Constrained Least-Squares

I need to solve a constrained least-squares (LS) problem as follows $min_X \text{ } ||Y-AX||_F^2$ $s.t. \text{ } {X\in \chi}$ where $A\in R^{n\times m}$, $(n\ge m)$ , $X\in R^{m\times k}$ and ...
1
vote
1answer
28 views

How can I compute fast the minimum of a linear plus Kulback-Leibler on the unit simplex?

Given $a, x^0 \in \mathbb{R}^n$ I wish to compute $$\min_{x \in \Delta_n} a^t x + \sum_{i=1}^n x_i\log(x_i/x^0_i) - x_i +x^0_i $$ where $\Delta_n$ is the unit simplex $\{x \in \mathbb{R}^n \mid ...
1
vote
1answer
37 views

For a non-convex function f, how to find a function g such that $g\circ f$ is strictly convex?

The following function $f(x)={1\over (1+e^{-x})}$ is non-convex but $\ln(f(x))$ is convex. Given a non-convex function $f$, can we find a function $g$ such that $g\circ f$ is strictly convex? If yes, ...
0
votes
0answers
22 views

How to convert the following optimization problem to quadratic program?

Given positive constants $C$ and $\epsilon$ and points $\{ (x^i,b_i)\} _{i=1}^I \subset \mathbb{R}^{n+1}$, how can we rewrite the following optimization problem as minimizing a convex quadratic ...
0
votes
0answers
22 views

Book on duallity and sensitivity in nonlinear optimization

I am looking for a recommended book on duallity and sensitivity in nonlinear optimization, as duallity and sensitivity is a well studied topic in LP , I am struggeling to find books in this subject ...
0
votes
0answers
21 views

Continuity of optimisation problem

Consider $$F(z)=\min ae^{-x}+b e^{-y} s.t. x\ge 0, y\ge 0\text{ and } x+y=z$$ I checked if this function is continuous, but it is not at $z=0$. $F(z)=2\sqrt{ab}e^{-z/2}$ when $z\ne 0$, and ...
1
vote
1answer
35 views

Convergence rate - Convex optimization

What is the best known algorithm in terms of convergence rate for unconstrained convex optimization and under what assumptions? $\min_{x} f(x)$ where $f(x)$ is a given twice differentiable convex ...
1
vote
1answer
27 views

Show the Gini Coefficient is Quasiconvex

The Gini-coefficient is defined as $$ G(x) = \sum_{i = 1}^n \frac{i}{n} - \sum_{j=1}^{i} \frac{x_{(j)}}{\mathbb{1}^{T}x}, $$ where $x_{i} $ is nonnegative numbers with positive sum. $x_{(j)}$ denotes ...
1
vote
1answer
73 views

Augmented Lagrangian Method for Inequality Constraints

Augmented Lagrangian Method can be used with inequality constraints. The question is how. One approach (according to Numerical Optimization Book by Nocedal and Wright; page 522), is linearly ...
0
votes
0answers
34 views

Formulate an optmization problem as a convex optmization problem

Let $P$ be a polyhedron, i.e. $P = \{ x \in \mathbb{R}^{n}\, |\,\, a_{i}^{T}x \leq b_{i} \}$. Define $R$ as the rectangle given by $\{ x \in \mathbb{R}^{n}\, \mid\, \, l \preceq x \preceq u \}$. Find ...
0
votes
1answer
68 views

intuition behind subspace of $R^n$

Hi: I've been reading an optimization text by Charles Byrne, "A First Course In Optimization". I'm currently going through the chapter where he explains things about convex sets and convex functions ...
0
votes
0answers
42 views

strong convex implies exp-concave

Prove that if f is strong convex (for some m>0) $\mbox(\nabla f(\mathbf{x})-\nabla f(\mathbf{y}))^{T}(\mathbf{x}-\mathbf{y})\geq m||\mathbf{x}-\mathbf{y}||_{2}^{2} $ then f is also ...
0
votes
1answer
34 views

proof that length of difference of projections implies equality of length of normals

Hi: I'm reading a book on optimization and there is an interesting stated theorem but I don't know how to prove it. Notation: Let $P_{c}(x)$ denote the projection of onto a convex set c which is a ...
3
votes
1answer
53 views

$\arg\max$ of an increasing function grows as the region grows.

$f_1,\dots,f_N:\mathbb{R}^+\rightarrow\mathbb{R}^+$ are strictly increasing, bounded functions whose derivatives monotonically decrease to $0$ as their argument increases. (Picture the shape of the ...
0
votes
0answers
43 views

Non-convex function with global minimum [duplicate]

I am working on a complicated objective function which I suppose is not convex. But when I use a global optimization tool that can find all its local minimums, it will always converge to the same ...
0
votes
0answers
38 views

How can I minimize a quadratic on the unit simplex?

How can I compute $$ \min_{x \in \Delta_n} \frac{1}{2}\lVert Bx\rVert^2 + x^tAy$$ with $x \in \mathbb{R}^n, y \in \mathbb{R}^m, A_{m \times n}$, $B_{n \times n}$ where $\Delta_n$ is the unit simplex ...
1
vote
0answers
45 views

Proximal operator of spectral norm of a matrix

How can I calculate the proximal operator of spectral norm for any general matrix, $X\in R^{m\times n}$ i.e., $X^* = \arg \min_X ||X||_2 + \frac{1}{2\tau} ||X-Y||_F^2$ I understand that the proximal ...
0
votes
0answers
21 views

How can I solve $\min \{ \langle A(x),y\rangle + f(y) \text{ s.t. } y \in S^n, \operatorname{tr}(y) =1, y \geq 0\}$?

I'm trying to solve the problem $$\min \{ \langle A(x),y\rangle + f(y) \mid y \in S^m, \operatorname{tr}(y) =1, y \geq 0\}$$ where $x \in \mathbb{R}^n$, $y \in S^M$, that is, it's a symmetric $m$ by ...
0
votes
0answers
32 views

Krein Milman Property

If a closed bounded (not compact) set $X$ in a Banach space $B$ (like $L^1$) has extreme point(s), must the max of a linear functional defined on $X$ occur at one of them? I suppose it depends on $B$. ...
0
votes
0answers
30 views

How to solve this entropy optimization problem with gradient projection method?

The problem is defined as $$ \min_{w} = \sum_{i=1}^{n} \sum_{j=1}^{n}\left\{ \left(\sum_{k=1}^{3}w_kP_{ij}^{(k)}\right) \log \left(\sum_{k=1}^{3}w_kP_{ij}^{(k)}\right) \right\} + \gamma \|w\|_2^2\\ $$ ...
0
votes
0answers
16 views

Minimizing a function known to have a unique local and global minimum

Quasi-convex functions are a class of functions known to have a unique local and global minimum, which can minimized over convex sets using numerical methods with convergence guarantees. A function is ...
1
vote
0answers
49 views

Proximal operator for the nuclear norm of Hankel (x)

I have a problem in hand for which I need to compute the proximal operator of the composite function $||Hankel(x)||_{nuc}$ where $x \in R^N$ and $||.||_{nuc}$ denotes the matrix nuclear norm. For a ...
2
votes
1answer
57 views

linear approximation with respect to L1 norm

I am trying to solve this problem: Find the best $L^1$ linear approximation of $e^x$ on [0,1] i.e. minimize $\int_0^1|e^x-\alpha-\beta x| dx$ any hints how to proceed
0
votes
0answers
29 views

Find an optimal solution for $\min_{x} F(x)$ analytically

I want to find an analytical solution (exact/closed-form) for $x$ of the following minimization problem: $$\min_{x} b x \left[e^\left(\frac{a}{x}\right)-1\right]+d (1-c-x) \left[e^ ...
0
votes
0answers
35 views

How to solve the least square with $L_2$ norm constraint directly?

I answered the question Why are additional constraint and penalty term equivalent in ridge regression? earlier, but I myself still have some questions on it. To solve \begin{align} \min_{\beta} ...
2
votes
1answer
71 views

Constructing a quasiconvex function

Let $C\subset\mathbb{R}^2$ be a nonempty convex set. A function $f:C\rightarrow\mathbb{R}$ is called convex if $$ f(\lambda u+(1-\lambda)v)\leq\lambda f(u)+(1-\lambda)f(v), \quad\forall u,v\in C, ...
1
vote
2answers
48 views

Is the optimum of this problem unique?

I have a convex optimisation problem: $$\min_{x_i} \sum_{i=1}^N a_i \exp(-x_i/b_i)\quad\text{ s.t. }\sum_{i=1}^N x_i=x\text{ and } x_i\ge 0$$ The KKT conditions are: $$\lambda=\begin{cases} ...
0
votes
0answers
20 views

Reference material on Alternating Minimization Algorithm

I am looking for some good reference material (book/paper) for learning Alternating Minimization Algorithm. Any recommendation from optimization experts will be much appreciated. Thank you.
1
vote
2answers
220 views

(Updated) Geometric Illustration of Monotone and Maximal Monotone Maps

I am writing a note about the Monotone and Maximal Monotone maps from the following book http://link.springer.com/book/10.1007%2Fb97594 In this book we read a map ...
0
votes
1answer
29 views

Is this function jointly convex in its variables?

I have a function which I suspect is jointly convex, but have a difficult time proving it, especially since the Hessian is messy. The function is $f(y_i,i=1.2,\ldots,N)=\sum_i l_i w_i + y_i$, where ...
0
votes
0answers
66 views

Is there a unique saddle value for a convex/concave optimization?

Here is the question: Consider a function of two variables $f(x,y)$ on some compact domain. Let it be convex in $x$ and concave in $y$. Is it true that $f(x,y)$ has a uniqe saddle point ...
0
votes
1answer
86 views

Step-by-step example of solving a quadratic program with linear inequality constraints

I'm doing an exercise work about Support Vector Machines which involves solving a quadratic program of the form $$\begin{aligned} & \underset{\boldsymbol\alpha \in \mathbb{R}^N}{\text{minimize:}} ...
4
votes
1answer
48 views

Is the optimal solution of a strictly convex function over $\mathbb{Z}^d$ a rounded version of its optimal solution over $\mathbb{R}^d$

Consider a strictly convex function $f: \mathbb{R}^d \rightarrow \mathbb{R}$. Let $x^* = \min_{\mathbb{R}^d} f(x)$ denote the (unique) minimum of this function over $\mathbb{R}^d$. Similarly, let ...
1
vote
1answer
51 views

how to write largest circle inscribed inside a triangle as an optimization problem?

can someone show me how to write this problem as a convex optimization problem.Find the largest disk that can be bounded by $X \geq 0$ , $Y \geq0$ and $X+2Y\leq1$. My institution is to cast to ...
4
votes
2answers
81 views

Learning about convex optimisation

I'm interested in learning a bit about convex optimisation. The wikipedia article contains the following paragraph: The convexity of $f$ makes the powerful tools of convex analysis applicable. ...
0
votes
0answers
24 views

Quick Constrained Optimization Huerstistics

I am wondering if there is a way to find very quick optimization heuristics for the form. $$ f(x) = cx^a $$ $$ s.t. $$ $$ L \le Ax \le B$$ $$ 0 \le x \le \infty $$ I know with only a few variables ...
1
vote
1answer
42 views

Convexity of Conjugate Function on Determinant

If $f: \mathbb R^n \to \mathbb R$ then $conj(f) : \mathbb R^n\to \mathbb R$ is defined as $conj(f)(y) = \sup_{x \in dom_f} (y^Tx - f(x))$ and it is called the conjugate function of $f$. if $f(X) = ...
0
votes
0answers
38 views

Does every boundary segment of a convex polyhedron lies on one of its faces?

When I was reading this note, I found Theorem 3.1.5 said: Let $P\in\mathbb{R}^n$ be a polytope whose affine dimension is $d$. Then, every point on the boundary of $P$ lies in a facet of $P$. I have ...
1
vote
1answer
33 views

condition for uniform input to minimize convex function

Let $f:\mathbb{P}(X) \rightarrow \mathbb{R}$ be a convex function where $\mathbb{P}(X)$ is the set of probability distribution on (finite) set $X$. I am looking for condition on $f$ so I can said ...
2
votes
1answer
76 views

Is standard eigenvalue optimization problem convex

For any arbitrary symmetric matrix A , is the standard eigenvalue problem convex $ \lambda_{max}(A)= \max_{\|x\| \leq1} x^{T}Ax$
1
vote
0answers
47 views

Tucker's theorem from Farkas lemma

I am trying to understand the proof of Tucker's theorem using Farkas lemma but there are some points that are not clear to me. The proof I am following is in this paper at page 16. What I do not ...
0
votes
0answers
23 views

How can I solve $\inf_{x \in X} x^T(Ax + b) + \sum_{i=1}^n x_i \log(x_i)$ in a closed form depending on projection?

I'm trying to solve the minimization problem $$\inf_{x \in X} x^T(Ax + b) + \sum_{i=1}^n x_i \log(x_i)$$ where $b \in \mathbb{R}^n$, $X \subset \mathbb{R}^n$ is a convex set. And $A$ is a symmetric ...
3
votes
0answers
37 views

Are these equivalent definitions of faces of convex sets?

I consulted several books and found that the definitions of faces and exposed faces of convex sets are a bit messy. Many books just treat them as the same stuff. In book "foundations of ...
1
vote
1answer
48 views

Are these inconsistent definitions of extreme subset of convex set?

I need some elementary knowledge of polyhedral and I am consulting several books. However, I found the definitions may not be consistent. I am not sure if I understand them right. The question is ...
1
vote
0answers
52 views

Convex Optimization: Advantages of Symmetric Primal-Dual Algorithms?

This is a follow-up to an answer on a previous question on PD algorithms: http://math.stackexchange.com/a/1193928/36257 I have done some research learning the mechanics of how Infeasible PD ...
0
votes
1answer
47 views

Is $\mathbf{y}^*$ a local minimizer of $f(\mathbf{h}(\mathbf{y}))$?

Let $f(\mathbf{x})$ be a twice differentiable function, where $\mathbf{x} \in \mathbb{R}^n$. Let $\mathbf{x}^*$ be a local minimizer of $f(\mathbf{x})$. Consider a differentiable and invertible ...