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

learn more… | top users | synonyms

3
votes
3answers
906 views

Prove $ax - x\log(x)$ is convex?

How do you prove a function like $ax - x\log(x)$ is convex? The definition doesn't seem to work easily due to the non-linearity of the log function. Any ideas?
1
vote
2answers
156 views

What does the statement “Optimality condition for convex problem” mean? KKT or other condition?

I am stuck to the problem 4 here, course Mat-2.3139, the due day was yesterday. The hint is "Optimality-condition for a convex-problem". I have asked this now from 3 assistants and everyone with ...
0
votes
1answer
138 views

Matrix computations problem: rank, pseudo inverse,…

Suppose we are given two arbitrary $m \times n$ matrices, $A$, $B$, where we know $B$ has full column rank. Let $m>>n$. Can we always find a square $m \times m $ matrix $X$, such that $A=XB$? I ...
0
votes
0answers
148 views

Is positively weighted sum of eigenvalues of a matrix X, convex function of X?

Is positively weighted sum of eigenvalues of a matrix X, convex function of the matrix X?
3
votes
1answer
943 views

Why does a positive definite matrix defines a convex cone?

I've been working on convex optimization and got stuck. What exactly does a positive definite(p.d) matrix represent geometrically ? what kind of vector space it forms ? If I have a p.d matrix which ...
1
vote
1answer
115 views

Convex Combination of Hermitian Matrices

Assume all the matrices I discuss about are $N \times N$. Consider any two hermitian matrices $A_1$ and $A_2$ which are indefinite. The question is, In general, for any $A_1$ and $A_2$, does there ...
2
votes
1answer
140 views

Positive values for a set of quadratic forms of Hermitian Matrices. (To find a set of vectors in which a hermitian matrix is positive definite)

Assume all matrices I discuss about are $N \times N$ and the vectors conform with dimensions. Consider the following set of Quadratic inequalities where all the matrices $A_i$ are hermitian. ...
3
votes
1answer
398 views

Lagrangian Multipliers

I have a fundamental question about Lagrange multipliers. Here it is: I have a function to maximize with respect to a parameter say $\theta$, subject to two constraints. Lets assume that the first ...
0
votes
1answer
27 views

unstable optimizer, stable objective

I am trying to minimize a convex objective numerically using gradient descent. I select the starting point randomly. I repeat the experiment multiple times. The optimal objective value I get each time ...
1
vote
0answers
130 views

Upper bound for L1-L2 optimization problem

I am interested in the following convex optimization problem: \begin{align*} \max & ||x||_1 \\ \text{s.t.} & ||x-a||_1 \le K \\ & ||b\circ x||_2 \le 1\\ & x \in R^n \end{align*} where ...
3
votes
0answers
210 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 ...
0
votes
2answers
41 views

Convexity of a function and constraint

Consider the quadratic function $f(x_1,x_2,x_3,x_4)=x_1+2x_2+4x_4+x_1^2+5x_2^2+3x_3^2x_4^2-4x_1x_2-2x_2x_3+2x_3x_4$. Is f a convex function? Consider a constraint defined using the above function f: ...
2
votes
4answers
339 views

definition of strongly convex

