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

learn more… | top users | synonyms

1
vote
1answer
148 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
842 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 ...
1
vote
1answer
339 views

Closed form solution of a convex optimization problem

Suppose we want to solve the following optimization problem: \begin{equation*} \begin{aligned} & \underset{x,y,z}{\text{minimize}} && x(a-y) \\ & \text{subject to} && ...
1
vote
2answers
385 views

Maximize the product of linear functions

Suppose $f(x,y) = \prod_{i=1}^n (a_ix+b_iy)$ where $n$ is a constant larger than 500, and $a_i>0$, $b_i>0$ are known coefficient. There is only one global maximum. What's the most efficient ...
1
vote
2answers
103 views

computational strategy for solving convex-concave minmax problem

Assume f(x,y) is convex in $x$ and concave in $y$. Then \begin{equation}\min_x \max_y f(x,y)\end{equation} is globally solvable, because f is convex in x (max of convex is convex.) But can we find a ...
1
vote
1answer
188 views

Submodularity of the product of two non-negative, monotone increasing submodular functions

I'm trying to prove the submodularity of the product of two non-negative, monotone increasing submodular functions Formally, we have $f$ and $g$ are submodular functions, that is, ...
1
vote
1answer
95 views

On the convexity of the element-wise norm 1 of a pseudoinverse

Let us define $\|A\|_1$ the element wise norm 1 of a matrix $A \in \mathbb{R}^{n \times m}$ as $$ \|A\|_1= \sum_{i,j} |A_{i,j}|. $$ Obviously, this function is convex over $\mathbb{R}^{n \times m}$. ...
1
vote
2answers
584 views

What Stopping Criteria to Use in Projected Gradient Descent

Suppose we want to solve a convex constrained minimization problem. We want to use projected gradient descent. If there was no constraint the stopping condition for a gradient descent algorithm would ...
1
vote
1answer
388 views

What is a good technique to decide step size in sub-gradient method for dual decomposition?

I am looking at the following paper to implement dual decomposition for my algorithm: http://www.csd.uoc.gr/~komod/publications/docs/DualDecomposition_PAMI.pdf On Pg.29 they suggest setting the step ...
1
vote
1answer
28 views

In an engineering/optimisation context, does set $E$ have any special significance?

I am reading a paper about optimsation and the description, while mostly being a very good description, makes reference to some variables being in some set $E$. For example, it states that parameter ...
1
vote
2answers
475 views

Proof of Convexity?

Given a positive semidefinite matrix $A$, is $\operatorname{Tr}X^TAX$ a convex function in $X$? Am looking for a proof of convexity or non-convexity, whichever is true.
1
vote
1answer
448 views

Convex Conjugate of Absolute Norm

Let $f:\mathbb{R}\rightarrow[-\infty,\infty]$ be a continuous function. The convex conjugate of $f$ is: $$f^*(p) := \sup_{x\in\mathbb{R}}\{px-f(x)\}~.$$ Furthermore, let us define the subderivative ...
1
vote
1answer
869 views

Prove convexity/concavity of a complicated function

Can anyone help me to prove the convexity/concavity of following complicated function...? I have tried a lot of methods (definition, 1st derivative etc.), but this function is so complicated, and I ...
1
vote
1answer
97 views

Please help me find the maxima of this expression

