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

learn more… | top users | synonyms

2
votes
0answers
57 views

convex optimization with inconsistent constraints

If you have a problem in convex optimization where all $N$ constraints ($N >> 0$) yield no possible solution but you are able to rank, or weight the constraint in terms of their importance are ...
2
votes
0answers
84 views

Convexity of a function

Suppose we have $F: R^n \longrightarrow R$ , $P: R^n \longrightarrow R^n$ and $G: R^n \longrightarrow R$ all nice- let's say given by polynomial and $P$ is invertible - such that $F(x) =G( P(x) )$. ...
2
votes
0answers
54 views

Duality gap in cone programming

Let $K\subset \mathbb{R}^2$ be a closed convex and pointed cone, $A$ be a $2\times 2$ square matrix and $b, c\in \mathbb{R}^2$. Consider the problem $$ (P)\quad \min\{\langle c, x\rangle: Ax\geq_K b\}...
2
votes
0answers
80 views

Find a vector such that its matrix product is positive in every element

Given a matrix $A$ I want to find a vector $\vec{x}$ such that every element of $A\vec{x}$ is strictly positive. Also, the columns of $A$ do not span the full space, so if I were to just naively pick ...
2
votes
0answers
372 views

A convex programming problem involving sum of logarithms of linear functions

Here is a convex programming problem I encountered while working on an estimation problem for a mixture of multinomial distributions. We have a matrix $A_{m \times n}$ containing non-negative real ...
2
votes
0answers
423 views

real-time linear programming

I'm going to implement in C a light-weight embedded lp-solver for a production system. I need to be able to sequentially solve a series of (possibly unrelated) linear programming problems with ~6-60 ...
1
vote
0answers
11 views

Constructing another dual to reach primal optimal

In Boyd's convex optimization book, he gives an example of weak duality where dual optimal is strictly less than primal optimal. He says that the intuition behind this is that we were able to hide the ...
1
vote
0answers
13 views

Conjugate function

I am looking for a geometric and intuitive explanation of the conjugate function and how it maps to the below analytical formula. $$ f^*(y)= \sup_{x \in \operatorname{dom} f } (y^Tx-f(x))$$
1
vote
0answers
37 views

maximising sinusoidal functions

I have come across a maximisation problem that I do not know how to handle. I have posted the question here in the past. I have the following function to maximise for $x,y$ $$f(x,y)=a_1 \cos(x) +b_1 ...
1
vote
0answers
63 views

Analytical, numerical and graphical approaches to solve convex optimization problems?

I'm wondering if there are analytical approaches to solve these problems(I found these problems in a book by Stephen Boyd): minimize $f_0(x_1,x_2)$ subject to $2x_1+x_2\ge1$ $x_1+3x_2\ge1$ $x_1\...
1
vote
0answers
11 views

Proof of the existence of a rational finitely generated cone