There are several equivalent definitions for strongly convex. For example, some literature said: A function $f$ is strongly convex with modulus $c$ if either of the following holds $$f(\alpha ...
0
votes
1answer
99 views

what math topic is this kind of example part of? or what is needed to understand how to solve it? [closed]

we 100000000 sets/locations. each set has, A = % chance of finding a cure (there are many different types of cures) for cancer B = time it takes to extract a cure to caner C = the optimal % chance (IN ...
1
vote
0answers
94 views

minimum of the function over symmetric body

Let $X$ be a normed space. Let $K$ be centrally symmetric convex body with $M$ known vertices and with $Vol(K)=V$. We subdivide body $K$ be $M$ equal pieces, $P_i, i=1, \ldots, M$, such that each ...
0
votes
1answer
132 views

Parametric Linear Program: Continuous Solution?

Consider the parametric linear problem $$ x^*(\theta) := \min_{Y , \ Z } \left\| Z \right\|_1 $$ $$ \text{sub. to: } \ \theta A + B Y = \theta C Z.$$ where $Y \in \mathbb{R}^{m \times s} $, $Z \in ...
0
votes
2answers
262 views

Numerical optimization with nonlinear equality constraints

A problem that often comes up is minimizing a function $f(x_1,\ldots,x_n)$ under a constraint $g(x_1\ldots,x_n)=0$. In general this problem is very hard. When $f$ is convex and $g$ is affine, there ...
1
vote
2answers
261 views

Gradient of Moreau-Yosida Regularization

Let $f(x):\Re^n\rightarrow \Re$ be a proper and closed convex function. Its Moreau-Yosida regularization is defined as $F(x)=\min_yf(y)+\frac{1}{2}\|y-x\|_2^2$ $Prox_f(x)=\arg\min_y ...
6
votes
4answers
694 views

Why is the affine hull of the unit circle $\mathbb R^2$?

In Boyd's "Convex Optimization" it defines the affine hull of a subset $C$ of $\mathbb R^n$ as $$\text{aff} C = \left\{\theta_1 x_1 + \ldots +\theta_k x_k \mid x_1, \ldots x_k \in C, \theta_1 + ...
0
votes
2answers
329 views

Intuition behind gradient VS curvature

In Newton's method, one computes the gradient of a cost function, (the 'slope') as well as its hessian matrix, (ie, second derivative of the cost function, or 'curvature'). I understand the intuition, ...
4
votes
4answers
528 views

Summary of Optimization Methods.

Context: So in a lot of my self-studies, I come across ways to solve problems that involve optimization of some objective function. (I am coming from signal processing background). Anyway, I seem to ...
0
votes
0answers
126 views

MiniMax Theorem

Consider the compact sets $X \in \mathbb{R}^n$, $Y \in \mathbb{R}^m$, $A \in \mathbb{R}^n$, $M \in \mathbb{R}^{n \times m}$. For fixed $(\bar{a},\bar{B}) \in A \times M$, by the MiniMax Theorem we ...
2
votes
3answers
1k views

Trace of a quadratic function, Convexity

Is trace($XX^T$) a convex function of matrix $X$? A linear function of a quadratic should be convex, but I could not prove by definition.
0
votes
3answers
71 views

Membership based on maximum of a function over the set.

Let $S\subset \mathbb{R}^n$ and let $f(x)$ be a continuous function over $\mathbb{R}^n$. Furthermore, define $s_{\text{max}}:= \sup_{x\in S} \{f(x)\}$ and let $f(x)$ attain its minimum for at least ...
1
vote
1answer
145 views

Equality constrained norm minimization

In these slides (5) the dual function for the norm minimization problem: $$ \min_x \|x\| \quad \mbox{s.t.} \quad Ax =b $$ is defined as: $$ g(v) = \inf_x (\|x\| - ν^\intercal Ax + b^\intercal ν) $$ ...
0
votes
2answers
183 views

distance between a polytope point and a polytope vertex

How to find distance in between any polytope point to the closest vertex of the polytope (the verteces of the polytope are known)? How to find a distance from the farest polytope point to the closest ...
2
votes
1answer
67 views

Is this operator monotone?

Consider a convex optimization problem. $$\min_{u\in\Re^k} f(u)$$ s.t. $g_i(u)\leq0,\ i=1,\ldots,m$ Let ...
0
votes
1answer
107 views

How I can find an optimal solution for a model with concave-convex objective function?

My objective function is sum of three functions, 2 linear functions and a concave function ($1-\exp(x)$); constraints of my model are convex. How can I obtain optimal solution from this problem?
1
vote
1answer
161 views

Is concave quadratic + linear a concave function?

Basic question about convexity/concavity: Is the difference of a concave quadratic function of a matrix $X$ given by f(X) and a linear function l(X), a concave function? i.e, is f(X)-l(X) concave? ...
2
votes
0answers
84 views

How to get the initial ellipsoid in the ellipsoid method for solving optimization problem?

If what I assume is correct, assumption : for a maximization problem, we run a binary search over estimated values, starting with max estimated value, and narrow down to the feasible optimal value ...
0
votes
0answers
98 views

Iterative scheme for a nonlinear optimization problem

Let $\mathbb{PD}_3 \subset \mathbb{R}^{3 \times 3}$ be the set of the positive-definite $3 \times 3$ real matrices. For given $v \in \mathbb{R}^{3 \times 1}$, consider the function $f_v: ...
1
vote
2answers
445 views

LP relaxation for ILP\IP (integer linear programming)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
2
votes
1answer
566 views

Lasso with linear constraints

I want to efficiently solve the following optimization problem: \begin{align} \min &\quad \left\|\mathbf{x}-\mathbf{x}_0\right\|_2^2 + \lambda\left\|\mathbf{x}\right\|_1\\ \text{Subject to}& ...
2
votes
0answers
70 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 ...
1
vote
1answer
367 views

projected gradient method, multiple constraints

I am trying to minimize convex objective $f(X)$, for matrix $X$ s.t. $X\ge 0$ component-wise, and $X1^T = 1^T$. I want to use projected gradient descent. However, I only know how to project on ...
1
vote
1answer
242 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 ...
0
votes
0answers
300 views

Bivariate function maximization

I have a bivariate function like $ f(x,y) = \frac{1}{x^3 \sqrt{\pi}}. e^{\frac{2-x}{x^2}} . y^3 . e^{3.y \over 3-y} $ and I want to find its global maximum over a range of $ x \in [0, 200] \text{, ...
0
votes
2answers
176 views

Simple example where strong convexity is necessary over strict (or even regular) convexity.

I am trying to get a hold on exactly what strong convexity gives you over strict (or regular) convexity. Yes there are simple functions which demonstrate the difference between these ideas, but what ...
1
vote
1answer
25 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 ...
3
votes
1answer
276 views

Solving Linearly Constrained Quadratic Programming with Coordinate Descent

Does anybody have any idea about how to solve the following problem with Coordinate Descent? \begin{align} \min &\quad \mathbf{x}^{\top}P\mathbf{x} + b^{\top}\mathbf{x}\\ \text{Subject to}& ...
3
votes
1answer
282 views

Going in the direction of the gradient

First, a motivating example. Suppose $f(x)$ is convex, differentiable, with a single minimum $x^*$. Then the differential equation $$\dot{x}(t) = -\nabla f(x(t))$$ drives $x(t)$ to $x^*$. Now my ...
0
votes
1answer
45 views

Degeneracy of the analytic center of a set of linear inequalities

I have a question about the degeneracy of the analytic center of a set of linear inequalities. When the set of linear inequalities is degenerate, I guess that the analytic center would also be ...
3
votes
1answer
56 views

Convex programming when the problem has an underlying combinatorial structure that's a DAG

I have a nonlinear convex objective function to minimize. The function is defined on a set of variables: $\{ x_1,x_2, \ldots ,x_p \},$ where each $x_i$ is a number associated with a path in the DAG. ...
1
vote
0answers
163 views

Efficient Algorithm For Projection Onto A Convex Set

Given $\mathbf{x} \in \mathbb{R}^n$ and $\tau$ a scalar, I would like to solve the following Euclidean projection problem: $\underset{p}{\mathrm{argmin}} \; \|\mathbf{p}-\mathbf{x}\|_2 \;\; ...
1
vote
2answers
171 views

Entropy expression optimization with Langrange multipliers

I have recently encountered variants of the following expression: \begin{equation} S = H(a,b,c,d)-H(a+b,c+d) \end{equation} where $H$ is the Shannon entropy function, that is $H(X)=\sum_{x\in X}-x\log ...
1
vote
2answers
550 views

Null space of a matrix

I was referring to this lecture http://www.stanford.edu/class/ee364a/videos/video05.html (about 0:38:10) related to convex optimization and for optimization it had a certain affine function equality ...
13
votes
4answers
6k views

Difference between supremum and maximum

Referring to this lecture , I want to know what is the difference between supremum and maximum. It looks same as far as the lecture is concerned when it explains pointwise supremum and pointwise ...
0
votes
3answers
198 views

Confusion regarding convexity of a function

I was reading this lecture on convex functions and I came across this $f\colon \Bbb R^n\to \Bbb R$ is convex if and only if the function $g\colon \Bbb R\to \Bbb R$, $g(t) = f(x+tv)$, ...
1
vote
0answers
232 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 ...
0
votes
2answers
865 views

How can I know this simple quadratic function is a convex function?

Sorry.I don't know enough about convex optimization. How can I know this function for the $\theta$ vector $(\theta_0+\theta_1x_1+\theta_2x_2-y_0)^2$ is a convex function? The other variables are ...