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

learn more… | top users | synonyms

2
votes
0answers
20 views

Analogue of Helly’s theorem for non-exact interpolation

Let $\overrightarrow{x}=(x_1,x_2, \ldots ,x_n),\overrightarrow{a}=(a_1,a_2, \ldots ,a_n)$ and $\overrightarrow{b}=(b_1,b_2, \ldots ,b_n)$ be vectors in ${\mathbb R}^n$, with $a_k \leq b_k$ for every ...
1
vote
2answers
70 views

How many methods for smoothing an unsmoothed function?

Which is the simplest one? For example, we smooth $f(x)=|x|$ to $$f(x)=\begin{cases} \frac{x^2}{\epsilon}+\frac{\epsilon}{2} & |x| \le \epsilon\\ |x| & |x|\ge epsilon ...
0
votes
2answers
43 views

Distance between convex set and non-convex set?

So in http://en.m.wikipedia.org/wiki/Shapley%E2%80%93Folkman_lemma there is some talk about distance between a mintowksi sum and a convex set. But I couldn't get how distance is being defined. Can ...
1
vote
0answers
215 views

Error on optimization problem, maximize log determinant on CVX

$A$ is an $N \times N$ complex matrix $W$ is an $N \times N$ complex matrix $C$ is an $N \times N$ complex diagonal matrix $u$ is a scalar $V$ is an $N \times N$ complex matrix, whose diagonal elects ...
0
votes
1answer
51 views

A reference to learn about duality

I am interested in learning about duality in convex optimization. I am looking for something to read which is: Reasonably short. Fairly self-contained (if it is a chapter in a textbook, I would ...
0
votes
1answer
61 views

convex function, inequality

If $f: R^n\rightarrow R$ is convex and $f(\alpha x)=\alpha f(x), \alpha \geq 0$, show that: a) $f(x+y)\leq f(x)+f(y)$ for all $x,y\in R^n$ b) $f(0)\geq 0$ c) $f(-x)\geq -f(x)$ for all $x\in R^n$ d) ...
1
vote
1answer
49 views

Proof of convexity of a function

I have to prove that function $J(x)=e^{x^3+x^2+1}$ is convex on $[0,\infty]$. I used a Theorem which says: **$U\subset R^n$ is convex set with non-empty interior and $J\in C^2(U)$. Function $J$ is ...
1
vote
2answers
553 views

Carathéodory's theorem

Carathéodory's theorem says "If $C\subset R^n$, then every point from ${\rm conv}\; C$ can be expressed as a convex combination at the most of $n+1$ elements from $C$" In every proof I found, it ...
1
vote
0answers
105 views

Confusion related to derivation of soft thresholding

I was going through the derivation of soft threholding at http://dl.dropboxusercontent.com/u/22893361/papers/Soft%20Threshold%20Proof.pdf. It says the three unique solutions for $\operatorname{arg ...
2
votes
2answers
182 views

Optimize a log det function with respect to a matrix, and the saddle point analysis

Suppose I want to to find the local minima of a logdet function $\mathcal{L}$ with respect to a Matrix $\mathbf{A}$, $$ \mathcal{L} = \log\vert \mathbf{I} + \mathbf{A}\mathbf{S} \vert - ...
1
vote
1answer
134 views

Sparse least-squares fitting of discrete probability distributions

I have an optimization problem involving $n$ discrete probability distributions and I am looking for a suitable solution for this problem that I can implement as computer program. Let the vector ...
0
votes
1answer
38 views

convexity of two linear spaces connected by a convex equality constraint

If there are two sets of linear constraints in different variables, Ax <= b with x_l <= x <= x_u and Cy <= d with y_l <= y <= y_u, and a set of equality constraints of a specific ...
0
votes
1answer
88 views

maximization of a Strictly convex function

The things we know, usually minimization of a convex function, unique solution will exist. My question is, maximization of a strictly convex function, will that give an unique maximum? If so how we ...
1
vote
1answer
150 views

formulate this scheduling problem as linear programming problem

Sorry if this very silly, but i am something new to optimization theory: We have $m$ identical Machines and $n$ jobs. A job $j$ can be done in any of the identical machines in $p_{j}$ time units. ...
0
votes
1answer
89 views

Composition of a convex function

If $f:[a,b]\rightarrow R$ is convex function and $f'(x)\geq 0$ for all $x\in [a,b]$ and $g:U\rightarrow [a,b]$ is convex function, how to show that $f(g(u)), u\in U$ is convex function?
2
votes
1answer
34 views

supremum of an array of a convex functions

If $\{J_n\}$ is an array of a convex functions on a convex set $U$ and $G(u)=\sup J_i(u), u\in U$, how to show that $G(u)$ is convex too? I've done this, but I am not sure about properties of a ...
1
vote
0answers
104 views

Confusion related to optimization of log(det(X)) function

