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

learn more… | top users | synonyms

7
votes
0answers
300 views

Is this question solvable? $2$ non-linear equations and the proof that the solution is unique (with asymmetric bounty option)

As mentioned in the title I want to show the uniqueness of the solution to $2$ non-linear equations. However, it seems that I can not solve this question with my current mathematical knowledge. More ...
6
votes
0answers
199 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 ...
6
votes
0answers
186 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 ...
5
votes
0answers
162 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
44 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
293 views

Properties of the square norm in Banach spaces

Let $X$ be a Banach space with its dual $X^*$. Consider the mapping $f: X\rightarrow \mathbb{R}$ given by $$ f(x)=\frac{1}{2}\|x\|^2. $$ We have know that when $X$ is a real Hilbert space ($X=X^*$) ...
4
votes
0answers
103 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
94 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
342 views

Convex analysis books and self study.

I have taken some courses in Convex optimization. Now I would like to know a little bit more about the pure mathematical side. Is there any good books in convex analysis? I have read and worked with ...
4
votes
0answers
114 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
39 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
20 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
51 views

Strong duality: When does the optimal primal variable coincide with the primal variable giving the dual function.

I'm considering the inequality-constrained optimization problem of finding $$ x^{\star} = \arg \min_{x} f(x) \;\; \text{s.t.} \;\; h(x) \le 0 $$ which is assumed to have a unique minimizer. The ...
3
votes
0answers
109 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
102 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
202 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
238 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
146 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
688 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
18 views

Log concavity/convexity of a determinant

I was wondering if anyone would be able to help me determine whether the following quantity is log concave or not with respect to $\alpha$? $$\left[\det(\textbf Y^\top \textbf P \textbf G \textbf ...
2
votes
0answers
26 views

Maximin problem as LP?

Consider the following setting. Let $A\in \mathbb{R}^{3 \times m}$ and $B\in \mathbb{R}^{m\times 3}$ be two matrices such that each of their columns must add up to a given $c\in \mathbb{R}$. Denote by ...
2
votes
0answers
34 views

does this convex set have a specific name?

Let $x_1,\dots,x_N$ be points of $\mathbb{R}^n$. Define the following set: $\mathcal{A} = \left\{\sum_{j=1}^N a_j x_j : -1 \le a_j \le 1, \, \, \forall j=1,...,N\right\}$. It is an easy exercise to ...
2
votes
0answers
20 views

What decides the structure of the dual variables taken in designing min-max type combinatorial optimization algorithms?

There are a bunch of combinatorial optimization problems like min cost flows and min weight perfect matchings that invoke duality and complimentary slackness to improve the primal feasible solution. ...
2
votes
0answers
21 views

Dual Decomposition with multiple coupling constraints

This is probably a a simple question, but have been stuck on this for a while and unable to figure out my issue from the standard Boyd/Vandhenbergen decomposition references. I am interested in dual ...
2
votes
0answers
34 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 ...
2
votes
0answers
79 views

Strong duality for nonconvex quadratic program (with multiple constraints)

Consider the following optimization \begin{eqnarray} P_1: \quad &\underset{x\in\mathbb{C}^N}{\mathrm{minimize}}&\; f_0(x) \\ &\mathrm{subject\;to}&\; f_i(x) \leq 0, i=1,\ldots,m \\ ...
2
votes
0answers
19 views

discrete nonlinear convex optimization relaxation over a dense set

Be a discrete nonlinear convex optimization problem $P$ \begin{align} \underset{x\in \mathrm{C}^n}{\mathrm{min}} \ \ \ f(x) \\ Ax=b \\ c \leq x \leq d \end{align} $C$ is a dense in $F$. Is solving ...
2
votes
0answers
41 views

Can we ever have E(argmin(f)) = argmin(E(f))?

Consider a parametric real-valued function $f_{\boldsymbol{\alpha}}:\ \mathbb D^N \rightarrow\mathbb R$ whose parameters $\boldsymbol\alpha$ vary according to some distribution $\psi$, and $\mathbb D$ ...
2
votes
0answers
29 views

proving that the ewma is convex

Hi: I know it's true but I don't know how to prove that exponentially weighted moving average when view ed as a function of $\lambda$, is strictly convex. The exponentially weighted moving average ...
2
votes
0answers
34 views

Effective convexity criterion for the finite point set in $\mathbb{R}^3$

I need to find effective convexity criterion for the finite point set. Below there is description of what is meant by "effective" criterion. Definition. Let $M = \{A_{1}, \ldots, A_{n}\}$ be the ...
2
votes
0answers
64 views

Affine functions as equality constraints in convex optimization problems

I am studying on an introduction to convex optimization problems. When defining a convex optimization problem, we have a convex object function, $f(x)$, a set of convex functions $g_i(x)$ where the ...
2
votes
0answers
49 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 ...
2
votes
0answers
67 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 ...
2
votes
0answers
40 views

Solve the linear program

Please help to solve this problem. I am new to this type of problems and any help will be greatly appreciated $$\text{ Minimize } 7x-5y+3z$$ $$\text{ Such that } \ \ \ 0 ≤ x ≤ 6 , -2 ≤ y ≤ 7 , -4 ...
2
votes
0answers
41 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 ...
2
votes
0answers
75 views

How to prove the convexity of the logrithmic gamma function?

Here's what I did: $$\Gamma'(z)=\int_0^\infty \log(t)e^{-t}t^{z-1}dt$$ $$\Gamma''(z)=\int_0^\infty ...
2
votes
0answers
46 views

Strictly convex self-concordant function

Some definitions: A function $f:R^n\rightarrow R$ is convex[strictly convex] if for every $\lambda\in[0,1]$ [$\lambda\in(0,1)$] and for every $x,y$ [$x\neq y$] in $R^n$ we have $f(\lambda ...
2
votes
0answers
38 views

Semidefinite Program formulation

I have the following problem and would like to formulate that as an SDP. I am not sure how to approach this : A set $S$ is given such that : $$ S = \{P \in R^{n \times m} : ||p_i - c_i|| \leq d_i ...
2
votes
0answers
100 views

Uniqueness of the solution

We know that 1) Minimise of a convex function the unique solution exists 2) Maximise of a concave function the unique solution exists How about 1) Minimise of a strictly convex function? 2) ...
2
votes
0answers
67 views

