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

learn more… | top users | synonyms

7
votes
0answers
222 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
287 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
191 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
127 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
199 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
120 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
93 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
111 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
122 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
35 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
93 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
100 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 $\boldsymbol{\...
3
votes
0answers
82 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
27 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
48 views

Center of mass of vertices without enumeration?

Given a $n$-dimensional convex polytope defined by $A x\leq b$ and $A_{eq} x = b_{eq}$, is there an efficient way to determine the average coordinates of all vertices without enumerating them? (As if ...
3
votes
0answers
45 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
111 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} \sum_{i=1}^...
3
votes
0answers
70 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\\ (x-a_2)^2+(y-b_2)...
3
votes
0answers
55 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 optimization",...
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
94 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) + \bar{\...
3
votes
0answers
197 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 u_i(k)$...
3
votes
0answers
158 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
87 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, \theta_1+.....
3
votes
0answers
77 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 $\mathbb{R}^{...
3
votes
0answers
249 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 \mathbf{f}...
3
votes
0answers
109 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
160 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
556 views

SDP relaxation of non-convex QCQP and duality gap

Short version Is there a duality gap between a QCQP problem and the SDP problem obtained through Lagrangian relaxation? A paper I'm studying is using this fact, but I cannot achieve the authors' ...
3
votes
0answers
123 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
348 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
477 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
366 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
205 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
1k 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
39 views

Convex optimization with $\ell_0$ “norm”

I have an optimization problem of the form $$\begin{align*}\text{minimize }\;&f(x)\\ \text{subject to }\;&||x||_0 \le t,\end{align*}$$ where $t$ is a given constant and $f:\mathbb{R}^d \to \...
2
votes
0answers
31 views

Sup of a linear function

Let $X$ be a banach space or simply a normed space and $C$ a convex (closed) subset of $X$. It is true that if $x \in C$ is such that $f(x)=\sup f(C)$, (in other words $x$ is a supporting point for $C$...
2
votes
0answers
41 views

Optimizing potential

Let $X$ be a vector field on a Riemmanian manfiold $M$. I recently read that solving: \begin{equation} \operatorname{argmin}_{\phi}\int_M (\nabla \phi - X)^2 d\mu, \end{equation} where $\mu$ is ...
2
votes
0answers
92 views

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 \mathcal{...
2
votes
0answers
26 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
75 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: $$ \|Xw-y\|^2+\lambda\left(\...
2
votes
0answers
29 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
32 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
24 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
29 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
23 views

How to deal with a convex constraint

I want to deal with a convex constraint \begin{align} F(P)=P^{H}AP_{0}+P_{0}^{H}AP-P_{0}^{H}AP_{0}\succeq 0 \end{align} where $(\cdot)^{H}$ represents Hermitian transpose, $A$ is a positive definite ...
2
votes
0answers
30 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 $$ ...