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)

3
votes
0answers
18 views

Bounding a function of norms on the unit cube

For a vector $v \in [0,1]^n$ and $p > 1$ we denote the p-norm of $v$ as: $||v||_p = (\sum_iv_i^p)^{\frac{1}{p}}$. where $v_i$ are the entries of $v$. Define the following (weird looking) function ...
0
votes
0answers
8 views

Approximation of logistic function

Given the function: \begin{eqnarray} y=\frac{1}{1+\exp(-\sum_j w_j x_j-b)}. \end{eqnarray} How could I work out this approximation: \begin{eqnarray} \Delta \mbox{y} \approx \sum_j ...
0
votes
1answer
24 views

How to maximize a product of integers?

I have been given a positive integer $B$. How can I find a positive integer $k$ and positive integers $n_1,n_2,\ldots,n_k$ such that $\sum_{i=1}^k n_i=B$ and $\prod_{i=1}^k n_i$ is as large as ...
0
votes
1answer
9 views

Monotonic optimal value function

Are there any theorems/sufficient conditions about when the optimal value function of a parametrized optimization problem is monotonic in the parameter? Specifically, are there simple conditions ...
3
votes
3answers
52 views

Show that among all quadrilaterals of a given perimeter the square has the largest area

Show that among all quadrilaterals of a given perimeter the square has the largest area. By Ptolemy's theorem we have that if $a,b,c,d$ are the side lengths of the quadrilateral then $ac+bd \geq ...
2
votes
0answers
12 views

Can the non-uniqueness of a linear program's dual feasible set be exploited?

I was originally under the impression that a primal LP had a single corresponding dual feasible set. However, it is possible to alter the primal to an algebraically equivalent form which has a ...
1
vote
0answers
11 views

Which one is better to minimize SSE or MSE in ADMM?