Maximizing the smallest eigenvalue of a linear combination of matrices

I have an engineering back ground. Due to work, I came across this problem \begin{align} &\max_{\lambda,y_i\in \mathbb{R}}~\lambda \\\ ...
2
votes
0answers
61 views

the objective function $\|F\|_F^2$ is quasiconvex in the optimization?why?

I have read a paper, but I can not understand one optimization thoroughly.Generally, Frobenius norm of one matrix, $\|F\|_F^2$, as the objective function is convex, so we can resolve it not using the ...
2
votes
0answers
72 views

How to get the minimum and maximum of one convex function?

Condition: $h,f\in \mathbb{C}^{N\times1}, \text{where}f =\hat{f} + e \text{ and } e^H e \leq 1,\ \ \ Q=h^Hff^Hh$. The Lagrangian function of $Q$ is $\mathcal{L} = h^H(\hat{f} + e)(\hat{f} + e)^Hh + ...
2
votes
0answers
96 views

The most efficient algorithm to solve the following problem

Is there an efficient optimization algorithm to solve the following problem? $(\alpha,\beta,\gamma,\cdots) =$ argmax $\sum_{i}\log(\alpha a_i+\beta b_i+\gamma c_i+\cdots)$, s.t. ...
2
votes
0answers
54 views

Proving an optimization problem has a rational optimum.

Consider the function $$ J_\gamma(X) = \det\left( I - \tfrac{1}{\gamma^2} (A+BXC)^\mathsf{T}(A+BXC)\right) $$ where $A$, $B$, $C$, $X$ are matrices of real numbers. Further suppose that ...
2
votes
0answers
26 views

Tractability of a cardinality problem

I have this confusion related to the convexity and tractability of a problem. The given problem is maximize $u^TSu$ subject to $||u||_2 = 1$ and card(u) <= r This is a NP hard problem because ...
2
votes
0answers
89 views

are elementary symmetric polynomials concave on probability distributions?

Let $S_{n,k}=\sum_{S\subset[n],|S|=k}\prod_{i\in S} x_i$ be the elementary symmetric polynomial of degree $k$ on $n$ variables. Consider this polynomial as a function, in particular a function on ...
2
votes
0answers
57 views

Quadratic Integer Programming

Would anyone mind helping me solve this problem $$ \min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda $$ where $x$ is a vector whose entries are positive ...
2
votes
0answers
21 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 ...
2
votes
0answers
185 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$. ...
2
votes
0answers
72 views

Nonlinear optimization of constraint parameter - subdifferential?

Disclaimer: I discovered that the FAQ suggests to post research-level to mathoverflow instead of math.stackexchange. I "moved" the question accordingly, cp. post at mathoverflow. Sorry for the ...