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

learn more… | top users | synonyms

7
votes
0answers
217 views

Optimization of relative entropy

Wondering if my following question is an application of information theory: Lets say we have a factory and ship boxes of stuff outside. If a competitor stands outside my factory, observes the stream ...
6
votes
0answers
278 views

Subgradient of convex minimization duality

$$\min(f_0(x))$$ $$\text{s.t. }f_i(x) \le y_i \forall i, i = 1 ,\ldots, m$$ $$f_i : \text{convex};\quad x : \text{variable}$$ It is also considered that $g(y)$ is the optimal value of the problem ...
5
votes
0answers
184 views

Need advice: what should be my next step?

I am dealing with a quite algebraic question and I arrived at some good point. I had $2$ equations with $2$ unknowns and I was able to eleminate one of the variables. My final equation still seems ...
4
votes
0answers
117 views

Conditions under which the damped Newton method is globally convergent?

Consider the problem of minimizing a convex function over $\mathbb{R}^n$ \begin{align} \min_{x\in\mathbb{R}^n}f(x) \end{align} Consider the damped Newton method (from Nesterov's book Introductory ...
4
votes
0answers
186 views

the continuity of argmin on convex funtion

Define $$x'=\text{argmin}_{x_1}f(x_1,\lambda),$$ where $f$ is a strictly convex function on $x_1$ and $\lambda$. I would like to ask if there is any theorem about the continuity of $x'$ w.r.t ...
4
votes
0answers
176 views

How to find accuracy of Matlab's quadprog solver?

I have solved with quadprog from Matlab a strong convex quadratic problem given as $$ f(x) = x^TQx + c^Tx$$ with constrains $$ Cx \leq b.$$ Now the output of quadprog is: Minimum found that ...
4
votes
0answers
116 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 ...
4
votes
0answers
91 views

the dual of the dual is the primal?

Consider a convex optimization problem (call it $P$). Consider its dual (call it $D$). Is it true that the dual of $D$ is $P$? For linear programming, it is true. I'd just like to know under which ...
4
votes
0answers
110 views

Primal-Dual pair in SDP

Let's we have a primal model like $\max~~ x + \langle I, Z \rangle$ $s.t. ~~~Ax + y I - Z \preceq B$ $~~~~~~~~~Z \succeq 0, ~X \geq 0, ~~y ~free$ where $A, B \in {\mathbb R^{n \times n}}$. The ...
4
votes
0answers
119 views

When can the optimal value of a SDP be achieved?

Looking at semidefinite programs, are there any sufficient conditions for the solvability (i.e. the optimal value can be achieved, that is infimum=minimum)? Obviously if the problem is unbounded, the ...
3
votes
0answers
34 views

Reference for elementary result in optimization

Let $U(\mathbf{z})$ be a convex, twice differentiable function, and $F(\mathbf{z},\mathbf{q})$ be convex and twice differentiable separately in $\mathbf{z}$ and $\mathbf{q}$. Consider the problem of ...
3
votes
0answers
70 views

Variational characterization of nuclear norm

The nuclear norm $||\cdot||_{*}$ of a matrix is defined as the sum of its singular values. Working from the result at the bottom of this blog post, we have, for a matrix $\mathbf{X}$ and its ...
3
votes
0answers
89 views

How to prove the matrix fractional function is convex by definition

It is well known that the matrix fractional function $f(\mathbf{w},\boldsymbol{\Omega})=\mathbf{w}^T\boldsymbol{\Omega}^{-1}\mathbf{w}$ is jointly convex with respect to $\mathbf{w}$ and ...
3
votes
0answers
79 views

A complex optimization problem (maximize determinant of matrix)

Background Assume we have a 2 columned matrix ${\bf P}$ and this matrix can be written as $${\bf P}= [ {\bf p_1 \,\,\,\, p_2}]$$ where ${\bf p_1}$ is the first column (vector) of ${\bf P}$ and ${\bf ...
3
votes
0answers
25 views

Maximum overlap of two convex bodies

Let $\Delta_n=\big\{(x_1,x_2,\ldots,x_n): \sum_i x_i \leq 1, x_i \geq 0\big\}$ denote an n-dimensional simplex. I am trying to find an $y \in \mathbb{R}^n$ such that the $y-$shifted negative simplex ...
3
votes
0answers
44 views

Submodular function, square of which is also submodular?

A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions: for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $ for every $ ...
3
votes
0answers
107 views

If this problem is not unbounded, what's wrong in this dual derivation?

In a paper with 100 citation, Robust Support Vector Machine Training via Convex outlier Ablation, a convex relaxation is used. In this paper, a form of robust svm proposed: \begin{align} \min_{0\leq ...
3
votes
0answers
50 views

Is minmax equivalent to maxmin?

More precisely, problem $1$ is as follows: \begin{eqnarray} &\max_{1{\le}i{\le}N}\min_{[\gamma_m^i]}\left[\lambda_i - \sum_{m=1}^M\phi_m\gamma_m^iF_m^i\right] \\ &\mbox{subject to} ...
3
votes
0answers
69 views

Is $K =\{ S: \exists \text{ positive diagonal} D, D^TSD \;\text{diagonally dominant}\}$ convex?

I am doing some convex cone optimization and wonder whether the following set $K_1$ is convex or not. Assume the following matrices are all in $\mathbb{R}^{n\times n}$ and symmetric. Let the set of ...
3
votes
0answers
29 views

On the solutions of a system of inequalities avoiding Helly's theorem

Let $a_1,b_1,\cdots,a_4,b_4\in\mathbb{R},r_1,\cdots,r_4\in(0,+\infty)$. Show that, if $\not\exists (x,y)\in\mathbb{R}^2$ such that $$ \begin{cases} (x-a_1)^2+(y-b_1)^2\le r_1\\ ...
3
votes
0answers
53 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 ...
3
votes
0answers
52 views

Online stochastic convex optimization.

I need to find/approximate the argument that minimizes a stochastic convex function $F(\theta, Z)$: $$ {\arg\min_{\theta}} E_{Z}[ F(\theta, Z) ]$$ Where $Z$ is some random variable (we could assume ...
3
votes
0answers
90 views

Proving or disproving concavity of a function

I want to prove that the following function is concave (as a part of another proof). $$f(p) = \max_{\begin{matrix}x,y\\0\le x \le 1\\0\le y \le 1 \\ x * y = p\end{matrix}} \lambda h(x) + ...
3
votes
0answers
191 views

Dynamic programming problem for discrete linear time varying system

I'm working on a linear time varying discrete(LTV) multi input multi output(mimo) system. I formulate the problem description in the following way $$x_i(k+1) = x_i(k)\cdot A_i(k) + B_i(k)\cdot ...
3
votes
0answers
145 views

Conic hull of outer products

Consider the set of rank-k outer products, defined as $\{XX^T | X \in R^{n\times k}, rankX = k \}$. Describe its connic hull in simple terms. I have found the solution of this exercise but I have ...
3
votes
0answers
85 views

The difference between affine set and affine hull

According to the definition of affine hull and affine set. $$aff [C] = [\theta_1x_1+...+\theta_nx_n|x_1,...x_n \in C, ...
3
votes
0answers
75 views

Normalize gradient

I want to minimize a function $f \, : \, \mathbb{R}^{N} \, \longrightarrow \, \mathbb{R}$ (with $N \in \mathbb{N}^{\ast}$. In my problem, $N = 315$). I know that $f$ is differentiable on ...
3
votes
0answers
222 views

Complexity analysis of convex optimization problem

I am studying an optimization problem \begin{equation} \mathbf{x}^*=\text{argmax}\quad\sum_{d=1}^{D}\log(\mathbf{a}_d^T\mathbf{x}+b)+\mathbf{c}_d^T\mathbf{x}+f_d\\ \text{subject to}\quad ...
3
votes
0answers
104 views

The importance of the full-row-rank assumption for the simplex method

Consider a linear programming model in the usual form ready for applying the simplex method. I understand that having the constraint equations' coefficient matrix $A$ be of full row rank means not ...
3
votes
0answers
48 views

Is the optimizer of a strongly-convex cost function bounded?

Let f(x) be strongly-convex. Can its minimizer be unbounded? I suspect not. Can we obtain a bound on it in relation to the strong-convexity constant? I believe an equivalent formulation of this ...
3
votes
0answers
154 views

Does convexity of a function guarantee tractability of finding its minimum?

Formulating a problem as a convex optimization problem usually implicitly considered to imply being able to find global minimizer of the objective. My question is that if it is true or not. ...
3
votes
0answers
122 views

On the duality gap for quasiconvex optimisation problems

This stack exchange question got me thinking about quasiconvex analysis. Given a compact,convex subset $X\subset \mathbb{R}^n$ and a quasiconvex function $f:X\rightarrow \mathbb{R}$ Define the ...
3
votes
0answers
334 views

How to show that a function is piecewise linear

Let z(t) = min $(c+t d)^T x$ s.t $Ax <= b$ Show that Z(t) is a concave, piecewise linear function of t. I'm really not sure how to even start proving this, I would really ...
3
votes
0answers
443 views

sufficient condition for KKT problems

For the Karush-Kuhn Tucker optimsation problem, Wikipedia notes that: "The necessary conditions are sufficient for optimality if the objective function f and the inequality constraints g_j are ...
3
votes
0answers
347 views

Global optimum of sum of convex functions

Take two real differentiable convex functions, $f_1$ and $f_2$, defined on the unit interval $[0; 1]$. I want to find the global optimum of: $\min_{x \in [0;1]} af_1(x)+bf_2(x)$, for given $a, b \in ...
3
votes
0answers
201 views

How to calculate the maximal ellipsoid in a given polyhedron

I am faced with the problem of finding the ellipsoid $B$ ($B$ is a symmetric positive definite matrix) of maximal volume within a convex set $C$ given as a set of linear inequalities $C=\{x| a_i^T x ...
3
votes
0answers
996 views

Convex minimization over the Unit Simplex

I have a simple (few variables), continuous, twice differentiable convex function that I wish to minimize over the unit simplex. In other words, $\min. f(\mathbf{x})$, $\text{s.t. } \mathbf{0} \preceq ...
2
votes
0answers
38 views
+100

Optimization of approximate functions using varying objective function

Let $g(\theta;x)$ and $f(\theta;x)$ be two convex functions such that $g$ asymptotically approximates $f$: $g(\theta;x)\approx f(\theta;x)$, specifically: $$ |g(\theta;x)-f(\theta;x)| \leq ...
2
votes
0answers
22 views

How to efficiently solve a quadratic program repeatedly?

I have a quadratic problem, \begin{align} \min_{x\in [0,1]^n} x^T p+ \frac{1}{2\lambda} x^T Q x \end{align} ($Q$ is semidefinite) which I want to solve repeatedly, with the slight change of p and Q, ...
2
votes
0answers
68 views

LASSO constrained and penalised forms: first - order conditions?

The LASSO problem can be formulated in two ways: 1) Constrained formulation: $$ \|Xw-y\|^2\to\min_{w}\\ \text{s.t. } \sum_{i}|w_i|\leq{t}. $$ 2)Penalised formulation: $$ ...
2
votes
0answers
25 views

Theoretically understanding the algorithmic solution to this Quadratically Constrained Quadratic Optimization Problem

I have a simple QCQP problem to solve: $\min_{t} x(t)^{T}Ax(t)$ subject to constraints $x(t)^{T}Ax(t) > 1 $ where A is a positive definite matrix and $x(t) \in \mathbb{R}^2$ is some time ...
2
votes
0answers
20 views

Duality between $Ax<b$ and another system, but Gordan's just misses

I am trying to show that $$Ax < b$$ Is feasible iff $$ A^T y =0 , b^Ty + s = 0, (y,s) \ge 0, (y,s) \ne 0$$ Is infeasible. Work So Far Now when I try to hit this with Gordan's Lemma I seem ...
2
votes
0answers
26 views

Is it possible to use regularization to minimize the (expected) number of non-zero digits in a number?

This question may be slightly related to this question on length of the representation of a number in a certain basis. Introduction / Background In image and video coding, particularly the ...
2
votes
0answers
23 views

Can a subgradient always be found in polynomial time?

Given a convex function, under what conditions can we find a subgradient in polynomial time? There are easy examples such as $f$ being an supremum of a finite number of differentiable functions, but ...
2
votes
0answers
26 views

Example 2.13 Conditional Probabilities, Convex Optimization by Stephen Boyd

I am reading Stephen Boyd's Convex Optimization. I can't understand the example below: what is the "convex set of joint probabilities" in this example? what is the convex set $C$ here?
2
votes
0answers
28 views

Why does the dual problem of the SDP become a maximum eigenvalue problem?

This SDP problem with the variable $X \in \mbox{S}^n$ where $\rho \gt 0$ $$\max \mbox{Tr}(AX) - \rho \mbox{1}\lvert X \rvert \mbox{1} \\ \mathrm{subject\; to}\;\mbox{Tr}(X)=1, \\ X \succeq 0 $$ ...
2
votes
0answers
22 views

What happens if the segment between two vertices of a polyhedron is the intersection of the polyhedron with a half-space?

I think that given any two vertices, say $x$ and $y$, of a convex polyhedron, if the line segment between $x$ and $y$ is the intersection of the polyhedron with a half-space, then $xy$ forms an edge. ...
2
votes
0answers
41 views

Fenchel duality of infinity norm

The minimization problem is $\min\limits_{f_i} \sum^K_{i=1} \|f_i(\mathbf{p})\|_\infty$ Could someone explain how the Fenchel duality is used so the primal-dual formation becomes $$\min_{f_i} ...
2
votes
0answers
23 views

Question on optimization problem computing its solution function

I was just presented with this in Optimization class involving an optimization problem, on which I have no clue, it reads: (P) minimize-> $ f(x_1,x_2) = (x_1^2 -2x_1 + x_2^2 + 1)^{1/2} $ subject ...
2
votes
0answers
33 views

Is difference of convex hulls a convex hull of differences?

Let $K \subset \mathbb{R}^n$ be an n-dimensional simplex. Let $e_i$ denote the $i^{th}$ standard unit vector. Define $K-K$ as follows: $$ K-K=\{x-y: x,y \in K\} $$ We know that $K=$ convex hull ...