I have this confusion related to optimization of the log(det(X)) function. I didn't get how it implicitly maintains the constraint of X being positive definite. For eg if I have a matrix ...
1
vote
1answer
46 views

Convexity of expected value

I am trying to understand if the expected value of a variable is convex in that variable or not. I know that expectation is a linear operator, so must be convex. But I do not see why it does not ...
0
votes
1answer
225 views

Convex homogeneous function

Prove (or disprove) that any CONVEX function $f$, with the property that $\forall \alpha\ge 0, f(\alpha x) \le \alpha f(x)$, is positively homogeneous; i.e. $\forall \alpha\ge 0, f(\alpha x) = \alpha ...
3
votes
1answer
200 views

Show that any convex function is locally bounded

Show that a convex function $f:\mathbb{R}^n \rightarrow \overline{\mathbb{R}}$ is bounded in a neighborhood of $x\in \text{ri}(\text{dom}(f))$. Showing that it has an upper bound is not difficult ...
1
vote
1answer
111 views

Is the following optimization problem convex?

I'm not an mathematician so sorry for the possibly trivial question. I have written the following integer programming model: \begin{align} \max z &= \sum_{i=1}^M \left(\sum_{j=1}^N b_j x_{ij}- ...
0
votes
1answer
29 views

in the derivation of support vector classifier

I was studying the Stephen Boyd's textbook on convex optimization and have a question on the support vector classifier. The book says the following: In linear discrimination, we seek an affine ...
1
vote
1answer
118 views

Convex hull of an open set is an open set

I have to prove this. Actually, I have the proof, but I don't understand one part. It says: "Since $\operatorname{co}A$ is intersect of all convex sets that contain set A, it follows that ...
1
vote
1answer
121 views

Convex set, continuous function

Show that set of continuous functions $f$ on interval $[a,b]\subset R$ such that $|f(x)|\leq 1$, $x\in [a,b]$, is convex in $C[a,b]$. I've done this: $f_1 (x)$, $f_2 (x)$ are continuous ...
2
votes
3answers
59 views

Convex set. Proof.

Prove that if A is convex set and $\alpha, \beta ≥ 0$ then $(\alpha + \beta)A = \alpha A + \beta A$ What came first on my mind is that I have to show that $(\alpha + \beta)A\subset \alpha A + \beta ...
1
vote
0answers
98 views

why in Phase I of the simplex method, if artificial variable become nonbasic, it never become basic?

Does anybody has idea how to solve this problem ? "Show that in Phase I of the simplex method, if an arti cial variable becomes nonbasic, it need never again become basic. Thus, when an arti cial ...
0
votes
1answer
460 views

Pointwise supremum of a convex function collection

In Hoang Tuy, Convex Analysis and Global Optimization, Kluwer, pag. 46, I read: "A positive combination of finitely many proper convex functions on $R^n$ is convex. The upper envelope (pointwise ...
2
votes
2answers
489 views

How can I solve Lagrange multiplier equation with multi constraints?

This site is really awesome. :) I hope that we can share our ideas through this site! I have an equation as below, $$ min \ \ w^HRw \ \ subject \ \ to \ \ w^HR_aw=J_a, \ w^HR_bw=J_b$$ If there is ...
2
votes
2answers
179 views

Finding convex conjugate of a bounded function

The convex conjugate of a function $f:\mathcal{X}\mapsto \mathbb{R}$ is formally defined as $$f^\star\left(y\right)=\sup_{x\in\mathcal{X}}\ \left\langle x,y\right\rangle-f\left(x\right).$$ In cases ...
0
votes
1answer
54 views

Quadratic Functions

Consider the strictly convex quadratic function $f(x) = \frac{1}{2}x^tPx - q^tx + r,$ where $P \in \mathbb{R}^{n \times n}$ is a positive definite matrix, $q \in \mathbb{R}^n$ and $r \in \mathbb{R}.$ ...
0
votes
1answer
83 views

solve non-convex quadratic constrained quadratic programming

$\min_{\beta}\beta^{T} A \beta$ $s.t. \ \beta^{T} C \beta=1\ and\ \beta\geqslant 0$ Here $A,C\in \mathbb{R}^{M\times M}$, $\beta \in \mathbb{R}^{M}$ I saw in one paper saying that it could be ...
1
vote
1answer
173 views

Why does the non-negative matrix factorization problem non-convex?

Supposing $\mathbf{X}\in\mathbb{R}_+^{m\times n}$, $\mathbf{Y}\in\mathbb{R}_+^{m\times r}$, $\mathbf{W}\in\mathbb{R}_+^{r\times n}$, the non-negative matrix factorization problem is defined as: ...
1
vote
0answers
55 views

Suggestions for a reference-level text on optimization theory?

I'd be interested in knowing if anybody has suggestions on an advanced but still self-contained reference on optimization theory, centered around linear and convex problems. The key feature of my ...
0
votes
1answer
62 views