Let $P$ be a rational polyhedron and $F$ be the inclusion-wise minimal face. Then we define: $C_F= \left\{c\in \mathbb{R}^n : F \subseteq \left\{x \in P:c^Tx=\max\left\{ c^Ty:y \in P\right\}\right\}\...
1
vote
0answers
32 views

Maximize $\gamma$ such that $A+\lambda B-\gamma C\succeq 0$

This question follows this previous one: Maximize $\gamma$ such that $A+\gamma B\succeq 0$ This time, $A\succ 0$, $B$ is indefinite and $C = \begin{bmatrix} 0 & \dots & 0 \\ \vdots & \...
1
vote
0answers
21 views

proximal operator to sum of norm functions

The proximal operator is defined by: $$ prox_{\tau f} = \arg\min_u \frac 1 {2\tau} \|u-u^k\|^2 + f(u) $$ I know the solution when $$ f(u) = \|Au+b\|_1 $$ But I wonder how to derive the solution of ...
1
vote
0answers
24 views

Interpolating polynomial such that it is convex in specified region

The problem I have is that I have data at two points $x_1,x_2$ and $x_2>x_1>0$. At these two points, I know that the function $f$ has values $f(x_1)$ and $f(x_2)$ respectively. It is also ...
1
vote
0answers
17 views

Recommend a optimization book with more coding examples?

I am interested in continuous optimization problems. However, I feel it is very difficult for me to understand the classic books such as Convex Optimization or Numerical Optmization. My problem with ...
1
vote
0answers
23 views

Gradient Descent and Scale of Data and Objective Function

One way to tune step size in gradient descent is via backtracking line search. backtracking line search (with parameters α ∈ (0, 1/2), β ∈ (0, 1)) starting at $t = 1$, repeat $t := \beta t$ ...
1
vote
0answers
15 views

Demonstrating convexity of a convex optimization problem

I am working on the following problem. Consider the following function $\textit{f}: \mathbb{R^n}$ × $\mathbb{R^n}$ → $\mathbb{R}$. $$f(\vec{z},\vec{d}) := \min_{t \in \mathbb{R},\vec{v} \in \mathbb{...
1
vote
0answers
49 views

How to solve a binary generalized assignment problem

I have the following generalized assignment problem: Z=max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ such that $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad\quad\...
1
vote
0answers
52 views

What are some applications of vertex separators?

What are applications of finding a vertex separator that minimizes a cut in a graph. To clarify the problem I am talking about is is given a graph of n vertices and a partition $m_1,m_2,..,m_k $of ...
1
vote
0answers
43 views

Help needed to define a constraint in an optimization problem?

Given objective function is \begin{align} \underset{\mathbf{p},\mathbf{q}}{\text{min}}\hspace{4mm} (\mathbf{p*q})^T \mathbf{A}(\mathbf{p*q}) \hspace{4mm} \\ s.t \hspace{4mm}\mathbf{p^Te_p}-1=0\\\...
1
vote
0answers
29 views

How to minimize objective function involving convolution?

My objective function is \begin{align} \underset{\mathbf{p},\mathbf{q}}{\text{min}}\hspace{4mm} (\mathbf{p*q})^T \mathbf{A}(\mathbf{p*q}) \hspace{4mm} \\ s.t \hspace{4mm}\mathbf{p^Te_p}-1=0\\\mathbf{...
1
vote
0answers
40 views

Good text book recomendation

I would like to do some reading about a technique called sequential convex programming. There is a lot of material about sequential quadratic programming out there, including books (Nocedal & ...
1
vote
0answers
24 views

A question on Edgeworth Expansion

I'm working Edgeworth Expansion. I couldn't understand one thing . Can you help me about that please. $$Z= \frac{\sqrt {n} (\bar {x} -\mu)}{\sigma}$$ converges in distribution to N(0,1) I have ...
1
vote
0answers
41 views

maximum of a concave function in a minkowski sum

Let: $f(x,y)$ - a strictly-concave function, monotonically increasing in $x$ and $y$; $A,B$ - two compact and convex sets in the positive quadrant; $C$ - their Minkowski sum, $A+B$; $(x_A,y_A)$ - ...
1
vote
0answers
10 views

Why this problem is unbounded, even though it's dual is feasible?

In this paper, An Efficient Inexact ABCD Method for Least Squares Semidefinite Programming,page 2, there is a problem called, (P): \begin{align} P: &\min_{X,s} && ‎ \frac{1}{2} ‎\Vert X-G\...
1
vote
0answers
28 views

Variational inequality and saddle point problem

I refer to the following paper: (fix the wrong link) https://papers.nips.cc/paper/5723-adaptive-primal-dual-splitting-methods-for-statistical-learning-and-image-processing.pdf In that paper, we ...
1
vote
0answers
22 views

Can a linear program be optimal if its basis is infeasible?

I want to know thanks to the dual theorem wether the following basis is or isn't optimal. That is to say looking for the slack variables. As far as the third line doesn't respect the constraints: $...
1
vote
0answers
59 views

When does a variable goes out with the revised Simplex method?

Let be the following linear program. \begin{cases} \max & 3x_1& +x_2\\ &x_1&-x_2 &\le -1\\ &-x_1 &-x_2&\le -3\\ &2x_1 &+x_2 &\le4\\ x_1,x_2\ge 0 \end{...
1
vote
0answers
12 views

Variant of conjugate function: $V(s) = \underset{x}\max \{\langle s,x-x_0\rangle-\beta f(x)\}$

Consider one variant of conjugate function: $$V(s) = \underset{x}\max \{\langle s,x-x_0\rangle-\beta f(x)\}$$ You can think $s$ as a linear functional. If I do the following steps: \begin{...
1
vote
0answers
25 views

Is there a way to determine if the Convex Hull of two polyhedra is going to be huge?

So in this post: Faster Algorithms for Convex Hulls I was interested in determining if a convex hull of two $n$ dimensional polyhedra can be computed quickly, and the answer was in general: no, ...
1
vote
0answers
86 views

Some intuition on the support function of a convex set

I have some doubts on the interpretation and properties of the support function of a convex subset of $\mathbb{R}^d$. (1)Let $K$ be a convex set in $\mathbb{R}^d$. (2) The support function of $K$ is ...
1
vote
0answers
33 views

Why the trace norm of a tensor is a good approximation to its rank?

In many literature, they use the trace norm of a tensor to approximate its rank, which is defined as follows: $$\|\mathcal{X}\|_{\ast}:=\sum_{i=1}^{n}\alpha_i\|X_{(i)}\|_{\ast}$$ where ${\alpha_i}'s$ ...
1
vote
0answers
23 views

Expressing $\forall$ in linear programing

I'm doing a linear program to a game and I don't know how to express $\forall$ in linear programing (or if I had the right intuition to do it). Here is the problem: I have several vessels that are ...
1
vote
0answers
56 views

Can we use simple alternating optimization for minimax (saddle point) problems?

Consider a function $f(x,y)$, convex in $x$ and concave in $y$. we are interested in the following optimization problem, \begin{align} \min_{x \in D_x} \max_{y \in D_y} f(x,y) \end{align} Because of ...
1
vote
0answers
40 views

Generalizations of Positive Definiteness

What, if any, notions of positive definiteness can be extended to 3rd order tensors (and beyond)? The reason I ask is because the Hessian matrix of a convex function is positive semi-definite, but ...
1
vote
0answers
31 views

Converting a norm-computation SemiDefinite program to standard SDP form.

I'm trying to express this norm-computation semidefinite program: for given $A \in R^{m \times n}$ and a scalar $\epsilon \in (0,1)$ $$\gamma_{2}^{\epsilon}(A):= \min\,t\,\, subject\, to\, \left( \...
1
vote
0answers
21 views

Boyd & Vandenberghe's proof that all simplexes are polyhedra.

On page 33 of B&V's convex optimization book, during the proof that any simplex can be represented as a polyhedron, they discuss a $n \times k$ matrix $B$ with full column rank and conclude that: ...
1
vote
0answers
99 views

matrix optimization in diagonal and orthonormality constraint

I'd like to solve the following optimization problem. Y is a CxN matrix A is a CxC and diagonal matrix Q is a CxC and orthonormal matrix X is a CxN matrix $$ min_{A,Q} {|| Y − AQX ||}^2_F $$ The ...
1
vote
0answers
37 views

Logarithmic Function Behaivour

I have read about Logarithmic function. We can use the second-order condition to show that the $f(x)=\log_2(1+x), x \geq 0$ is a concave function. Now, is $g(x)$ a concave function? How can I prove ...
1
vote
0answers
62 views

Convex Conjugate of Log Sum Exp Function

Convex Optimization Snippet In showing the convex conjugate of log-sum-exp function, $f(x) = \log(\sum_{i=1}^n e^{x_i})$, Boyd argues that the domain of the convex conjugate, $$f^*(y) = \sup_{x \in ...
1
vote
0answers
14 views

Condition on linearly separable datasets

I am trying to understand linear classification with hyperplanes. So far I understood that for a binary classifier with labels $y_i \in \lbrace -1, 1\rbrace$ points $(x_i, y_i)$ are separable if ...
1
vote
0answers
31 views

Efficiency of quasiconvex optimization

Summary: Could we minimize quasiconvex objectives in polynomial time? Whenever an objective function of an optimization problem can be formed as a convex function, this is considered as victory. ...
1
vote
0answers
55 views

How to prove that unnormalized neg entropy is strongly convex with respect to 1-norm?

the unnormalized negative entropy of $\mathbf{x} \in \mathbb{R}^n_+$ is $$ g(\mathbf{x}) = \sum_i (x_i \log(x_i) - x_i) $$ it is stated that $g(\mathbf{x})$ is strongly convex with respect to 1-norm, ...
1
vote
0answers
31 views

Moreau Decomposition with Bregman Distance

I am working with a non-Euclidean proximity operator defined by a Bregman distance function $D(\cdot, \cdot)$: $$ \operatorname{prox}_f(x) = \operatorname*{argmin}_u \{ f(u) + D(u, x) \} $$ Is ...
1
vote
0answers
44 views

Scaled proximal operator for proximal Newton method

The scaled proximal operator was introduced as an extension of the (regular) proximal operator: $prox^H_h(x) = \arg\min_y h(y) + \frac{1}{2}\|y-x\|^2_H$. (See http://papers.nips.cc/paper/4740-...
1
vote
0answers
37 views

KKT conditions for a convex optimization (optimal crowdsourcing with budget constraint)

I am having some troubles deriving the optimal solution of the following convex optimization problem, $w_j$, $c_{ij}$, and $B$ are fixed and non negative. \begin{align} & \underset{n_{ij}}{\text{...
1
vote
0answers
28 views

What is the Computational Complexity of Minimising a Linear Function over a General Convex Set?

Is the computational complexity of finding or approximating $\inf\{c^Tx:x\in X\}$ (where $X$ is a compact convex given explicitly or by some reasonable oracle) known? EDIT: Suppose we had an ...
1
vote
0answers
45 views

Quasiconcavity of a product of ratios

Given $f(x_1\ldots x_k) = \dfrac{x_1x_2\cdots x_k}{(x_0+c_1)(x_0+c_2)\cdots(x_0+c_k)}$ where $x_i > 0$, the $c_i > 0$ are constants, and $$x_0 = \sum_{i=1}^k x_i$$ is it true that $f$ is ...
1
vote
0answers
28 views

Analytical algorithm to obtain solution to convex optimization problem.

Assume a vector $\vec{P}$ with N elements $\in \mathbb{R}^+$ and constants $T_P$ and $\epsilon$. The vector $\vec{P}$ is arranged in a column $(N\times 1)$. Consider the problem: $$ \begin{aligned} ...
1
vote
0answers
67 views

How to find the tangent cone to a set in a point?

Let $S\in R^{n}$ is a set and $x\in S$. We define tangent cone of $S$ in $x$ as: $$T_{S}(x)=\{z\in R^{n}:\exists (x_{k}), x_{k}\in S, x_{k}\rightarrow x, \exists (y_{k}), y_{k}>0, y_{k}(x_{k}-x)\...