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

learn more… | top users | synonyms

1
vote
2answers
23 views

Easier way of finding out whether a given linear programming problem has optimal solution or not

I have the linear program $$\begin{array}{ll} \text{minimize} & -2x-5y\\ \text{subject to} & 3x + 4y \geq 5\\ & x, y \geq 0\end{array}$$ I can solve it using Simplex algorithm, but I ...
1
vote
0answers
19 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 ...
1
vote
2answers
601 views

Convex Optimization of quadratic function with inequality constraints

How would I solve the following problem? $$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$ where A is positive semidefinite and symmetric. Is it possible to ...
1
vote
1answer
46 views

Optimization problem: $\min \limits_{\mathbf{q}} \sum_{n=1}^N q_n$, s.t. $\frac{c_{nn} q_n }{\sum_{m \ne n} c_{nm} q_m } \ge a$

\begin{array}{rl} \min \limits_{\mathbf{q}} & \sum_{n=1}^N q_n \\ \mbox{s.t.} & \frac{c_{nn} q_n }{\sum_{m \ne n} c_{nm} q_m } \ge a, \forall n \in \{1,\ldots,N\} \end{array} For this ...
1
vote
0answers
16 views

Can Extragradient method be expressed with proximal steps?

As we know, for solving saddle point problems, forward-backward algorithm is generally not guaranteed to converge. But extragradient method converge Structured Prediction via the Extragradient Method ...
0
votes
0answers
22 views

Global maximum for constrained optimization of concave function

Suppose I maximize function $x_{1}-f(x_{2})$ where $f$ is strictly convex so $\frac{df}{dx}>0, \frac{d^2f}{d^2x}>0$. Also here is a set of linear constraints in a form $g(x_{1},x_{2})\leq0, ...
0
votes
1answer
31 views

Convex function and convex optimization

I would like to ask something about convex function and convex model. For example, the function $f(x,y)=\frac{x^2}{y}$ is convex when $x\geqslant0$ and $y>0$. For a convex model (minimization), ...
0
votes
0answers
32 views

SVM optimality criterion in Bottou, Lin (2006)

My question relates to an alternative optimality criterion for an SVM dual solution derived in Bottou, Lin (2006) in pages 8 and 9. Let: $\alpha^* = (\alpha_1^*,\dots,\alpha_n^*)$ be a dual ...
0
votes
0answers
36 views

Conditions for all positive $x$ solved by $\min \bf{x}^T\bf{x}$ $s.t. Ax=b$

I want to find a condition for having all nonnegative $x_i$ in $\min \bf{x}^T\bf{x}$ $s.t. \bf{Ax}=\bf{b}$ where $\bf{x}\in \mathbb{R}^{n\times 1}$, $\bf{A}\in \mathbb{R}^{m\times n}$, $\bf{b}\in ...
-1
votes
0answers
24 views

how to minimize huber loss? (SVM related) [closed]

I don't know how to minimize huber loss which is convex and continuous, but how can I minimize that? Can I express it in only one ojective function and obtain its dual problem? My object is to ...
0
votes
1answer
18 views

Closure of intersection of convex sets

Let $C_i$ be a convex set in $R^n$ for $i\in I$, suppose sets $ri \, C_i$ have at least one point in common, then how to prove this: $cl\bigcap\{C_i\mid i\in I\} = \bigcap\{cl \, C_i \mid i\in I\}$
0
votes
1answer
57 views

Product of the differences of two pd matrices and their respective inverses is pd

Given two $\textbf{positive definite (pd), Hermitian}$ matrices X and Y, I am trying to determine whether $(X-Y)(Y^{-1}-X^{-1})$ will always be pd as well, and how to prove this. This formulation ...
2
votes
1answer
25 views

Existence of direction for polyhedral set

I refer to Lemma 4.42 of this lecture notes on linear programming, about the relationship between the boundedness of a polyhedral set and its directions. Let $P$ be a non-empty polyhedral set. ...
0
votes
0answers
25 views

Stability of a semidefinite programming problem

For the minimum trace factor analysis problem, I want to prove that if I change a parameter in the optimization problem, the solution will be stable. Let $\mathbf{D}^p$ denote the set of $p \times ...
2
votes
1answer
34 views

Non-convex QCQP

Consider the following optimization problem: $$\begin{array}{ll} \text{minimize} & \mathbf{x}^{T} \mathbf{A} \mathbf{x}\\ \text{subject to } & \mathbf{x}^{T} \mathbf{P}_i \mathbf{x} > 0, ...
-1
votes
0answers
10 views

Difference between mirror descent and dual averaging [closed]

What is the main differences between mirror descent and dual averaging methods? When the number of steps or accuracy are fixed, they are equivalent. But what can be said when these parameters are not ...
3
votes
2answers
277 views