I am minimizing the following ERM objective function. \begin{equation} \sum_i^m \ell(w;x_i,y_i) + r(w) \end{equation} within ADMM framework. ADMM convergence takes a long time (primal and dual ...
0
votes
0answers
14 views

Efficiency of quasiconvex optimization

Summary: Could we minimize quasiconvex objectives in polynomial time? Whenever an objective function of an optimization problem can be formed as a convex function, this is considered as victory. ...
1
vote
0answers
17 views

Relation between error of estimate and rate of convergence

How is bounds on estimated error of an iterative algorithm related to rate of convergence? Referring to references is appreciated.
1
vote
1answer
48 views

Prove that the following function has a unique maximum?

I was working on a problem and reduced it to showing $$f(\alpha)=n\ln \alpha-\ln \left(\sum_{i=1}^n t_i^\alpha+\int_a^b x^{\alpha+\beta-1} e^{-\lambda x^\beta} \, dx \right) + (\alpha-1)\sum_{i=1}^n ...
1
vote
1answer
35 views

Find minimum number of coins with Largest value coins?

There is a greedy algorithm for coin change problem : using most valuable coin as possible. How We can find a quick method to see which of following sets of coin values this algoithms cannot find ...
0
votes
0answers
24 views

For any integer $n$ find $x<n$, and $y<n$ to minimize the natural number $z=xy-n$

I need to develop an algorithm for finding the optimal dimensions for setting a set of symbols on a grid (for a typesetting library I'm writing). I need to minimize the number of cells in my grid ...
1
vote
1answer
20 views

Maximizing symmetric functions on the unit cube

Let $f:[0,1]^n \to \mathbb{R}$. We say that $f$ is symmetric, if for every permutation $\sigma \in S_n$ and every $(x_1,..,x_n) \in [0,1]^n$ we have that $$f(x_1,..,x_n) = ...
3
votes
2answers
63 views

Turn off the ovens! An optimization problem

The problem is more abstract, but can be illustrated nicely using ovens. A oven can produce any heat, but is most efficient when it produces $c$ heat. The inefficency increases quadratically as one ...
0
votes
0answers
14 views

convex optimization with multiple nonsmooth terms

Is there a general algorithm for solving $$ \min f(x) + g(x) + h(x) $$ where all three functions are convex and proximable, $f(x)$ is smooth, and $g(x)$ and $h(x)$ are both nonsmooth? Note that if ...
0
votes
2answers
40 views

Maximize the function $x+y$ on the closure of the unit ball

Find the maximum of $\{x +y : (x,y) \in closure [B(0,1)] \}$. Here $B(0,1)=\{(x,y) \in \mathbb{R}^2 : x^2+y^2 \leq 1\}$ I can't proceed in this as to how to maximize this value. Will it lie on ...
0
votes
1answer
21 views

Maximum hyperrectangle

Is there a way to determine the coordinates of the maximum hyper-rectangle in n-D space subject to linear constraints and $x_i\ge0$ ? Example: Argument Maximum of $x_1 x_2 x_3$ Given ...
0
votes
0answers
14 views

Designing an aggregate weighted cost function

In my undergraduate thesis, I am trying to solve a problem which finds an optimal POI (e.g. a restaurant) for a group of users. Each user $q_i$ is assigned a cost $c_{ij}$ with respect to a POI $o_j$. ...
0
votes
0answers
17 views

Travelling Salesperson MTZ

I have been solving a $10$ city travelling salesperson problem. Having solved the assignment based relaxation problem, I have $5$ subtours: $1 \rightarrow 10 \rightarrow 1$ $2 \rightarrow 8 ...
1
vote
0answers
13 views

Estimation of binomial probabilities $f(r)$ over $r \in [0,\frac{1}{2}]$

I want to fit a (decreasing) univariate function, \begin{equation} f(r), \end{equation} over $r \in [0,\frac{1}{2}]$ to a series ($r =\frac{1}{100}, \frac{2}{100}, \frac{3}{100} ,\ldots,\frac{1}{2}$) ...
0
votes
1answer
29 views

Proving f cannot be convex

The following question I encountered in a convex optimization course and I can't seem to understand the solution.
0
votes
1answer
18 views

Maximize two variables function subject to quadratic constraint

Two mariners end up on a island, with 1800 pounds of food to share, i.e. $F1 + F2 = 1800$. I'm expected to maximize the social welfare function given by $W=U1^{0.25}*U2^{0.75}$ where $U1=\sqrt{F1}$ ...
1
vote
2answers
44 views

Solving the devil's penny puzzle

I was reading an article about the devil's penny puzzle. We are given $n$ boxes, one of which contains the devil's penny while the others contain an amount of money $a_1,\ldots,a_{n-1}$. These numbers ...
0
votes
0answers
13 views

What star rating is representative of this distribution? [on hold]

100 people vote. They can vote 1, 2, 3, or 4 stars. Distribution: 1 = 33, 2 = 26, 3 = 12, and 4 = 28. What star rating would you say is "representative" of these 100 people: 2.36 (2), the average, ...
1
vote
1answer
17 views

Signed angle difference without conditions

I've got two angles in $0 \leqslant a < 360$ and I need to find the signed difference between them which should be $-180 < \Delta < 180$. Is there a way to calculate the difference with ...
-1
votes
0answers
19 views

Effects of degenerate basic feasible solutions in the simplex algorithm? [on hold]

Let $P$ =$\{x\in \mathbb{R}^n :Ax=b,x\geq 0\}$,where $A$ is a $d×n$ matrix of rank $d$. Suppose that all basic feasible solutions are nondegenerate. Let $x \in P$ have exactly $d$ positive entries. ...
0
votes
1answer
40 views

why are the Bisection and Newton Method for finding roots complementary to each other?

my lecture note states that the bisection and newton method for finding roots are most of the time complementary to each other but I can not figure out why. I have basic understanding of both of the ...
2
votes
2answers
32 views

Am I allowed to do this chain-rule type thing when optimizing wrt to a functional?

So we have a function $f(x) = g(x)h(y(x))$ that is convex in $y$ which we want to optimize by choosing the appropriate $y(x)$. I have seen the following done in engineering books, but it just looks so ...
0
votes
0answers
30 views

minimize this objective function

I have a function to minimize and I don't understand how I should proceed. The function is coming from a publication. Background: In a 2D image, $P_1$ and $P_2$ represents 2 patches of colors (RGB) ...
1
vote
2answers
53 views

Find the smallest positive value taken by $a^3+b^3+c^3-3abc$

Find the smallest positive value taken by $a^3+b^3+c^3-3abc$ for positive integers $a,b,c$. Find all integers $a,b,c$ which give the smallest value. Since it is generally hard to find the minimum ...
0
votes
0answers
19 views

Maximization over minimum function

I want to solve the following optimization problem. Suppose we are given $p_r^i \in [0,1]$ for $r={1,2,...,N}$ and $i={1,2}$ such that $\sum_{r=1}^N p_r^i =1$ for i={1,2}. We want to find $x_r \in ...
0
votes
1answer
32 views

Optimizing the area of a rectangle with one side against a wall using the am-gm inequality

Given 300 meters of fence, how can I find the dimensions of a rectangle that is built against a wall the encloses the maximum area. I found this question in a calculus book and saw a simple solution ...
0
votes
0answers
13 views

Using the Fourier Series in Variational Optimization Problems

Say I have a functional $L(f)$ which takes as input the function $f:\mathbb{R}\to\mathbb{R}$, and I want to find the function that optimizes $L$. Unfortunately, there's no way to define a functional ...
0
votes
1answer
17 views

Find the positions of $A$ and $B$ which minimizes the length $AB$.

The line $AB$ joins the points $A(a, 0 )$, $B(0, b)$ on the $x$ and $y$ axes respectively and passes through the points $(8, 27)$. Find the positions of $A$ and $B$ which minimizes the length $AB$. ...
0
votes
1answer
10 views

Softmax Regression Derivative

This website, http://deeplearning.stanford.edu/wiki/index.php/Softmax_Regression, claims the derivative of a multinomial regression: $$ J(\theta) = -\frac{1}{m}\sum_{i=1}^m \sum_{j=1}^k 1\{y^i =j\} ...
0
votes
0answers
18 views

Singularities of composite function

Given a smooth, compact manifold $M$ (of dimension much less than $n$) and two maps $f:\mathbb{R}^n \rightarrow M$, $g:M\rightarrow \mathbb{R}$, I want to understand the topology of the critical set ...
0
votes
0answers
12 views

Derivation of SVM algorithm (Lagrangian)

I have a question about the derivation of the SVM algorithm (for example, page 3 here ). The question is about the math, so that's why I'm asking this here. Suppose I have the following optimization ...
5
votes
2answers
199 views

Set is Convex regardless of b

Let the function $f$ be convex, $f :\Bbb R^n \rightarrow \Bbb R$ and let $$S = \{x : f(x) \le b\}$$ The proposition states that the set $S$ is convex regardless of $b$. Can someone explain to me how ...
0
votes
1answer
53 views

Maximum of polynomial [on hold]

I was studying statics and came across this problem: Find the value $\beta$ such that $P$ has a maximum value in $R^2 - 1000^2 = P^2 + 2000P\cos(75^{\circ}+\beta)$. When $R$ is constant, the ...
3
votes
1answer
26 views

How do you find $∠XPC$ + $∠XPB$ such that $PB+PC$ is maximum where $P$ is a point on $f(x) = (x-1)(x-3)(x-5)$?

Problem: $f(x) = (x-1)(x-3)(x-5)$ intersects the x axis at $A(1,0)$, $B(3,0)$ and $C(5,0)$. A point $P(t,f(t))$ is selected on the curve such that $PB+PC$ is maximum and $t \in (3,5).$ Let $PX$ be ...
0
votes
0answers
8 views

Optimize polling frequency between producer and consumer to achieve minimum waiting time

Background: I am trying to optimize what we call AJAX request polling frequency in the domain of web design, and I wanted to check if I could use some help from math guys to explore a better ...
0
votes
1answer
25 views

How can we solve this system of linear inequalities?

Let $c_i$ be a given non-negative integer for all $i\in\{1,\ldots,n\}$. I would like to find the non-negative integers $a_i$ and $b_i$ for all $i\in\{1,\ldots,n\}$ such that: \begin{align} ...
0
votes
0answers
23 views

Local maximum of $(2^{xy}{z \choose y})^{z+1}$

I have an optimization problem where I need to calculate the maximum of the following function $$ f(x,y,z) = (2^{xy}{z \choose y})^{z+1} $$ where $$ (z+1)(a+y(\lceil{\log_2{(z+1)}}\rceil+x))\leq C $$ ...
0
votes
0answers
8 views

ADMM Formulation for fractional programs?

I have a fractional program $$ \min \frac{f(x)}{g(x)} $$ where $f(x)$ and $g(x)$ are both quadratic functions (i.e. they are convex). It has been shown that this can be alternatively represented by ...
1
vote
1answer
50 views

minimum possible value of a linear function of n variables

Suppose $x_1,x_2,\ldots,x_n$ are unknowons satisfying the constraint $a_1x_1 + \cdots + a_nx_n ≥ b$, where $a_1, \ldots , a_n, b ≥ 0$. Then the minimum possible value of the expression $c_1x_1 + ...
0
votes
2answers
26 views

SVD with Sparisty Penalties

I am trying to solve a problem like $$\min_{u,v} \Vert X-uv^T \Vert_F^2 + \beta \Vert v \Vert_1 \mbox{ s.t. } \Vert u \Vert_2 \le 1$$ where $X \in \mathbb{R}^{N\times N}$, $u, v \in ...
1
vote
0answers
29 views

Show that any vertex $v$ of $P$ is half-integral.

Let $G$ be an undirected graph and define $$P=\{x \in R^{V}: x(u)+x(v) \leq 1 \:\:\text{for all edges}\:\: e=uv,\:\: x \geq 0\}$$ Show that any vertex $v$ of $P$ is half integral.
0
votes
0answers
14 views

Optimizing functions with a complex domain and a real codomain

In general I want to understand if it makes sense to optimize a function of the following form $f: \mathbb{C} → \mathbb{R}$ for my specific problem $f(z) = | z | ^{2} $ (wich I is not analytic since ...
-1
votes
0answers
12 views

Removing variables from convex linear program

I am solving linear program (possibly non-convex). Then we know that dual is always convex. Then I noticed that depending on objective functional I can sometimes remove particular variables from this ...
0
votes
0answers
19 views

Negative eigenvalue of a hessian matrix entails a local decrease in function value?

I was reading up on non-convex optimization, and I can across this sentence: "Since Hessian(f(w)) has a negative eigenvalue, there is always a point that is near w which has smaller function value" ...