I want to find $p$ which maximizes the given functional. $p$ is a function of the form $\mathbb{R}^2 \to \mathbb{R}$. $\Omega$ is a region in the 2-d plane. $\underset{p}{\sup} \int_\Omega \{ ...
1
vote
1answer
212 views

Supremum of vector dot-product

I am curious what is the precise math reasoning behind this: $$ \sup \{ a_i^T u | \lVert u\rVert_2 \leq r \} = r \lVert a_i \rVert_2$$ It is on page 148, last line, of Boyd's Convex Optimization ...
1
vote
2answers
446 views

Proving quadratic function is bounded (vector input)

I am reading Boyd's Convex Optimization textbook and I am looking at example 3.22, line 2. It says $y^T x - \frac12 x^T Q x$ is bounded from above for all possible values of $y$. Also, it is ...
1
vote
1answer
313 views

Can Minkowski difference be realized with support functions?

Minkowski sum of two compact convex sets is easily computed if they are represented in terms of support functions, one just adds the two support vectors for each direction. $X \oplus Y = \{x+y : x ...
1
vote
1answer
202 views

Scaling a decimal number to have leading digit 5 or more

Suppose we are given two real numbers: $a, b \in \mathbb{R}$, $b > a$. Find $m \in \{1, 2, 2.5, 5\}$ and $k \in \mathbb{Z}$, satisfying the following condition: $\frac{b-a}{m10^k} \in [5,10)$. How ...
1
vote
1answer
14 views

Subgradient of the optimal value of a linear program with respect to its parameters

Consider the linear program $f(c)=\min\{c'x\mid x\in\mathbb{R}^n,Ax=b,x\geq0\}$. Are there any results on what is $\partial f/\partial b$?
1
vote
1answer
27 views

what does separable convex program mean?

In literature,a separable program is formulated like this: $$\min_{x_{1},...x_{n}}\sum_{i=1}^{n}f_{i}(x_{i})$$ where $f_{i}$ is a closed proper convex function. My question is what does 'closed' ...
1
vote
1answer
28 views

does constant convexity assures global minimum

I have the following question: Consider a function $f:R^n \longrightarrow R$, s.t.: there is a point $x_0 \in R^n$ s.t. $\frac{\partial f}{\partial x^k} =0$ $\forall k$. the hessian matrix ...
1
vote
1answer
38 views

Why is this function, related to SVM derivation, non-convex?

I'm working through a support vector machines tutorial. In eventually deriving the solvable objective function, the following objective function (to be maximized) was proposed, but dismissed as ...
1
vote
1answer
74 views

Is there any way to make the following function convex?

I need to find optimal lagrangian multiplier vectors for a quadratic programming problem subject to three quadratic equality constraints and several other linear inequality constraints. I would like ...
1
vote
1answer
66 views

How to project gradient vector to subspace defined by linear constraints

I have the following set of linear constraints: $$\begin {align}\textbf{y}^T\textbf {x} &= 0 \\ \textbf {0} &\leq\textbf {x} \leq C\cdot\textbf {1},\end {align}$$ where $\textbf {y} \in ...
1
vote
1answer
23 views

How can a second-order cone problem be expressed as a conic problem?

I realize that a second-order cone is a cone, and thus an SOCP is a type of conic problem. However, to me it doesn't seem so apparent, looking at their equations. Could someone explain how one could ...
1
vote
1answer
27 views

How can I compute fast the minimum of a linear plus Kulback-Leibler on the unit simplex?

Given $a, x^0 \in \mathbb{R}^n$ I wish to compute $$\min_{x \in \Delta_n} a^t x + \sum_{i=1}^n x_i\log(x_i/x^0_i) - x_i +x^0_i $$ where $\Delta_n$ is the unit simplex $\{x \in \mathbb{R}^n \mid ...
1
vote
1answer
34 views

Convergence rate - Convex optimization

What is the best known algorithm in terms of convergence rate for unconstrained convex optimization and under what assumptions? $\min_{x} f(x)$ where $f(x)$ is a given twice differentiable convex ...
1
vote
1answer
24 views

Show the Gini Coefficient is Quasiconvex

The Gini-coefficient is defined as $$ G(x) = \sum_{i = 1}^n \frac{i}{n} - \sum_{j=1}^{i} \frac{x_{(j)}}{\mathbb{1}^{T}x}, $$ where $x_{i} $ is nonnegative numbers with positive sum. $x_{(j)}$ denotes ...
1
vote
1answer
53 views

Augmented Lagrangian Method for Inequality Constraints

Augmented Lagrangian Method can be used with inequality constraints. The question is how. One approach (according to Numerical Optimization Book by Nocedal and Wright; page 522), is linearly ...
1
vote
1answer
47 views

how to write largest circle inscribed inside a triangle as an optimization problem?

can someone show me how to write this problem as a convex optimization problem.Find the largest disk that can be bounded by $X \geq 0$ , $Y \geq0$ and $X+2Y\leq1$. My institution is to cast to ...
1
vote
1answer
61 views

Convex Optimization: do Primal Dual methods need to start with strictly feasible point?

I'm learning about Primal-Dual interior point algorithms from Boyd & Vandenberghe Convex Optimization, ch.11.7. Now the text mentions: In a primal-dual interior-point method, the primal and ...
1
vote
1answer
40 views

Proving a function of matrix is convex

I have a function of a matrix and a vector $f(A,b)=y^\top (I-A)^{-1} b$ and I want to know the conditions under which it is convex. For functions of a vector, the positive definiteness of the Hessian ...
1
vote
1answer
52 views

How to derive the solution in quadratic optimization

I'm reading the book "Convex Analysis and Optimization" written by Prof. Bertsekas. In Example 2.2.1, there are the following description: I don't know how to ...
1
vote
1answer
22 views

Show the following statements are equivalent - convexity

Let $C \subset \mathbb{R}^n$ be a set. Show the following are equivalent: (a) The set $C$ is convex. (b) The function $\delta_C : \mathbb{R}^n \to \mathbb{R} \cup \infty$ defined as: ...
1
vote
1answer
36 views

Convexity proof - can I get some pointers?

Prove that $C \subset \mathbb{R}^n$ is convex iff $\forall m \in \mathbb{N}$ and every set of $m$ points $\{x_1,...,x_m\} \subset C$ we have that $\sum_{i=1}^m \lambda_i x_i \in C$ Where ...
1
vote
1answer
35 views

how to find the solution of this cost function?

I have the following cost function. $J = \sum_{i=1}^N a\, Trace(W^TX_iW) - b\, Trace(W^TY_iW)$ Where $X_i$ and $Y_i$ are symmetric matrices, $a$ and $b$ are scalars. How can I find W?
1
vote
1answer
19 views

Convexity of a subset is convex?

Let $V$ be the set of sequences whose terms are contained in $\mathbb{R}^n . V$ is the set of functions $x(·) : N → \mathbb{R}^n $ which we denote as $\{x_n\}_n \subset \mathbb{R}^n$. $V$ is a vector ...
1
vote
1answer
38 views

Showing affinity of a function - proof help

Let $V$ be the set of sequences whose terms are contained in $\mathbb{R}^n . V$ is the set of functions $x(·) : N → \mathbb{R}^n $ which we denote as $\{x_n\}_n \subset \mathbb{R}^n$. $V$ is a vector ...
1
vote
1answer
49 views

Help with this convex set proof

Take $C ⊂ \mathbb{R}^n$ a convex set. Fix $x_0 ∈ C$ and a nonzero vector $v ∈ \mathbb{R}^n$ . Define the set $I(x_0,v) := \{t ∈ R : x_0 + tv ∈ C \}$. Prove that $I_(x_0,v)$ is a convex subset of ...
1
vote
1answer
87 views

infimum and supremum notation

I have stumbled across this blob of text when reading my textbook, and would like to know how to interpret it more intuitively. I understand the definitions of inf and sup, however not so much what ...
1
vote
1answer
58 views

Showing the intersection/union of a cone is a cone

Defining a set $C \subset \mathbb{R}^n$ as a cone if for ever $x \in C$ and $\alpha \geq 0$ we have $\alpha x \in C$. ie they are closed under scalar multiplication. How can I show that the ...
1
vote
1answer
44 views

How can I show the following statements are equivalent?

Let $C ⊂ \mathbb{R}^n$ Prove that the following statements are equivalent. (i) $C$ is an affine set (ii) For every $x_0 ∈ C$ , the set $C − x_0 := \{ z − x_0: z ∈ C \}$ is a subspace. (iii) There ...
1
vote
1answer
57 views

Showing convexity proof

Let $F: \mathbb{R}^n \rightarrow \mathbb{R}^m$ be an affine function, i.e., $F (x) = L(x) + b$, with $L : \mathbb{R}^n \rightarrow \mathbb{R}^m$ linear and $b \in \mathbb{R}^m$ Then for every convex ...
1
vote
1answer
139 views

Scale ellipsoid maximally within polyhedron

Given an ellipsoid around the origin with scaling parameter $e$ in the form $x^T E x \leq e$ and a polyhedron $P$ given by $A x \leq b$, how can we define an optimization problem that maximizes e such ...
1
vote
1answer
19 views

Conjectured characterization of a set relative to a convex cone

Let $X\subset \mathbb{R}^N$ be a convex cone (i.e., for all $x,y\in X$ and $\alpha,\beta\geq 0$ scalars, $\alpha x+\beta y\in X$). Define the set $$A(x)=\{a:x+a\in X \wedge x-a\in X\}.$$ Then, ...
1
vote
1answer
41 views

Efficient solution for a quadratic + norm objective.

I want to minimize an objective function of the following form: $$ \begin{split} \text{Minimize} \quad & x^T D_x x + y^T D_y y + z^T D_z z + q_x^T x + q_y^T y + ...
1
vote
1answer
52 views

What does 'the level set is bounded' exactly want to tell?

'The level set is bounded.' occurs in many theorems and other places. I think I can understand the definition of 'level set' but I don't know what does 'it's bounded' want to tell me exactly in ...
1
vote
2answers
99 views

Local optimality of a KKT point.

Consider the problem \begin{equation} \min_x f(x)~~~{\rm s.t.}~~~ g_i(x)\leq 0,~~i=1,\dots,I, \end{equation} where $x$ is the optimization parameter vector, $f(x)$ is the objective function and ...
1
vote
1answer
32 views

Express this linear optimization problem subject to a circular disk as a semidefinite problem.

I have to express following problem as a semidefinite problem: $ min \, F(x,y) = x + y +1$ subject to (1) $(x,y) \in \mathbb{R}^2 : (x-1)^2+y^2\leq 1$ Only affin equality conditions should be used. ...
1
vote
1answer
26 views

Is it right for chain rule in trace function?

The objective function is $$ f(X)=\min_X trace(B^TX^TCXBD) $$ we know the following derivatives from Matrix Cookbook, $$ \frac{\delta{trace(B^TX^TCXB)}}{\delta X}=C^TXBB^T+CXBB^T \\ \frac{\delta ...