Prove $\exists\bar{b}$ s.t. every solution in polyhedron $P = \{x | Ax \ge \bar{b}\}$ is nondegenerate

I'm doing an exercise in the book "Introduction to Linear Optimization" and be stuck in this problem. Can anyone here help me solve this. I really appreciate all your help. Consider a ...
0
votes
1answer
45 views

Is the set of probability density functions convex?

Given is the set of probability density functions defined as $P:=\left \{ p(x)\mid p(x)\, is\ a\ probability \ density \ function \right \}$ Is $P$ a convex set? I am not sure that here i have to ...
1
vote
1answer
39 views

How to get explicit solution of the fractional minimization problem?

I need to minimize $f(x) = \frac{x^tQx}{a^tx-b}$, $Q$ is positive definite, $a,b$ are constant vector. But when I take gradient and set it equal to $0$, it's hard to get an explicit expression for ...
2
votes
1answer
29 views

Solving a quadratic convex optimization problem

There's this convex optimization problem which I got stuck after writing the Lagrange equation. I simply couldn't find a way to eliminate the Lagrange multiplier. $$\begin{array}{ll} \text{minimize} ...
0
votes
0answers
13 views

References to: If $C\subset\mathbb{R}^n$ is convex and $0\notin C$ then there exists $v\in C$ such that $C$ is in the closed halfspace $H_v$.

For each $v\in\mathbb{R}^n$, we define the notation $H_v=\{u\in\mathbb{R}^n:\langle u,v\rangle\geq0\}$, where $\langle\cdot,\cdot\rangle$ denotes the usual inner product in $\mathbb{R}^n$. Recently, ...
1
vote
0answers
37 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 & ...
2
votes
1answer
543 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
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 ...
0
votes
1answer
20 views

To what extent can the column generation method for solving linear programs be extended to solving more general convex optimization problems?

Are there column generation approaches to solving classes of convex optimization problems other than LPs, and are they guaranteed to find a global minimizer?
14
votes
3answers
865 views

If the Minkowski sum of two convex closed sets is a Euclidean ball, then can the two sets be anything other than Euclidean balls?

If for two convex closed sets $S_1$ and $S_2$, the Minkowski sum is a Euclidean ball then can $S_1$ and $S_2$ be anything other than Euclidean balls themselves. I suspect they can be but I haven't ...
1
vote
1answer
22 views

Property of Conical Hull

Let $H$ be a real Hilbert space and $C$ be a nonempty convex subset of $H$. The conical hull of $C$ is defined by $$ \operatorname{cone}{C} := \bigcup_{\lambda >0}{\lambda C}. $$ (it is a cone in ...
5
votes
3answers
466 views

Shortest distance between two lines in 3-dimensional space [closed]

Can someone explain to me how to solve this question? Find the shortest distance between the lines $L_1 = \left\{t \begin{bmatrix} 1\\ 1\\ 1\end{bmatrix} : t \in \mathbb{R}\right\}$ and $L_2 = ...
0
votes
0answers
15 views

subdifferential of $\max_{i=1,\cdots,k} x_i+\frac{1}{2}\|x\|_2^2,\ \ \ x\in \mathbb{R}^n$

How to find the subdifferential of $$f(x) = \max_{i=1,\cdots,k} x_i+\frac{1}{2}\|x\|_2^2,\ \ \ x\in \mathbb{R}^n$$ My derivation is: $\nabla \frac{1}{2}\|x\|_2^2=\nabla \frac{1}{2}x^Tx=x$ ...
1
vote
0answers
37 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)$ - ...
0
votes
0answers
16 views

Diagonal Newton's method for unconstrained optimisation.

Assume you are minimising a convex function $f$. The function is twice-differentiable. The well-known Newton's method consists in starting form some point $x_0$ and then using the iteration below. $$ ...
3
votes
1answer
822 views

Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate and unique.

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate and unique? What I tried: Let the primal be $$\max z=cx$$ subject to $$Ax ...
0
votes
0answers
18 views

Solving optimization problem where objective function is of type (affine+(affine/affine))

I need to solve a non linear optimization of the form minimize $f(x) +\frac{g(x)}{h(x)}$ subject to $p(x)\leq0$ $q(x)=0$ Here $f,g,h,p,q$ are affine functions of $x$ and they are convex in the ...
0
votes
0answers
7 views

Deriving a minimizer involving proximal operator

The following are from this thesis http://gpu4vision.icg.tugraz.at/papers/2012/werlberger_phd.pdf I have a difficulty understanding the lines: For example, (4.38) seems very weird to me. I think ...
0
votes
0answers
23 views

Converges extremely slowly, using Douglas-Rachford splitting, how to improve?