Strict convexity condition

I have an if and only if, and I am having trouble with one of the arrows! Here it is: Let $C \subset \mathbb{R}^n$ such that the interior of $C$, $\operatorname{int} C \neq \emptyset$. $C$ is ...
2
votes
1answer
243 views

Maximum of quasi-convex functions

A function $f$ is quasiconvex if all its sub-level sets are convex (i.e., $\{ x: f(x) \le \alpha\}$ is convex for all $\alpha$.) For a convex function $f$, it is true that $f$ acheives its maximum ...
4
votes
0answers
97 views

On a version of gradient descent

I am trying to read this paper and have gotten stuck. The author considers the problem of minimizing a convex function whose gradient has coordinate-wise Lipschitz constant $M$ (meaning that for all ...
0
votes
0answers
110 views

KKT conditions of this convex optimization problem

Consider a continuous function $f: \mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R}$ such that $\forall y \in \mathbb{R}^m$ $f(\cdot,y)$ is convex, and $\forall x \in \mathbb{R}^n$ $f(x,\cdot)$ ...
1
vote
0answers
106 views

non-degenerate basic feasible of Polyhydron

I couldn't show this problem. Can somebody help me by this question? Consider a polyhedron $\{X \in \mathbb{R}^n | AX \leq b, X \geq 0 \}$ and a non-degenerate basic feasible solution $X^*$. We ...
0
votes
0answers
252 views

polyhedra and extreme points

I am stuck with solving this problem, does anybody has idea, how to solve it ? Let $P$ and $Q$ be polyhedra in $\mathbb{R}^n$. Let $P +Q := \{x+y ~\vert~ x \in P; y \in Q \}$ a) Show that $P + Q$ ...
0
votes
1answer
62 views

How to re-parametrize for quadratic minimization?

Given a real-rectangular matrix $S$ and inorder to solve this simple quadratic programming problem: Minimize $w'S'Sw = \|S w\|^2$ over $w$ subject to $e^Tw = 1$ and $w \geq 0$ using a solver I ...
0
votes
1answer
39 views

Where the gradient of a convex function approaches zero

Does there exists a differentiable convex function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ with a unique global minimum which we denote by $x^*$ such that there exists a sequence $x_k$, not ...
2
votes
0answers
184 views

$\{x:Ax\leq 0\}$ contains a subset of type $\{x:A'x=0, ax\leq 0\}$

If $C:=\{x:Ax\leq 0\}\neq\{x:Ax=0\}$, an independent set of rows of $A$ can be chosen, one denoted by $a$ and the others put as rows into a matrix $A'$, such that $\{x:A'x=0,ax\leq 0\}\subseteq C$. ...
1
vote
2answers
315 views

Convex Optimization of quadratic function with inequality constraints

How would I solve the following problem? $$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$ where A is positive semidefinite and symmetric. Is it possible to ...
0
votes
1answer
283 views

Positive semidefinite Matrix examples query

This might be really dumb question but I've just started dealing with such matrices. I would like to know why $$\begin{bmatrix} 0 & 1 \\ 1 & x \end{bmatrix}$$ cannot be a positive semidefinite ...
2
votes
3answers
229 views

A robust convex optimization problem

Consider a function $ f: \mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R} $ such that $\forall x \in \mathbb{R}^n$ the map $f(x,\cdot)$ is convex, and $\forall y\in \mathbb{R}^m$ the map ...
6
votes
1answer
4k views

L1 norm and L2 norm

I was studying the Stephen Boyd's textbook on convex optimization. It says the following: The amplitude distribution of the optimal residual for the l1-norm approximation problem will tend to have ...
17
votes
1answer
585 views

Properties of the Cone of Positive Semidefinite Matrices

The set of positive semidefinite symmetric real matrices form a cone. We can define an order over the set of matrices by saying $X\geq Y$ if and only if $X-Y$ is positive semidefinite. I suspect that ...
0
votes
1answer
54 views

KKT formulation

How to reformulate the following problem $$min \frac{1}{2} (x_1-a_1)^2+ \frac{1}{2} (x_2-a_2)^2$$ $$s.t. \mathbf{1}^Tx=1$$ $$ ||x||_2\leq2$$ as the following system of KKT conditions: $$(1 + ...
1
vote
0answers
31 views

“Buzzword” for approximate gradients (that form a positive scalar product with the real gradient)

Let $\vec g(\vec x)\in\mathbb R^N$ be the gradient of a convex function $L: \mathbb R^N\mapsto \mathbb R$ and $\vec h(\vec x)$ such that $$ \vec h(\vec x)^T\vec g(\vec x) \geq 0\quad\quad \forall \vec ...
3
votes
2answers
1k views

KKT and Slater's condition

I was studying Stephen Boyd's text book and got confused in the KKT part. The book says the following: "For any convex optimization problem with differentiable objective and constraint function, any ...