Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

0
votes
1answer
17 views

multi objective optimization

Suppose we want to maximize two positive bounded objectives. A usual approach for this aim is to maximize a weighted sum of these two objectives. Now, my question is why not to maximize the product ...
2
votes
0answers
41 views

How does one evaluate the derivative of a matrix with a tensor $\frac{\partial \operatorname{Tr}[A(\mathrm{Id}\otimes w)]}{\partial w}$?

I am stuck on the following: $$\frac{\partial \operatorname{Tr}[A(\mathrm{Id}\otimes w)]}{\partial w}=\text{ ?}$$ with $A$ a $d\times d^2$ matrix, $\mathrm{Id}$ the identity matrix of $d\times d$ ...
2
votes
1answer
42 views

binary quadratic optimization problem

I am trying to solve the following binary quadratic program. $$ \min_{\Delta} \Delta^T H \Delta + c^T\Delta \\ \text{Such that:} ~~~\Delta\in \{0,1\}^n ~~\text{and}~~ \sum_{i=1}^n \Delta_i \leq \Gamma ...
6
votes
3answers
82 views

Optimal approximation of quadratic form

Let $\mathbf{x}\in\Bbb{R}^n$ and $A\in\Bbb{S}_{++}^n$, where $\Bbb{S}_{++}^n$ denotes the space of symmetric positive definite $n\times n$ real matrices. Also, let $Q\colon\Bbb{R}^n\to\Bbb{R}_{+}$ be ...
2
votes
1answer
36 views

If $H$ is positive definite and $s^Ty>0$, then $s^THs-\frac{s^Tyy^Ts}{s^Ty+y^TH^{-1}y}\ne -1$

Let $H\in\mathbb{R}^{n\times n}$ be symmetric and positive definite $s,y\in\mathbb{R}^n$ with $s^Ty>0$ How can we show, that $$s^THs-\frac{s^Tyy^Ts}{s^Ty+y^TH^{-1}y}\ne -1\;?\tag{1}$$ ...
3
votes
1answer
51 views

Minimizing Area by Approximation

Suppose I have an increasing step function $E_c$ given by $$E_c(\phi) = \sum_{i=1}^n E_i \theta(\phi - \phi_i),$$ where $\theta$ is the Heaviside step function and $E_i$, $\phi$, and $\phi_i$ are all ...
0
votes
1answer
20 views

Maximization of quadratic form over complex unit cube

I am trying to find the maximum of a hermitian positive definite quadratic form $xQx^H$ (where $Q=Q^H$ and all eigenvalues of $Q$ are non-negative) over the complex unit cube $|x_i|\leq 1$, ...
1
vote
0answers
31 views

Coin distribution problem to optimize

There are $N$ users, with each user having a money request. There are $T$ coins, these coins are to be assigned to the user in such a way that its request is fulfilled. Assume each coin may have ...
0
votes
0answers
11 views

Prove that if $e \in \left ( S\to \overline S \right )$ when $\left ( S, \overline S \right )$ is a min-cut, then $f(e) = c(e)$

Given a min-cut $\left( S, \overline S \right )$, we define $\left ( S\to \overline S\right ) =\{\left (u\to v\right )|u \in S, v\in \overline S\}$ and $\left ( \overline S \to S \right )$ similarly. ...
0
votes
0answers
13 views

For which values of $c_1, c_2$ and $c_3$ is (1, 2, -2) a local minimum