my problem looks like this: $\min _{ E,A }{ { \lambda }_{ 1 }{ \left\| E \right\| }_{ 1 }+{ { \lambda }_{ 2 }\left\| A \right\| }_{ * }+{ \left\| D-ME-A \right\| }_{ 2 }^{ 2 } } $ the M is a ...
1
vote
0answers
35 views

Proving function is convex argmin

How can I show that the following function is convex in which Z is a random variable? $$\rho(Z)=\frac{2}{3}argmin_{t}\{t+10\mathbf{E}[Z-t]_{+}\}+\frac{1}{3}argmin_{t}\{t+5\mathbf{E}[Z-t]_{+}\}$$ I ...
0
votes
0answers
13 views

Convex solver returns disordered dual variables, how to re-order?

I have the following convex optimization problem: $$ \begin{align*} \min_{x} &f(x) \\ \text{subject to} \\ x_{k+1} &= x_k+\cdots\qquad k=0,1,2,\ldots,N-1 \end{align*} $$ I managed to solve ...
5
votes
2answers
99 views

Equivalent characterizations of the dual norm on finite dimensional vector spaces

In their book on Convex Optimization, Boyd and Vandenberghe state that given a norm, $||\cdot||$, defined on $\mathbb{R}^n$, the dual norm is defined as $$||z||_*= \sup \{ z^Tx : ||x|| \leq 1 \}$$ ...
0
votes
0answers
18 views

How you can model the other players replies in a game theoretic model?

In a game theory field, the payoff function of a player n is basically a function of the other players responses which are considered as constants. I'm trying to solve the maximization of the payoff ...
0
votes
1answer
20 views

Has $\max\{cx:Ax\le b\}$ an optimal solution $x_1=\sqrt 2$ with $A\in \{-1,0,1\}^{m*n}$ with exactly one $1$ and one $-1$?

Let be $A\in \{-1,0,1\}^{m*n}$ with exactly one $1$ and one $-1$ and zeroes at each line. $c\in\mathbb{Z}^n$ such that $\sum\limits_{j=1}^{j=n}c_j=0$. $b\in\mathbb{Z}^m$ positive. How to start to ...
0
votes
0answers
56 views

Do corner points optimise a linear function over a bounded convex region?

This proof says if $Z_P \ne Z_Q$... ...then $Z$ is maximised (or minimised, I guess) at one of the $\color{red}{\text{endpoints}}$ -- of what exactly? $\overline{PQ}$? So the maximum value of ...
0
votes
0answers
37 views

Weights in goal programming

I'm not quite convinced about assigning weights in goal programming. Here is an example formulation problem. What I tried: Let $x_j$ be the number of minutes for ad $j = R, T$ We want to ...
0
votes
1answer
17 views

Why the dual and the canonical dual may have the same optimal solution?

For instance let be \begin{cases} \max & 3x_1 &+2x_2 &+4x_3 & -x_4\\ &x_1 &+x_2 &-2x_3&&\le4\\ &2x_1&+3x_3&&-4x_4&\ge 5\\ ...
1
vote
1answer
35 views

Converting generic linear problems into their dual

I'm revising how to do dual problems in linear algebra. I'm very weak in Linear programing but I struggle to cope with the topic during lectures and assignements. I have to convert the following ...
0
votes
0answers
54 views

Yale College's Housing Draw Problem — Convex optimization techniques on a modified stable marriage problem?

I'd like to run various optimization techniques on this variation of the stable marriage problem I formulated. Ideally, I'd be able to convert the problem I constructed into one that is more ...
0
votes
1answer
36 views

A Question On Triple Integration

Can anyone construct a nonzero continuous function $f:[0, 1]\times[0, 1]\times [0, 1]\rightarrow [0, \infty)$ such that \begin{equation*} \int_{t_1=0}^1 \int_{t_2=0}^1 \int_{t_3=0}^1 f(t_1, t_2, ...
1
vote
1answer
997 views

convex hull function in matlab

Is there any way to compute the convex hull of a finite set of points in Matlab and gives the half-space representation as its result? I usually use a toolbox called MPT developed at ETHZ Zurich, but ...
5
votes
1answer
82 views

Why is the Barycenter operation in Hadamard spaces Lipschitz continuous?

I am looking into exercise 9.2.22 of "A course in metric geometry" by Burago-Burago-Ivanov. For a Hadamard space $H$ (a complete simply connected metric space of nonpositive curvature in the ...
1
vote
1answer
20 views

Can geometric programs be solved more efficiently than general convex optimization problems?

I want to solve an optimization problem for which I have already proven that it is feasible and convex. Introducing further variables and considering a special case of the problem, I can formulate it ...
1
vote
1answer
38 views

piecewise linear minimization equivalent to linear programming

Why is \begin{equation} \begin{aligned} & \min\max_{i=1,\ldots,n} & &a_i^Tx+b_i\\ \end{aligned} \end{equation} equivalent to an LP \begin{equation} \begin{aligned} & \min & ...