Consider the problem $$\left\{\begin{matrix} \min & x^2 -2xy + 2xz +y^2 + 4yz + z^2 + c_1x + c_2y + c_3z \\ s.t & g(x,y,z)=-x^2 -4xy - 4xz -2y^2 -4yz - 2z^2 + x -y+z+4 =0 \\ \; & ...
0
votes
1answer
52 views

Minimal area of triangle

We have the points $A(2, 3-m), B(m+2, -1)$ and $C(m, 2-m)$. Where $m$ is a real number. Find $m$ for which the area of triangle $ABC$ is minimal. So I've tried to find the equation of line $BC$(the ...
0
votes
1answer
14 views

Constrained Optimization: $\min x_1$

Consider the problem $$\left\{\begin{matrix}\min & x_1 \\ s.t & x_2 \geq 0 \\ \; & x_2 \leq x_1^3 \end{matrix}\right.$$ It is asked to find the minimum and show why this does not satisfy ...
2
votes
4answers
86 views

Minimization on compact region

I need to solve the minimization problem $$\begin{matrix} \min & x^2 + 2y^2 + 3z^2 \\ subject\;to & x^2 + y^2 + z^2 =1\\ \; & x+y+z=0 \end{matrix}$$ I was trying to verify the first ...
0
votes
0answers
7 views

Gomory's cut typical running time until the constraint is fractional

I was considering the following problem. Say we are given an linear programming problem $$ \max c^Tx $$ $$ Ax \le b $$ $$ x \ge 0$$ Where instead I consider $i^{th}$ the optimal solution $X_i$ of ...
0
votes
0answers
11 views

what is the dual problem of finding chebyshev's center?

let $a_j$ $(j=1,...,m)$ be a set of points in $R^2$. The problem of finding Chebyshev's center is: min r s.t. $norm(x-a_j)<=r$ $(j=1,...,m)$ Where r is the maximal radius and x is the center ...
0
votes
0answers
16 views

Convex signal reconstruction for convex generator function?

Let $f : \mathbb{R} \mapsto \mathbb{R}$ be a convex (not affine) function and suppose that $y = f(x)$. We want to reconstruct the input $x$ for a given $y$, and the standard approach would be to ...
6
votes
2answers
141 views

Find the minimum value of $A=\frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{2-c^3}{c}$

Let $a, b$ and $c$ three positive real numbers such that $a+b+c=3$. Find the minimum value of $$A=\frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{2-c^3}{c}.$$ Here is my attempt. By symmetry we can assume that ...
1
vote
0answers
23 views

Is there only one set of KKT conditions for a given optimization problem?

Consider an optimization problem $$ \begin{align} \max_{x}&\quad f(x)\\ \nonumber \text{subject to } \quad & g_i(x) \le0,\,i=1,\ldots,m\\ \quad & h_j(x)=0,\,j=1,\ldots,l\\ \end{align} $$ ...
0
votes
0answers
12 views

How to optimize a generalized trace problem in dimensionality reduction

I know how to solve this problem in dimensionality reduction. $argmax_{X}$ $Trace[XLX^T]$ with $XX^T=I$ ,where $L$ is symmetric, $X$ is unitary, and $I$ is identity matrix. But I'd like to know how ...
1
vote
0answers
16 views

closed form solution to best invertible matrix which minimizes product

Let $U, X \in \mathbb{R}^{n_1 \times r}$ and let $V, Y \in \mathbb{R}^{n_2 \times r}$. Consider the optimization problem $$ \begin{align*} \min_{A, B, \Sigma \in \mathbb{R}^{r \times r}} \left\{ \| ...
-1
votes
2answers
18 views

Determine vector which maximizes the given function

Determine vector x $\in R^3$ with $\|x\|^2=x^Tx=1$ which maximizes the function below $$ f(x) = 2x_1^2 +2x_2^2-x_3^2+2x_1x_2$$ If someone can show me how to tackle this problem then I have at least ...
2
votes
1answer
135 views

If $a,b,c>0, a+b+c=3$, minimize $\frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{3-c^3}{c}$ [duplicate]

Let $a,b,c$ be positive real numbers such that $a+b+c=3$. Find the minimum value of the expression $A= \frac{2-a^3}{a}+\frac{2-b^3}{b}+\frac{3-c^3}{c}$ I tried solving it, but I got nothing
0
votes
0answers
26 views

Will the result of this maximization problem be the same for the two considered cases?

Suppose I have $2$ options: option1 and option2. For each option we associate a quantity $q$ that changes each time $t$, namely $q_1(t)$ and $q_2(t)$. Let $\mathbf{q}=(q_1(t),q_2(t))$. The different ...
2
votes
1answer
17 views

Proving that a local maximum of a given bounded function is global.

I am studying a certain maximisation problem (coming from some sort of likelyhood estimations); after a number of generalisations I need to examine $$f(x_1, x_2,y) = a_1\ln x_1 +a_2 \ln x_2 + \ln y - ...
0
votes
0answers
25 views

Approximate inverse (or fast optimization) of non-linear least squares problem

Problem Statement Let ${\bf x}\in\mathbb{R}^N$ and ${\bf W}\in\mathbb{R}^{K\times N}$, ${\bf V}\in\mathbb{R}^{N\times K}$. We define $${\bf y} = f({\bf x}) = [{\bf V}[{\bf Wx}]_+]_+$$ where $[.]_+ = ...
0
votes
1answer
15 views

How to optimally cut kitchen worktops (countertops) from slabs of material

Given a number N of rectangular kitchen worktops, of variable dimensions to be cut from slabs of material of fixed dimensions Determine an optimal fit to minimise wastage and number of slabs used. ...
0
votes
0answers
29 views

Convex envelopes of bivariate functions

In order to convexify my nonlinear non-convex program I need convex envelopes for the function $(x/y)^2$, both x,y are positive. I am only aware of the convex envelopes of the type $xy$ from here ...
1
vote
1answer
30 views

Multivariable optimization- Nature of critical points when det of hessian matrix = 0

I'm struggling a bit with my multivariable optimization. Assuming the determinant of the hessian matrix ≠ 0 I have no issue, though when the det = 0 I get stumped. Example- $$f(x,y)=x^4+y^4-(x+y)^2$$ ...
0
votes
2answers
37 views

Optimization Problem: Fence with adjacent sides rather than opposing sides

I'm unsure if I got the following right on a test I just took: A farmer wants to build a rectangular fence using both wood and metal and wants adjacent sides to be of the same material. Metal costs ...
2
votes
1answer
202 views

Regarding Nesterov's smooth minimization

I am currently studying this Nesterov's paper for project purposes, and I am trying to figure out how the smoothing and the minimization algorithm works I have tried looking at the example ...
0
votes
1answer
41 views

Minimization involving equality constraints

I am trying to find closed form solution to following problem \begin{equation} \begin{array}{c} \underset{\mathbf{x},\mathbf{y}}{\text{minimize}} \hspace{4mm} \big(\left( \mathbf{y}^T ...
1
vote
1answer
30 views

The optimal function value in linear programming has analytic solution

Consider the following linear programming problem: $\min c'x$ subject to $Ax=b$ and $x\geq0$, where $A$ is $m\times n$ with rank$A=m$. The dual is $\max -b'v$ subject to $A'v+c=\lambda$ and ...
1
vote
1answer
40 views

Optimizing a function of a matrix

Let \begin{equation} \begin{aligned} W= & \underset{X}{\mathrm{maximize}} & & \log \left|X + K_1\right|- \alpha \log \left|X + K_2\right|\\ & \mathrm{subject \; to} & & 0 ...
1
vote
3answers
89 views

Maximize the following sum

Let $a, b, c, d, e$ be nonnegative integers such that $625a + 250b + 100c + 40d + 16e = 15^3$ . What is the maximum possible value of $a + b + c + d + e$? Quick arithmetic gives: ...
2
votes
2answers
50 views

How to determine a function of a matrix is increasing or decreasing

We know that the derivative of a function can be used to determine whether the function is increasing or decreasing on any intervals in its domain. If $f'(x) > 0 $ at certain interval I, then the ...
2
votes
5answers
466 views

Find the maximum possible area of a certain right triangle

I want to find the maximum possible area of a right triangle with hypotenuse $=10$. My approach so far: let $x,y$ be the lengths of the two sides adjacent to the right angle; then $$100=x^2+y^2$$ ...
0
votes
1answer
24 views

Functional Lifting in Optimisation - Reference Request

I'm looking to learn about the use of (functional) lifting applied to a non-convex optimisation problem to give a (larger) convex problem. Unfortunately, I'm having a great deal of trouble finding ...
1
vote
0answers
48 views

Minimizing the max function

Suppose we have the single-variable function $$f(x) = \max_k \{f_k(x)\}$$ where each $f_k$ is convex and smooth (and known beforehand). We want to minimize it over some bounded interval. We can, in ...
0
votes
1answer
55 views

Optimization problem in flight scheduling

I found this question here The question is I wrote the LP problem as this: Let $x_{ij}$ be the maximum no.of flights between city i and city j. Let $a_0$ be the artificial link and $x_0$ be the ...
2
votes
1answer
30 views

optimization network models

This is a question from Wane Winston 's Book. I don't understand how to do this. I tried to do it this way but it doesn't seem to work. Let $C_{ij}$ be the cost of using box of i $ i>=j$ Then ...
0
votes
0answers
23 views

strengths and weaknesses of analytical method

I was wondering if anyone could suggest any books or paper that explain/discuss the advantages and drawbacks of analytical methods for optimization. Also, if we have a convex objective function ...
0
votes
0answers
35 views

What does $\frac{d^k h}{dx^k}$ mean in the context of vectors and regularization in machine learning?

I was watching a machine learning videos from the caltech course CS 156 and they have a slide where they talk about how radial basis functions (RBFs) can be derived from the following variational ...
1
vote
3answers
36 views

Finding extrema.

Find the minimum distance between point $M(0,-2)$ and points $(x,y)$ such that: $y=\frac{16}{\sqrt{3}\,x^{3}}-2$ for $x>0$ . I used the formula for distance between two points in a plane to get: ...
1
vote
1answer
22 views

Complexity of finding M nodes in a graph to maximize the pairwise minimum distance between nodes

I want to know the complexity of finding a set of M nodes, $\{U_1,\dots,U_M\}$, in a given graph $G$, to maximize $d(U_i,U_j)$ over all pairs $i\neq j$, where $d(\cdot,\cdot)$ is the length of the ...
1
vote
1answer
32 views

Find min/max values of $f(x,y)=x^3-y^3+3xy$ in the set $K=[0,4]\times[-4,0]$

Find the biggest and the smallest values of the function $f(x,y)=x^3-y^3+3xy$ in the set $K=[0,4]\times[-4,0]$. So using partial derivatives we find that the critical points are $(0,0)$ and $(1,-1)$. ...
0
votes
0answers
33 views

Expected probability maximization with binomial distribution

I need to solve an optimization problem that involves an expected value like $$F(n,x) = \sum_{k=0}^n \binom{n}{k} p^k(1 - p)^{n - k} f(k,x).$$ Here $f(k,x)$ is actually a probability coming from a ...
0
votes
0answers
26 views

Estimate Beam and Ball Problem System Parameters

I'm trying to estimate the parameters of beam and ball problem model. In the problem we have output as ball position and input as gear rotation angle. The issue that i want to ask is that our ...
0
votes
3answers
39 views

What algorithm will maximize utility when assigning of students to practicum locations

I have the following problem: Students from a class of 150 are beginning practicum training. Students have the option of either staying in an urban centre for their practicum, or optionally, they ...
0
votes
1answer
48 views

Let $S = \{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. Prove $(1-\lambda)x + \lambda y \in S$ for $x=\lambda'y$, $\lambda' < 0$.

Let $S = \{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. I've verified that $x,y \in S$ implies $(1-\lambda)x + \lambda y \in S$ when $x,y$ are linearly independent using Pythagoras and when ...
0
votes
1answer
18 views

Compute the extreme points of a polyhedron $P$ and write $(1/2,1/2,1/2)$ as a linear combination of these.

Compute the extreme points of a polyhedron $P$ and write $(1/2,1/2,1/2)$ as a linear combination of these. I want to compute all the extreme points of the set $P$ (polyhedron) in $\mathbb R^3$ ...